DATA PRE-PROCESSING

-Swati Varma
CHAPTER 3: DATA PREPROCESSING

 Data Preprocessing: An Overview

 Major Tasks in Data Preprocessing

 Data Cleaning

 Data Integration

 Data Reduction

 Data Transformation and Data Discretization

 Summary
2

2
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(remove unimportant attributes)
 Numerosity reduction (clustering, sampling)
 Data compression
 Data transformation and data discretization
 Normalization
 Concept hierarchy generation (organizes concepts )
CHAPTER 3: DATA PREPROCESSING

 Data Preprocessing: An Overview

 Major Tasks in Data Preprocessing

 Data Cleaning

 Data Integration

 Data Reduction

 Data Transformation and Data Discretization

 Summary
4

4
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)
DATA CLEANING

 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?
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 registered history or changes of the data
 Missing data may need to be inferred
HOW TO HANDLE MISSING DATA?
 Ignore the tuple
 Fill in the missing value manually: tedious + infeasible?
 Fill in it automatically with
 a global constant
 the attribute mean
 the most probable value: inference-based such as Bayesian formula or
decision tree
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
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)
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
BINNING METHODS FOR DATA SMOOTHING
 Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
• Smoothing by bin means:
• Each value in a bin is replaced by the mean value of the bin
- Bin 1: 9, 9, 9, 9
- Bin 2: 23, 23, 23, 23
- Bin 3: 29, 29, 29, 29
BINNING METHODS FOR DATA SMOOTHING
 Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
• Smoothing by bin median:
• Each bin value is replaced by its bin median value
- Bin 1: 8.5, 8.5, 8.5, 8.5
- Bin 2: 22.5, 22.5, 22.5, 22.5
- Bin 3: 28.5, 28.5, 28.5, 28.5
BINNING METHODS FOR DATA SMOOTHING
 Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
• Smoothing by bin boundaries:
• The minimum and maximum values in a given bin are identified as the bin
boundaries. Each bin value is then replaced by the closest boundary value.
- Bin 1: 4, 4, 4, 15
- Bin 2: 21, 21, 25, 25
- Bin 3: 26, 26, 26, 34
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)
CHAPTER 3: DATA PREPROCESSING

 Data Preprocessing: An Overview

 Major Tasks in Data Preprocessing

 Data Cleaning

 Data Integration

 Data Reduction

 Data Transformation and Data Discretization

 Summary
16

16
DATA INTEGRATION
 Combines data from multiple sources into a coherent store
 Schema integration:
 e.g.,cust-id, cust-no
 Integrate metadata from different sources
 Entity identification problem:
 Identify real world entities from multiple data sources,
 e.g., Bill Clinton = William Clinton
DATA INTEGRATION
 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, weight in kg
vs pound
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
CORRELATION ANALYSIS (NOMINAL DATA)
Χ2 (chi-square) test
 Used for nominal data
