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 transformation
◼ Normalization and aggregation

◼ Data reduction
◼ Obtains reduced representation in volume but

produces the same or similar analytical results

◼ Data discretization: part of data reduction, of

particular importance for numerical data

September 9, 2021 Data Mining: Concepts and Techniques 1
 Data Cleaning
◼ No quality data, no quality analyzing results!
◼ Quality decisions must be based on quality data
◼ e.g., duplicate or missing data may cause incorrect or even
misleading statistics
◼ “Data cleaning is the number one problem in data warehousing”—
DCI survey
◼ Data extraction, cleaning, and transformation comprises the
majority of the work of building a data warehouse
◼ Data cleaning tasks
◼ Fill in missing values
◼ Identify outliers and smooth out noisy data
◼ Correct inconsistent data
◼ Resolve redundancy caused by data integration

September 9, 2021 Data Mining: Concepts and Techniques 2

 Data in the Real World Is Dirty
◼ 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/1997”

◼ Was rating “1,2,3”, now rating “A, B, C”

◼ discrepancy between duplicate records

September 9, 2021 Data Mining: Concepts and Techniques 3

 Why Is Data Dirty?

◼ Incomplete data may come from

◼ “Not applicable” data value when collected
◼ Different considerations between the time when the data was
collected and when it is analyzed.
◼ Human/hardware/software problems
◼ Noisy data (incorrect values) may come from
◼ Faulty data collection instruments
◼ Human or computer error at data entry
◼ Errors in data transmission
◼ Inconsistent data may come from
◼ Different data sources
◼ Functional dependency violation (e.g., modify some linked data)
◼ Duplicate records also need data cleaning
September 9, 2021 Data Mining: Concepts and Techniques 4
 Multi-Dimensional Measure of Data Quality
◼ A well-accepted multidimensional view:
◼ Accuracy

◼ Completeness

◼ Consistency

◼ Timeliness

◼ Believability

◼ Value added

◼ Interpretability

◼ Accessibility

◼ Broad categories:
◼ Intrinsic, contextual, representational, and accessibility

September 9, 2021 Data Mining: Concepts and Techniques 5

 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

September 9, 2021 Data Mining: Concepts and Techniques 6

 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
September 9, 2021 Data Mining: Concepts and Techniques 7
 Noisy Data
◼ Noise: random error or variance in a measured variable
◼ Incorrect attribute values may due to
◼ faulty data collection instruments

◼ data entry problems

◼ data transmission problems

◼ technology limitation

◼ inconsistency in naming convention

◼ Other data problems which requires data cleaning

◼ duplicate records

◼ incomplete data

◼ inconsistent data

September 9, 2021 Data Mining: Concepts and Techniques 8

 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)

September 9, 2021 Data Mining: Concepts and Techniques 9

 Simple Discretization Methods: 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
September 9, 2021 Data Mining: Concepts and Techniques 10
 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
September 9, 2021 Data Mining: Concepts and Techniques 11
 Regression

Y1

Y1’ y=x+1

X1 x

September 9, 2021 Data Mining: Concepts and Techniques 12

 Cluster Analysis

September 9, 2021 Data Mining: Concepts and Techniques 13

 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)

September 9, 2021 Data Mining: Concepts and Techniques 14

 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

September 9, 2021 Data Mining: Concepts and Techniques 15

 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
◼ Careful integration of the data from multiple sources may
help reduce/avoid redundancies and inconsistencies and
improve mining speed and quality
September 9, 2021 Data Mining: Concepts and Techniques 16
 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

September 9, 2021 Data Mining: Concepts and Techniques 17

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)

correlatio n( p, q) = p • q

September 9, 2021 Data Mining: Concepts and Techniques 18

 Visually Evaluating Correlation

Scatter plots
showing the
similarity from
–1 to 1.

September 9, 2021 Data Mining: Concepts and Techniques 19

 Correlation Analysis (Categorical Data)
◼ Χ2 (chi-square) test
(Observed − Expected ) 2
2 = 
Expected
◼ The larger the Χ2 value, the more likely the variables are
related
◼ The cells that contribute the most to the Χ2 value are
those whose actual count is very different from the
expected count
◼ Correlation does not imply causality
◼ # of hospitals and # of car-theft in a city are correlated
◼ Both are causally linked to the third variable: population

September 9, 2021 Data Mining: Concepts and Techniques 20

 Chi-Square Calculation: An Example

