1 of 125

Data Warehouse Implementation and Data Mining

:

MODULE 2

1

5/23/2022

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

2 of 125

Module II

Data Warehouse Implementation and Data Mining

2

  • Efficient Data Cube Computation
    • The “Compute Cube” Operator
  • Indexing OLAP Data: Bitmap Index
  • Indexing OLAP Data: Join Indices
  • Efficient Processing OLAP Queries
  • OLAP Server Architectures: ROLAP versus MOLAP versus HOLAP

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

3 of 125

Efficient Data Cube Computation

  • Data warehouses contain huge volumes of data.
  • OLAP servers demand that decision support queries be answered in the order of seconds.
  • Therefore, it is crucial for data warehouse systems to support highly efficient cube computation techniques, access methods, and query processing techniques.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

4 of 125

Efficient Data Cube Computation

  • At the core of multidimensional data analysis is the efficient computation of aggregations across many sets of dimensions.
  • In SQL terms, these aggregations are referred to as group-by’s.
  • Each group-by can be represented by a cuboid, where the set of group-by’s forms a lattice of cuboids defining a data cube.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

5 of 125

The “Compute Cube” Operator

66

  • The compute cube operator computes aggregates over all subsets of the

dimensions specified in the operation.

  • Example: A data cube is a lattice of cuboids. Suppose that you want to create a data cube for AllElectronics sales that contains the following: city, item, year, and sales in dollars. You want to be able to analyze the data, with queries such as the following:

“Compute the sum of sales, grouping by city and item.” “Compute the sum of sales, grouping by city.” “Compute the sum of sales, grouping by item.”

  • What is the total number of cuboids, or group-by’s, that can be computed for this data cube?

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

6 of 125

The “Compute Cube” Operator

  • Taking the three attributes, city, item, and year, as the dimensions for the data cube, and sales in dollars as the measure, the total number of cuboids, or group by’s, that can be computed for this data cube is 2^3 =8.
  • The possible group-by’s are the following: {(city, item, year), (city, item), (city, year), (item, year), (city), (item), (year), ()}, where () means that the group-by is empty (i.e., the dimensions are not grouped).
  • These group-by’s form a lattice of cuboids for the data cube, as shown in Figure

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

7 of 125

The “Compute Cube” Operator

7

5/23/2022

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

8 of 125

The “Compute Cube” Operator

  • Base cuboid -all three dimensions
    • city, item, and year.
    • It can return the total sales for any combination of the three

dimensions.

    • the least generalized (most specific) of the cuboids.
  • Apex cuboid/0-D cuboid-refers to the case where the group-by is empty.
    • the most generalized (least specific) of the cuboids, and is often denoted as all.
    • It contains the total sum of all sales.
  • An SQL query containing no group-by (e.g., “compute the sum of total sales”) is a zero dimensional operation.

​

  • An SQL query containing one group-by (e.g., “compute the sum of sales, group-by city”) is a one-dimensional operation.

​

  • A cube operator on n dimensions is equivalent to a collection of group-by statements, one for each subset of the n dimensions.
  • Therefore, the cube operator is the n-dimensional generalization of the group-by

operator.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

9 of 125

The “Compute Cube” Operator

  • Similar to the SQL syntax, the data cube in Example could be defined as

define cube sales cube [city, item, year]: sum(sales in dollars)

  • For a cube with n dimensions, there are a total of 2n cuboids, including the base cuboid.
  • A statement such as

compute cube sales cube

  • would explicitly instruct the system to compute the sales aggregate cuboids for all eight subsets of the set {city, item, year}, including the empty subset.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

10 of 125

The “Compute Cube” Operator

  • Online analytical processing may need to access different cuboids for different queries. – Precomputation
  • Precomputation leads to fast response time and avoids some redundant

computation.

  • A major challenge related to this precomputation, however, is that the required storage space may explode if all the cuboids in a data cube are precomputed, especially when the cube has many dimensions.
  • The storage requirements are even more excessive when many of the dimensions have associated concept hierarchies, each with multiple levels. This problem is referred to as the curse of dimensionality.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

11 of 125

  • “How many cuboids are there in an n-dimensional data cube?”

If there were no hierarchies associated with each dimension, then the total

number of cuboids for an n-dimensional data cube, as we have seen, is 2n.

  • However, in practice, many dimensions do have hierarchies.

