Chapter-4

Data Preprocessing

1
 Why Data Preprocessing?

• Data which do not have the required quality has the

effect of bad quality mining results!

• Quality decisions must be based on quality data

• Quality data is key for success in data warehousing and

data mining

2
Why Data Preprocessing?
• Data in the real world is full of dirty
• incomplete:
• lacking attribute values that is vital for decision making so they have
to be added,
• lacking certain attributes of interest in certain dimension and should
be again added with the required value,
• containing only aggregate data so that the primary source of the
aggregation should be included
• noisy: containing errors or outliers that deviate from the
expected
• inconsistent: containing discrepancies in codes or names of
the organization or domain
• etc

3
 Why Data Preprocessing?

• Incomplete, noisy and inconsistent data are commonplace

properties of large real world databases and data sources
• Data cleaning routine work to clean such problems so that results
can be accepted
• Before starting data preprocessing, it will be adviceable to have
overall picture of the data we have so that it tell as high level
summary such as
• General property of the data
• Which data values should be considered as noise or outliers
• This can be done with the help of descriptive data summarization

4
 Descriptive data summarization
• Descriptive summary about data can be generated with the help of
measure of central tendency of the data and dispersion of the data
• Measure of central tendency includes
• Mean
• Median
• Mode
• Mid-Range
• Measure of dispersion includes
• range
• The five number summary (based on Quartiles)
• Interquartile range (IQR)
• Standard deviation

5
 Descriptive data summarization
• Mean

• Appropriate for data distributed normally

• Mean is the most important quantity for describing dataset but it

is sensitive to extreme values of an attribute (example outliers)

• So we should consider options

• Trim extremely large and small value (may be 2% from each side)
• Consider another central tendency measure
6
 Descriptive data summarization
• Median
• Appropriate for skewed (asymmetric) data
• However, it is holistic function and difficult to compute
• There are heuristics used to estimate median by grouping the
data into groups of equal width intervals and assume the median
is in the median of the intervals
• Let the median interval has lowest value l, the number of values
in the entire data set is N, the total number of data in all intervals
bellow the median interval is F, the frequency of data in the
median interval is f, and w is the width of the median interval
then median can be estimated as

7
 Descriptive data summarization
• Measure of central tendency includes
• Mode
• Is the set of data that occur most frequently
• Data can be uni-modal, bimodal, tri-modal or multimodal in general
• It tells the most frequent data points
• Is holistic function
• For uni-modal data that is moderately skewed, the mode can be
estimated as

• Mid range
• Is the average of the largest and smallest values in the set
• Is an algebraic function computed as

8
 Descriptive data summarization

• Measure of dispersion (Variance) includes

• range
• The five number summary (based on Quartiles)
• Interquartile range (IQR)
• Standard deviation
• Boxplot can be plotted based on the five number
summary and are useful tool for identifying outliers

9
 Descriptive data summarization
• Range
• Is the difference between the maximum and the minimum
values
• We can assume the data is sorted in ascending for analyzing
the other values
• Hence range is the first value subtracted from last value
• The data bellow has range of 455

1, 3, 4, 4, 12, 19,
23, 34, 43, 45, 45, 56,
56, 56, 56, 65, 67, 76,
78, 78, 86, 250, 456

10
 Descriptive data summarization
• Quartiles
• The Kth percentile of a set of data in numerical order is the
value xi having the property that K% of the data entries lie at
or bellow xi
• Median is the 50th percentile
• Important percentile is quartiles
• 1st quartile refers to 25th percentile (Q1)
• 2nd quartile refers to 50th percentile (median) (Q2)
• 3rd quartile refers to 75th percentile (Q3)

11
 Descriptive data summarization
• Inter Quartile Range
• The Inter-Quartile Range refers to the difference between the
third and the first quartile(i.e. IQR = Q3- Q1)
• Q1, median, Q3, IQR are all holistic functions
• For the above data
• Q1 = 19 Q2 = 56 Q3 = 76 IQR = 57

12
 Descriptive data summarization
• The five number summary (based on Quartiles)
• Includes the parameters: the minimum, Q1, median (Q2), Q3,
IQR, and maximum
• The quartiles including the median gives some indication of the
center, spread, and shape of the distribution

• A common rule of thumb for identifying suspected outliers are