Play chess Not play chess Sum (row)

Like science fiction 250(90) 200(360) 450

Not like science fiction 50(210) 1000(840) 1050

Sum(col.) 300 1200 1500

◼ Χ2 (chi-square) calculation (numbers in parenthesis are

expected counts calculated based on the data distribution
in the two categories)
(250 − 90) 2 (50 − 210) 2 (200 − 360) 2 (1000 − 840) 2
 =2
+ + + = 507.93
90 210 360 840
◼ It shows that like_science_fiction and play_chess are
correlated in the group
September 9, 2021 Data Mining: Concepts and Techniques 21
 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

◼ Aggregation: Summarization, data cube construction

◼ Generalization: Concept hierarchy climbing

◼ Normalization: Scaled to fall within a small, specified

range
◼ min-max normalization

◼ z-score normalization

◼ normalization by decimal scaling

◼ Attribute/feature construction

◼ New attributes constructed from the given ones

September 9, 2021 Data Mining: Concepts and Techniques 22
 Data Transformation: Normalization
◼ Min-max normalization: to [new_minA, new_maxA]
v − minA
v' = (new _ maxA − new _ minA) + new _ minA
maxA − minA
◼ Ex. Let income range $12,000 to $98,000 normalized to [0.0,
73,600 − 12,000
1.0]. Then $73,000 is mapped to 98,000 − 12,000 (1.0 − 0) + 0 = 0.716
◼ Z-score normalization (μ: mean, σ: standard deviation):
v − A
v' =
 A

73,600 − 54,000
◼ Ex. Let μ = 54,000, σ = 16,000. Then = 1.225
16,000
◼ Normalization by decimal scaling
v
v' = j Where j is the smallest integer such that Max(|ν’|) < 1
10
September 9, 2021 Data Mining: Concepts and Techniques 23
 Data Reduction Strategies

◼ Why data reduction?

◼ A database/data warehouse may store terabytes of data

◼ Complex data analysis/mining may take a very long time to run

on the complete data set

◼ Data reduction: 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
◼ Data reduction strategies
◼ Dimensionality reduction — e.g., remove unimportant attributes

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

◼ Data cub aggregation

◼ Data compression

◼ Regression

◼ Discretization (and concept hierarchy generation)

September 9, 2021 Data Mining: Concepts and Techniques 24

 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

◼ Principal component analysis

◼ Singular value decomposition

◼ Supervised and nonlinear techniques (e.g., feature selection)

September 9, 2021 Data Mining: Concepts and Techniques 25

 Data Reduction Method: 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)
September 9, 2021 Data Mining: Concepts and Techniques 26
 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

September 9, 2021 Data Mining: Concepts and Techniques 27

 Sampling: With or without Replacement

Raw Data
September 9, 2021 Data Mining: Concepts and Techniques 28
 Sampling: Cluster or Stratified Sampling

Raw Data Cluster/Stratified Sample

September 9, 2021 Data Mining: Concepts and Techniques 29

 Data Reduction: 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
◼ Continuous — real numbers, e.g., integer or real numbers
◼ Discretization:
◼ Divide the range of a continuous attribute into intervals
◼ Some classification algorithms only accept categorical attributes.
◼ Reduce data size by discretization
◼ Prepare for further analysis

September 9, 2021 Data Mining: Concepts and Techniques 30

 Discretization and Concept Hierarchy

◼ Discretization
◼ 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
◼ Supervised vs. unsupervised
◼ Split (top-down) vs. merge (bottom-up)
◼ Discretization can be performed recursively on an attribute
◼ Concept hierarchy formation
◼ Recursively reduce the data by collecting and replacing low level
concepts (such as numeric values for age) by higher level concepts
(such as young, middle-aged, or senior)

September 9, 2021 Data Mining: Concepts and Techniques 31

 Discretization and Concept Hierarchy
Generation for Numeric Data
◼ Typical methods: All the methods can be applied recursively
◼ Binning (covered above)
◼ Top-down split, unsupervised,
◼ Histogram analysis (covered above)
◼ Top-down split, unsupervised
◼ Clustering analysis (covered above)
◼ Either top-down split or bottom-up merge, unsupervised
◼ Entropy-based discretization: supervised, top-down split
◼ Interval merging by 2 Analysis: unsupervised, bottom-up merge
◼ Segmentation by natural partitioning: top-down split, unsupervised

September 9, 2021 Data Mining: Concepts and Techniques 32