COMP9318: Data Warehousing and Data Mining 1
COMP9318: Data Warehousing
and Data Mining
— L3: Data Preprocessing and Data Cleaning —
COMP9318: Data Warehousing and Data Mining 2
n Why preprocess the data?
COMP9318: Data Warehousing and Data Mining 3
Why Data Preprocessing?
n Data in the real world is dirty
n incomplete: lacking attribute values, lacking certain
attributes of interest, or containing only aggregate
data
n e.g., occupation=“”
n noisy: containing errors or outliers
n e.g., Salary=“-10”
n inconsistent: containing discrepancies in codes or
names
n e.g., Age=“42” Birthday=“03/07/1997”
n e.g., Was rating “1,2,3”, now rating “A, B, C”
n e.g., discrepancy between duplicate records
COMP9318: Data Warehousing and Data Mining 4
Why Is Data Dirty?
n Incomplete data comes from
n n/a data value when collected
n different consideration between the time when the data was
collected and when it is analyzed.
n human/hardware/software problems
n Noisy data comes from the process of data
n collection
n entry
n transmission
n Inconsistent data comes from
n Different data sources
n Functional dependency violation
COMP9318: Data Warehousing and Data Mining 5
Why Is Data Preprocessing Important?
n No quality data, no quality mining results!
n Quality decisions must be based on quality data
n e.g., duplicate or missing data may cause incorrect or even
misleading statistics.
n Data warehouse needs consistent integration of quality
data
n Data extraction, cleaning, and transformation comprises
the majority of the work of building a data warehouse. —
Bill Inmon
n Also a critical step for data mining.
COMP9318: Data Warehousing and Data Mining 6
Major Tasks in Data Preprocessing
n Data cleaning
n Fill in missing values, smooth noisy data, identify or remove
outliers, and resolve inconsistencies
n Data integration
n Integration of multiple databases, data cubes, or files
n Data transformation
n Normalization and aggregation
n Data reduction
n Obtains reduced representation in volume but produces the
same or similar analytical results
n Data discretization & Data Type Conversion
COMP9318: Data Warehousing and Data Mining 7
n Data cleaning
COMP9318: Data Warehousing and Data Mining 8
Data Cleaning
n Importance
n “Data cleaning is one of the three biggest problems
in data warehousing”—Ralph Kimball
n “Data cleaning is the number one problem in data
warehousing”—DCI survey
n Data cleaning tasks
n Fill in missing values
n Identify outliers and smooth out noisy data
n Correct inconsistent data
n Resolve redundancy caused by data integration
9
Missing Data
n Data is not always available
n E.g., many tuples have no recorded value for several
attributes, such as customer income in sales data
n Missing data may be due to
n equipment malfunction
n inconsistent with other recorded data and thus deleted
n data not entered due to misunderstanding
n certain data may not be considered important at the time of
entry
n not register history or changes of the data
n Missing data may need to be inferred.
n Many algorithms need a value for all attributes
n Tuples with missing values may have different true values
COMP9318: Data Warehousing and Data Mining 10
How to Handle Missing Data?
n Ignore the tuple: usually done when class label is missing (assuming
the tasks in classification—not effective when the percentage of
missing values per attribute varies considerably.
n Fill in the missing value manually: tedious + infeasible?
n Fill in it automatically with
n a global constant : e.g., “unknown”, a new class?!
n the attribute mean
n the attribute mean for all samples belonging to the same class:
smarter
n the most probable value: inference-based such as Bayesian
formula or decision tree
COMP9318: Data Warehousing and Data Mining 11
Noisy Data
n Noise: random error or variance in a measured variable
n Incorrect attribute values may due to
n faulty data collection instruments
n data entry problems
n data transmission problems
n technology limitation
n inconsistency in naming convention
n Other data problems which requires data cleaning
n duplicate records
n incomplete data
n inconsistent data
COMP9318: Data Warehousing and Data Mining 12
How to Handle Noisy Data?
n Binning method:
n first sort data and partition into (equi-depth) bins
n then one can smooth by bin means, smooth by bin
median, smooth by bin boundaries, etc.
n Clustering
n detect and remove outliers
n Combined computer and human inspection
n detect suspicious values and check by human (e.g.,
deal with possible outliers)
n Regression
n smooth by fitting the data into regression functions
To be
discussed in
discretization
13
Regression
X1
X2
X2 = 1.1X1 + 0.7
2
6
2.9
Suburb #Residents Usage Charge
Kingsford 2 1502 3047
Kensington 3 987 265.6
Maroubra 1 568 198.3
… … … …
COMP9318: Data Warehousing and Data Mining 14
n Data integration and transformation
COMP9318: Data Warehousing and Data Mining 15
Data Integration
n Data integration:
n combines data from multiple sources into a coherent
store
n Schema integration
n integrate metadata from different sources
n Entity identification problem: identify real world entities
from multiple data sources, e.g., A.cust-id ≡ B.cust-#
n Detecting and resolving data value conflicts
n for the same real world entity, attribute values from
different sources are different
n possible reasons: different representations, different
scales, e.g., metric vs. British units
Example
n Data source 1:
n Book(bid, title, isbn)
n Author(aid, fname, lname, birthdate)
n Writes(bid, aid, order)
n Data source 2:
n Book(isbn, title, year, author1, author2, …,
author10)
n Data source 3:
n Author(name, bornInYear, description, book1,
book2, …, book5)
COMP9318: Data Warehousing and Data Mining 16
COMP9318: Data Warehousing and Data Mining 17
Handling Redundancy in Data Integration
n Redundant data occur often when integration of multiple
databases
n The same attribute may have different names in
different databases
n One attribute may be a “derived” attribute in another
table, e.g., annual revenue
n Redundant data may be able to be detected by
correlational analysis
n Careful integration of the data from multiple sources may
help reduce/avoid redundancies and inconsistencies and
improve mining speed and quality
COMP9318: Data Warehousing and Data Mining 18
Data Transformation
n Smoothing: remove noise from data
n Aggregation: summarization, data cube construction
n Generalization: concept hierarchy climbing
n Normalization: scaled to fall within a small, specified
range
n min-max normalization
n z-score normalization
n normalization by decimal scaling
n Attribute/feature construction
n New attributes constructed from the given ones
Also see other transformations later in the Clustering part
19
Data Transformation: Normalization
n min-max normalization
n z-score normalization
n normalization by decimal scaling
min
‘ ( _ max _min ) _min
max min
A
A A A
A A
v
v new new new
−
= − +
−
j
v
v
10
‘= Where j is the smallest integer such that max( ‘ ) 1v < MinMaxScaler StandardScaler; sklearn uses biased variance estimate In scikit-learn, they are called Scaling. Normalization means converting vectors to unit vectors. COMP9318: Data Warehousing and Data Mining 20 n Data reduction 21 Data Reduction Strategies n Modern datasets may be very large n Ratings of millions of customers on millions of items n Many ML algorithms have high time and space complexities. n Even learned models could be very large. n E.g., learned word embeddings (300 dims) for 1M words è at least 1.2GB memory n Data reduction n Obtain a reduced representation of the data set that is much smaller in volume but yet produce the same (or almost the same) analytical results n Data reduction strategies n Dimensionality reduction—remove unimportant attributes n Data Compression n Numerosity reduction—fit data into models n Discretization and concept hierarchy generation High-dimensional Features n It is common for many datasets to contain many features n More is better at data capturing/creation n 561 features for human activity recognition using smartphone dataset: https://archive.ics.uci.edu/ml/datasets/Human +Activity+Recognition+Using+Smartphones n GIST: 128 dimensional feature n Mandated by some model n A document is converted into a high-dimensional feature vector. #dims = |vocabulary| COMP9318: Data Warehousing and Data Mining 22 The Curse of Dimensionality n Data in only one dimension is relatively packed n Adding a dimension “stretches” the points across that dimension, making them further apart n Adding more dimensions will make the points further apart—high dimensional data is extremely sparse è hard to learn n Distance measure tends to become meaningless (graphs from Parsons et al. KDD Explorations 2004) High-dimensional space n High-dimensional space is totally different from low- dimensional space (e.g., 3D) n Many counter-intuitive facts about the high-dimensional space n Two random vectors are almost surely orthogonal n Random sample n points within a unit hypercube è most points are on a thin layer of the surface (annulus) 24 http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/ Goals n Reduce dimensionality of the data, yet still maintain the meaningfulness of the data Dimensionality reduction n Dataset X consisting of n points in a d- dimensional space n Data point xi є Rd (d-dimensional real vector): xi = [xi1, xi2,…, xid]T n Dimensionality reduction methods: n Feature selection: choose a subset of the features n Feature extraction: create new features by combining new ones COMP9318: Data Warehousing and Data Mining 27 Feature Selection n Feature selection (i.e., attribute subset selection): n Select a minimum set of features such that the probability distribution of different classes given the values for those features is as close as possible to the original distribution given the values of all features n reduce # of patterns in the patterns, easier to understand n Heuristic methods (due to exponential # of choices): n step-wise forward selection n step-wise backward elimination n combining forward selection and backward elimination n decision-tree induction COMP9318: Data Warehousing and Data Mining 28 Heuristic Feature Selection Methods n There are 2d possible sub-features of d features n Several heuristic feature selection methods: n Best single features under the feature independence assumption: choose by significance tests. n Best step-wise feature selection: n The best single-feature is picked first n Then next best feature condition to the first, ... n Step-wise feature elimination: n Repeatedly eliminate the worst feature n Best combined feature selection and elimination: n Optimal branch and bound: n Use feature elimination and backtracking 29 n Original dataset: N d-dimensional vectors X = {xi}i=1..n n Find k ≤ d orthogonal basis vectors that can be best used to represent data n Preserves maximum “information” (i.e., variance under the orthogonal constraint) if projected onto these k basis vectors n Reduced data set: Project each xi to the k basis vectors (aka., principal components) n xi’ = [b1…bk]T xi n X’ = [b1…bk]T X (en masse) n Closed related to Singular Vector Decomposition (SVD) Principal Component Analysis (PCA) b1 b2 … bk x1 x2 x3 Projection 30 https://gist.github.com/anonymous/7d888663c6ec679ea65428715b99bfdd n bT x: projection of x onto the basis vector b n What about x’ = BT x, where B consists of another set of d-dim basis vectors? JL Lemma n Johnson-Lindenstrauss Flattening Lemma ‘84: n Given ε>0, and an integer n, let k be a positive
integer such that k ≥ k0=O(ε-2 logn). For every
set X of n points in Rd there exists F: Rd à Rk
such that for all xi, xj in X
n What is the intuitive interpretation of the Lemma?
COMP9318: Data Warehousing and Data Mining 31
kF (xi)� F (xj)k2 2 (1± “)kxi � xjk2
Distributional JL Lemma
n Given ε in (0, ½], δ > 0, there is a random linear
mapping F: Rd à Rk with k = O(ε-2 logδ-1) such
that for any unit vector x in Rd,
n Take δ = n-2, so k = O(ε-2 log(n)), and then for
for all xi, xj є X,
n Hence, by a simple union bound, the same
statement holds for all pairs from X
simultaneously with probability at least ½.
n There exists a deterministic linear mapping which is an
approximate isometry. ç Why/How?
32
Pr[kF (x)k2 2 1± “] � 1� �
Pr[kF (xi)� F (xj)k2 2 (1± “)kxi � xjk2] � 1�
1
n
2
✓
n
2
◆
Explicit Mapping
n F(x) = k-½ * Ux, where Uij ~ N(0, 1), i.e., i.i.d. samples
from the standard Gaussian distribution.
33
yj = hU⇤j , xi =
dX
i=1
xiUij ⇠ N (0, kxk2)
kyk2 ⇠ kxk2 · �2k
U*1
U*1
…
U*k
x F(x) = y1 y2 … yk
=
V ar[kyk2] = 2k
if z ⇠ �2k
Quick proof:
Concentration bound of chisquared distribution:
Pr[|
z
k
� 1| < "] � 1� exp
✓
�
3
16
k"2
◆
E[kyk2] = kxk2 · k
Approximating Inner Product
34
n 20 news groups
n Origin dim: 5000
COMP9318: Data Warehousing and Data Mining 35
Non-linear Dimensionality Reduction
n There are many advanced non-linear dimensionality
reduction methods
n Hypothesis: real high-dimensional data live in a
manifold with low intrinsic dimensionality
Digits dataset (d = 64, Class = 0..5)
COMP9318: Data Warehousing and Data Mining 36
PCA (time = 0.01s)
COMP9318: Data Warehousing and Data Mining 37
t-SNE (time = 5.69s)
COMP9318: Data Warehousing and Data Mining 38
39
Data Compression
n String compression
n There are extensive theories and well-tuned algorithms
n Typically lossless
n But only limited manipulation is possible without
expansion
n Audio/video compression
n Typically lossy compression, with progressive
refinement
n Sometimes small fragments of signal can be
reconstructed without reconstructing the whole
n Time sequence is not audio
n Typically short and vary slowly with time
COMP9318: Data Warehousing and Data Mining 40
Numerosity Reduction
n Parametric methods
n Assume the data fits some model, estimate model
parameters, store only the parameters, and discard
the data (except possible outliers)
n Log-linear analysis: obtain value at a point in m-D
space as the product on appropriate marginal
subspaces
n Non-parametric methods
n Do not assume models
n Major families: histograms (binning), clustering,
sampling
COMP9318: Data Warehousing and Data Mining 41
Random Sampling
8000 points 2000 Points 500 Points
n Allow a mining algorithm to run in complexity that is
potentially sub-linear to the size of the data
n For approximately evaluating models/parameters, etc.
n Then run the “best” model/parameters on large
dataset
42
Other Sampling Methods
n Simple random sampling may have very poor
performance in the presence of skew
n Adaptive sampling methods
n Stratified sampling:
n Approximate the percentage of each class (or
subpopulation of interest) in the overall database
n Used in conjunction with skewed data
n Sketch/synopsis based methods
n E.g., count-min sketch
n A simple and versatile data structure to remember the
frequency of elements approximately
COMP9318: Data Warehousing and Data Mining 43
n Conversion of data types:
n Discretization
n Kernel density estimation
COMP9318: Data Warehousing and Data Mining 44
Discretization
n Three types of simple attributes:
n Nominal/categorical — values from an unordered set
n Profession: clerk, driver, teacher, …
n Ordinal — values from an ordered set
n WAM: HD, D, CR, PASS, FAIL
n Continuous — real numbers, including Boolean values
n Other types:
n Array
n String
n Objects
Discrete values è Continuous values
n Here we focus on
n Continuous values è discrete values
n Removes noise
n Some ML methods only work with discrete valued features
n Reduce the number of distinct values on features, which may
improve the performance of some ML models
n Reduce data size
n Discrete values è continuous values
n Smooth the distribution
n Reconstruct probability density distribution from samples,
which helps generalization
45
COMP9318: Data Warehousing and Data Mining 46
Discretization
n Discretization
n reduce the number of values for a given continuous
attribute by dividing the range of the attribute into
intervals. Interval labels can then be used to replace
actual data values
n Methods
n Binning/Histogram analysis
n Clustering analysis
n Entropy-based discretization
COMP9318: Data Warehousing and Data Mining 47
Simple Discretization Methods: Binning
n Equal-width (distance) partitioning:
n Divides the range into N intervals of equal size:
uniform grid
n if A and B are the lowest and highest values of the
attribute, the width of intervals will be: W = (B –A)/N.
n The most straightforward, but outliers may dominate
presentation
n Skewed data is not handled well.
n Equal-depth (frequency) partitioning:
n Divides the range into N intervals, each containing
approximately same number of samples
n Good data scaling
n Managing categorical attributes can be tricky.
Optimal Binning Problem
n After binning, the educated guess or the smoothed value
is E(xi), where xi are all the values in the same bin
n cost(bin) = SSE([x1, …, xm]) = ∑i=1m (xi – E(xi))2
n cost of B bins = sum(cost(bin1), …, cost(binB))
n Problem: find the B-1 bin boundaries such that the cost of
the resulting bins is minimized
n Alg( {x1, ..., xn}, B )
n Optimal Binning: Solve the problem optimally in
O(B*n2) time and O(n2) space.
n MaxDiff: Solve the problem heuristically in O(n*log(n))
time and O(n) space.
n Note: both algorithms do not sort input data
n Send in sorted({x1, ..., xn}) if necessary
48
COMP9318: Data Warehousing and Data Mining 49
Recursive Formulation
• Observation
OPT(x[1.. n], B) = mini in [n]{SSE(x[1 .. i]) +
OPT(x[i+1 .. n], B-1)}
• Example
• n=4, B=3
x[1] x[2] X[3] x[4]
7 9 13 5
(7,9,13,5)3
(7)1+(9,13,5)2
(7,9)1+(13,5)2
(7)1+(9)1+(13,5)1
(7)1+(9,13)1+(5)1
(7,9)1+(13)1+(5)1
0 + (42+42)
(22+22) + 0
0 + 0
0 + 8
(12+12) + 0
2
what about
(7,9, 13)1+(5)2
For simplicity, we use integers, rather than real numbers, for the examples here.
22/03/17 50
Problem Caused by Overlapping Sub-
problems
n Consider calculating Fibonacci function
n fib(0)=0
n fib(1)=1
n fib(n) = fib(n-1) + fib(n-2), for n>1
n Naïve D&C implementation is
in efficient
fib(4)
fib(3) fib(2)
fib(1) fib(0) fib(2)
fib(1) fib(0)
fib(1)
Boundary Condition
22/03/17 51
Memoization
n Remember solutions of all the sub-problems
n Trade space for time
fib(4)
fib(3)
fib(2)
fib(1) fib(0)
Sub-problem solution
fib(4)
fib(3)
fib(2)
fib(1) 1
fib(0) 0
1
2
3
Dynamic Programming
Sub-problem solution
n Ideas
n Ensure all needed recursive calls are already computed
and memorized è a good schedule of computation
n (Optional) Reused space to store previous recursive call
results fib(4)
fib(3) fib(2)
fib(1) fib(0) fib(2)
fib(1) fib(0)
fib(1)
2D Dynamic Programming
n OPT(x[1.. n], B) = mini in [n]{SSE(x[1 .. i]) +
OPT(x[i+1 .. n], B-1)}
n OPT(S1, B) = mini in [n]{… + OPT(Si+1, B-1)}
n Goal:
53
OPT(Sj, )
OPT(Sj+1, )
… … OPT(Sn, )
OPT(S1, )
… OPT(Sn, )
How to schedule the computations?
Pseudocode
54
OPT(Sj, )
OPT(Sj+1, )
… … OPT(Sn, )
OPT(S1, )
… OPT(Sn, )
Example
n X = [7, 9, 13, 5], B = 3
n (B=2, S2)
n What’s the problem?
n How to calculate it?
COMP9318: Data Warehousing and Data Mining 55
B S1 S2 S3 S4
1 32 0
2 ?? 0 –
3 *** – –
COMP9318: Data Warehousing and Data Mining 56
MaxDiff
• Complexity of the DP algorithm:
• O(n2*B) running time!
• Consider a heuristic method: MaxDiff
• Idea: use the top-(B-1) max “gaps” in the data as the
bin/bucket boundary
• Example:
x[1] x[2] X[3] x[4]
7 9 13 5 n=4, B=3
gap(1-2) gap(2-3) gap(3-4)
2 4 8
(7,9)1 (13)1 (5)1
Discretization via Clustering
n Can consider multiple attributes together
57
An example where univariate discretization does not work well
Supervised Discretization Methods
n MDLPC [Fayyad & Irani, 1993]
COMP9318: Data Warehousing and Data Mining 58
59
Entropy measures uncertainty
n Two classes:
n Give a set S of instances with binary classes {+,-}.
Let the proportions of + and – be p+ and p-.
n Ent(S) = – (p+ log2 p+ + p- log2 p-) (Note: log 0 ≣ 0)
n m classes:
0 1 0.5
1
Ent(S) From information
theory, number of
bits to encode the
class label.
p+
Ent(S) = �
mX
i=1
pi log pi
n Consider drawing a random
sample from S. What can you
tell about its label?
n If Ent(S) = 0:
n If Ent(S) = log(m):
60
Entropy After Splitting T
n Split S into two subsets: S1 and S2.
n What about the label of a random sample given that you
know which subset it is drawn from?
n
n
n Define
n Intuitive meaning of Gain?
E(T ;S) =
|S1|
|S|
Ent(S1) +
|S2|
|S|
Ent(S2)
Gain(T ) = Ent(S)� E(T ;S)
Can be generalized to n-ary split
COMP9318: Data Warehousing and Data Mining 61
Entropy-Based Discretization: MDLPC
n Given a set of samples S, if S is partitioned into two
intervals S1 and S2 using boundary T, the entropy after
partitioning is
n The boundary that minimizes the entropy function over all
possible boundaries is selected as a binary discretization.
n The process is recursively applied to partitions obtained
until some stopping criterion is met, e.g.,
n Experiments show that it may reduce data size and
improve classification accuracy
Ent S E T S( ) ( , )− >δbefore after
These functions are also used in Decision Trees.
E(T ;S) =
|S1|
|S|
Ent(S1) +
|S2|
|S|
Ent(S2)
Stopping Condition of MDLPC
n Stop when
COMP9318: Data Warehousing and Data Mining 62
Not needed. Just for the sake of completeness.
Comments
n Understanding the underlying data distribution is
important
n e.g., via visualization
n Supervised methods usually works well
n More advanced methods exist
n After learning some ML models, you need to
rethink
n Why discretization?
n Why different method/parameters affects the
model performance? 63
Continuous values è Discrete values
n After repeating the experiments (e.g., measuring
customers arriving 3-4pm), we observed the
following random variable xi (e.g., #customers):
n xi = 2, 3, 3, 3, 3, 1, 5
n What’s the probability to see x = 3 in a new
experiment? What about x = 4?
n Naive estimation
n P(x = 3) = 4/7 P(x = 4) = 0 / 7
n Assume x follows the Poisson distribution
n MLE estimation of
n MAP estimation with a prior (typically Gamma)
64
� P (x;�) =
�
x
e
��
x!
Non-parametric Estimation
n Kernel density estimation (KDE)
n Let {xi}i=1:n be n i.i.d. sample of an unknown
f(x)
n We can estimate f(x) as
n K(z) controls the weight given to f(xi) to influence
f(x)
n May think K(x, xi) as measuring their similarity
n h is the bandwidth parameter
n Gaussian kernel:
65
f(x;h) =
1
n
nX
i=1
K
✓
x� xi
h
◆
K(x;h) / exp
✓
�
x
2
2h
2
◆
Impact of h
COMP9318: Data Warehousing and Data Mining 66
Categorical Values
n One hot encoding is widely used in ML
n Let there be m distinct values for the attribute
n The i-th (category) value is converted into a m-
dimensional binary vector v, where
n vj = 0, if j !=1
n vj = 1, otherwise
n scikit-learn: OneHotEncoder
n Disadvantages:
n Ignores similarity between values
n Embedding-based methods can learn better (real)
vectors
67
n Case Study
n c.f., TUN_datacleansing.ppt
COMP9318: Data Warehousing and Data Mining 68