Chapter Three

Data Preprocessing
• Why preprocess the data?
• Descriptive data summarization
– Graphic display of basic descriptive summaries
• Major Tasks in Data Preprocessing
– Data cleaning
– Data integration
– Data transformation
– Data reduction
 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

January 2, 2026 Data Mining: Concepts and Techniques 3

 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

January 2, 2026 Data Mining: Concepts and Techniques 4

 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
January 2, 2026 Data Mining: Concepts and Techniques 5
 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
January 2, 2026 Data Mining: Concepts and Techniques 6
 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

January 2, 2026 Data Mining: Concepts and Techniques 7

 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

January 2, 2026 Data Mining: Concepts and Techniques 8

 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

January 2, 2026 Data Mining: Concepts and Techniques 9

 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

January 2, 2026 Data Mining: Concepts and Techniques 10

 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

January 2, 2026 Data Mining: Concepts and Techniques 11

 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)

January 2, 2026 Data Mining: Concepts and Techniques 12

 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

January 2, 2026 Data Mining: Concepts and Techniques 13

 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

January 2, 2026 Data Mining: Concepts and Techniques 14

 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

January 2, 2026 Data Mining: Concepts and Techniques 15

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

16
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

January 2, 2026 Data Mining: Concepts and Techniques 17

 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
January 2, 2026 Data Mining: Concepts and Techniques 18
 Graphic display of basic descriptive
summaries
• Bar chart
– It is a mechanism to compare and contrast individual variable
using bars whose length

2020
q3
1400

1200
q2 Male
1000
Female

1890
q1
500

0 500 1000 1500 2000 2500

January 2, 2026 Data Mining: Concepts and Techniques 19

 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

500

q1
1400
q2
q3

1000

January 2, 2026 Data Mining: Concepts and Techniques 20

 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
6000

5000

4000

3000 Female
Male
2000

1000

0
q1 q2 q3 q4 q5 q6 q7

January 2, 2026 Data Mining: Concepts and Techniques 21

 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

January 2, 2026 Data Mining: Concepts and Techniques 22

 Graphic display of basic descriptive
summaries

January 2, 2026 Data Mining: Concepts and Techniques 23

 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

January 2, 2026 Data Mining: Concepts and Techniques 24

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

January 2, 2026 Data Mining: Concepts and Techniques 25

 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

January 2, 2026 Data Mining: Concepts and Techniques 26

 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

January 2, 2026 Data Mining: Concepts and Techniques 27

 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

January 2, 2026 Data Mining: Concepts and Techniques 28

 Graphic display of basic descriptive
summaries
• Scatter plot
– Example

January 2, 2026 Data Mining: Concepts and Techniques 29

 Graphic display of basic descriptive
summaries
• Loess curves
– Loess is an abbreviation for local regression
– Is a scatter plot that adds a smooth curve in order to provide better
perception of the pattern dependence
– The curve is drawn with the help of regression taking the data point as
sample data points in the curve
– Finding a fitting function for two dimensional case so that the value
of the second variable can be estimated using the value of the first
variable
– The regression function can be linear or non-linear
– Linear regression will try to fit the best linear function predicted using
the available data

January 2, 2026 Data Mining: Concepts and Techniques 30

 Graphic display of basic descriptive
summaries
• Loess curves: Linear regression function
– Linear regression will try to fit the best linear function predicted
using the available data
– Has the general formula as Y =a+ bX
– The two parameters , a and b specify the line and are to be
estimated by using the data at hand using the formula shown
bellow

January 2, 2026 Data Mining: Concepts and Techniques 31

 Graphic display of basic descriptive
summaries
• Loess curves: Non-Linear Regression Models
• In addition to the linear regression more types of regression of a variable y on a variable x
exist namely:
• Logarithmic model: The logarithmic curve-fitting model requires positive x-values.

• Exponential model: This model requires positive y-values.

January 2, 2026 Data Mining: Concepts and Techniques 32

 Graphic display of basic descriptive
summaries
• Power model: The power model requires positive x-values and positive y-values

• Inverse model:

• Quadratic model: Bear in mind that this model needs at least three points. An example is
the relation between kinetic energy and speed.

January 2, 2026 Data Mining: Concepts and Techniques 33

 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

January 2, 2026 Data Mining: Concepts and Techniques 34

 Data Cleaning