For example, time is usually explored not at only one conceptual level (e.g.,

year), but rather at multiple conceptual levels such as in the hierarchy “day

< month < quarter < year.” For an n-dimensional data cube, the total number of cuboids that can be generated (including the cuboids generated

by climbing up the hierarchies along each dimension) is

∏

T =

n

i =1

i

(L +1)

  • Li -number of levels associated with dimension i. One is added to Li in Eq. to include the virtual top level.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

12 of 125

  • If the cube has 10 dimensions and each dimension has five levels (including all), the total number of cuboids that can be generated is 510

≈9.8×106.

​

  • The size of each cuboid also depends on the cardinality (i.e., number of distinct values) of each dimension.

​

  • For example, if the AllElectronics branch in each city sold every item, there would be |city|×|item| tuples in the city−item group-by alone.

​

  • As the number of dimensions, number of conceptual hierarchies, or cardinality increases, the storage space required for many of the group- by’s will grossly exceed the (fixed) size of the input relation.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

13 of 125

Partial Materialization: Selected Computation of Cubiods

​

  • common technique used in data warehouse is to materialize( precompute) cuboids of a data cube. To do this, there are three possibilities:
    1. No materialization
    2. Full materialization
    3. Partial materialization
  • The partial materialization of cuboids or subcubes should consider three factors:
  • identify the subset of cuboids or subcubes to materialize;
  • exploit the materialized cuboids or subcubes during query processing; and
  • efficiently update the materialized cuboids or subcubes

during load and refresh.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

14 of 125

Indexing OLAP Data: Bitmap Index

  • To facilitate efficient data accessing, most data warehouse systems support index structures and materialized views (using cuboids).
  • The bitmap indexing method is popular in OLAP products because it allows quick

searching in data cubes.

  • The bitmap index is an alternative representation of the record ID (RID) list.
  • In the bitmap index for a given attribute, there is a distinct bit vector, Bv, for each value v in the attribute’s domain.
  • If a given attribute’s domain consists of n values, then n bits are needed for each entry in the bitmap index (i.e., there are n bit vectors).
  • If the attribute has the value v for a given row in the data table, then the bit representing that value is set to 1 in the corresponding row of the bitmap index. All other bits for that row are set to 0.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

15 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

16 of 125

Indexing OLAP Data: Bitmap Index

  • Bitmap indexing is advantageous compared to hash and tree indices.
  • It is especially useful for low-cardinality domains because comparison, join, and aggregation operations are then reduced to bit arithmetic, which substantially reduces the processing time.
  • Bitmap indexing leads to significant reductions in space and input/output (I/O) since a string of characters can be represented by a single bit.
  • For higher-cardinality domains, the method can be adapted using compression techniques.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

17 of 125

Indexing OLAP Data: Join Indices

79

  • Traditional indexing maps the value in a given column to a list of rows having that value.
  • In contrast, join indexing registers the joinable rows of two relations from a relational database.
  • For example, if two relations R(RID, A) and S(B, SID) join on the attributes A and B, then the join index record contains the pair (RID, SID), where RID and SID are record identifiers from the R and S relations, respectively.
  • Hence, the join index records can identify joinable tuples without performing costly join operations.
  • Join indexing is especially useful for maintaining the relationship between a foreign key 2 and its matching primary keys, from the joinable relation.
  • Join indexing maintains relationships between attribute values of a dimension (e.g., within a dimension table) and the corresponding rows in the fact table.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

18 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

19 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

20 of 125

Efficient Processing OLAP Queries

82

  • Determine which operations should be performed on the available cuboids
    • Transform drill, roll, etc. into corresponding SQL and/or OLAP operations,
    • e.g: dice = selection + projection
  • Determine which materialized cuboid(s) should be selected for OLAP op.
    • This involves identifying all of the materialized cuboids that may potentially be used to answer the query, pruning the set using knowledge of “dominance” relationships among the cuboids, estimating the costs of using the remaining materialized cuboids, and selecting the cuboid with the least cost.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

21 of 125

“Which of these four cuboids should be selected to process the query?”

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

22 of 125

Efficient Processing OLAP Queries

  • Finer-granularity data cannot be generated from coarser-granularity

​

data.

  • Therefore, cuboid 2 cannot be used because country is a more general concept than province or state.
  • Cuboids1,3,and 4 can be used to process the query because

