Data Science: Data

Lecture Notes for Chapter 2

DATA

by
Dr. Fiaz Gul Khan
CIIT Abbottabad
Outline

 What is data
 Types of Attributes
 Types of Data
 The Quality of the Data
 Data Preprocessing
 Measurement of Similarity and Dissimilarity
What is Data/Data Set?

 Data: Collection of data objects Attributes

and their attributes

 An attribute is a property or Tid Refund Marital Taxable

Status Income Cheat
characteristic of an object
1 Yes Single 125K No
– Examples: eye color of a
2 No Married 100K No
person, temperature, etc.
3 No Single 70K No
– Attribute is also known as
4 Yes Married 120K No
variable, field, characteristic,
5 No Divorced 95K Yes
feature or dimention Objects
6 No Married 60K No
 A collection of attributes
7 Yes Divorced 220K No
describe an object
8 No Single 85K Yes
– Object is also known as
9 No Married 75K No
record, point, case, sample,
10 No Single 90K Yes
entity, or instance 10

Data Set
Types of Attributes

Categorical (Qualitative)
Lack most of the properties of numbers e.g. employee ID represented
by integer they should be treated more like symbols.
Numeric (Quantitative)
Have most of the properties of numbers
 Types of Attributes (=type of
measurement scale)
 There are different types of attributes
Categorical (Qualitative)
– 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 in {tall, medium, short}

Numeric (Quantitative)
– Interval
 Examples: calendar dates, temperatures in Celsius or Fahrenheit.
– Ratio
 Examples: temperature in Kelvin, length, time, counts
– IMPORTANCE: Type of data determines the which tools and techniques can be
used to analyze the data
Attribute Values
(Measurement/properties)

 Attribute values are numbers or symbols

assigned to an attribute

 Distinction between attributes and attribute values

– Different attributes can be mapped to the same set of

values (but their properties are different)
 Example: Attribute values for ID (nominal) and age (interval)
are integers
 But properties of attribute values can be different

– ID has no limit but age has a maximum and minimum value

Measurement of Length (attrb.
property)
 The way you measure an attribute is somewhat may not match the
attributes properties. (not matching the additive property of length
attribute on left side)

– Thus attribute can be measured in a way that does not capture all the
properties of the attribute
Properties of Attribute Values

 The type of an attribute depends on, which of the following properties

of numbers it possesses:
– Distinctness: = 
– Order: < >
– Addition: + -
– Multiplication: */

– Nominal attribute: distinctness

– Ordinal attribute: distinctness & order
– Interval attribute: distinctness, order & addition
– Ratio attribute: all 4 properties
– Commutative in nature (each attribute type possesses all the
properties and operations of the attribute type above it)
Attribute Description Examples Operations
Type

Nominal The values of a nominal attribute zip codes, employee mode, entropy,
are just different names, i.e., ID numbers, eye color, contingency
nominal attributes provide only sex: {male, female} correlation, 2 test
enough information to distinguish
one object from another. (=, )

Ordinal The values of an ordinal attribute hardness of minerals, median, percentiles,

provide enough information to order {good, better, best}, rank correlation,
objects. (<, >) grades, street numbers run tests, sign tests

Interval For interval attributes, the calendar dates, mean, standard

differences between values are temperature in Celsius deviation, Pearson's
meaningful, i.e., a unit of or Fahrenheit correlation, t and F
measurement exists. tests
(+, - )

Ratio For ratio variables, both differences temperature in Kelvin, geometric mean,
and ratios are meaningful. (*, /) monetary quantities, harmonic mean,
counts, age, mass, percent variation
length, electrical
current
Operations
 Mode: The number that is repeated more often than any other number
 Median: The middle value
 Mean: Average
 Ratio: how many times the first number contains the second
 Range: largest value – smallest value
 Entropy: is a precise description of the randomness in the system
 Deviation: deviation is a measure of difference between the observed value of a
variable and some other value, often that variable's mean
 Variance: is the mean of the square of deviation. Or squared deviation from
mean
 Standard deviation: square root of variance
 Percentile: A percentile (or a centile) is a measure used in statistics indicating
the value below which a given percentage of observations in a group of
observations fall. For example, the 20th percentile is the value (or score) below
which 20% of the observations may be found
 Correlation: measure linear dependency between two variable X and Y
synonym= interdependence e.g. demand supply curve
Discrete and Continuous Attributes (type of attributes
by number of values they can take)