• Refers to the process of
• filling in missing values,
• smooth noisy data,
• identify or remove outliers, and
• resolve inconsistencies

January 2, 2026 Data Mining: Concepts and Techniques 35

 Data Cleaning: Missing Data
• Data attribute value is not always available (missing data)
– E.g.,
• Some patient doesn’t have know their address (patient DB)
• Some drivers education level is not recorded (traffic penalty data)
• Encoders doesn’t understand the patient disease code and left un
encoded (patient DB)
• Encoder jump patient telephone unrecorded as he/she feel
unimportant (patient DB)
• Encoder leave the value of an attribute as the attribute is not among
the valid value list (Example: age is valid in some system if it is less
than 120 hence 130 can not be recorded)

January 2, 2026 Data Mining: Concepts and Techniques 36

 Data Cleaning: Missing Data
• Causes for missing data
– equipment malfunction
– inconsistent with other recorded data and thus deleted
– data not entered due to lack of understanding
– certain data may not be considered important at the time of entry and
hence left blank
– not register history or changes of the data

• Missing data may need to be inferred.

January 2, 2026 Data Mining: Concepts and Techniques 37

 Data Cleaning: 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
January 2, 2026 Data Mining: Concepts and Techniques 38
 Data Cleaning: 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
January 2, 2026 Data Mining: Concepts and Techniques 39
 Data Cleaning: Noisy Data
• Noise is a characteristics of an attribute value when it has incorrect
attribute value
• Noise is defined as a 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

January 2, 2026 Data Mining: Concepts and Techniques 40

 Data Cleaning: How to Handle Noisy Data?
• Noisy data can be handled by the techniques such as
– Simple Discretization Methods (Binning method)
– Clustering
– Regression
– Combined computer and human inspection
• detect suspicious values and check by human

January 2, 2026 Data Mining: Concepts and Techniques 41

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)

• Algorithm
1. Sort the data and partition into bins
2. Choose the number of bins (N) and do binning
• The bins can be equal-depth or equal-width
3. Do Smoothing
• The algorithm can be
1. smooth by bin means,
2. smooth by bin median,
3. smooth by bin boundaries, etc.

January 2, 2026 Data Mining: Concepts and Techniques 42

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)

• Equal-width (distance) partitioning:

– It 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.

January 2, 2026 Data Mining: Concepts and Techniques 43

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)
• Equal-width: Example:
– Given the data set (say 24, 21, 28, 8, 4, 26, 34, 21, 29, 15, 9, 25)
• Determine the number of bins N (say 3)
• Sort the data as 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
• Determine the range R = Max – Min = 30
• Divide the range into N equal width where the ith bin is [Xi-1,
Xi) where X0=Min and XN=Max and Xi = Xi-1 + R/N
(R/N=10)
• Hence X0= 4, X1 = 14, X2 = 24, and X3 = 34
• Therefore:
– Bin 1 = 4,8,9
– Bin 2 = 15, 21, 21
– Bin3 = 24, 25, 26, 28, 29, 34

January 2, 2026 Data Mining: Concepts and Techniques 44

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)
• Equal-width (distance) partitioning:
– The most straightforward approach
– But outliers may dominate presentation
– Skewed data is not handled well.

January 2, 2026 Data Mining: Concepts and Techniques 45

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)
• Equal-depth (frequency) partitioning:
– It divides the range into N intervals, each containing
approximately same number of samples
– Given the data set (say 24, 21, 28, 8, 4, 26, 34, 21, 29, 15, 9, 25)
• Determine the number of bins : N (say 3)
• Determine the number of data elements F(F=12)
• Sort the data as 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34
• Place F/N (12/3 = 4) element in order into the different bins
• Therefore:
– Bin 1 = 4,8,9 ,15
– Bin 2 = 21, 21,24, 25
– Bin3 = 26, 28, 29, 34

January 2, 2026 Data Mining: Concepts and Techniques 46

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)
• Equal-depth (frequency) partitioning:
– Good data scaling
– Managing categorical attributes can be tricky.

January 2, 2026 Data Mining: Concepts and Techniques 47

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)

Smoothing algorithm
• Three different bin smoothing techniques are most common
1. smooth by bin means,
2. smooth by bin median,
3. smooth by bin boundaries