(1)they have the same set or as uper set of the dimensions in the query,

(2) the selection clause in the query can imply the selection in the cuboid, and (3) the abstraction levels for the item and location

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

23 of 125

OLAP Server Architectures

85

  • Relational OLAP (ROLAP)
    • Use relational or extended-relational DBMS to store and manage

warehouse data and OLAP middle ware

    • Intermediate servers between a relational back-end server and client front-end tools.
    • Include optimization of DBMS backend, implementation of

aggregation navigation logic, and additional tools and services

    • Greater scalability
  • Multidimensional OLAP (MOLAP)
    • Support multidimensional data views through array-based

multideimensional storage engine

    • Fast indexing to pre-computed summarized data

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

24 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

25 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

26 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

27 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

28 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

29 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

30 of 125

OLAP Server Architectures

  • Hybrid OLAP (HOLAP) (e.g., Microsoft SQLServer)
    • Flexibility, e.g., low level: relational, high-level: array
    • Combines ROLAP and MOLAP
    • Greater scalability of ROLAP and faster computation of MOLAP.
  • Specialized SQL servers
    • Specialized support for SQL queries over star/snowflake schemas

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

31 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

32 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

33 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

34 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

35 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

36 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

37 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

38 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

39 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

40 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

41 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

42 of 125

Motivating Challenges

  • Scalability

​

  • High Dimensionality

​

  • Heterogeneous and Complex Data

​

  • Data Ownership and Distribution

​

  • Non-traditional Analysis

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

43 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

44 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

45 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

46 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

47 of 125

Data Mining Tasks

  • Prediction Tasks
    • The objective of these tasks is to predict the value of a particular attribute based on the values of other attributes,
    • Use some variables to predict unknown or future values of other variables.
  • Descriptive Tasks
    • Objective is to derive patterns(corelations, trends, clusters) that summarize the underlying relationships in data.
  • Find human-interpretable patterns describe the data.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

48 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

49 of 125

Data Mining Tasks …

Tid

Refund

Marital Status

Taxable Income

Cheat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Yes

No

No Yes No No Yes No No No No Yes No No No

Single

Married

Single Married Divorced Married Divorced Single Married Single Married Divorced Single Married Single

125K

100K

70K

120K

95K

60K

220K

85K

75K

90K

60K

220K

85K

75K

90K

No

No

No No Yes No No Yes No Yes No No Yes No Yes

​

10

Milk

Data

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

50 of 125

Predictive Modeling: Classification

​

  • Once data has been collected for relevant predictors, a statistical model is formulated.
  • As additional data becomes available, the statistical analysis model is validated or revised.
  • One of the most common uses of predictive modeling is in online advertising and marketing.
  • Modelers use web surfers' historical data, running it through algorithms to determine what kinds of products users might be interested in and what they are likely to click on.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

51 of 125

  • There are two forms of data analysis that can be used for extracting models describing important classes or to predict future data trends. These two forms are as follows
    • Classification
    • Regression
  • Classification models - predict categorical class labels; and
  • Regression models - predict continuous valued functions.

​

For example,

we can build a classification model to categorize bank loan applications as either safe or risky, or a prediction model to predict the expenditures in dollars of potential customers on computer equipment given their income and occupation.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

52 of 125

What is Classification?

Following are the examples of cases where the data analysis

task is Classification −

​

  • A bank loan officer wants to analyze the data in order to know which customer (loan applicant) are risky or which are safe.

​

  • A marketing manager at a company needs to analyze a customer with a given profile, who will buy a new computer.

​

In both of the above examples, a model or classifier is

constructed to predict the categorical labels.

These labels are risky or safe for loan application data and

yes or no for marketing data.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

53 of 125

What is Regression?

Following are the examples of cases where the data analysis task is Prediction −

Suppose the marketing manager needs to predict how much a given customer will spend during a sale at his company.

  • In this example we are bothered to predict a numeric value.
  • Therefore the data analysis task is an example of numeric prediction.

​

  • In this case, a model or a regression will be constructed that predicts a continuous-valued-function or ordered value.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

54 of 125

  • In data mining, anomaly detection (also outlier detection) is the identification of rare items, events or observations which raise suspicions by differing significantly from the majority of the data.

​

  • Typically the anomalous items will translate to some kind of problem such as bank fraud, a structural defect, medical problems or errors in a text.

