Data Mining:

Concepts and Techniques

(3rd ed.)

— Chapter 3 —
Jiawei Han, Micheline Kamber, and Jian Pei
University of Illinois at Urbana-Champaign &
Simon Fraser University
©2011 Han, Kamber & Pei. All rights reserved.
1
 Chapter 3: Data Preprocessing

■ Data Preprocessing: An Overview

■ Data Quality
■ Major Tasks in Data Preprocessing
■ Data Cleaning
■ Data Integration

■ Data Reduction
■ Data Transformation and Data Discretization
■ Summary

2
 Data Quality: Why Preprocess the Data?
■ Measures for data quality: A multidimensional view
■ Accuracy: correct or wrong, accurate or not
■ Completeness: not recorded, unavailable, …
■ Consistency: some modified but some not, dangling, …
■ Timeliness: timely update?
■ Believability: how trustable the data are correct?
■ Interpretability: how easily the data can be
understood?

3
 Major Tasks in Data Preprocessing
■ Data cleaning
■ Fill in missing values, smooth noisy data, identify or remove
outliers, and resolve inconsistencies
■ Data integration
■ Integration of multiple databases, data cubes, or files
■ Data reduction
■ Dimensionality reduction
■ Numerosity reduction
■ Data compression
■ Data transformation and data discretization
■ Normalization
■ Concept hierarchy generation

4
 Chapter 3: Data Preprocessing

■ Data Preprocessing: An Overview

■ Data Quality
■ Major Tasks in Data Preprocessing
■ Data Cleaning
■ Data Integration

■ Data Reduction
■ Data Transformation and Data Discretization
■ Summary

5
 Data Cleaning
■ Data in the Real World Is Dirty: Lots of potentially incorrect data,
e.g., instrument faulty, human or computer error, transmission error
■ incomplete: lacking attribute values, lacking certain attributes of
interest, or containing only aggregate data
■ e.g., Occupation=“ ” (missing data)
■ noisy: containing noise, errors, or outliers
■ e.g., Salary=“−10” (an error)
■ inconsistent: containing discrepancies in codes or names, e.g.,
■ Age=“42”, Birthday=“03/07/2010”
■ Was rating “1, 2, 3”, now rating “A, B, C”

■ discrepancy between duplicate records

■ Intentional (e.g., disguised missing data)

■ Jan. 1 as everyone’s birthday?

6
 Incomplete (Missing) Data

■ Data is not always available

■ E.g., many tuples have no recorded value for several
attributes, such as customer income in sales data
■ Missing data may be due to
■ equipment malfunction
■ inconsistent with other recorded data and thus deleted
■ data not entered due to misunderstanding
■ certain data may not be considered important at the
time of entry
■ not register history or changes of the data
■ Missing data may need to be inferred
7
 How to Handle Missing Data?
■ Ignore the tuple: usually done when class label is missing
(when doing classification)—not effective when the % of
missing values per attribute varies considerably
■ Fill in the missing value manually: tedious + infeasible?
■ Fill in it automatically with
■ a global constant : e.g., “unknown”, a new class?!
■ the attribute mean
■ the attribute mean for all samples belonging to the
same class: smarter
■ the most probable value: inference-based such as
Bayesian formula or decision tree
8
 Noisy Data
■ Noise: random error or variance in a measured variable
■ Incorrect attribute values may be due to
■ faulty data collection instruments

■ data entry problems

■ data transmission problems

■ technology limitation

■ inconsistency in naming convention

■ Other data problems which require data cleaning

■ duplicate records

■ incomplete data

■ inconsistent data

9
 How to Handle Noisy Data?

■ Binning
■ first sort data and partition into (equal-frequency) bins

■ then one can smooth by bin means, smooth by bin

median, smooth by bin boundaries, etc.

■ Regression
■ smooth by fitting the data into regression functions

■ Clustering
■ detect and remove outliers

■ Combined computer and human inspection

■ detect suspicious values and check by human (e.g.,

deal with possible outliers)

10
 Data Cleaning as a Process
■ Data discrepancy detection
■ Use metadata (e.g., domain, range, dependency, distribution)
■ Check field overloading
■ Check uniqueness rule, consecutive rule and null rule
■ Use commercial tools
■ Data scrubbing: use simple domain knowledge (e.g., postal

code, spell-check) to detect errors and make corrections

