What is Data?
Download
Report
Transcript What is Data?
Data Mining:
Concepts and Techniques
— Chapter 2 —
March 21, 2017
Data Mining: Concepts and Techniques
1
What is about Data?
General data characteristics
Basic data description and exploration
Measuring data similarity
March 21, 2017
Data Mining: Concepts and Techniques
2
What is Data?
Attributes
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, or
Objects
feature
A collection of attributes describe
an object
Object is also known as record,
point, case, sample, entity, or
instance
March 21, 2017
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
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
10
Data Mining: Concepts and Techniques
3
Important Characteristics of Structured Data
Dimensionality
Curse of dimensionality
Sparsity
Only presence counts
Resolution
Patterns depend on the scale
Similarity
Distance measure
March 21, 2017
Data Mining: Concepts and Techniques
4
Attribute Values
Attribute values are numbers or symbols assigned to an attribute
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
ID has no limit but age has a maximum and
minimum value
March 21, 2017
Data Mining: Concepts and Techniques
5
Types of Attribute Values
Nominal
E.g., profession, ID numbers, eye color, zip codes
Ordinal
E.g., rankings (e.g., army, professions), grades, height
in {tall, medium, short}
Binary
E.g., medical test (positive vs. negative)
Interval
E.g., calendar dates, body temperatures
Ratio
E.g., temperature in Kelvin, length, time, counts
March 21, 2017
Data Mining: Concepts and Techniques
6
Properties of Attribute Values
The type of an attribute depends on which of the following properties it
possesses:
Distinctness:
=
Order:
< >
Addition:
+ Multiplication:
*/
Nominal attribute: distinctness
Ordinal attribute: distinctness & order
Interval attribute: distinctness, order & addition
Ratio attribute: all 4 properties
March 21, 2017
Data Mining: Concepts and Techniques
7
Attribute
Type
Description
Examples
Nominal
The values of a nominal attribute are
just different names, i.e., nominal
attributes provide only enough
information to distinguish one object
from another. (=, )
zip codes, employee
ID numbers, eye color,
sex: {male, female}
mode, entropy,
contingency
correlation, 2 test
Ordinal
The values of an ordinal attribute
provide enough information to order
objects. (<, >)
hardness of minerals,
{good, better, best},
grades, street numbers
median, percentiles,
rank correlation,
run tests, sign tests
Interval
For interval attributes, the
differences between values are
meaningful, i.e., a unit of
measurement exists.
(+, - )
calendar dates,
temperature in Celsius
or Fahrenheit
mean, standard
deviation, Pearson's
correlation, t and F
tests
For ratio variables, both differences
and ratios are meaningful. (*, /)
temperature in Kelvin,
monetary quantities,
counts, age, mass,
length, electrical
current
geometric mean,
harmonic mean,
percent variation
Ratio
March 21, 2017
Data Mining: Concepts and Techniques
Operations
8
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
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
March 21, 2017
Data Mining: Concepts and Techniques
9
Types of data sets
Record
Graph
Data Matrix
Document Data
Transaction Data
World Wide Web
Molecular Structures
Ordered
Spatial Data
Temporal Data
Sequential Data
Genetic Sequence Data
March 21, 2017
Data Mining: Concepts and Techniques
10
Important Characteristics of Structured Data
Dimensionality
Sparsity
Only presence counts
Resolution
March 21, 2017
Curse of Dimensionality
Patterns depend on the scale
Data Mining: Concepts and Techniques
11
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
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
10
March 21, 2017
Data Mining: Concepts and Techniques
12
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
March 21, 2017
Data Mining: Concepts and Techniques
13
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
pla
y
ball
score
game
wi
n
lost
timeout
season
March 21, 2017
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
Data Mining: Concepts and Techniques
14
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.
March 21, 2017
TID
Items
1
Bread, Coke, Milk
2
3
4
5
Beer, Bread
Beer, Coke, Diaper, Milk
Beer, Bread, Diaper, Milk
Coke, Diaper, Milk
Data Mining: Concepts and Techniques
15
Graph Data
Examples: Generic graph and HTML Links
2
1
5
2
<a href="papers/papers.html#bbbb">
Data Mining </a>
<li>
<a href="papers/papers.html#aaaa">
Graph Partitioning </a>
<li>
<a href="papers/papers.html#aaaa">
Parallel Solution of Sparse Linear System of Equations </a>
<li>
<a href="papers/papers.html#ffff">
N-Body Computation and Dense Linear System Solvers
5
March 21, 2017
Data Mining: Concepts and Techniques
16
Chemical Data
Benzene Molecule: C6H6
March 21, 2017
Data Mining: Concepts and Techniques
17
Ordered Data
Sequences of transactions
Items/Events
An element of
the sequence
March 21, 2017
Data Mining: Concepts and Techniques
18
Ordered Data
Genomic sequence data
GGTTCCGCCTTCAGCCCCGCGCC
CGCAGGGCCCGCCCCGCGCCGTC
GAGAAGGGCCCGCCTGGCGGGCG
GGGGGAGGCGGGGCCGCCCGAGC
CCAACCGAGTCCGACCAGGTGCC
CCCTCTGCTCGGCCTAGACCTGA
GCTCATTAGGCGGCAGCGGACAG
GCCAAGTAGAACACGCGAAGCGC
TGGGCTGCCTGCTGCGACCAGGG
March 21, 2017
Data Mining: Concepts and Techniques
19
Ordered Data
Spatio-Temporal Data
Average Monthly
Temperature of
land and ocean
March 21, 2017
Data Mining: Concepts and Techniques
20
General data characteristics
Basic data description and exploration
Measuring data similarity
March 21, 2017
Data Mining: Concepts and Techniques
21
Mining Data Descriptive Characteristics
Motivation
Data dispersion characteristics
To better understand the data: central tendency, variation
and spread
median, max, min, quantiles, outliers, variance, etc.
Numerical dimensions correspond to sorted intervals
Data dispersion: analyzed with multiple granularities of
precision
Boxplot or quantile analysis on sorted intervals
Dispersion analysis on computed measures
Folding measures into numerical dimensions
Boxplot or quantile analysis on the transformed cube
March 21, 2017
Data Mining: Concepts and Techniques
22
Measuring the Central Tendency
1 n
Mean (algebraic measure) (sample vs. population): x
xi
n i 1
Weighted arithmetic mean:
x
N
n
Trimmed mean: chopping extreme values
x
Median: A holistic measure
w x
i 1
n
i
i
w
i 1
i
Middle value if odd number of values, or average of the middle two
values otherwise
Estimated by interpolation (for grouped data):
median L1 (
Mode
Value that occurs most frequently in the data
Unimodal, bimodal, trimodal
Empirical formula:
March 21, 2017
N / 2 ( freq)l
freqmedian
) width
mean mode 3 (mean median)
Data Mining: Concepts and Techniques
23
Symmetric vs. Skewed Data
Median, mean and mode of
symmetric, positively and
negatively skewed data
positively skewed
March 21, 2017
symmetric
negatively skewed
Data Mining: Concepts and Techniques
24
Measuring the Dispersion of Data
Quartiles, outliers and boxplots
Quartiles: Q1 (25th percentile), Q3 (75th percentile)
Inter-quartile range: IQR = Q3 – Q1
Five number summary: min, Q1, M, Q3, max
Boxplot: ends of the box are the quartiles, median is marked, whiskers, and
plot outlier individually
Outlier: usually, a value higher/lower than 1.5 x IQR
Variance and standard deviation (sample: s, population: σ)
Variance: (algebraic, scalable computation)
1 n
1 n 2 1 n
2
s
( xi x )
[ xi ( xi ) 2 ]
n 1 i 1
n 1 i 1
n i 1
2
1
N
2
n
1
(
x
)
i
N
i 1
2
n
xi 2
2
i 1
Standard deviation s (or σ) is the square root of variance s2 (or σ2)
March 21, 2017
Data Mining: Concepts and Techniques
25
Boxplot Analysis
Five-number summary of a distribution:
Minimum, Q1, M, Q3, Maximum
Boxplot
Data is represented with a box
The ends of the box are at the first and third
quartiles, i.e., the height of the box is IQR
The median is marked by a line within the box
Whiskers: two lines outside the box extend to
Minimum and Maximum
March 21, 2017
Data Mining: Concepts and Techniques
26
Histogram Analysis
Graph displays of basic statistical class descriptions
Frequency histograms
March 21, 2017
A univariate graphical method
Consists of a set of rectangles that reflect the counts or
frequencies of the classes present in the given data
Data Mining: Concepts and Techniques
27
Histograms Often Tells More than Boxplots
The two histograms
shown in the left may
have the same boxplot
representation
March 21, 2017
The same values
for: min, Q1,
median, Q3, max
But they have rather
different data
distributions
Data Mining: Concepts and Techniques
28
Quantile Plot
Displays all of the data (allowing the user to assess both
the overall behavior and unusual occurrences)
Plots quantile information
For a data xi data sorted in increasing order, fi
indicates that approximately 100 fi% of the data are
below or equal to the value xi
March 21, 2017
Data Mining: Concepts and Techniques
29
Quantile-Quantile (Q-Q) Plot
Graphs the quantiles of one univariate distribution against
the corresponding quantiles of another
Allows the user to view whether there is a shift in going
from one distribution to another
March 21, 2017
Data Mining: Concepts and Techniques
30
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
March 21, 2017
Data Mining: Concepts and Techniques
31
Loess Curve
Adds a smooth curve to a scatter plot in order to
provide better perception of the pattern of dependence
Loess curve is fitted by setting two parameters: a
smoothing parameter, and the degree of the
polynomials that are fitted by the regression
March 21, 2017
Data Mining: Concepts and Techniques
32
Positively and Negatively Correlated Data
The left half fragment is positively
correlated
March 21, 2017
The right half is negative correlated
Data Mining: Concepts and Techniques
33
Not Correlated Data
March 21, 2017
Data Mining: Concepts and Techniques
34
Data Visualization and Its Methods
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
Typical visualization methods:
Geometric techniques
Icon-based techniques
Hierarchical techniques
March 21, 2017
Data Mining: Concepts and Techniques
35
Geometric Techniques
Visualization of geometric transformations and projections
of the data
Methods
Landscapes
Projection pursuit technique
Finding meaningful projections of multidimensional
data
Scatterplot matrices
Prosection views
Hyperslice
Parallel coordinates
March 21, 2017
Data Mining: Concepts and Techniques
36
Used by ermission of M. Ward, Worcester Polytechnic Institute
Scatterplot Matrices
Matrix of scatterplots (x-y-diagrams) of the k-dim. data
March 21, 2017
Data Mining: Concepts and Techniques
37
Used by permission of B. Wright, Visible Decisions Inc.
Landscapes
news articles
visualized as
a landscape
Visualization of the data as perspective landscape
The data needs to be transformed into a (possibly artificial) 2D
spatial representation which preserves the characteristics of the data
March 21, 2017
Data Mining: Concepts and Techniques
38
Parallel Coordinates
n equidistant axes which are parallel to one of the screen axes and
correspond to the attributes
The axes are scaled to the [minimum, maximum]: range of the
corresponding attribute
Every data item corresponds to a polygonal line which intersects each
of the axes at the point which corresponds to the value for the
attribute
• • •
Attr. 1
March 21, 2017
Attr. 2
Attr. 3
Data Mining: Concepts and Techniques
Attr. k
39
Parallel Coordinates of a Data Set
March 21, 2017
Data Mining: Concepts and Techniques
40
Icon-based Techniques
Visualization of the data values as features of icons
Methods:
Chernoff Faces
Stick Figures
Shape Coding:
Color Icons:
TileBars: The use of small icons representing the
relevance feature vectors in document retrieval
March 21, 2017
Data Mining: Concepts and Techniques
41
Chernoff Faces
A way to display variables on a two-dimensional surface, e.g., let x be
eyebrow slant, y be eye size, z be nose length, etc.
The figure shows faces produced using 10 characteristics--head
eccentricity, eye size, eye spacing, eye eccentricity, pupil size,
eyebrow slant, nose size, mouth shape, mouth size, and mouth
opening): Each assigned one of 10 possible values, generated using
Mathematica (S. Dickson)
REFERENCE: Gonick, L. and Smith, W. The
Cartoon Guide to Statistics. New York:
Harper Perennial, p. 212, 1993
Weisstein, Eric W. "Chernoff Face." From
MathWorld--A Wolfram Web Resource.
mathworld.wolfram.com/ChernoffFace.html
March 21, 2017
Data Mining: Concepts and Techniques
42
Hierarchical Techniques
Visualization of the data using a hierarchical
partitioning into subspaces.
Methods
Dimensional Stacking
Worlds-within-Worlds
Treemap
Cone Trees
InfoCube
March 21, 2017
Data Mining: Concepts and Techniques
43
Tree-Map
Screen-filling method which uses a hierarchical partitioning
of the screen into regions depending on the attribute values
The x- and y-dimension of the screen are partitioned
alternately according to the attribute values (classes)
MSR Netscan Image
March 21, 2017
Data Mining: Concepts and Techniques
44
Tree-Map of a File System (Schneiderman)
March 21, 2017
Data Mining: Concepts and Techniques
45
General data characteristics
Basic data description and exploration
Measuring data similarity (Sec. 7.2)
March 21, 2017
Data Mining: Concepts and Techniques
46
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 (i.e., distance)
Numerical measure of how different are two data
objects
Lower when objects are more alike
Minimum dissimilarity is often 0
Upper limit varies
Proximity refers to a similarity or dissimilarity
March 21, 2017
Data Mining: Concepts and Techniques
47
Data Matrix and Dissimilarity Matrix
Data matrix
n data points with p
dimensions
Two modes
Dissimilarity matrix
n data points, but
registers only the
distance
A triangular matrix
Single mode
March 21, 2017
x11
...
x
i1
...
x
n1
...
x1f
...
...
...
...
xif
...
...
...
...
... xnf
...
...
0
d(2,1)
0
d(3,1) d ( 3,2) 0
:
:
:
d ( n,1) d ( n,2) ...
Data Mining: Concepts and Techniques
x1p
...
xip
...
xnp
... 0
48
Example: Data Matrix and Distance Matrix
3
point
p1
p2
p3
p4
p1
2
p3
p4
1
p2
0
0
1
2
3
4
5
p1
p2
p3
p4
0
2.828
3.162
5.099
y
2
0
1
1
Data Matrix
6
p1
x
0
2
3
5
p2
2.828
0
1.414
3.162
p3
3.162
1.414
0
2
p4
5.099
3.162
2
0
Distance Matrix (i.e., Dissimilarity Matrix) for Euclidean Distance
March 21, 2017
Data Mining: Concepts and Techniques
49
Minkowski Distance
Minkowski distance: A popular distance measure
d (i, j) q (| x x |q | x x |q ... | x x |q )
i1 j1
i2
j2
ip
jp
where i = (xi1, xi2, …, xip) and j = (xj1, xj2, …, xjp) are two
p-dimensional data objects, and q is the order
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
March 21, 2017
Data Mining: Concepts and Techniques
50
Special Cases of Minkowski Distance
q = 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
q= 2: (L2 norm) Euclidean distance
d (i, j) (| x x |2 | x x |2 ... | x x |2 )
i1 j1
i2
j2
ip
jp
q . “supremum” (Lmax norm, L norm) distance.
This is the maximum difference between any component of the
vectors
Do not confuse q with n, i.e., all these distances are defined for all
numbers of dimensions.
Also, one can use weighted distance, parametric Pearson product
moment correlation, or other dissimilarity measures
March 21, 2017
Data Mining: Concepts and Techniques
51
Example: Minkowski Distance
point
p1
p2
p3
p4
x
0
2
3
5
y
2
0
1
1
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
L2
p1
p2
p3
p4
p1
p2
2.828
0
1.414
3.162
p3
3.162
1.414
0
2
p4
5.099
3.162
2
0
L
p1
p2
p3
p4
p1
p2
p3
p4
0
2.828
3.162
5.099
0
2
3
5
2
0
1
3
3
1
0
2
5
3
2
0
Distance Matrix
March 21, 2017
Data Mining: Concepts and Techniques
52
Binary Variables
1
0
a
b
A contingency table for binary data Object i 1
0
c
d
sum a c b d
Distance measure for symmetric
d (i, j)
binary variables:
Distance measure for asymmetric
binary variables:
Jaccard coefficient (similarity
measure for asymmetric binary
variables):
Object j
d (i, j)
sum
a b
cd
p
bc
a bc d
bc
a bc
simJaccard (i, j)
a
a b c
A binary variable is symmetric if
both of its states are equally
valuable and carry the same weight.
March 21, 2017
Data Mining: Concepts and Techniques
53
Dissimilarity between Binary Variables
Example
Name
Jack
Mary
Jim
Gender
M
F
M
Fever
Y
Y
Y
Cough
N
N
P
Test-1
P
P
N
Test-2
N
N
N
Test-3
N
P
N
Test-4
N
N
N
gender is a symmetric attribute
the remaining attributes are asymmetric binary
let the values Y and P be set to 1, and the value N be set to 0
01
0.33
2 01
11
d ( jack , jim )
0.67
111
1 2
d ( jim , mary )
0.75
11 2
d ( jack , mary )
March 21, 2017
Data Mining: Concepts and Techniques
54
Nominal Variables
A generalization of the binary variable in that it can take
more than 2 states, e.g., red, yellow, blue, green
Method 1: Simple matching
m: # of matches, p: total # of variables
m
d (i, j) p
p
Method 2: Use a large number of binary variables
creating a new binary variable for each of the M
nominal states
March 21, 2017
Data Mining: Concepts and Techniques
55
Ordinal Variables
An ordinal variable can be discrete or continuous
Order is important, e.g., rank
Can be treated like interval-scaled
replace xif by their rank
map the range of each variable onto [0, 1] by replacing
i-th object in the f-th variable by
zif
rif {1,...,M f }
rif 1
M f 1
compute the dissimilarity using methods for intervalscaled variables
March 21, 2017
Data Mining: Concepts and Techniques
56
Ratio-Scaled Variables
Ratio-scaled variable: a positive measurement on a
nonlinear scale, approximately at exponential scale,
such as AeBt or Ae-Bt
Methods:
treat them like interval-scaled variables—not a good
choice! (why?—the scale can be distorted)
apply logarithmic transformation
yif = log(xif)
March 21, 2017
treat them as continuous ordinal data treat their rank
as interval-scaled
Data Mining: Concepts and Techniques
57
Variables of Mixed Types
A database may contain all the six types of variables
symmetric binary, asymmetric binary, nominal, ordinal,
interval and ratio
One may use a weighted formula to combine their effects
pf 1 ij( f ) dij( f )
d (i, j)
pf 1 ij( f )
f is binary or nominal:
dij(f) = 0 if xif = xjf , or dij(f) = 1 otherwise
f is interval-based: use the normalized distance
f is ordinal or ratio-scaled
Compute ranks rif and
r
1
zif
M 1
Treat zif as interval-scaled
if
f
March 21, 2017
Data Mining: Concepts and Techniques
58
Vector Objects: Cosine Similarity
Vector objects: keywords in documents, gene features in micro-arrays, …
Applications: information retrieval, biologic taxonomy, ...
Cosine measure: If d1 and d2 are two vectors, then
cos(d1, d2) = (d1 d2) /||d1|| ||d2|| ,
where indicates vector dot product, ||d||: the length of vector d
Example:
d1 = 3 2 0 5 0 0 0 2 0 0
d2 = 1 0 0 0 0 0 0 1 0 2
d1d2 = 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
March 21, 2017
Data Mining: Concepts and Techniques
59
Correlation Analysis (Numerical Data)
Correlation coefficient (also called Pearson’s product
moment coefficient)
rp ,q
( p p)( q q) ( pq) n p q
(n 1) p q
(n 1) p q
where n is the number of tuples, p and q are the respective
means of p and q, σp and σq are the respective standard deviation
of p and q, and Σ(pq) is the sum of the pq cross-product.
If rp,q > 0, p and q are positively correlated (p’s values
increase as q’s). The higher, the stronger correlation.
rp,q = 0: independent; rpq < 0: negatively correlated
March 21, 2017
Data Mining: Concepts and Techniques
60
Correlation (viewed as linear relationship)
Correlation measures the linear relationship
between objects
To compute correlation, we standardize data
objects, p and q, and then take their dot product
pk ( pk mean( p)) / std ( p)
qk (qk mean(q)) / std (q)
correlation( p, q) p q
March 21, 2017
Data Mining: Concepts and Techniques
61
Visually Evaluating Correlation
Scatter plots
showing the
similarity from
–1 to 1.
March 21, 2017
Data Mining: Concepts and Techniques
62