​

  • Anomalies are also referred to as outliers, novelties, noise, deviations and exceptions.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

55 of 125

Association Rule Discovery: Definition

  • Given a set of records each of which contain some number of items from a given collection
    • Produce dependency rules which will predict occurrence of

an item based on occurrences of other items.

TID

Items

1

Bread, Coke, Milk

2

Pepsi, Bread

3

Pepsi, Coke, Chips, Milk

4

Pepsi, Bread, Chips, Milk

5

Coke, Chips, Milk

Rules Discovered:

{Milk} --> {Coke}

{Chips, Milk} --> {Pepsi}

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

56 of 125

Association Analysis: Applications

  • Market-basket analysis
    • Rules are used for sales promotion, shelf management, and inventory management

​

  • Telecommunication alarm diagnosis
    • Rules are used to find combination of alarms that occur together frequently in the same time period

​

  • Medical Informatics
    • Rules are used to find combination of patient symptoms and test results associated with certain diseases

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

57 of 125

Clustering

  • Finding groups of objects such that the objects in a group will be similar (or related) to one another and different from (or unrelated to) the objects in other groups

Inter-cluster distances are maximized

Intra-cluster distances are minimized

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

58 of 125

What is Data?

  • Collection of data objects

and their attributes

  • An attribute is a property or characteristic of an object
    • Examples: eye color of a person, temperature, etc.
    • Attribute is also known as variable, field, characteristic, dimension, or feature
  • A collection of attributes describe an object
    • Object is also known as record, point, case, sample, entity, or instance

Tid

Refund

Marital Status

Taxable Income

Cheat

1

Yes

Single

125K

No

2

No

Married

100K

No

3

No

Single

70K

No

4

Yes

Married

120K

No

5

No

Divorced

95K

Yes

6

No

Married

60K

No

7

Yes

Divorced

220K

No

8

No

Single

85K

Yes

9

No

Married

75K

No

10

No

Single

90K

Yes

​

10

Attributes

Objects

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

59 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

60 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

61 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

62 of 125

Attribute Values

  • Attribute values are numbers or symbols assigned to an attribute for a particular object
  • Distinction between attributes and attribute values
    • Same attribute can be mapped to different attribute values
      • Example: height can be measured in feet or meters

​

    • Different attributes can be mapped to the same set of values
      • Example: Attribute values for ID and age are integers
      • But properties of attribute values can be different

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

63 of 125

Types of Attributes

63

5/23/2022

  • There are different types of attributes
    • Nominal
      • Examples: ID numbers, eye color, zip codes
    • Ordinal
      • Examples: rankings (e.g., taste of potato chips on a scale from 1-10), grades, height {tall, medium, short}
    • Interval
      • Examples: calendar dates, temperatures in Celsius or Fahrenheit.
    • Ratio
      • Examples: temperature in Kelvin, length, time, counts

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

64 of 125

Properties of Attribute Values

  • The type of an attribute depends on which of the following properties/operations it possesses:

= ≠

< >

  • Distinctness:
  • Order:
  • Differences are meaningful :
  • Ratios are

meaningful

+ -

* /

  • Nominal attribute: distinctness
  • Ordinal attribute: distinctness & order
  • Interval attribute: distinctness, order & meaningful

differences

  • Ratio attribute: all 4 properties/operations

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

65 of 125

This categorization of attributes is due to S. S. Stevens

Categorical Qualitative

Numeric Quantitative

​

Attribute

Description

Examples

Operations

​

Type

​

​

​

Nominal

Nominal attribute values only

distinguish. (=, ≠)

zip codes, employee

ID numbers, eye color, sex: {male, female}

mode, entropy, contingency

correlation, χ2 test

Ordinal

Ordinal attribute

values also order objects.

(<, >)

hardness of minerals,

{good, better, best}, grades, street numbers

median,

percentiles, rank correlation, run tests, sign tests

Interval

For interval

attributes, differences between values are meaningful. (+, - )

calendar dates,

temperature in Celsius or Fahrenheit

mean, standard

deviation, Pearson's correlation, t and F tests

Ratio

For ratio variables,

both differences and ratios are meaningful. (*, /)

temperature in Kelvin,

monetary quantities, counts, age, mass, length, current

geometric mean,

harmonic mean, percent variation

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

66 of 125

66