■ Data auditing: by analyzing data to discover rules and

relationship to detect violators (e.g., correlation and clustering

to find outliers)
■ Data migration and integration
■ Data migration tools: allow transformations to be specified
■ ETL (Extraction/Transformation/Loading) tools: allow users to
specify transformations through a graphical user interface
■ Integration of the two processes
■ Iterative and interactive (e.g., Potter’s Wheels)

11
 Chapter 3: Data Preprocessing

■ Data Preprocessing: An Overview

■ Data Quality
■ Major Tasks in Data Preprocessing
■ Data Cleaning
■ Data Integration

■ Data Reduction
■ Data Transformation and Data Discretization
■ Summary

12
 Data Integration
■ Data integration:
■ Combines data from multiple sources into a coherent store
■ Schema integration: e.g., [Link]-id ≡ [Link]-#
■ Integrate metadata from different sources
■ Entity identification problem:
■ Identify real world entities from multiple data sources, e.g., Bill
Clinton = William Clinton
■ Detecting and resolving data value conflicts
■ For the same real world entity, attribute values from different
sources are different
■ Possible reasons: different representations, different scales, e.g.,
metric vs. British units
13
 Handling Redundancy in Data Integration

■ Redundant data occur often when integration of multiple

databases
■ Object identification: The same attribute or object
may have different names in different databases
■ Derivable data: One attribute may be a “derived”
attribute in another table, e.g., annual revenue
■ Redundant attributes may be able to be detected by
correlation analysis and covariance analysis
■ Careful integration of the data from multiple sources may
help reduce/avoid redundancies and inconsistencies and
improve mining speed and quality
14
 Chapter 3: Data Preprocessing

■ Data Preprocessing: An Overview

■ Data Quality
■ Major Tasks in Data Preprocessing
■ Data Cleaning
■ Data Integration

■ Data Reduction
■ Data Transformation and Data Discretization
■ Summary

15
 Data Reduction Strategies
■ Data reduction: Obtain a reduced representation of the data set that
is much smaller in volume but yet produces the same (or almost the
same) analytical results
■ Why data reduction? — A database/data warehouse may store
terabytes of data. Complex data analysis may take a very long time to
run on the complete data set.
■ Data reduction strategies
■ Dimensionality reduction, e.g., remove unimportant attributes
■ Wavelet transforms

■ Principal Components Analysis (PCA)

■ Feature subset selection, feature creation

■ Numerosity reduction (some simply call it: Data Reduction)

■ Regression and Log-Linear Models

■ Histograms, clustering, sampling

■ Data cube aggregation

■ Data compression

16
Data Reduction 1: Dimensionality Reduction
■ Curse of dimensionality
■ When dimensionality increases, data becomes increasingly sparse
■ Density and distance between points, which is critical to clustering, outlier
analysis, becomes less meaningful
■ The possible combinations of subspaces will grow exponentially
■ Dimensionality reduction
■ Avoid the curse of dimensionality
■ Help eliminate irrelevant features and reduce noise
■ Reduce time and space required in data mining
■ Allow easier visualization
■ Dimensionality reduction techniques
■ Wavelet transforms
■ Principal Component Analysis
■ Supervised and nonlinear techniques (e.g., feature selection)

17
 Data Reduction 2: Numerosity Reduction
■ Reduce data volume by choosing alternative, smaller
forms of data representation
■ Parametric methods (e.g., regression)
■ Assume the data fits some model, estimate model

parameters, store only the parameters, and discard

the data (except possible outliers)
■ Ex.: Log-linear models—obtain value at a point in m-D

space as the product on appropriate marginal

subspaces
■ Non-parametric methods
■ Do not assume models

■ Major families: histograms, clustering, sampling, …

18
 Parametric Data Reduction: Regression and
Log-Linear Models
■ Linear regression
■ Data modeled to fit a straight line

■ Often uses the least-square method to fit the line

■ Multiple regression
■ Allows a response variable Y to be modeled as a

linear function of multidimensional feature vector

■ Log-linear model
■ Approximates discrete multidimensional probability

distributions

19
 Clustering