January 2, 2026 Data Mining: Concepts and Techniques 48

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)
• Smoothing by bin means:
– Find the mean in each bin and replace all the element by the
bin mean
– For example: given the data set in bins as say:
- Bin 1: 4, 8, 9, 15
- Bin 2: 21, 21, 24, 25
- Bin 3: 26, 28, 29, 34
– The values will be smoothed as
• Bin 1: 9, 9, 9, 9
• Bin 2: 23, 23, 23, 23
• Bin 3: 29, 29, 29, 29

January 2, 2026 Data Mining: Concepts and Techniques 49

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)
• Smoothing by bin median:
– Find the median in each bin and replace all the element
by the bin median
– For example: given the data set in bins as say:
- Bin 1: 4, 8, 9, 15
- Bin 2: 21, 21, 24, 25
- Bin 3: 26, 28, 29, 34
– The resulting bin values become
• 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

January 2, 2026 Data Mining: Concepts and Techniques 50

 Data Cleaning: Handling Noisy Data by
Simple Discretization Methods (Binning)
• Smoothing by bin boundaries:
– Replace each element by the bin min or bin max
which ever is the nearest
– For example: given the data set in bins as say:
- Bin 1: 4, 8, 9, 15
- Bin 2: 21, 21, 24, 25
- Bin 3: 26, 28, 29, 34
– The resulting bin values become
• Bin 1: 4, 4, 4, 15
• Bin 2: 21, 21, 25, 25
• Bin 3: 26, 26, 26, 34

January 2, 2026 Data Mining: Concepts and Techniques 51

 Data Cleaning: Handling Noisy Data by
Cluster Analysis

•Detect and remove outliers

January 2, 2026 Data Mining: Concepts and Techniques 52

 Data Cleaning: Handling Noisy Data by Regression
• Smooth by fitting the data into regression functions
• Finding a fitting function for two a variable using its relation with
another variable(s):
• In this way, the missing value of the first variable can be predicted
from the fitting function
Y

Dependent variable y =F(x)=x+1

y1

x1 x
Independent variable

January 2, 2026 Data Mining: Concepts and Techniques 53

 Data Cleaning: Handling Noisy Data by Regression

• If the dependent variable is determined by one independent

variable we will have two dimensional representation of the fitting
function as shown above

• It can be extended to N dimensional case in which regression finds

multidimensional space so that value of one of the dimension can
be predicted from the rest N-1 values

January 2, 2026 Data Mining: Concepts and Techniques 54

 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

January 2, 2026 Data Mining: Concepts and Techniques 55

 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

January 2, 2026 Data Mining: Concepts and Techniques 56

 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

January 2, 2026 Data Mining: Concepts and Techniques 57

 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

January 2, 2026 Data Mining: Concepts and Techniques 58

 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

January 2, 2026 Data Mining: Concepts and Techniques 59

 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

January 2, 2026 Data Mining: Concepts and Techniques 60

 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)

January 2, 2026 Data Mining: Concepts and Techniques 61

 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

January 2, 2026 Data Mining: Concepts and Techniques 62

 Data Transformation: Normalization
• min-max normalization
– Perform a linear transformation on the original data into a
range 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

January 2, 2026 Data Mining: Concepts and Techniques 63

 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

January 2, 2026 Data Mining: Concepts and Techniques 64

 Data Transformation: Normalization
• Normalization by decimal scaling
– Normalizes by moving the decimal point of values of attribute A.
– The resulting value ranges from -1 to +1 exclusive

v
v' j Where j is the smallest integer such that Max(| v' |)<1
10

January 2, 2026 Data Mining: Concepts and Techniques 65

 Data Transformation: Normalization
• Normalization by decimal scaling
v
v' j Where j is the smallest integer such that Max(|v’|)<1
10
• For example:
• given the data set V= 132, -89, 756, -1560, 234, -345 and 1234
• The value of v’ becomes in the range from -1 to +1 if j=10,000
• In that case V’ = 0.0132, -0.0089, 0.0756, -0.156, 0.0234, -
0.0345, and 0.1234

January 2, 2026 Data Mining: Concepts and Techniques 66

Data Transformation: Attribute construction
• Attribute construction is the process of driving new attributes from
the existing attributes.

• Attribute construction is important to improve performance of data

mining as the derived attribute will have more discriminative power
than the base attributes

• Enable to discover missing information or information hidden

within the data set

• For example area can be derived from width and height which may
be more informative than any of the two or their combinations