5/23/2022

  • Discrete Attribute
    • Has only a finite or countably infinite set of values
    • Examples: zip codes, counts, or the set of words in a collection of documents
    • Often represented as integer variables.
    • Note: binary attributes are a special case of discrete attributes
  • Continuous Attribute
    • Has real numbers as attribute values
    • Examples: temperature, height, or weight.
    • Practically, real values can only be measured and represented using a finite number of digits.
    • Continuous attributes are typically represented as floating- point variables.

​

What is an Asymmetric Attribute?

→ Only non-zero values are important in this.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

67 of 125

Important Characteristics of Data sets

​

  • Dimensionality (number of attributes)
    • High dimensional data brings a number of challenges

​

  • Sparsity
    • Only presence counts

​

  • Resolution
    • Patterns depend on the scale

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

68 of 125

What is Dimensionality?

→ The dimensionality of a data set is the number of attributes that the objects in the data set have.

What is Sparsity?

→ For some data sets, such as those with asymmetric features, most attributes of an object have values of 0; in many cases fewer than 1% of the entries are non-zero. Such a data is called sparse data or it can be said that the data set has Sparsity.

What is Resolution?

→ The patterns in the data depend on the level of resolution. If the resolution is too fine, a pattern may not be visible or may be buried in noise; if the resolution is too coarse, the pattern may disappear.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

69 of 125

Types of data sets

  • Record
    • Data Matrix
    • Document Data
    • Transaction Data
  • Graph
    • World Wide Web
    • Molecular Structures
  • Ordered
    • Sequential Data
    • Genetic Sequence Data
    • Temporal Data
    • Spatial Data

​

​

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

70 of 125

Record Data

  • Data that consists of a collection of records, each of which consists of a fixed set of attributes

Tid

Refund

Marital Status

Taxable Income

Cheat

1

Yes

Single

125K

No

2

No

Married

100K

No

3

No

Single

70K

No

4

Yes

Married

120K

No

5

No

Divorced

95K

Yes

6

No

Married

60K

No

7

Yes

Divorced

220K

No

8

No

Single

85K

Yes

9

No

Married

75K

No

10

No

Single

90K

Yes

​

10

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

71 of 125

Data Matrix

  • If data objects have the same fixed set of numeric attributes, then the data objects can be thought of as points in a multi-dimensional space, where each dimension represents a distinct attribute

​

  • Such data set can be represented by an m by n matrix, where there are m rows, one for each object, and n columns, one for each attribute

Projection of x Load

Projection of y load

Distance

Load

Thickness

10.23

5.27

15.22

2.7

1.2

12.65

6.25

16.22

2.2

1.1

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

72 of 125

Document Data

  • Each document becomes a ‘term’ vector
    • Each term is a component (attribute) of the vector
    • The value of each component is the number of times the corresponding term occurs in the document.

​

team

coach

play

ball

score

game

win

lost

timeout

season

Document 1

3

0

5

0

2

6

0

2

0

2

Document 2

0

7

0

2

1

0

0

3

0

0

Document 3

0

1

0

0

1

2

2

0

3

0

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

73 of 125

Transaction Data

  • A special type of record data, where
    • Each record (transaction) involves a set of items.
    • For example, consider a grocery store. The set of products purchased by a customer during one shopping trip constitute a transaction, while the individual products that were purchased are the items.

TID

Items

1

Bread, Coke, Milk

2

Pepsi, Bread

3

Pepsi, Coke, Chips, Milk

4

Pepsi, Bread, Chips, Milk

5

Coke, Chips, Milk

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

74 of 125

This can be further divided into types:

Graph-based data

1. Data with Relationships among Objects: The data objects are mapped to nodes of the graph, while the relationships among objects are captured by the links between objects and link properties, such as direction and weight

2. Data with Objects That Are Graphs: If objects have structure, that is, the objects contain sub objects that have relationships, then such objects are frequently represented as graphs

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

75 of 125

Graph Data

5

  • Examples: Generic graph, a molecule, and webpages

​

2

1

2

5

Benzene Molecule: C6H6

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

76 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

77 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

78 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

79 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

80 of 125

Data Quality …

  • What kinds of data quality problems?
  • How can we detect problems with the data?
  • What can we do about these problems?

​

  • Examples of data quality problems:
    • Measurement and data correction errors
    • Noise and outliers
    • Inconsistent values
    • Missing values
    • Duplicate data
    • Wrong data

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