(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 Analysis
 Suppose that a group of 1500 people was surveyed.
 The gender of each person was noted.
 Each person was polled as to whether his or her preferred type of reading
material was fiction or nonfiction.
 Two attributes: gender and preferred reading.
 Let the hypothesis be that A and B(gender and preferred reading) are
independent, that is, there is no correlation between them
CHI-SQUARE CALCULATION: AN EXAMPLE

expected

 Χ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 male are correlated in the group
Correlation Analysis
 Let the hypothesis be that A and B(gender and preferred reading) are independent,
that is, there is no correlation between them

 For this 2*2 table, the degrees of freedom are (2-1) * (2-1)= 1.
 For 1 degree of freedom, the chi sqr value needed to reject the hypothesis at the 0.001
significance level is 10.828 (taken from the table on statistics).

 Since our computed value is above this, we can reject the hypothesis that gender and
preferred reading are independent and conclude that the two attributes are (strongly)
correlated for the given group of people.
CORRELATION ANALYSIS (NUMERIC DATA)

 Used for numeric attributes

 Correlation coefficient (also called Pearson’s product moment
coefficient)  (ai  A)(bi  B)  (aibi )  n AB
n n

rA, B  i 1
 i 1
(n  1) A B (n  1) A B

 where n is the number of tuples, A and B are the

respective means of A and B,
 σA and σB are the respective standard deviation of A and B
CORRELATION ANALYSIS (NUMERIC DATA)

 If rA,B > 0,
 A and B are positively correlated (A’s values increase as
B’s). The higher, the stronger correlation.
 rA,B = 0:
 independent;
 rAB < 0:
 negatively correlated
COVARIANCE (NUMERIC DATA)
 Covariance is similar to correlation

Correlation coefficient:

where n is the number of tuples, A and B are the respective

mean or expected values of A and B, σA and σB are the
respective standard deviation of A and B.

i1 (ai  A)(bi  B) 

n n
(ai bi )  n AB
rA, B   i 1
(n  1) A B (n  1) A B
COVARIANCE (NUMERIC DATA)
 Positive covariance:
 If CovA,B > 0, then A and B both tend to vary in the same direction
 Negative covariance:
 If CovA,B < 0 then A and B tend to vary in the opposite direction

 Independence: CovA,B = 0
 They don't vary together.
CO-VARIANCE: AN EXAMPLE

 It can be simplified in computation as

 Suppose two stocks A and B have the following values in one week:
 (2, 5), (3, 8), (5, 10), (4, 11), (6, 14).
 Question: If the stocks are affected by the same industry trends, will their
prices rise or fall together?
CO-VARIANCE: AN EXAMPLE

 E(A) = (2 + 3 + 5 + 4 + 6)/ 5 = 20/5 = 4

 E(B) = (5 + 8 + 10 + 11 + 14) /5 = 48/5 = 9.6
 Cov(A,B) = (2×5+3×8+5×10+4×11+6×14)/5 − 4 × 9.6 = 4
 Thus, A and B rise together since Cov(A, B) > 0.
 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
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.

32
DATA REDUCTION STRATEGIES
 Dimensionality reduction, e.g., remove unimportant attributes
 Wavelet transforms
 Principal Components Analysis (PCA)
 Feature subset selection
 Numerosity reduction (some simply call it: Data Reduction)
 Regression
 Histograms, clustering, sampling
 Data cube aggregation
 Data compression

33
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

 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
34
DATA REDUCTION 1: DIMENSIONALITY REDUCTION
 Dimensionality reduction techniques
 Wavelet transforms
 Principal Component Analysis
 Attribute sub set selection

35
 ATTRIBUTE SUBSET SELECTION
 Another way to reduce dimensionality of data- reduces the data set
size by removing irrelevant or redundant attributes
 Redundant attributes
 Irrelevant attributes
 Contain no information that is useful for the data mining task at
hand
 E.g., students' ID is often irrelevant to the task of predicting
students' GPA

36
HEURISTIC SEARCH IN ATTRIBUTE SELECTION

 Best step-wise feature selection:

 The procedure starts with an empty set of attributes as the reduced set.
 The best of the original attributes is determined and added to the reduced set.
 At each subsequent iteration or step, the best of the remaining original
attributes is added to the set.

38
HEURISTIC SEARCH IN ATTRIBUTE SELECTION
 Step-wise attribute elimination:
 The procedure starts with the full set of attributes.
 At each step, it removes the worst attribute remaining in the
set.
 Best combined attribute selection and elimination
 at each step, the procedure selects the best attribute and
removes the worst from among the remaining attributes.

39
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)
 Non-parametric methods
 Do not assume models
 Major families: histograms, clustering, sampling, …
40
HISTOGRAM ANALYSIS 40
35
 Divide data into buckets
30
and store average (sum)
for each bucket 25
 1, 1, 5, 5, 5, 5, 5, 8, 8, 10, 10, 10, 10, 12, 14,
14, 14, 15, 15, 15, 15, 15, 15, 18, 18, 18, 18,
20
18, 18, 18, 18, 20, 20, 20, 20, 20, 20, 20, 21,
21, 21, 21, 25, 25, 25, 25, 25, 28, 28, 30, 30, 15
30
10
 Instead of storing each
and every number, store 5
the information 0
10000 30000 50000 70000 90000 41
displayed by the
histogram.
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”
 There are many choices of clustering algorithms

42
SAMPLING
 Sampling: obtaining a small sample s to represent the whole
data set N
 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:

43
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) 44

 Used in conjunction with skewed data

Sampling: With or without Replacement

45
Raw Data
SAMPLING: CLUSTER OR STRATIFIED SAMPLING
Raw Data Cluster/Stratified Sample

46
DATA CUBE AGGREGATION

• A hierarchy for branch could

allow branches to be grouped
into regions, based on their
address.
• Data cubes provide fast
access to precomputed,
summarized data.
Data Cube Aggregation
Data Cube Aggregation
 The cube created at the lowest abstraction level is referred to