January 2, 2026 Data Mining: Concepts and Techniques 67

 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

January 2, 2026 Data Mining: Concepts and Techniques 68

 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

January 2, 2026 Data Mining: Concepts and Techniques 69

 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

January 2, 2026 Data Mining: Concepts and Techniques 70

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

January 2, 2026 Data Mining: Concepts and Techniques 71

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

January 2, 2026 Data Mining: Concepts and Techniques 72

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

January 2, 2026 Data Mining: Concepts and Techniques 73

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

January 2, 2026 Data Mining: Concepts and Techniques 74

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

January 2, 2026 Data Mining: Concepts and Techniques 75

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}

January 2, 2026 Data Mining: Concepts and Techniques 76

Data reduction strategies: Dimensionality reduction

• Tries to compress the data using encoding scheme such as

– minimum length encoding,
• Huffman Encoding
– wavelet encoding,
– principal component analysis, etc

January 2, 2026 Data Mining: Concepts and Techniques 77

Data reduction strategies: Dimensionality reduction

compression
Compressed Original Data
Original Data Data Approximated
lossless

January 2, 2026 Data Mining: Concepts and Techniques 78

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

January 2, 2026 Data Mining: Concepts and Techniques 79

 Data reduction : Huffman coding for dimension
reduction
• Huffman coding is an entropy encoding algorithm used for lossless
data compression.
• The term refers to the use of a variable-length code table for
encoding a source symbol (such as a character in a file) where the
variable-length code table has been derived in a particular way
based on the estimated probability of occurrence for each possible
value of the source symbol.

80
 Data reduction : Huffman coding for dimension
reduction
• Given the data as:
―aaab babdbab abcb dbaeb ababd cbaab dbcaebf”

• This data will be analyzed and may be the followed character set
and their frequency will be generated
character frquency
a 12
b 15
c 3
d 4
e 2
f 1 This will require 43 byte in the normal
space 6 circumstance
Total 43

81
 Data reduction : Huffman coding for dimension
reduction
• One possible compression is as shown in the table called Huffman coding
charact frquenc possible Total bit
er y code required
b 15 0 15
1 12 10 24
space 6 110 18
d 4 1110 16
c 3 11110 15
e 2 111110 12
f 1 111111 6
Total 43 13.25

•The above can be represented by replacing each character with the specified
code which require a total of 106 bits (13.25 bytes)

•This reduce the total memory requirement to 30.8%

82
Data reduction : Wavelet Transforms for dimension
reduction
• Discrete wavelet transform (DWT): linear signal processing
• Compressed approximation: store only a small fraction of the
strongest of the wavelet coefficients
• Similar to discrete Fourier transform (DFT), but better lossy
compression, localized in space
• Link

January 2, 2026 Data Mining: Concepts and Techniques 83

 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

January 2, 2026 Data Mining: Concepts and Techniques 84

 Data Compression: Principal Component Analysis for
dimension reduction

X2

Y1

Y2

X1

Link

January 2, 2026 Data Mining: Concepts and Techniques 85

 Data Reduction: Numerosity Reduction
• Refers to replacing the data by alternatives representation which is
smaller in size

• This can be
– parametric or
– non-parametric methods

January 2, 2026 Data Mining: Concepts and Techniques 86

 Data Reduction: Numerosity Reduction

• Parametric methods
– Assume the data fits some model, estimate model parameters,
store only the parameters, and discard the data (except possible
outliers)

– Some examples include: Gaussian distribution, regression and

log-linear models

January 2, 2026 Data Mining: Concepts and Techniques 87

 Data Reduction: Numerosity Reduction

• Non-parametric methods
– Do not assume models

– Find alternate smaller representation and discard the data

– Major families: histograms, clustering, sampling

January 2, 2026 Data Mining: Concepts and Techniques 88

 Data Reduction: Numerosity Reduction using
Histograms
• A popular data reduction technique
40

• Divide data into buckets and store 35

average or count or sum for each
bucket 30
25
• Can be constructed optimally in
one dimension using dynamic 20
programming
15
10
5
0
January 2, 2026 10000and Techniques
Data Mining: Concepts 30000 50000 70000 90000
89
 Data Reduction: Numerosity Reduction using
Histograms
• There exist different types of histogram
– Equiwidth
– Equidepth
– V-Optimal (Variance-Optimal)
– MaxDiff

