Data Mining

Concepts and
Techniques

Dr. Mohamad Shady Ahmad Alrahhal

1
AI & Data Mining:
Concepts and
Techniques

— Chapter 2 —
(Getting to Know Your Data)
Jiawei Han, Micheline Kamber, and Jian Pei
University of Illinois at Urbana-Champaign
Simon Fraser University
©2011 Han, Kamber, and Pei. All rights
reserved.
Dr. Mohamad Shady Ahmad Alrahhal 2
Chapter 2: Getting to Know Your
Data

 Data Objects and Attribute Types

 Basic Statistical Descriptions of Data

 Data Visualization

 Measuring Data Similarity and Dissimilarity

 Summary

3
 Types of Data Sets
 Record

Relational records

Data matrix, e.g., numerical matrix,

timeout

season
coach

game
score
team

ball

lost
pla

wi
crosstabs

n
y

Document data: text documents: term-
frequency vector
Document 1 3 0 5 0 2 6 0 2 0 2

Transaction data
 Graph and network Document 2 0 7 0 2 1 0 0 3 0 0

World Wide Web
Document 3 0 1 0 0 1 2 2 0 3 0

Social or information networks

Molecular Structures ‫الهياكل الجزئية‬
 Ordered TID Items

Video data: sequence of images
1 Bread, Coke, Milk

Temporal data: time-series

Sequential Data: transaction 2 Beer, Bread
sequences 3 Beer, Coke, Diaper, Milk

Genetic sequence data 4 Beer, Bread, Diaper, Milk
 Spatial, image and multimedia:
5 Coke, Diaper, Milk

Spatial data: maps

Image data:

Video data:
4
 Important Characteristics of
Structured Data

 Dimensionality
 Curse of dimensionality
 Sparsity ‫التبعثر‬
 Only presence counts
 Resolution

Patterns depend on the scale
 Distribution
 Centrality and dispersion ‫المركزية و‬
‫التشتت‬
5
 Data Objects

 Data sets are made up of data objects.

 A data object represents an entity.
 Examples:
 sales database: customers, store items, sales

medical database: patients, treatments

university database: students, professors, courses
 Also called samples , examples, instances, data
points, objects, tuples.
 Data objects are described by attributes.
 Database rows -> data objects; columns -
>attributes.
6
 Attributes
 Attribute (or dimensions, features,
variables): a data field, representing a
characteristic or feature of a data object.
 E.g., customer _ID, name, address

 Types:
 Nominal

 Binary

 Numeric: quantitative


Interval-scaled

Ratio-scaled
7
 Types of Attributes
● 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 in {tall, medium, short}
– Interval
◆Examples: calendar dates, temperatures in Celsius or
Fahrenheit.
– Ratio
◆Examples: temperature in Kelvin, length, time, counts
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
Attribute Transformation Comments
Level

Nominal Any permutation of values If all employee ID numbers

‫أي تقليب للقيم‬ were reassigned, would it
make any difference?

Ordinal An order preserving change of An attribute encompassing

values, i.e., the notion of good, better
new_value = f(old_value) best can be represented
where f is a monotonic function. equally well by the values
{1, 2, 3} or by { 0.5, 1, 10}.

Interval new_value =a * old_value + b Thus, the Fahrenheit and

where a and b are constants Celsius temperature scales
differ in terms of where
their zero value is and the
size of a unit (degree).

Ratio new_value = a * old_value Length can be measured in

meters or feet.
 Discrete vs. Continuous
Attributes
 Discrete Attribute
 Has only a finite or countably infinite set ‫غيرمحدودة‬of values

E.g., zip codes, profession, or the set of words
in a collection of documents
 Sometimes, represented as integer variables

 Note: Binary attributes are a special case of

discrete attributes
 Continuous Attribute
 Has real numbers as attribute values


E.g., 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
11
Chapter 2: Getting to Know Your
Data

 Data Objects and Attribute Types

 Basic Statistical Descriptions of Data

 Data Visualization

 Measuring Data Similarity and Dissimilarity

 Summary

12
Graphic Displays of Basic Statistical
Descriptions

 Boxplot: graphic display of five-number summary

 Histogram: x-axis are values, y-axis repres.
frequencies
 Scatter plot: each pair of values is a pair of