1. 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
e.g true/false, yes/no, male/female, or 0/1 often represented as
boolean or integer variable that take values only 0 or 1.

2. 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 with limited precision
– Continuous attributes are typically represented as floating-point
variables.
Asymmetric Attributes (types of attributes by
number of values it take)

3. Binary attributes where only non-zero values are

important are called asymmetric binary attributes
 E.g. student took a course at a university

attribute has a value 1 : if he takes a course

attribute has a value 0 : if he does not takes a course
 Normally students take only a small fraction of all
available courses, so most of the values in such a data
set would be zero
 So it is more meaningful and more efficient to focus on
non zero values.
 E.g. sparse matrices
Types of data sets
There are many types of data sets, some of the most common types are
given below in three major groups.
 Record (collection of records=data objects each of which consist of fixed set of
data fields = attributes )
– Data Matrix
– Document Data / Document-term matrix
– Transaction Data
 Graph (convenient and powerful representation for data)
– Data with relation among objects e.g. World Wide Web
– Data with objects that are graphs e.g. Molecular Structures
 Ordered ( For some type of data, the attributes have relationships that involves
order in time or space)
– Spatial Data
– Temporal Data
– Sequential Data
– Genetic Sequence Data
1. Record Data

 Data that consists of a collection of records, each

of which consists of a fixed set of attributes
Tid Refund Marital Taxable
Status 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

 Different types of record data is discussed next

1.1 Data Matrix (record data)

 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
 Standard matrix operation can be applied to transform and
manipulate the data

Projection Projection Distance Load Thickness

of x Load of y load

10.23 5.27 15.22 2.7 1.2

12.65 6.25 16.22 2.2 1.1
1.2 Document Data (sparse data matrix)

 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.

timeout

season
coach

game
score
team

ball

lost
pla

wi
n
y

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
1.3 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 Beer, Bread
3 Beer, Coke, Diaper, Milk
4 Beer, Bread, Diaper, Milk
5 Coke, Diaper, Milk
2. Graph Data

2.1 Data with relationships among objects:

– The data objects are mapped to nodes of the
graph
– While the relationship among objects are
captured by the link between objects and link
properties such as direction, weight
– Example: Web page which contain both text
and links
2.1 Data with relationships among
objects
2.2 Data with objects that are
graph

 If objects have structure, that is, the objects

contain sub objects that have relationships, then
such objects are represented as graphs.
 Example chemical compounds: such as
Benzene Molecule: C6H6
 Nodes= Atoms
 Link = Chemical Bond
 Presence of sub structure or
graph contains the information
of chemical properties e.g. melting
point or heat of formation etc.
3. Ordered Data

For some types of data, the attributes have relationships that

involve order in
time or space. Different types of ordered data are
1. Sequential Data: also referred as temporal data, can be
thought of as an extension of record data, where each record
has time associated with it.
e.g. temporal data helps to find pattern like “candy sales
before Halloween”
e.g. time with each attribute of the transaction helps to find
pattern such as “ people who buy DVD players tend to buy
DVDs in the period immediately following the purchase”
Ordered Data

 Example of sequential transaction data.

Ordered Data

2. Sequence Data: consists of a data that is a

sequence of individual entities, such as sequence of
words or letters. It is quite similar to sequential data,
except there are no time stamps infect there are
positions in an ordered sequence

Example: Genetic information of plants and animals can be

represented in the form of nucleotides that are know as
genes.

Problem: Predicting similarities in the structure and function

of genes from similarities in nucleotide sequences. A, T,
G, C
Ordered Data

Genomic sequence data

GGTTCCGCCTTCAGCCCCGCGCC
CGCAGGGCCCGCCCCGCGCCGTC
GAGAAGGGCCCGCCTGGCGGGCG
GGGGGAGGCGGGGCCGCCCGAGC
CCAACCGAGTCCGACCAGGTGCC
CCCTCTGCTCGGCCTAGACCTGA
GCTCATTAGGCGGCAGCGGACAG
GCCAAGTAGAACACGCGAAGCGC
TGGGCTGCCTGCTGCGACCAGGG
Ordered Data
3. Time Series Data: Is a special type of sequential
data in which each record is a time series, i.e. a series
of measurements taken over time.
e.g. daily prices of various stocks
 Temporal autocorrelation: if two measures are close
in time, then values of measurements are often very
similar
Ordered Data

4. Spatial Data: Some objects have spatial attributes,