January 2, 2026 Data Mining: Concepts and Techniques 90

 Data Reduction: Numerosity Reduction using
Histograms

• Equiwidth histogram
– the width of each bucket is set to be the same (say in the interval from i to i+10
for the ith bucket)

• Equidepth Histogram
– each bucket will have variable width but the roughly same number of items in
them

January 2, 2026 Data Mining: Concepts and Techniques 91

 Data Reduction: Numerosity Reduction using
Histograms
• V-Optimal
– Given the number of buckets needs to be formed, there are many
alternative histograms for a given data set by setting the bin
boundaries
– Among the possible buckets V-Optimal histogram is the one with
the least variance
– Variance of histogram is a weighted sum of the original values
(bin boundaries) that each bucket represents
– The weight is equals to the number of items/values in the buckets

January 2, 2026 Data Mining: Concepts and Techniques 92

 Data Reduction: Numerosity Reduction using
Histograms
• V-Optimal (steps given number of histogram = N)
 For each possible N-1 bucket boundaries
1. Form the N buckets using the bucket boundaries
2. Add values of each bucket and multiply by the number of items the
bucket has
3. Add the values obtained for each buckets (call it sum_i) where i is unique
reference for the bucket boundaries
 Choose the bucket boundaries that results in the smallest sum_i
value

January 2, 2026 Data Mining: Concepts and Techniques 93

 Data Reduction: Numerosity Reduction using
Histograms
• MaxDiff
– Procedure:
• attribute values will be sorted first
• Attribute values difference will be computed
• Selected the largest N-1 attribute differences
• Those attribute value pairs that gives the N-1
attribute differences will be taken as bucket
boundaries

January 2, 2026 Data Mining: Concepts and Techniques 94

 Data Reduction: Numerosity Reduction using
Clustering
• Partition data set into clusters, and one can store cluster
representation only (cluster index)
• Can be very effective if data can be organized into distinct clusters
but not effective if data is ―smeared‖
• Can have hierarchical clustering and be stored in multi-dimensional
index tree structures like B+ tree
• There are many choices of clustering definitions and clustering
algorithms, further detailed will be given later

January 2, 2026 Data Mining: Concepts and Techniques 95

 Data Reduction: Numerosity Reduction using
sampling
• Sampling can be used as a data reduction technique because it
allows a large data set to be represented by a much smaller
sample (or subset) of the data.

• Different types of sampling exists

– Simple random sampling without replacement
– Simple random sampling with replacement
– Cluster sampling (do sampling on cluster, choose m clusters out of
the N)
– Stratified sampling (do simple random sampling on each cluster)

January 2, 2026 Data Mining: Concepts and Techniques 96

 Data Reduction: Numerosity Reduction using
sampling
• Simple random sampling may have very poor performance for
skewed dataset
• Stratified sampling need to approximate the percentage of each
class (or subpopulation of interest) in the overall database
– Appropriate for data which are skewed

January 2, 2026 Data Mining: Concepts and Techniques 97

 Data Reduction: Numerosity Reduction using
sampling

Raw Data
January 2, 2026 Data Mining: Concepts and Techniques 98
 Data Reduction: Numerosity Reduction using
sampling

Raw Data

Stratified Sampling Cluster Sampling

January 2, 2026 Data Mining: Concepts and Techniques 99

 Data Reduction: Numerosity Reduction

• Parametric methods
– Assume some model to fit into the data distribution
– Find alternate smaller representation and discard the data
(values of the parameters that define the model)

• Major families: Linear regression model, Multiple regression

model, Log-linear regression model

January 2, 2026 Data Mining: Concepts and Techniques 100

Data Reduction: Numerosity Reduction using
Regression and Log-Linear Models
• Linear regression:
– Data are modeled to fit a straight line

– Often uses the least-square error method to fit the line

– Y = mX + b (m and b are the parameters; both are scalar values)

• Multiple regression:
– allows a response variable Y to be modeled as a linear function of
multidimensional feature vector

– Y = mX + b (m and b are the parameters; both are vectors values)

January 2, 2026 Data Mining: Concepts and Techniques 101

Data Reduction: Numerosity Reduction using
Regression and Log-Linear Models
• Log-linear model:
– approximates discrete multidimensional probability distributions using log
function

January 2, 2026 Data Mining: Concepts and Techniques 102