coordinates and plotted as points in the plane

13
Boxplot: Providing Outliers

14
 Histogram Analysis
 Histogram: Graph display of
tabulated frequencies, shown as 40
bars
35
 It shows what proportion of cases
fall into each of several categories 30
 Differs from a bar chart in that it 25
is the area of the bar that denotes 20
the value, not the height as in bar
15
charts, a crucial distinction when
the categories are not of uniform 10
width 5
 The categories are usually
0
specified as non-overlapping 10000 30000 50000 70000 90000
intervals of some variable. The
categories (bars) must be
adjacent
15
 Scatter plot
 Provides a first look at bivariate‫ داتا ثنائية‬data to
see clusters of points, outliers, etc
 Each pair of values is treated as a pair of
coordinates and plotted as points in the plane

16
Chapter 2: Getting to Know Your
Data

 Data Objects and Attribute Types

 Basic Statistical Descriptions of Data

 Data Visualization

 Measuring Data Similarity and Dissimilarity

 Summary

17
 Data Visualization
 Why data visualization?
 Gain insight into an information space by mapping data onto
graphical primitives
 Provide qualitative overview of large data sets
 Search for patterns, trends, structure, irregularities, relationships
among data
 Help find interesting regions and suitable parameters for further
quantitative analysis
 Provide a visual proof of computer representations derived
 Categorization of visualization methods:
 Pixel-oriented visualization techniques
 Geometric projection visualization techniques
 Icon-based visualization techniques
 Hierarchical visualization techniques
 Visualizing complex data and relations
18
Pixel-Oriented Visualization Techniques
■ For a data set of m dimensions, create m windows on the screen, one for
each dimension
■ The m dimension values of a record are mapped to m pixels at the
corresponding positions in the windows
■ The colors of the pixels reflect the corresponding values

(a) Income (b) Credit Limit (c) transaction volume (d) age
19
 Laying Out Pixels in Circle Segments
■ To save space and show the connections among multiple
dimensions, space filling is often done in a circle segment

(a) Representing a data

(b) Laying out pixels in circle segment
record in circle segment
Representing about 265,000 50-dimensional Data Items
with the ‘Circle Segments’ Technique 20
Chapter 2: Getting to Know Your
Data

 Data Objects and Attribute Types

 Basic Statistical Descriptions of Data

 Data Visualization

 Measuring Data Similarity and Dissimilarity

 Summary

21
 Similarity and Dissimilarity
 Similarity
 Numerical measure of how alike two data objects

are
 Value is higher when objects are more alike

 Often falls in the range [0,1]

 Dissimilarity (e.g., distance)

 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

22
 Data Matrix and Dissimilarity
Matrix
 Data matrix
 n data points with  x11 ... x1f ... x1p 
 
p dimensions  ... ... ... ... ... 
 Two modes x ... xif ... xip 
 i1 
 ... ... ... ... ... 
x ... xnf ... xnp 
 n1 
 Dissimilarity matrix
 n data points, but
 0 
 d(2,1) 0 
registers only the  
 d(3,1) d ( 3,2) 0 
distance  
 A triangular matrix  : : : 
 d ( n,1) d ( n,2) ... ... 0
 Single mode

23
 Proximity Measure for Nominal
Attributes
 Can take 2 or more states, e.g., red, yellow,
blue, green (generalization of a binary attribute)
 Method 1: Simple matching

m: # of matches, p: total # of variables

d (i, j)  p p m
 Method 2: Use a large number of binary
attributes

creating a new binary attribute for each of the
M nominal states

24
 Proximity Measure for Binary
Attributes
Object j
 A contingency table for binary data
Object i

 Distance measure for symmetric

binary variables:
 Distance measure for asymmetric
binary variables:
 Jaccard coefficient (similarity
measure for asymmetric binary
variables):

 Note: Jaccard coefficient is the same as “coherence”:

25
 Dissimilarity between Binary
Variables

 Example
Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4
Jack M Y=1 N=0 P=1 N=0 N=0 N=0
Mary F Y=1 N=0 P=1 N=0 P=1 N=0
Jim M Y=1 P=1 N=0 N=0 N=0 N=0

 Gender is a symmetric attribute

 The remaining attributes are asymmetric binary
 Let the values Y and P be 1, and the value N 0