such as position or areas.
Example: Weather data (precipitation, temperature,
pressure) that is collected for a variety of geographical
locations
 Spatial Auto-correlation: objects that are physically
close to each other usually have similar values for
temperature and rainfall.

Average Monthly
Temperature of
land and ocean
Data Quality

 Data mining applications are often applied to data

that was collected for other purpose, or for future,
but unspecified applications.

Data mining focuses on

1. (Data cleaning)The detection and correction of
data quality problems

2. The use of algorithms that can tolerate poor data

quality
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:

– Noise and Artifacts
– Outliers
– missing values
– duplicate data
1. Noise and artifacts

 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
 It may involves the distortion of a value or addition
of false objects
 Noise is often used in connection with data that has
spatial or temporal component
 In such cases techniques from signal and image
processing can be used to reduce noise
 Artifacts: The deterministic phenomenon present
in the data is referred as artifacts such as a streak
in the same place on a set of photographs
Noise and artifacts (cont…)
2. Outliers

 Outliers are data objects with characteristics that

are considerably different than most of the other
data objects in the data set.
 It is important to distinguish between the notion of
noise and outliers.
– Outliers can be legitimate data objects or values
– Thus unlike noise, outliers
may sometimes be
of interest
3. Missing Values (collection
issues)

 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 (simple, if only few data objects have missing values,
if many objects have missing value then reliable analysis is difficult)
– Estimate Missing Values (for continuous attribute average value of nearest
neighbor can be used and for categorical attribute most commonly attribute value can be
used )
– Ignore the Missing Value During Analysis (e.g. in clustering the
similarities between two objects can be measured by using only the attributes that do not
have missing values “problem missing attribute having large value or too many missing
attributes”)
– Replace with all possible values (weighted by their
probabilities) brute force approach
4. 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: such as
accidentally combining data objects that are similar,
but not duplicates
Data Preprocessing

 (GOAL) In this section, we will discuss which

preprocessing steps should be applied to make
the data more suitable for data mining with
respect to time, cost and quality.
Data Preprocessing

 Aggregation
 Sampling
 Dimensionality Reduction
 Feature subset selection ( feature=attribute=variable)
 Feature creation
 Discretization and Binarization
 Attribute/variable Transformation

These items fall into two categories

1. Selecting data objects and attributes for analysis
2. Creating/changing the attributes
Aggregation

 Some times “less is more” combining two or more

attributes (or objects) into a single attribute (or
object)
 ISSUES: e.g table 2.4 in book
– How the value of each attributes are combined across
all the records
– Quantitative attributes, such as price, are
aggregated by taking sum or an average
– Qualitative attributes, such as item name, can either
be omitted or summarized as set of all items
Aggregation

 Purpose/motivation
– Data reduction
 Reduce the number of attributes or objects
 Hence reducing the cost (memory, processing, time)
– Change of scale or scope
 providing high level view of the data instead of low level view