values greater than Q3 + 1.5IQR and bellow Q1-1.5IQR
• For the above data
• Q3 + 1.5*IQR = 165.6 and
• Q1-1.5IQR = -66.5
• See that 250 and 456 are outliers

13
 Descriptive data summarization
• Box Plots
• BoxPlots are popular way of visualizing a distribution which
incorporate the five number summary as
• The end of the box are the quartiles Q1 and Q3 so that the length
of the box is the IQR
• The median is marked by a line within the box
• Two lines (called whiskers) outside the box extends to the
smallest (Minimum) and largest (Maximum) observation
• The whiskers should extended to the extreme low and high
value only if these values are less than 1.5IQR beyond the
quartiles. Otherwise the whiskers terminates at the most
extreme observation occurring within 1.5IQR of the quartiles
• The remaining observations are plotted individually to show
outliers

14
 Descriptive data summarization
• Box Plot
• Box Plots are popular way of visualizing a distribution which
incorporate the five number summary as

15
Boxplot for the unit price data for items sold at four branches
 Descriptive data summarization
• Variance and Standard deviation
• Variance can be computed as follows

• The basic properties of standard deviation () are

• Measure spread about the mean and should be used if mean is chosen
as a measure of central tendency
•  =0 when there is spread (all data value are the same) otherwise  >0
• Variance and  are algebraic measures

16
Graphic display of basic descriptive summaries

• The following are some of the graphical data

presentations tools in statistics for the display of data
summaries and distributions
• bar chart,
• pie chart,
• line graph
• Histograms
• Quantile plot
• q-q plots
• Scatter plot and
• Loess curves

17
 Graphic display of basic descriptive summaries

• Bar chart
• It is a mechanism to compare and contrast individual variable
using bars

18
 Graphic display of basic descriptive summaries

• Pie chart
• It is a mechanism to compare and contrast individual variable
using sectors of a circle. Area of the sector shows the
proportion of the variable value

19
 Graphic display of basic descriptive summaries

• Line Graph
• It is a graph that show the relationship between two variables.
It enable to show dependency of the variables and allows
comparison of two or more variables as well

20
 Graphic display of basic descriptive summaries
• Histograms
• Is also called frequency histogram
• If data set is categorical like grade then one bar is drawn for
each value (say A, B, C,D, F, NG, I) resulting a bar chart
• If data set is numeric, then different buckets should be created
usually intervals of the same width and a bar shows the
frequency of data values at each interval

21
 Graphic display of basic descriptive summaries
•

22
 Graphic display of basic descriptive summaries
• Quantile plot
• Quantile plot is a plots drawn for the data value xi (Y-axis)
against fi (X-axis)
• it displays
• all of the data for the given attribute allowing the user to assess both the
overall behavior and unusual occurrences
• it plots quantile information.
• Note 0.25, 0.5 and 0.75 quantiles corresponds to the quartiles
Q1, Q2, and Q3 respectively

23
 Graphic display of basic descriptive summaries
• Quantile plot
• The following figure shows the data set and the quantile plot

24
 Graphic display of basic descriptive summaries
• q-q plots
• q-q (quantile-quantile) plot shows the plots of the quantile
of one data set distribution against quantile of another
distribution (say unit price at branch 1 against unit price at
branch2)
• The X-Axis and Y-Axis shows the data values of the two
distribution
• A point in the plot shows the pair of values having the same
quantile (a point at (xi, yj) shows that xi and yj have the same
quantile)
• This plot is powerful visualization tool in showing weather
there is a shift in going from one distribution into another

25
 Graphic display of basic descriptive summaries
• q-q plots
• Example This point shows Q2 (0.5 quantile) of branch one
and two are at value 80 and 90 respectively

26
 Graphic display of basic descriptive summaries
• Scatter plot
• Is one of the most effective graphical methods for determining if
there appears a relationship, pattern or trend between two
numeric attributes
• For example unit price versus amount of item sold
• A point in scatter plot indicate the relation between the data
values on each axis as the number of items sold at that unit price
• If there is no relation between the attribute the plots will be
uniformly scattered across the space otherwise there is some kind
of relation

27
 Graphic display of basic descriptive summaries
• Scatter plot
• Example

28
Major Tasks in Data Preprocessing
• Data pre-processing in data mining activity refers to the processing
of data attributes and values to prepare for the mining operation.
• Any activity performed prior to mining the data is called
pre-processing