81 of 125

What is Measurement Error?

→ It refers to any problem resulting from the measurement process. In other words, the recorded data values differ from true values to some extent. The difference between measured and true value is called the error.

​

​

​

​

What is Data Collection Error?

→ It refers to errors such as omitting data objects or attributes values, or including an unnecessary data object.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

82 of 125

Noise

  • For objects, noise is an extraneous object
  • For attributes, noise refers to modification of original values
    • Examples: distortion of a person’s voice when talking

on a poor phone and “snow” on television screen

Two Sine Waves

Two Sine Waves + Noise

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

83 of 125

Outliers

83

5/23/2022

  • Outliers are data objects with characteristics that are considerably different than most of the other data objects in the data set
    • Case 1: Outliers are noise that interferes with data analysis
    • Case 2: Outliers are the goal of our analysis
      • Credit card fraud
      • Intrusion detection
  • Causes?

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

84 of 125

Missing Values

  • Reasons for missing values
    • Information is not collected

(e.g., people decline to give their age and weight)

    • Attributes may not be applicable to all cases (e.g., annual income is not applicable to children)

​

  • Handling missing values
    • Eliminate data objects or variables
    • Estimate missing values
      • Example: time series of temperature
      • Example: census results
    • Ignore the missing value during analysis

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

85 of 125

Duplicate Data

  • Data set may include data objects that are duplicates, or almost duplicates of one another
    • Major issue when merging data from heterogeneous sources

​

  • Examples:
    • Same person with multiple email addresses

​

  • Data cleaning
    • Process of dealing with duplicate data issues

​

  • When should duplicate data not be removed?

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

86 of 125

The quality of measurement process and the resulting data are measured by Precision and Bias.

What is Precision?

→ The closeness of repeated measurements (of the same quantity) to one another. It is often measured by the standard deviation of a set of values.

​

What is Bias?

→ A systematic variation of measurements from the quantity being measured. It is measured by taking the difference between the mean of the set of values and the known values of the quantity being measured. It can only be determined for those objects whose measured quantity is already known.

​

It is common to use the more general term, accuracy, to refer to the degree of measurement error in data.

​

What is Accuracy?

→ The closeness of measurements to the true value of the quantity being measured.

Accuracy depends on precision and bias, but since it is a general concept, there is no specific formula for accuracy in terms of these two quantities.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

87 of 125

87

5/23/2022

  • Aggregation
  • Sampling
  • Dimensionality Reduction
  • Feature subset selection
  • Feature creation
  • Discretization and Binarization
  • Attribute Transformation

Data Preprocessing

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

88 of 125

Aggregation

  • Combining two or more attributes (or objects) into a single attribute (or object)
  • Purpose
    • Data reduction
      • Reduce the number of attributes or objects
    • Change of scale
      • Cities aggregated into regions, states, countries, etc.
      • Days aggregated into weeks, months, or years
    • More “stable” data
      • Aggregated data tends to have less variability

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

89 of 125

Sampling

  • Sampling is the main technique employed for data reduction.
  • Statisticians often sample because obtaining the entire set of data of interest is too expensive or time consuming.

​

  • Sampling is typically used in data mining because processing the entire set of data of interest is too expensive or time consuming.

It is often used for both the preliminary investigation of the data and the final data analysis

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

90 of 125

Sampling …

  • The key principle for effective sampling is the following:

​

    • Using a sample will work almost as well as using the entire data set, if the sample is representative

​

    • A sample is representative if it has approximately the same properties (of interest) as the original set of data

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

91 of 125

Sample Size

2000 Points

500

8000 points Points

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

92 of 125

Types of Sampling

  • Simple Random Sampling
    • There is an equal probability of selecting any particular item
    • Sampling without replacement
      • As each item is selected, it is removed from the population
    • Sampling with replacement
      • Objects are not removed from the population as they are

selected for the sample.

      • In sampling with replacement, the same object can be picked up more than once
  • Stratified sampling
    • Split the data into several partitions; then draw random samples from each partition

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

93 of 125

Curse of Dimensionality

  • When dimensionality increases, data becomes increasingly sparse in the space that it occupies

​

  • Definitions of density and distance between points, which are critical for clustering and outlier detection, become less

meaningful

  • Randomly generate 500 points
  • Compute difference between max and min distance between any pair of points

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