as the base cuboid
 E.g. It should correspond to an individual entity of interest
such as sales or customer
 A cube at the highest level of abstraction is the apex cuboid.
 The total sales for all three years, for all item types, and for
all branches.
DATA REDUCTION 3: DATA COMPRESSION
 String compression
 There are extensive theories and well-tuned algorithms
 Typically lossless
 Audio/video compression
 Typically lossy compression, with progressive refinement
 Sometimes small fragments of signal can be reconstructed
without reconstructing the whole

50
DATA COMPRESSION

Original Data Compressed

Data
lossless

Original Data
Approximated
51
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
52
DATA TRANSFORMATION
 The data are transformed or consolidated into forms appropriate for mining.
 A function that maps the entire set of values of a given attribute to a new
set of replacement values such that each old value can be identified with
one of the new values

53
DATA TRANSFORMATION
 Smoothing: Remove noise from data(binning, regression, clustering)
 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: where the raw values of a numeric attribute (e.g., age) are replaced
by interval labels (e.g., 0–10, 11–20, etc.) or conceptual labels (e.g., youth, adult, 54
senior)
 Concept hierarchy generation for nominal data
Normalization
 Expressing an attribute in smaller units will lead to a larger
range for that attribute, and thus tend to give such an
attribute greater effect or “weight.”
 To help avoid dependence on the choice of measurement units,
the data should be normalized or standardized.
 This involves transforming the data to fall within a smaller or
common range such as [-1, 1] or [0.0, 1.0].
MIN-MAX NORMALIZATION
 Suppose that minA and maxA are the minimum and maximum
values of an attribute, A.
 Min-max normalization maps a value, vi , of A in the range
[new minA,new maxA] by computing

v  minA
v'  (new _ maxA  new _ minA)  new _ minA
maxA  minA
Min-max normalization
 Suppose that the minimum and maximum values
for the attribute income are $12,000 and $98,000,
respectively. We would like to map income to the
range [0.0, 1.0]. for Salary of $73,600
73,600  12,000
(1.0  0)  0  0.716
98,000  12,000
Z SCORE NORMALIZATION
 The values for an attribute, A, are normalized based on the
mean (i.e., average) and standard deviation of A.
v  A
v' 
 A

 Let μ = 54,000, σ = 16,000, V=73600

73,600  54,000
 1.225
16,000
NORMALIZATION
 Normalization by decimal scaling

v
v'  j
10

59
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
 The raw values of a numeric attribute (e.g., age) are replaced by interval
labels (e.g., 0–10, 11–20, etc.) or conceptual labels (e.g., youth, adult, senior).
 The labels, in turn, can be recursively organized into higher-level concepts,
resulting in a concept hierarchy for the numeric attribute.

60
DISCRETIZATION
 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
 Types: Supervised vs. unsupervised
 Types: Split (top-down) vs. merge (bottom-up)
 Discretization can be performed recursively on an attribute

61
DATA DISCRETIZATION METHODS
 Typical methods: All the methods can be applied recursively
 Binning
 Histogram analysis
 Clustering analysis
 Decision-tree analysis
 Correlation (e.g., 2) analysis - Initially, each distinct value of a numeric
attribute A is considered to be one interval. χ 2 tests are performed for
every pair of adjacent intervals. Adjacent intervals with the least χ 2
values are merged together

62
CONCEPT HIERARCHY GENERATION
 Concept hierarchies can be explicitly specified by domain experts and/or
data warehouse designers

 Concept hierarchy can be automatically formed for both numeric and

nominal data.

63
CONCEPT HIERARCHY GENERATION FOR NOMINAL
DATA
 Specification of a partial/total ordering of attributes explicitly
at the schema level by users or experts
 street < city < state < country
 Specification of a hierarchy for a set of values by explicit data
grouping
 {Mumbai, Pune, Nashik} < Maharashtra

64
CONCEPT HIERARCHY GENERATION FOR NOMINAL
DATA
 Specification of only a partial set of attributes
 E.g., only street < city, not others

 Automatic generation of hierarchies (or attribute levels) by the

analysis of the number of distinct values
 E.g., for a set of attributes: {street, city, state, country}

65
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(20 years, 12 months,
7 days)
country 15 distinct values
province_or_ state 365 distinct
values
city 3567 distinct values
66
street 674,339 distinct values