• This involves:
• Data cleaning
• Data integration
• Data transformation
• Data reduction
• Data Discretization and concept hierarchy generation

29
 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 (heterogeneous data
sources)
 Data transformation
 Normalization and aggregation ( as deemed necessary)
 Data reduction
 Obtains reduced representation in volume but produces the same or similar
analytical results. Very important for Big Data Analysis
 Data discretization
 Data discritization refers to transforming the data set which is usually
continuous into discrete interval values.
Note: Reading Assignment: read the details of each data processing tasks 30
Forms of Data Preprocessing

31
 How to Handle Missing Data
• Ignore the tuple: usually done when class label is missing
(assuming the tasks is classification—not effective when the
percentage of missing values per attribute varies considerably.

• Fill in the missing value manually: tedious and infeasible

• Use a global constant to fill in the missing value: E.g.,

“unknown”, a new class?! Simple but not recommended as this
constant may form some interesting pattern for the data mining
task which mislead decision process

32
 How to Handle Missing Data
• Use the attribute mean: for all samples belonging to the same
class to fill in the missing value with the class mean

• Use the most probable value: fill in the missing values by

predicting its value from correlation of the available values and
values of other attributes through regression analysis, inference-
based tools such as Bayesian formula or decision tree

• Except the first two approach, the rest filled values are incorrect

• The last two approaches are the most commonly used technique to
fill missing data

33
 Data Integration
• Data integration:
• Combines data from multiple sources (databases, data cubes,
or files) into a coherent store
• There are a number of issues to consider during data
integration
• Some of these are
• Schema integration issue
• Entity identification issue
• Data value conflict issue
• Avoiding redundancy issue

34
 Data Integration

• Schema integration
• Schema refers to the design of an entity and its relation in the
data source
• Integrate metadata from different sources

• Entity identification problem:

• identify real world entities from multiple data sources which
are identical so that they can be integrated properly
• As data source for data mining differ, the same entity will
have different representation in the different sources
• Identical entities may have different representation of attribute
naming in different sources

35
 Data Integration
• Data value conflict issue
• Involves detecting and resolving data value conflicts
• for the same real world entity, attribute values from different
sources may be different
• possible reasons: different representations, different scales,
measurement unit used

36
 Data Integration
• Avoiding redundancy issue
• Redundant data occur often during integration of multiple
databases
• The same attribute may have different names in different databases
• One attribute may be a “derived” attribute in another table, e.g., annual
revenue from monthly revenue
• Redundant data may be able to be detected by correlation
analysis for numeric data

37
 Data Integration
• Avoiding redundancy issue
• The correlation between two attribute A and B (rA,B) is always
in the range from -1 to +1.
• rA,B = -1 is to mean negatively correlated, rA,B = 0 to mean
uncorrelated and rA,B = +1 is perfectly correlated

• Careful integration of the data from multiple sources may help

to reduce/avoid redundancies and inconsistencies and improve
mining speed and quality

38
 Data Transformation
• Data transformation is the process of transforming or
consolidating data into a form appropriate for mining which is
more appropriate for measurement of similarity and distance
• This involves
• Smoothing
• Aggregation
• Generalization
• Normalization
• Attribute/feature construction

39
 Data Transformation

• Smoothing: concerned mainly to remove noise from data using

techniques such as binning, clustering, and regression

• Aggregation: summarization or aggregation operations are

performed

• Generalization: concept hierarchy climbing (from low level into

higher level)

40
 Data Transformation
• Normalization: scaled to fall within a small, specified range
– Used mainly
• for classification algorithms such as neural network,
• distance measurements such as clustering, nearest neighbor approach

– Normalization exist in various forms

1. min-max normalization
2. z-score normalization
3. normalization by decimal scaling
4. Attribute/feature construction

41
Data Transformation: Normalization

• min-max normalization
• Perform a linear transformation on the original data into a
specified range of min and max value

MINA v
MAXA

NEW_MINA NEW_MAXA
v’
v  minA
v'  (new _ maxA  new _ minA)  new _ minA
maxA  minA

42
 Data Transformation: Normalization

• z-score (zero mean) normalization

• A value will be normalized based on the mean and standard
deviation of the original data
• The transformed data will have zero mean value

v  meanA
v' 
stand _ devA

43
 Data Reduction
• 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 tries to obtain a reduced representation of the data set
that is much smaller in volume but yet produces the same (or almost
the same or better) analytical results

47
 Data Reduction
• Data reduction strategies includes
• Data cube aggregation
• Attribute subset selection
• Dimensionality reduction
• Huffman coding
• Wavelet transforms
• Principal component analysis
• Numerosity reduction
• Regression and log-linear models
• Histograms
• Clustering
• Sampling

48
 Data reduction strategies: by Data Cube Aggregation

• Data cube aggregation and using it for data mining task reduces the
data set size significantly
• For example, one can aggregate sales amount specified at each year
and quarter into the sum of the sales amount per year
• Multiple levels of aggregation in data cubes further reduce the size
of data to deal with
• One should select appropriate levels of aggregation
• Use the most reduced representation which is sufficient to solve the
task

49
Data reduction strategies: by Attribute subset selection
• Removes irrelevant attribute by attribute relevance analysis

• Let us assume we have d set of attributes in the data set.

• This set has 2d sub sets of attributes and dimensionality reduction

refers to selection of the subset which has the minimum number of
elements in it and represent the pattern as close as possible with the
original attributes

• Hence attribute subset selection may refer one approach of

dimensionality reduction

50
Data reduction strategies: by Attribute subset selection

• Several heuristic for attribute subset (feature) selection exists

• Four of them are:
• step-wise forward selection
• step-wise backward elimination
• combining forward selection and backward elimination
• decision-tree induction algorithm

51
Data reduction strategies: by Attribute subset selection
– step-wise forward selection
• Start with empty set
• The best single-feature is picked first
• Then next best feature will be selected conditioned by the first, ...
• Stop when the selected feature set closely represent the entire
features

52
Data reduction strategies: by Attribute subset selection
– step-wise backward elimination
• Start with all the feature set elements
• The feature which is most irrelevant will be discarded first
• Then next most irrelevant feature will be discarded and
repeated, ...
• Stop when removing the next candidate attribute for removal
affects the pattern significantly

53
Data reduction strategies: By Attribute subset selection
– combining forward selection and backward elimination
• At each step, the procedure selects the best feature and remove
the most irrelevant

– decision-tree induction algorithm

• This algorithm generate a decision tree using some of the
attributes
• The attributes used in building the decision tree will be taken
as attributes that represents closely the entire attributes

54
Data reduction strategies: By Attribute subset selection

Example of Decision Tree Induction

Initial attribute set:
{A1, A2, A3, A4, A5, A6}

A4 ?

A1? A6?

Class 1 Class 2 Class 1 Class 2

> Reduced attribute set: {A1, A4, A6}

55
Data reduction strategies: Dimensionality reduction

compression lossy
Compressed Original Data
Original Data Data Approximated
lossless

57
Data reduction strategies: Dimensionality reduction

• Compression can be made on data such as string, audio, and video

• String compression
• There are extensive theories and well-tuned algorithms
• Typically lossless
• But only limited manipulation is possible without expansion

• Wavelet transformation and principal component analysis are two of

the most common dimension reduction approaches which are lossy

58
Data reduction : Principal Component Analysis for dimension
reduction

• Given N data vectors from k-dimensions, find c <= k

orthogonal vectors that can be best used to represent data
• The original data set is reduced to one consisting of N data
vectors on c principal components (reduced dimensions)
• Each data vector is a linear combination of the c principal
component vectors
• Works for numeric data only
• Used when the number of dimensions is large

63
Dataset preparation for Classification
• Proper procedure in some classification system development
involves three sets of data :
• training data:
• Data used for parameter adjustment
• validation data:
• Data used for goodness of the model to decide next round re-
estimation or not
• Validation data is used to optimize parameters which is optional
in some other systems
• It is optional
• test data:
• Data used for measuring the final performance of the system for
reporting

84
Dataset preparation for Classification

85
Dataset preparation for Classification
• Once evaluation is complete, all the data can be used to build
the final classifier

• Generally, the larger the training data the better the classifier
(but returns diminish)

• The larger the test data the more accurate the error estimate

86
 Building Classification Model

Results Known
+ Model
+ Training set
-
-
Builder
+
Data
Evaluate
Model Builder
Predictions
+
-
Y N
+
Validation set -
+
- Final Evaluation
+
Final Test Set
87
Final Model -
Building Classification Model: Parameter tuning

• Some learning schemes operate in two stages:

• Stage 1: builds the basic structure
• Stage 2: optimizes parameter settings

• Optimizing the parameter setting refers to adjusting important

parameters to maximize the performance of the system

• The test data can’t be used for parameter tuning!

88
 Unbalanced data
• Sometimes, classes have very unequal frequency
• medical diagnosis: 90% healthy, 10% disease
• eCommerce: 99% don’t buy, 1% buy
• Security: >99.99% of Americans are not terrorists
• Majority class classifier can be 97% correct, but useless
• If we have two classes that are very unbalanced, then it
will be a bias to evaluate our classifier method

89
Balancing unbalanced data

• With two or more classes, a good approach to make a

balance between the class instances is to build
BALANCED train and test sets
• Approach
• randomly select desired number of minority class instances
• add equal number of randomly selected majority class
• Stratified sample: advanced version of balancing the data
• Make sure that each class is represented with approximately equal
proportions in both subsets
• Then train the model on a balanced set
• It is important that the test data is not used in any way to
create the classifier

90
 Dataset size
• Before we start building Classification model, we should check
how good is the size of the dataset we have
• Given balanced dataset, the next most important aspect of
goodness is size of the data set
• The model should be able to converge during learning the
parameters from the dataset
• If not, appropriate measure should be taken and care must be
given while reporting performance
• We will see learning curve analysis that best suit to detect
goodness of the size of the training dataset

91
Dataset Size
Learning Curve
• Learning curve is one of the measure of how well the training
data converge to a point of maximum performance.
• It is one of the most important tool to indicate whether the data
set is sufficiently large or not
• If it is sufficiently large, them we can model our system and
tune parameters and start evaluating the system
• If it is small, we should
• Design a means to get more data or
• We should modify the way how to measure performance

92
Dataset Size
Learning Curve

test accuracy

number of training examples

93
 Dataset Size
What to do with small data?
• Having small data but balanced can be approached in different
ways to relay on the performance
• Note that the total data set we have will be divided into three
for training, testing and validation
• The following are the techniques to minimize the effect of the
dataset size
1. Using Repeated holdout data for testing
2. Using k-fold cross validation
3. Using Leave-One-Out cross-validation

94
 Dataset Size
What to do with small data: Using repeated holdout data
• The holdout method reserves a certain amount for testing and uses
the remainder for training and start to evaluate the system
• Usually: one third for testing, the rest for training

• For “unbalanced” datasets, samples might not be representative

• Few or none instances of some classes
• What if we have a small data set?
• The chosen 2/3 for training may not be representative.
• The chosen 1/3 for testing may not be representative.

95
 Dataset Size
What to do with small data: Using repeated holdout data
• Holdout estimate can be made more reliable by repeating the process
with different subsamples
• In each iteration, a certain proportion is randomly selected for
training (possibly with stratification)
• The error rates on the different iterations are averaged to yield an
overall error rate
• Still not optimum: the different test sets overlap.
• Can we prevent overlapping?
• Yes which lead into the k-fold cross validation technique

96
 Dataset Size
What to do with small data: Using K-fold cross validation
• Cross-validation avoids overlapping test sets
• First step: data is split into k subsets of equal size
• Second step: each subset in turn is used for testing and the
remainder for training
• This is called k-fold cross-validation
• Often the subsets are stratified before the cross-validation is
performed
• The error estimates are averaged to yield an overall error estimate

97
 Dataset Size
What to do with small data: Using K-fold cross validation

example:
— Break up data into groups of the same size
—
—

— Hold aside one group for testing and use the rest to build
model
Test
—

— Repeat

98 98
 Dataset Size
What to do with small data: Using K-fold cross validation
• Standard method for evaluation: stratified ten-fold cross-validation
• Why ten?
• Extensive experiments have shown that this is the best choice to get
an accurate estimate
• Stratification reduces the estimate’s variance
• Even better: repeated stratified cross-validation
• E.g. ten-fold cross-validation is repeated ten times and results are
averaged (reduces the variance)

99
 Dataset Size
What to do with small data: Leave-One-Out cross validation

• Leave-One-Out:
a particular form of cross-validation:
• Set number of folds to number of training instances
• I.e., for n training instances, build classifier n times
• Makes best use of the data
• Involves no random sub sampling
• Very computationally expensive
• No stratification on test set as it has only one sample

100