94 of 125

Dimensionality Reduction

  • Purpose:
    • Avoid curse of dimensionality
    • Reduce amount of time and memory required by data mining algorithms
    • Allow data to be more easily visualized
    • May help to eliminate irrelevant features or reduce noise
  • Techniques
    • Principal Components Analysis (PCA)
    • Singular Value Decomposition
    • Others: supervised and non-linear techniques

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

95 of 125

Dimensionality Reduction: PCA

  • Goal is to find a projection that captures the largest amount of variation in data

x2

​

​

e

x1

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

96 of 125

Feature Subset Selection

  • Another way to reduce dimensionality of data
  • Redundant features
    • Duplicate much or all of the information contained in one or more other attributes
    • Example: purchase price of a product and the amount of sales tax paid
  • Irrelevant features
    • Contain no information that is useful for the data mining task at hand
    • Example: students' ID is often irrelevant to the task of predicting students' GPA
  • Many techniques developed, especially for

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

97 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

98 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

99 of 125

Feature Creation

  • Create new attributes that can capture the important information in a data set much more efficiently than the original attributes

​

  • Three general methodologies:
    • Feature extraction
      • Example: extracting edges from images
    • Feature construction
      • Example: dividing mass by volume to get density
    • Mapping data to new space
      • Example: Fourier and wavelet analysis

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

100 of 125

Mapping Data to a New Space

Two Sine Waves + Noise

  • Fourier and wavelet transform

Frequency

Frequency

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

101 of 125

Discretization

  • Discretization is the process of converting a continuous attribute into an ordinal attribute
    • A potentially infinite number of values are mapped into a small number of categories
    • Discretization is commonly used in classification
    • Many classification algorithms work best if both the independent and dependent variables have only a few values

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

102 of 125

Binarization

  • Binarization maps a continuous or categorical attribute into one or more binary variables

​

  • Typically used for association analysis

​

  • Often convert a continuous attribute to a categorical attribute and then convert a categorical attribute to a set of binary attributes
    • Association analysis needs asymmetric binary attributes
    • Examples: eye color and height measured as

{low, medium, high}

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

103 of 125

Attribute Transformation

  • An attribute transform is a function that maps the entire set of values of a given attribute to a new set of replacement values such that each old value can be identified with one of the new values
    • Simple functions: xk, log(x), ex, |x|
    • Normalization
      • Refers to various techniques to adjust to differences among attributes in terms of frequency of occurrence, mean, variance, range
      • Take out unwanted, common signal.
    • In statistics, standardization refers to subtracting off the means and dividing by the standard deviation

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

104 of 125

Similarity and Dissimilarity Measures

  • Similarity measure
    • Numerical measure of how alike two data objects are.
    • Is higher when objects are more alike.
    • Often falls in the range [0,1]
  • Dissimilarity measure
    • Numerical measure of how different two data objects are
    • Lower when objects are more alike
    • Minimum dissimilarity is often 0
    • Upper limit varies
  • Proximity refers to a similarity or dissimilarity

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

105 of 125

Proximity Measure

  • The similarity between object can range from “1”(not similar) to “10”(completely similar)

​

  • We can make them fall into the range [0,1] by formula, Sl=(S-1)/9

​

  • Where S – original similarity value and Sl – new similarity

value

​

  • The more general case Sl is calculated as

Sl=(S-min_S)/(max_S-min_S)

  • Where, min_s and max_s are the minimum and maximumm similarirty value respectively.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

106 of 125

Proximity Measure

  • Likewise, dissimilarity measure with a finite range can be mapped to the interval[0,1] using the formula

​

dl= (d-min_d)/(max_d-min_d)

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

107 of 125

Similarity/Dissimilarity for Simple Attributes

The following table shows the similarity and dissimilarity between two objects, x and y, with respect to a single, simple attribute.

The proximity of object, with number of attributes is defined by combining the proximities of individual attributes.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

108 of 125

Euclidean Distance

  • Distances are dissimilarities with certain properties.

​

  • Euclidean Distance d, between two points x and y is given

by

where n is the number of dimensions (attributes) and xk and yk are, respectively, the kth attributes (components) or data objects x and y.

​

  • Standardization is necessary, if scales differ.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

109 of 125

Euclidean Distance

2

3

0 1

p1

1

p2