■ Partition data set into clusters based on similarity, and
store cluster representation (e.g., centroid and diameter)
only
■ Can be very effective if data is clustered but not if data is
“smeared”
■ Can have hierarchical clustering and be stored in
multi-dimensional index tree structures
■ There are many choices of clustering definitions and
clustering algorithms
■ Cluster analysis will be studied in depth in Chapter 10

20
 Sampling

■ Sampling: obtaining a small sample s to represent the

whole data set N
■ Allow a mining algorithm to run in complexity that is
potentially sub-linear to the size of the data
■ Key principle: Choose a representative subset of the data
■ Simple random sampling may have very poor
performance in the presence of skew
■ Develop adaptive sampling methods, e.g., stratified
sampling:
■ Note: Sampling may not reduce database I/Os (page at a
time)
21
 Types of Sampling

■ Simple random sampling

■ There is an equal probability of selecting any particular
item
■ Sampling without replacement
■ Once an object is selected, it is removed from the
population
■ Sampling with replacement
■ A selected object is not removed from the population

■ Stratified sampling:
■ Partition the data set, and draw samples from each
partition (proportionally, i.e., approximately the same
percentage of the data)
■ Used in conjunction with skewed data

22
Sampling: With or without Replacement

W O R
SRS le random
i m p h ou t
(s e wi t
p l
sam ment)
p l a ce
re

SRSW
R

Raw Data
23
Sampling: Cluster or Stratified Sampling

Raw Data Cluster/Stratified Sample

24
 Data Cube Aggregation

■ The lowest level of a data cube (base cuboid)

■ The aggregated data for an individual entity of interest
■ E.g., a customer in a phone calling data warehouse
■ Multiple levels of aggregation in data cubes
■ Further reduce the size of data to deal with
■ Reference appropriate levels
■ Use the smallest representation which is enough to
solve the task
■ Queries regarding aggregated information should be
answered using data cube, when possible

25
 Data Reduction 3: Data Compression
■ String compression
■ There are extensive theories and well-tuned algorithms

■ Typically lossless, but only limited manipulation is

possible without expansion

■ Audio/video compression
■ Typically lossy compression, with progressive refinement

■ Sometimes small fragments of signal can be

reconstructed without reconstructing the whole

■ Time sequence is not audio
■ Typically short and vary slowly with time

■ Dimensionality and numerosity reduction may also be

considered as forms of data compression
26
 Data Compression

Original Data Compressed

Data
lossless

s s y
lo
Original Data
Approximated

27
 Chapter 3: Data Preprocessing

■ Data Preprocessing: An Overview

■ Data Quality
■ Major Tasks in Data Preprocessing
■ Data Cleaning
■ Data Integration

■ Data Reduction
■ Data Transformation and Data Discretization
■ Summary

28
 Data Transformation
■ A function that maps the entire set of values of a given attribute to a
new set of replacement values s.t. each old value can be identified
with one of the new values
■ Methods
■ Smoothing: Remove noise from data
■ Attribute/feature construction
■ New attributes constructed from the given ones
■ Aggregation: Summarization, data cube construction
■ Normalization: Scaled to fall within a smaller, specified range
■ min-max normalization
■ z-score normalization
■ normalization by decimal scaling
■ Discretization: Concept hierarchy climbing 29
 Normalization
■ Min-max normalization: to [new_minA, new_maxA]

■ Ex. Let income range $12,000 to $98,000 normalized to [0.0,

1.0]. Then $73,000 is mapped to
■ Z-score normalization (μ: mean, σ: standard deviation):

■ Ex. Let μ = 54,000, σ = 16,000. Then

■ Normalization by decimal scaling

Where j is the smallest integer such that Max(|ν’|) < 1

30
 Discretization
■ Three types of attributes
■ Nominal—values from an unordered set, e.g., color, profession
■ Ordinal—values from an ordered set, e.g., military or academic rank
■ Numeric—real numbers, e.g., integer or real numbers
■ Discretization: Divide the range of a continuous attribute into intervals
■ Interval labels can then be used to replace actual data values
■ Reduce data size by discretization
■ Supervised vs. unsupervised
■ Split (top-down) vs. merge (bottom-up)
■ Discretization can be performed recursively on an attribute
■ Prepare for further analysis, e.g., classification

31
 Data Discretization Methods