Citiesaggregated into regions, states, countries, days in to
months, months in to years etc.
– More “stable” data
Aggregated data tends to have less variability (stable behavior
 Disadvantage: the potential loss of interesting details
e.g. in the store example aggregating over months loses
information about which day of the week has highest sales
Aggregation

Variation of Precipitation in Australia

Standard Deviation of Average Monthly Precipitation Standard Deviation of Average Yearly Precipitation

This reflects the statistical fact that aggregate quantities,

such as averages or totals, has less variability than individual
objects being aggregated
Sampling
 Sampling is the main technique employed for data selection.
– It is often used for both the preliminary investigation of the data
and the final data analysis in statistics.

 Statisticians sample because obtaining the entire set of data

of interest is too expensive or time consuming.

 Sampling is used in data mining because processing the

entire set of data of interest is too expensive or time
consuming.
Sampling …

 The key principle for effective sampling is the

following:
– using a sample will work almost as well as using the
entire data sets

– A sample is representative if it has approximately the

same property (of interest) as the original set of data

e.g. if mean (average) is the property of interest, then a sample is

representative if it has a mean that is close to that of the original
data
This involves choosing the appropriate sample size and sampling
techniques as discussed next.
Types (approaches) of Sampling

 Simple Random Sampling

– There is an equal probability of selecting any particular item
There are two variation of random sampling and other sampling
techniques
1. Sampling without replacement
– As each item is selected, it is removed from the population

2. 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
Types of Sampling

Limitations of Random sampling

When the population consist of different types of objects
with widely different number of objects, simple random
sampling can fail to represent those types of objects that
are rare or less frequent

 Stratified sampling
– Split the data into several partitions; then draw random samples
from each partition with two approaches

1. Equal numbers of objects are drawn from each group even

though the groups are of different sizes. E.g. senate
2. The number of objects drawn from each group is proportional to
the size of that group e.g. parliament
Sample Size
 Sampling and loss of information: once a sampling technique
has been selected, it is still necessary to choose the appropriate sample size
 Larger sample size: increases the prob. that a sample will be representative,
but will eliminate the much of the advantages of sampling
 Smaller sample size: patterns may be missed or erroneous patterns can be
detected

8000 points 2000 Points 500 Points

Sample Size

 Progressive Sampling
 The proper size can be difficult to determine, so
adaptive or progressive schemes are some time
used
 It starts with a small sample and then increases
the sample size until a sample of sufficient size
has been obtained by observing the accuracy of
the predictive model
2. Curse of Dimensionality
(preprocessing)

 When dimensionality increases,

data becomes increasingly
sparse in the space that it
occupies e.g 1. document data
where dim=words in the
vocabulary 2. daily closing prices
of various stocks over a period of
30 years (30*365) attributes of
each item
 Definitions of density and distance
between points, which is critical
for clustering and outlier
detection, become less
meaningful or getting harder
• Randomly generate 500 points
 For classification impossible to
• Compute difference between max and min
reliably assign a class to all distance between any pair of points
possible objects (not enough data
objects)
Dimensionality Reduction

 Purpose:
– Avoid curse of dimensionality(phenomenon that many types of analysis
becomes harder like classification , clustering)

– 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
– Time and memory requirements are reduced

 Techniques
– Principle Component Analysis
– Singular Value Decomposition
– Others: supervised and non-linear techniques
Feature Subset Selection

 Another way to reduce dimensionality of data

(ways are)
 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
Feature Subset Selection

 Techniques: (of feature subset selection)

– Brute-force approach:
Try all possible feature subsets as input to data

mining algorithm
Since the number of subsets involving “n” attributes is

2n such an approach is impractical

– Embedded approaches:
 Feature selection occurs naturally as part of the data

mining algorithm, algorithm itself decides which

attributes to use and which to ignore e.g gini index
Feature Subset Selection

– Filter approaches:
 Features are selected before data mining
algorithm is run e.g. selecting set of attributes whose
pair wise correlation is as low as possible
– Wrapper approaches:
 Use the target data mining algorithm as a black

box to find best subset of attributes. It works similar

to brut force algorithm but with out enumerating all
possible subsets (apply subsets and see results)
Feature Subset Selection

 Validation: one way is to run algorithm with full sets of attributes and compare
the results
 Result of data mining algo with current subset compare to other subsets
evaluated
Feature Creation

 Create new attributes that can capture the

important information in a data set much more
efficiently than the original attributes
 Number of new features can be smaller than the
original number to take all benefits of
dimensionality reduction

 Three general methodologies:

– Feature Extraction
– Mapping Data to New Space
– Feature Construction
Feature Creation methodologies

 Feature Extraction
 Creation of features from original raw data
 E.g. consider a set of photographs, where we have to classify them
according to whether or not it contains human face
 We need to process the raw data (set of pixels) to provide high level
features, such as the presence or absence of certain types of edges
 Or the areas that are highly correlated with the presence of human
faces. Then we can apply different classification algorithms on such
data
 Feature extraction is highly domain specific i.e. feature extraction
approaches developed in one domain have limited applicability to
other fields.
 So we need new feature extraction techniques for new areas
Mapping Data to a New Space

 Fourier transform: A totally different view of the data can reveal

important and interesting features

Two Sine Waves Two Sine Waves + Noise Frequency

 In spite of the noise, there are two peaks that correspond to the periods of
two original non noisy time series
Feature construction (feature creation
continue)

 Sometimes the features in the original data sets

have the necessary information but it is not in a
form suitable for data mining
Example: checking the made of (wood, clay,
bronze, gold) historical artifact.
o Two of the features are volume and mass
o Where density=mass/volume created from mass
and volume will yield an accurate classification
Discretization and Binarization

 Discretization: It is often necessary to transform

a continuous attributes into a categorical
attributes (required for classification)

 Binarization: Transforming the both continuous

and discrete attributes into one or more binary
attributes (required for association analysis)
Techniques to Binarization

 If there are m categorical values, then uniquely assign

each original value to an integer in the interval [0, m-1]
 If the attribute is ordinal the maintain the order
 Next, convert each of the “m” integers to a binary number
 n= [log2(m)] binary digits are required
Categorical Integer X1 X2 x3
Value Value (Binary
(Discrete) attributes)
Awful 0 0 0 0
poor 1 0 0 1
OK 2 0 1 0
Good 3 0 1 1
great 4 1 0 0
Discretization of Continuous
Attributes

 Typically applied to attributes that are used in

classification or association analysis
 Transformation of continuous attributes to a
categorical attributes involves two subtasks:

 Step # 01: Continuous value is divided in to “n”

intervals by specifying “n-1” split points

 Step # 02: All the values in one interval are

mapped to same categorical value
Attribute Transformation
 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 (two
ways) e.g when you do not require negative values take an
absolute
1. Simple functions: xk, log(x), ex, |x|
2. Standardization: In statistics it refers to subtracting off
the means and dividing by the standard deviation. (to
make an entire set of values have a Particular property
eg. Mean 0 and SD 1)
Normalization: (interchangav)It refers to various techniques
to adjust to differences among attributes in terms of
frequency of occurrence, mean, variance, range etc
normalization and standardization terms are normally used interchangeably.
Normalization or Standardization
(attribute transformation cont..)

 Necessary to avoid having variable with larger values

dominates the results of calculation. E.g comparing
people on age and income
Similarity and Dissimilarity

 Are important for number of data mining

techniques such as
– Clustering
– Nearest neighbor classification
– Anomaly detection
 In some cases original dataset is not needed
once the similarity and dissimilarity have been
computed
 Means transforming the data to a similarity
(dissimilarity) space and then performing the
analysis
Proximity with multiple attributes

 Measures such as
– Euclidean Distance
– Correlation
– Jaccord coefficient
– Cosine similarity

Are proximity measures for objects with multiple

attributes
Euclidean Distance
 Euclidean Distance

Where n is the number of dimensions (attributes) and pk and qk are, respectively, the kth attributes (components) of data objects p and q.

n 2
dist   ( pk  qk )
k 1
Euclidean Distance

3
point x y
2 p1
p1 0 2
p3 p4
1
p2 2 0
p2 p3 3 1
0 p4 5 1
0 1 2 3 4 5 6

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

Distance Matrix
Minkowski Distance
 Minkowski Distance is a generalization of Euclidean Distance

Where r is a parameter, n is the number of dimensions (attributes) and pk and qk are, respectively, the kth attributes (components) or data objects p and q.
For r  , the above equation becomes

1
n r r
dist (  | pk  qk |)
k 1

 max n
k 1 | p k  q k |
Minkowski Distance: Examples

 r = 1. City block (Manhattan, taxicab, L1 norm) distance.

– A common example of this is the Hamming distance, which is just the
number of bits that are different between two binary vectors

 r = 2. Euclidean distance

 r  . “supremum” (Lmax norm, L norm) distance.

– This is the maximum difference between any component of the vectors

 Do not confuse r with n, i.e., all these distances are

defined for all numbers of dimensions.
Minkowski Distance

L1 p1 p2 p3 p4
p1 0 4 4 6
p2 4 0 2 4
p3 4 2 0 2
p4 6 4 2 0
point x y
p1 0 2 L2 p1 p2 p3 p4
p2 2 0 p1 0 2.828 3.162 5.099
p3 3 1 p2 2.828 0 1.414 3.162
p4 5 1 p3 3.162 1.414 0 2
p4 5.099 3.162 2 0

L p1 p2 p3 p4
p1 0 2 3 5
p2 2 0 1 3
p3 3 1 0 2
p4 5 3 2 0

Distance Matrix
Common Properties of a Distance

 Distances, such as the Euclidean distance,

have some well known properties.
1. d(p, q)  0 for all p and q and d(p, q) = 0 only if
p = q. (Positive definiteness)
2. d(p, q) = d(q, p) for all p and q. (Symmetry)
3. d(p, r)  d(p, q) + d(q, r) for all points p, q, and r.
(Triangle Inequality)
where d(p, q) is the distance (dissimilarity) between
points (data objects), p and q.
Measures that satisfy all these properties are known as
metrics, but practice is often violated e.g. set
difference
Common Properties of a Similarity

 Similarities, also have some well known

properties.
1. s(p, q) = 1 (or maximum similarity) only if p = q.

2. s(p, q) = s(q, p) for all p and q. (Symmetry)

where s(p, q) is the similarity between points (data

objects), p and q.

Violation e.g. confusion matrix of O and 0

Similarity Between Binary Vectors
 Common situation is that objects, p and q, have only
binary attributes
 Compute similarities using the following quantities
M01 = the number of attributes where p was 0 and q was 1
M10 = the number of attributes where p was 1 and q was 0
M00 = the number of attributes where p was 0 and q was 0
M11 = the number of attributes where p was 1 and q was 1

 Simple Matching and Jaccard Coefficients

SMC = number of matches / number of attributes
= (M11 + M00) / (M01 + M10 + M11 + M00)

J = number of 11 matches / number of not-both-zero attributes values

= (M11) / (M01 + M10 + M11)
SMC versus Jaccard: Example

p= 1000000000
q= 0000001001

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

M10 = 1 (the number of attributes where p was 1 and q was 0)
M00 = 7 (the number of attributes where p was 0 and q was 0)
M11 = 0 (the number of attributes where p was 1 and q was 1)

SMC = (M11 + M00)/(M01 + M10 + M11 + M00) = (0+7) / (2+1+0+7) = 0.7

e.g. similarity b/w student quiz with true false option only
J = (M11) / (M01 + M10 + M11) = 0 / (2 + 1 + 0) = 0
e.g. transactional data (asymmetric binary data)
Cosine Similarity (non binary data)
 If d1 and d2 are two document vectors, then
cos( d1, d2 ) = (d1  d2) / ||d1|| ||d2|| , where ||d1||=length of
vector d1
where  indicates vector dot product and || d || is the length of vector d.

“0” values should not be considered since two documents are likely
not to contain many of the same words, like jaccord measure.
But also able to handle non binary vectors.
Cosine Similarity

 The cosine measure computes the angle

between the two documents, which is insensitive
to the absolute length of the document
 Let X = (x . . . x ) and Y = (y . . . y ) be two
1 d 1 d
documents on a lexicon of size d
d
 xi y i
cos( X , Y )  i 1
d 2
d 2
 ( xi )  ( yi)
i 1 i 1
Cosine similarity

 Cosine similarity is the measure of angle between

x and y.
 1: if angle between x and y is 0 means totally
similar
 0: if angle is 90 not similar (do not share any
words)
 Dividing x and y by their length normalizes them
to have a length of 1 (means magnitude is not
considered)
Cosine Similarity (example)
 Example:

d1 = 3 2 0 5 0 0 0 2 0 0
d2 = 1 0 0 0 0 0 0 1 0 2

d1  d2= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5
||d1|| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481
||d2|| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245

cos( d1, d2 ) = .3150

 Correlation

 Correlation measures the linear relationship between

the attributes of the objects yk=axk+b for binary or
continuous variable
 Measure of linear dependency b/w two variables x and y
 Pearson’s correlation between two data objects x and y
is defined by the following equation (measures linear relationship)
 Where sd is the expectation of the root mean squared
deviation of random variable from its mean s
cov ariance( x, y ) xy
corr ( x, y )  
s tan dard _ dev ( x )*s tan dard _ dev ( y ) s x *s y
n
1
cov ariance ( x, y ) s xy  
n  1 k 1
( xk  x )( yk  y )
 Correlation

1 2
 k 1 ( xk  x)
n
s tan dard _ dev( x) s x 
n 1

1 2
 k 1 ( yk  y)
n
s tan dard _ dev( y ) s y 
n 1
1 n 1 n
x   xk
n k 1 y  
n k 1
y k
Visually Evaluating Correlation

Scatter plots
showing the
similarity from
–1 to 1.
Correlation

Example: find the correlation of two sets of

vectors
Case 1:
X=(-3,6,0,3,-6)
Y=(1,-2,0,-1,2)

Case 2:
X=(3,6,0,3,6)
Y=(1,2,0,1,2)
Non linear relationships

 If the correlation is 0, then there is no linear

relationship between the attributes of two data
objects.
 However, non-linear relationships may still exist

 E.g. x =y2
k k

Where
X=(-3,-2,-1,0,1,2,3)
Y=(9,4,1,0,1,4,9)
General Approach for Combining
Similarities

 Sometimes attributes are of many different

types, but an overall similarity is needed.
Using Weights to Combine
Similarities

 May not want to treat all attributes the same.

– Use weights wk which are between 0 and 1 and sum
to 1.
Pluses and Minuses of the Proximity functions

 Calculate all proximity functions (both dissimilarity

and similarity) for the bellow data and discuss
the results