0 2 3 4 5

p3

p4

point

x

y

p1

0

2

p2

2

0

p3

3

1

p4

5

1

Distance Matrix

​

p1

p2

p3

p4

p1

0

2.828

3.162

5.099

p2

2.828

0

1.414

3.162

p3

3.162

1.414

0

2

p4

5.099

3.162

2

0

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

110 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

111 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

112 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

113 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

114 of 125

Common Properties of a Distance

  • Distances, such as the Euclidean distance, have some well known properties.
    1. d(x, y) ≥ 0 for all x and y and d(x, y) = 0 only if

x = y. (Positive definiteness)

    • d(x, y) = d(y, x) for all x and y. (Symmetry)
    • d(x, z) ≤ d(x, y) + d(y, z) for all points x, y, and z. (Triangle Inequality)

where d(x, y) is the distance (dissimilarity) between points (data objects), x and y.

​

  • A distance that satisfies these properties is a metric

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

115 of 125

Similarity between Data Obects

  • Similarities, also have some well known properties.
    1. s(x, y) = 1 (or maximum similarity) only if x

= y.

​

    • s(x, y) = s(y, x) for all x and y. (Symmetry)

​

where s(x, y) is the similarity between points (data objects), x and y.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

116 of 125

Similarity Measures for Binary Data

  • Similarity measures between objects that contain only binary attributes are called “ Similarity Coefficients”

​

  • Simple Matching Coefficient(SMC) is the commonly used Similarity Coefficient .

​

  • Jaccard Coefficients measures only the presence of an item is relevant or not.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

117 of 125

Similarity Between Binary Vectors

  • Common situation is that objects, p and q, have only binary attributes
  • Compute similarities using the following quantities f01 = the number of attributes where p was 0 and q was 1 f10 = the number of attributes where p was 1 and q was 0 f00 = the number of attributes where p was 0 and q was 0 f11 = the number of attributes where p was 1 and q was 1
  • Simple Matching

SMC = number of matches / number of attributes

= (f11 + f00) / (f01 + f10 + f11 + f00)

  • Jaccard Coefficients

J = number of 11 matches / number of non-zero attributes

= (f11) / (f01 + f10 + f11)

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

118 of 125

SMC versus Jaccard: Example

p = 1 0 0 0 0 0 0 0 0 0

q = 0 0 0 0 0 0 1 0 0 1

f01 = 2

f10 = 1

f00 = 7

f11 = 0

(the number of attributes where p was 0 and q was 1) (the number of attributes where p was 1 and q was 0) (the number of attributes where p was 0 and q was 0) (the number of attributes where p was 1 and q was 1)

SMC = (f11 + f00) / (f01 + f10 + f11 + f00)

= (0+7) / (2+1+0+7) = 0.7

​

J = (f11) / (f01 + f10 + f11) = 0 / (2 + 1 + 0) = 0

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

/skit.org.in

119 of 125

In cosine similarity, data objects in a dataset are treated as a vector. The formula to find the cosine similarity between two vectors is –

Cos(x, y) = x . y / ||x|| * ||y||

​

where,

  • x . y = product (dot) of the vectors ‘x’ and ‘y’.
  • ||x|| and ||y|| = length of the two vectors ‘x’ and ‘y’.
  • ||x|| * ||y|| = cross product of the two vectors ‘x’ and ‘y’.

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

120 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

121 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

122 of 125

Example :

�Consider an example to find the similarity between two vectors – ‘x’ and ‘y’, using Cosine Similarity.

​

The ‘x’ vector has values, x = { 3, 2, 0, 5 }�The ‘y’ vector has values, y = { 1, 0, 0, 0 }

​

The formula for calculating the cosine similarity is : Cos(x, y) = x . y / ||x|| * ||y||

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

123 of 125

x . y = 3*1 + 2*0 + 0*0 + 5*0 = 3

​

||x|| = √ (3)^2 + (2)^2 + (0)^2 + (5)^2 = 6.16

​

||y|| = √ (1)^2 + (0)^2 + (0)^2 + (0)^2 = 1

​

∴ Cos(x, y) = 3 / (6.16 * 1) = 0.49

Solution:

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

124 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in

125 of 125

Sri Krishna Institute of Technology

(Approved by AICTE, Accredited by NAAC, Affiliated to VTU, Karnataka)

/skit.org.in