■ Typical methods: All the methods can be applied recursively
■ Binning
■ Top-down split, unsupervised
■ Histogram analysis
■ Top-down split, unsupervised
■ Clustering analysis (unsupervised, top-down split or
bottom-up merge)
■ Decision-tree analysis (supervised, top-down split)
■ Correlation (e.g., χ2) analysis (unsupervised, bottom-up
merge)

32
 Simple Discretization: Binning
■ Equal-width (distance) partitioning
■ Divides the range into N intervals of equal size: uniform grid
■ if A and B are the lowest and highest values of the attribute, the
width of intervals will be: W = (B –A)/N.
■ The most straightforward, but outliers may dominate presentation
■ Skewed data is not handled well

■ Equal-depth (frequency) partitioning

■ Divides the range into N intervals, each containing approximately
same number of samples
■ Good data scaling
■ Managing categorical attributes can be tricky

33
 Binning Methods for Data Smoothing
❑ Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26,
28, 29, 34
* Partition into equal-frequency (equi-depth) bins:
- Bin 1: 4, 8, 9, 15
- Bin 2: 21, 21, 24, 25
- Bin 3: 26, 28, 29, 34
* Smoothing by bin means:
- Bin 1: 9, 9, 9, 9
- Bin 2: 23, 23, 23, 23
- Bin 3: 29, 29, 29, 29
* Smoothing by bin boundaries:
- Bin 1: 4, 4, 4, 15
- Bin 2: 21, 21, 25, 25
- Bin 3: 26, 26, 26, 34

34
Discretization Without Using Class Labels
(Binning vs. Clustering)

Data Equal interval width (binning)

Equal frequency (binning) K-means clustering leads to better results

35
 Automatic Concept Hierarchy Generation
■ Some hierarchies can be automatically generated based on
the analysis of the number of distinct values per attribute in
the data set
■ The attribute with the most distinct values is placed at
the lowest level of the hierarchy
■ Exceptions, e.g., weekday, month, quarter, year

country 15 distinct values

province_or_ state 365 distinct values

city 3567 distinct values

street 674,339 distinct values

36
 Chapter 3: Data Preprocessing

■ Data Preprocessing: An Overview

■ Data Quality
■ Major Tasks in Data Preprocessing
■ Data Cleaning
■ Data Integration

■ Data Reduction
■ Data Transformation and Data Discretization
■ Summary

37
 Summary
■ Data quality: accuracy, completeness, consistency, timeliness,
believability, interpretability
■ Data cleaning: e.g. missing/noisy values, outliers
■ Data integration from multiple sources:
■ Entity identification problem
■ Remove redundancies
■ Detect inconsistencies
■ Data reduction
■ Dimensionality reduction
■ Numerosity reduction
■ Data compression
■ Data transformation and data discretization
■ Normalization
■ Concept hierarchy generation

38
 References
■ D. P. Ballou and G. K. Tayi. Enhancing data quality in data warehouse environments. Comm. of
ACM, 42:73-78, 1999
■ A. Bruce, D. Donoho, and H.-Y. Gao. Wavelet analysis. IEEE Spectrum, Oct 1996
■ T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley, 2003
■ J. Devore and R. Peck. Statistics: The Exploration and Analysis of Data. Duxbury Press, 1997.
■ H. Galhardas, D. Florescu, D. Shasha, E. Simon, and C.-A. Saita. Declarative data cleaning:
Language, model, and algorithms. VLDB'01
■ M. Hua and J. Pei. Cleaning disguised missing data: A heuristic approach. KDD'07
■ H. V. Jagadish, et al., Special Issue on Data Reduction Techniques. Bulletin of the Technical
Committee on Data Engineering, 20(4), Dec. 1997
■ H. Liu and H. Motoda (eds.). Feature Extraction, Construction, and Selection: A Data Mining
Perspective. Kluwer Academic, 1998
■ J. E. Olson. Data Quality: The Accuracy Dimension. Morgan Kaufmann, 2003
■ D. Pyle. Data Preparation for Data Mining. Morgan Kaufmann, 1999
■ V. Raman and J. Hellerstein. Potters Wheel: An Interactive Framework for Data Cleaning and
Transformation, VLDB’2001
■ T. Redman. Data Quality: The Field Guide. Digital Press (Elsevier), 2001
■ R. Wang, V. Storey, and C. Firth. A framework for analysis of data quality research. IEEE Trans.
Knowledge and Data Engineering, 7:623-640, 1995
39