0 1
d ( jack , mary )  0.33
2  0 1
11
d ( jack , jim )  0.67
111
1 2
d ( jim , mary )  0.75
11 2 26
 Example:
Data Matrix and Dissimilarity Matrix
Data Matrix
x2 x4
point attribute1 attribute2
4 x1 1 2
x2 3 5
x3 2 0
x4 4 5
2 x1
Dissimilarity Matrix
(with Euclidean Distance)
x3
0 4 x1 x2 x3 x4
2
x1 0
x2 3.61 0
x3 5.1 5.1 0
x4 4.24 1 5.39 0

27
Distance on Numeric Data: Minkowski
Distance
 Minkowski distance: A popular distance measure

where i = (xi1, xi2, …, xip) and j = (xj1, xj2, …, xjp) are two
p-dimensional data objects, and h is the order (the
distance so defined is also called L-h norm)
 Properties
 d(i, j) > 0 if i ≠ j, and d(i, i) = 0 (Positive definiteness)
 d(i, j) = d(j, i) (Symmetry)
 d(i, j)  d(i, k) + d(k, j) (Triangle Inequality)
 A distance that satisfies these properties is a metric

28
Special Cases of Minkowski Distance
 h = 1: Manhattan (city block, L1 norm) distance
 E.g., the Hamming distance: the number of bits that are
different between two binary vectors
d (i, j) | x  x |  | x  x | ... | x  x |
i1 j1 i2 j 2 ip jp

 h = 2: (L2 norm) Euclidean distance

d (i, j)  (| x  x |2  | x  x |2 ... | x  x |2 )
i1 j1 i2 j 2 ip jp

 h  . “supremum” (Lmax norm, L norm) distance.

 This is the maximum difference between any component
(attribute) of the vectors

29
 Example: Minkowski Distance
Dissimilarity Matrices
point attribute 1 attribute 2 Manhattan
x1 1 2 (L1)L x1 x2 x3 x4
x2 3 5 x1 0
x3 2 0 x2 5 0
x4 4 5 x3 3 6 0
x4 6 1 7 0
Euclidean (L2)
x2 x4
L2 x1 x2 x3 x4
4 x1 0
x2 3.61 0
x3 2.24 5.1 0
x4 4.24 1 5.39 0

2 x1
Supremum
L x1 x2 x3 x4
x1 0
x2 3 0
x3 x3 2 5 0
0 2 4 x4 3 1 5 0
30
 Cosine Similarity
 A document can be represented by thousands of attributes, each
recording the frequency of a particular word (such as keywords)
or phrase in the document.

 Other vector objects: gene features in micro-arrays, …

 Applications: information retrieval, biologic taxonomy, gene
feature mapping, ...
 Cosine measure: If d1 and d2 are two vectors (e.g., term-frequency
vectors), then
cos(d1, d2) = (d1  d2) /||d1|| ||d2|| ,
where  indicates vector dot product, ||d||: the length of vector
d
31
 Example: Cosine Similarity
 cos(d1, d2) = (d1  d2) /||d1|| ||d2|| ,
where  indicates vector dot product, ||d|: the length of vector d

 Ex: Find the similarity between documents 1 and 2.

d1 = (5, 0, 3, 0, 2, 0, 0, 2, 0, 0)
d2 = (3, 0, 2, 0, 1, 1, 0, 1, 0, 1)

d1d2 = 5*3+0*0+3*2+0*0+2*1+0*1+0*1+2*1+0*0+0*1 = 25
||d1||= (5*5+0*0+3*3+0*0+2*2+0*0+0*0+2*2+0*0+0*0)0.5=(42)0.5
= 6.481
||d2||= (3*3+0*0+2*2+0*0+1*1+1*1+0*0+1*1+0*0+1*1)0.5=(17)0.5
= 4.12
cos(d1, d2 ) = 0.94

32
 Summary
 Data attribute types: nominal, binary, ordinal, interval-scaled,
ratio-scaled
 Many types of data sets, e.g., numerical, text, graph, Web,
image.
 Gain insight into the data by:
 Basic statistical data description: central tendency,
dispersion, graphical displays
 Data visualization: map data onto graphical primitives
 Measure data similarity
 Above steps are the beginning of data preprocessing.
 Many methods have been developed but still an active area of
research.

33