Data Mining:

Concepts and Techniques

— Chapter 3 —

August 14, 2025 Data Mining: Concepts and Techniques 1

 Chapter 3: Data Preprocessing

 Why preprocess the data?

 Data cleaning
 Data integration and transformation
 Data reduction
 Discretization and concept hierarchy generation
 Summary

August 14, 2025 Data Mining: Concepts and Techniques 2

 Data Preprocessing

 Today's real-world databases are highly susceptible to

noise, missing, and inconsistent data due to their
typically huge size, often several gigabytes or
more
 How can the data be preprocessed in order to help
improve the quality of the data, and consequently, of
the mining results?
 How can the data be preprocessed so as to improve the
efficiency and ease of the mining process?

August 14, 2025 Data Mining: Concepts and Techniques 3

 There are a number of data preprocessing techniques.
 Data cleaning can be applied to remove noise and correct
inconsistencies in the data.
 Data integration merges data from multiple sources into
a coherent data store, such as a data warehouse or a
data cube.
 Data transformations, such as normalization, may be
applied.
 For example, normalization may improve the accuracy and

efficiency of mining algorithms involving distance

measurements.

August 14, 2025 Data Mining: Concepts and Techniques 4

  Data reduction can reduce the data size by
aggregating, eliminating redundant features, or
clustering, for instance.
 These data processing techniques, when applied
prior to mining, can substantially improve the
overall data mining results.

August 14, 2025 Data Mining: Concepts and Techniques 5

 Why Data Preprocessing?

 Data in the real world is dirty

 incomplete: lacking attribute values, lacking certain

attributes of interest, or containing only aggregate

data
 e.g., occupation=“”
 noisy: containing errors or outliers
 e.g., Salary=“-10”
 inconsistent: containing discrepancies in codes or
names
 e.g., Age=“42” Birthday=“03/07/1997”
 e.g., Was rating “1,2,3”, now rating “A, B, C”
 e.g., discrepancy between duplicate records

August 14, 2025 Data Mining: Concepts and Techniques 6

  Incomplete, noisy, and inconsistent data are
commonplace properties of large, real-world databases
and data warehouses.
 Incomplete data can occur for a number of reasons.
Attributes of interest may not always be available, such as
customer information for sales transaction data.
 Other data may not be included simply because it was not
considered important at the time of entry.
 Relevant data may not be recorded due to a
misunderstanding, or because of equipment malfunctions.

August 14, 2025 Data Mining: Concepts and Techniques 7

  Data that were inconsistent with other recorded data may
have been deleted.
 Furthermore, the recording of the history or modifications
to the data may have been overlooked.
 Missing data, particularly for tuples with missing values
for some attributes, may need to be inferred.

August 14, 2025 Data Mining: Concepts and Techniques 8

  Data can be noisy, having incorrect attribute values,
owing to the following.
 The data collection instruments used may be faulty.
 There may have been human or computer errors
occurring at data entry.
 Example Entering “750” instead of “75.0” for a patient’s
weight.
 Errors in data transmission can also occur.
 There may be technology limitations, such as limited
buffer size for coordinating synchronized data transfer
and consumption.
 Example Real-time video stream dropping frames
because of insufficient buffer space.
August 14, 2025 Data Mining: Concepts and Techniques 9
  Incorrect data may also result from inconsistencies in
naming conventions or data codes used.
 Duplicate tuples also require data cleaning.
 Solution:
 Drop the row with completely identical attribute values

August 14, 2025 Data Mining: Concepts and Techniques 10

 Why Is Data Preprocessing Important?

 No quality data, no quality mining results!

 Quality decisions must be based on quality data
 e.g., duplicate or missing data may cause incorrect or even
misleading statistics.
 Data warehouse needs consistent integration of quality
data
 Data extraction, cleaning, and transformation comprises
the majority of the work of building a data warehouse. —
Bill Inmon

August 14, 2025 Data Mining: Concepts and Techniques 11

 Major Tasks in Data Preprocessing

 Data cleaning
 Fill in missing values, smooth noisy data (use binning,
clustering, regression moving average) , identify or remove
outliers, and resolve inconsistencies
 Dirty data can cause confusion for the mining procedure.
 suppose that you would like to include data from multiple
sources in your analysis.
 This would involve integrating multiple databases, data cubes,
or files, i.e., data integration.
 Yet some attributes representing a given concept may have
different names in different databases, causing inconsistencies
and redundancies.

August 14, 2025 Data Mining: Concepts and Techniques 12

  For example, the attribute for customer identication may
be referred to as customer id is one data store, and
cust id in another.
 Naming inconsistencies may also occur for attribute
values. For example, the same first name could be
registered as “Bill" in one database, but “William" in
another, and “B." in the third.
 Furthermore, you suspect that some attributes may be
“derived" or inferred from others (e.g., annual revenue).

August 14, 2025 Data Mining: Concepts and Techniques 13

  Having a large amount of redundant data may slow
down or confuse the knowledge discovery process.
 Clearly, in addition to data cleaning, steps must be taken
to help avoid redundancies during data integration.
 Typically, data cleaning and data integration are
performed as a preprocessing step when preparing the
data for a data warehouse.
 Additional data cleaning may be performed to detect and
remove redundancies that may have resulted from data
integration.

August 14, 2025 Data Mining: Concepts and Techniques 14

  use a distance-based mining algorithm for your
analysis, such as neural networks, nearest neighbor
classifiers, or clustering.
 Such methods provide better results if the data to be
analyzed have been normalized, that is, scaled to a
specific range such as [0, 1.0].
 Your customer data, for example, contains the
attributes age, and annual salary.
 The annual salary attribute can take many more
values than age.

August 14, 2025 Data Mining: Concepts and Techniques 15

  Therefore, if the attributes are left un-normalized, then
distance measurements taken on annual salary will
generally outweigh distance measurements taken on
age..
 Data transformation operations, such as normalization
and aggregation, are additional data preprocessing
procedures that would contribute towards the success of the
mining process.

August 14, 2025 Data Mining: Concepts and Techniques 16

  Data reduction obtains a reduced representation of the data
set that is much smaller in volume, yet produces the same
(or almost the same) analytical results.
 There are a number of strategies for data reduction.
These include data aggregation (e.g., building a data
cube), dimension reduction (e.g., removing irrelevant
attributes through correlation analysis),
 data compression (e.g., using encoding schemes such as
minimum length encoding or wavelets),
 and numerosity reduction (e.g., “replacing" the data by
alternative, smaller representations such as clusters, or
parametric models).

August 14, 2025 Data Mining: Concepts and Techniques 17

  Data preprocessing is therefore an important step in the
knowledge discovery process, since quality decisions
must be based on quality data.
 Detecting data anomalies, rectifying them early, and
reducing the data to be analyzed can lead to huge pay-offs
for decision making.

August 14, 2025 Data Mining: Concepts and Techniques 18

 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

August 14, 2025 Data Mining: Concepts and Techniques 19

 Major Tasks in Data Preprocessing

 Data reduction
 Obtains reduced representation in volume but produces the
same or similar analytical results

 Data discretization
 Part of data reduction but with particular importance, especially
for numerical data.
 Example
 takes numeric ages and automatically converts them into
"Young", "Middle", or "Old" categories

August 14, 2025 Data Mining: Concepts and Techniques 20

 Forms of data preprocessing

August 14, 2025 Data Mining: Concepts and Techniques 21

 Data Cleaning

 Importance
 “Data cleaning is one of the three biggest problems
in data warehousing”—Ralph Kimball
 “Data cleaning is the number one problem in data
warehousing”—DCI survey
 Data cleaning tasks
 Fill in missing values
 Identify outliers and smooth out noisy data
 Correct inconsistent data
 Resolve redundancy caused by data integration

August 14, 2025 Data Mining: Concepts and Techniques 22

 How to Handle Missing Data?

 Ignore the tuple: usually done when class label is missing

(assuming the tasks in classification—not effective when the
percentage of missing values per attribute varies considerably.
 This method is not very effective, unless the tuple contains several
attributes with missing values.
 Fill in the missing value manually: tedious + infeasible?
 this approach is time-consuming and may not be feasible given a
large data set with many missing values.

August 14, 2025 Data Mining: Concepts and Techniques 23

 How to Handle Missing Data?

 Fill in it automatically with

 a global constant : e.g., “unknown”, a new class?!
 Replace all missing attribute values by the same constant, such
as a label like “Unknown",
 the attribute mean
For example, suppose that the average income of All Electronics
customers is $28,000. Use this value to replace the missing value
for income.

August 14, 2025 Data Mining: Concepts and Techniques 24

 How to Handle Missing Data?
 the attribute mean for all samples belonging to the same
class: smarter
For example, if classifying customers according to credit risk, replace
the missing value with the average income value for customers in the
same credit risk category as that of the given tuple.
 the most probable value: inference-based such as Bayesian
formula or decision tree

 For example, using the other customer attributes in your

data set, you may construct a decision tree to predict the
missing values for income.

August 14, 2025 Data Mining: Concepts and Techniques 25

 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

August 14, 2025 Data Mining: Concepts and Techniques 26

 How to Handle Noisy Data?

 Binning method:
 first sort data and partition into (equi-depth) bins

 then one can smooth by bin means, smooth by bin median,

smooth by bin boundaries, etc.

 Clustering
 detect and remove outliers. where similar values are

organized into groups or “clusters".

 Intuitively, values which fall outside of the set of clusters

may be considered outliers

August 14, 2025 Data Mining: Concepts and Techniques 27

 How to Handle Noisy Data?

 Combined computer and human inspection

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

with possible outliers).

 Regression
 smooth by fitting the data into regression functions

 Linear regression involves finding the “best" line to fit two

variables, so that one variable can be used to predict the

other.
 Multiple linear regression is an extension of linear

regression, where more than two variables are involved and

the data are fit to a multidimensional surface.

August 14, 2025 Data Mining: Concepts and Techniques 28

  Inconsistent data
There may be inconsistencies in the data recorded for some
transactions.
 Some data inconsistencies may be corrected manually using
external references.

August 14, 2025 Data Mining: Concepts and Techniques 29

 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.

 Example Age ranges from 10 to 70 and we want N=3
bins
 A=10, B=70, W = (70-10)/3= 20
 Bins:
 1. 10<=Age<30
 2. 30<=Age<50
 3. 50<=Age<=70

August 14, 2025 Data Mining: Concepts and Techniques 30

 Simple Discretization Methods: Binning

 .
 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.

August 14, 2025 Data Mining: Concepts and Techniques 31

 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 (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

August 14, 2025 Data Mining: Concepts and Techniques 32

 Cluster Analysis

August 14, 2025 Data Mining: Concepts and Techniques 33

 Regression

Y1

Y1’ y=x+1

X1 x

August 14, 2025 Data Mining: Concepts and Techniques 34

 Data Integration
 Data integration:
 combines data from multiple sources into a coherent store
as in data warehousing.
 These sources may include multiple databases, data cubes,
or flat files.
 Schema integration
 integrate metadata from different sources

 Entity identification problem: identify real world entities

from multiple data sources, e.g., [Link]-id  [Link]-#
 how can the data analyst or the computer be sure that
customer id in one database, and cust number in another
refer to the same entity?

August 14, 2025 Data Mining: Concepts and Techniques 35

 Data Integration
 Databases and data warehouses typically have metadata -
that is, data about the data.
 Such metadata can be used to help avoid errors in schema
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,
e.g., metric vs. British units
 For instance, a weight attribute may be stored in metric
units in one system, and British imperial units in another.
 The price of different hotels may involve not only
different currencies but also different services (such as free
breakfast) and taxes
August 14, 2025 Data Mining: Concepts and Techniques 36
 Handling Redundancy in Data Integration

 Redundant data occur often when 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
 Redundant data may be able to be detected by
correlational analysis
 Careful integration of the data from multiple sources may
help reduce/avoid redundancies and inconsistencies and
improve mining speed and quality

August 14, 2025 Data Mining: Concepts and Techniques 37

 

August 14, 2025 Data Mining: Concepts and Techniques 38

  If the resulting value of Equation (3.1) is greater than
1, then A and B are positively correlated. The higher
the value, the more each attribute implies the other.
 Hence, a high value may indicate that A (or B) may be
removed as a redundancy.
 If the resulting value is equal to 1, then A and B are
independent and there is no correlation between
them.
 If the resulting value is less than 1, then A and B are
negatively correlated. This means that each attribute
discourages the other.

August 14, 2025 Data Mining: Concepts and Techniques 39

 Data Transformation
 In data transformation, the data are transformed or
consolidated into forms appropriate for mining. Data
transformation can involve the following:
 Normalization, where the attribute data are scaled so
as to fall within a small specified range, such as -1.0 to
1.0, or 0 to 1.0.
 Smoothing, which works to remove the noise from
data. Such techniques include binning, clustering, and
regression.

August 14, 2025 Data Mining: Concepts and Techniques 40

 Data Transformation
 Aggregation, where summary or aggregation
operations are applied to the data.
 For example, the daily sales data may be aggregated
so as to compute monthly and annual total
amounts.
 This step is typically used in constructing a data cube for
analysis of the data at multiple granularities.

August 14, 2025 Data Mining: Concepts and Techniques 41

 Data Transformation
 Generalization of the data, where low level or
`primitive' (raw) data are replaced by higher level
concepts through the use of concept hierarchies.
 For example, categorical attributes, like street, can be
generalized to higher level concepts, like city or
county.
 Similarly, values for numeric attributes, like age, may
be mapped to higher level concepts, like young,
middle-aged, and senior.

August 14, 2025 Data Mining: Concepts and Techniques 42

 Data Transformation
 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

August 14, 2025 Data Mining: Concepts and Techniques 43

 Data Transformation: Normalization

 min-max normalization
v  minA
v'  (new _ maxA  new _ minA)  new _ minA
maxA  minA

Min-max normalization performs a linear transformation on

the original data.
Suppose that minA and maxA are the minimum and
maximum values of an attribute A.
Min-max normalization maps a value v of A to v’ in the range
[new_minA; new_maxA] by computing v’

August 14, 2025 Data Mining: Concepts and Techniques 44

 min-max normalization

August 14, 2025 Data Mining: Concepts and Techniques 45

 Data Transformation: Normalization

 z-score normalization

v  meanA
v' 
stand _ devA

This method of normalization is useful when the actual

minimum and maximum of attribute A are
unknown, or when there are outliers which
dominate the min-max normalizion v'

August 14, 2025 Data Mining: Concepts and Techniques 46

 Data Transformation: Normalization

August 14, 2025 Data Mining: Concepts and Techniques 47

 Data Transformation: Normalization

August 14, 2025 Data Mining: Concepts and Techniques 48

  Suppose that the recorded values of A range
from 986 to 917.
 The maximum absolute value of A is 986. To
normalize by decimal scaling, we therefore divide
each value by 1,000 (i.e., j = 3) so that 986
normalizes to 0.986

August 14, 2025 Data Mining: Concepts and Techniques 49

 Data Reduction Strategies

 A 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
 Data cube aggregation

 Dimensionality reduction—remove unimportant attributes

 Data Compression

 Numerosity reduction—fit data into models

 Discretization and concept hierarchy generation

August 14, 2025 Data Mining: Concepts and Techniques 50

 Data Cube Aggregation
 The lowest level of a data cube
where aggregation operations are applied to the data in the
construction of a data cube.
 Multiple levels of aggregation in data cubes
 Further reduce the size of data to deal with
 Reference appropriate levels
 Use the smallest representation which is enough to solve
the task
 Queries regarding aggregated information should be
answered using data cube, when possible
August 14, 2025 Data Mining: Concepts and Techniques 51
 Data Cube Aggregation

 Imagine that you have collected the data for your

analysis. These data consist of the All Electronics
sales per quarter, for the years 1997 to 1999.
You are, however, interested in the annual sales
(total per year), rather than the total per quarter.
Thus the data can be aggregated so that the
resulting data summarize the total sales per year
instead of per quarter

August 14, 2025 Data Mining: Concepts and Techniques 52

 Data Cube Aggregation

August 14, 2025 Data Mining: Concepts and Techniques 53

 Dimensionality Reduction
 Feature selection (i.e., attribute subset selection):
Data sets for analysis may contain hundreds of attributes,
many of which may be irrelevant to the mining task, or
redundant.
For example, if the task is to classify customers as to
whether or not they are likely to purchase a popular new CD
at All Electronics when notified of a sale, attributes such as
the customer's telephone number are likely to be
irrelevant, unlike attributes such as age or music
taste

August 14, 2025 Data Mining: Concepts and Techniques 54

 Dimensionality Reduction
 The goal of attribute subset selection is to find a
minimum set of attributes
 such that the resulting probability distribution of the
data classes is as close as possible to the original
distribution obtained using all attributes.
 It reduces the number of attributes appearing in the
discovered patterns, helping to make the patterns
easier to understant

August 14, 2025 Data Mining: Concepts and Techniques 55

 Dimensionality Reduction
 Heuristic methods (due to exponential # of choices):
 step-wise forward selection

 step-wise backward elimination

 combining forward selection and backward elimination

 decision-tree induction

August 14, 2025 Data Mining: Concepts and Techniques 56

 Dimensionality Reduction

August 14, 2025 Data Mining: Concepts and Techniques 57

 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}

August 14, 2025 Data Mining: Concepts and Techniques 58

  Decision tree induction: Decision tree algorithms,
such as ID3 and C4.5, were originally intended for
classification.
 Decision tree induction constructs a flow-chart-like
structure where each internal (non-leaf ) node
denotes a test on an attribute, each branch
corresponds to an outcome of the test, and each
external (leaf) node denotes a class prediction.
 At each node, the algorithm chooses the “best"
attribute to partition the data into individual classes.

August 14, 2025 Data Mining: Concepts and Techniques 59

 When decision tree induction is used for attribute
subset selection, a tree is constructed from the
given data.
All attributes that do not appear in the tree are
assumed to be irrelevant.
The set of attributes appearing in the tree form the
reduced subset of attributes

August 14, 2025 Data Mining: Concepts and Techniques 60

 How can we find a `good' subset of the original
attributes?"
 There are 2d possible subsets of d attributes.

 An exhaustive search for the optimal subset of attributes

can be prohibitively expensive, especially as d and the

number of data classes increase.
 Therefore, heuristic methods which explore a reduced

search space are commonly used for attribute subset

selection.
 These methods are typically greedy in that, while

searching through attribute space, they always make

what looks to be the best choice at the time.

August 14, 2025 Data Mining: Concepts and Techniques 61

 Data Compression

 In data compression, data encoding or

transformations are applied so as to obtain a
reduced or “compressed" representation of the
original data.
 If the original data can be reconstructed from the
compressed data without any loss of information, the
data compression technique used is called lossless.
 If, instead, we can reconstruct only an approximation of
the original data, then the data compression technique is
called lossy

August 14, 2025 Data Mining: Concepts and Techniques 62

 Data Compression

 String compression
 There are extensive theories and well-tuned algorithms

 Typically lossless

 But only limited manipulation is possible without

expansion
 Audio/video compression
 Typically lossy compression, with progressive

refinement
 Sometimes small fragments of signal can be

reconstructed without reconstructing the whole

August 14, 2025 Data Mining: Concepts and Techniques 63

 Data Compression

Original Data Compressed

Data
lossless

Original Data
Approximated

August 14, 2025 Data Mining: Concepts and Techniques 64

 Principal Component Analysis

 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

August 14, 2025 Data Mining: Concepts and Techniques 65

 Principal Component Analysis

 The basic procedure is as following

 1. The input data are normalized, so that each
attribute falls within the same range
 2. PCA computes N orthonormal vectors which
provide a basis for the normalized input data.
These are unit vectors that each point in a
direction perpendicular to the others.
 These vectors are referred to as the principal
components. The input data are a linear
combination of the principal component

August 14, 2025 Data Mining: Concepts and Techniques 66

 Principal Component Analysis

 3. The principal components are sorted in order

of decreasing “significance" or strength.
 The principal components essentially serve as a
new set of axes for the data, providing important
information about variance.
 That is, the sorted axes are such that the first
axis shows the most variance among the
data, the second axis shows the next highest
variance, and so on. This information helps
identify groups or patterns within the data

August 14, 2025 Data Mining: Concepts and Techniques 67

 Principal Component Analysis

 4. Since the components are sorted according to

decreasing order of “signficance", the size of the
data can be reduced by eliminating the
weaker components, i.e., those with low
variance.
 Using the strongest principal components, it
should be possible to reconstruct a good
approximation of the original data
 Multidimensional data of more than two
dimensions can be handled by reducing the
problem to two dimension
August 14, 2025 Data Mining: Concepts and Techniques 68
 Principal Component
Analysis
X2
X1, X2: original axes (attributes)
Y1,Y2: principal components
Y1
Y2
significant
component (high
variance)

X1

Order principal components by significance and eliminate weaker

August 14, 2025 Data Mining: Concepts and Techniques 70
 Numerosity Reduction

 Parametric methods
 Assume the data fits some model, estimate model
parameters, store only the parameters, and discard
the data (except possible outliers)
 Log-linear models: obtain value at a point in m-D
space as the product on appropriate marginal
subspaces ( discrete multidimensional probability
distribution)
 Non-parametric methods
 Do not assume models
 Major families: histograms, clustering, sampling
August 14, 2025 Data Mining: Concepts and Techniques 71
 Regression and Log-Linear Models
 Linear regression: Data are modeled to fit a straight line

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

 Regression and log-linear models can be used to approximate

the given data.

 For example, a random variable, Y (called a response

variable), can be modeled as a linear function of another
random variable, X (called a predictor variable), with the
equation Y = α + β X

August 14, 2025 Data Mining: Concepts and Techniques 72

 Regression and Log-Linear Models

Y=α+βX
where the variance of Y is assumed to be constant.
The coefficients and (called regression
coefficients) specify the Y -intercept and slope of
the line, respectively.
These coefficients can be solved for by the method
of least squares, which minimizes the error
between the actual line separating the data and the
estimate of the line.

August 14, 2025 Data Mining: Concepts and Techniques 73

 Regression and Log-Linear Models

 Multiple regression: allows a response variable Y to be

modeled as a linear function of multidimensional feature
vector

 Log-linear model: approximates discrete multidimensional

probability distributions

August 14, 2025 Data Mining: Concepts and Techniques 74

Regress Analysis and Log-Linear Models

 Linear regression: Y =  +  X
 Two parameters ,  and  specify the line and are to
be estimated by using the data at hand.
 using the least squares criterion to the known values
of Y1, Y2, …, X1, X2, ….

 Multiple regression: Y = b0 + b1 X1 + b2 X2.

 Many nonlinear functions can be transformed into the
above.
 Histograms

 A popular data reduction 40

technique 35
 Divide data into buckets 30
and store average (sum)
25
for each bucket
20
15
10
5
0

100000
10000

20000

30000

40000

50000

60000

70000

80000

90000
August 14, 2025 Data Mining: Concepts and Techniques 76
 Histograms

 Histograms use binning to approximate data

distributions and are a popular form of data
reduction.
 A histogram for an attribute A partitions the data
distribution of A into disjoint subsets, or buckets.
 The buckets are displayed on a horizontal axis,
while the height (and area) of a bucket typically
reflects the average frequency of the values
represented by the bucket.

August 14, 2025 Data Mining: Concepts and Techniques 77

 Histograms

 Example 3.4 The following data are a list of

prices of commonly sold items at All Electronics
(rounded to the nearest dollar).
 The numbers have been sorted. 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, 18, 18, 18, 18, 20, 20,
20, 20, 20, 20, 20, 21, 21, 21, 21, 25, 25, 25, 25,
25, 28, 28, 30, 30, 30.

August 14, 2025 Data Mining: Concepts and Techniques 78

August 14, 2025 Data Mining: Concepts and Techniques 79
 Histograms

August 14, 2025 Data Mining: Concepts and Techniques 80

 [Link]

August 14, 2025 Data Mining: Concepts and Techniques 81

 Clustering

 Partition data set into clusters, and one can store

cluster representation only
 Can be very effective if data is clustered
 Can have hierarchical clustering and be stored in multi-
dimensional index tree structures
 There are many choices of clustering definitions and
clustering algorithms, further detailed in Chapter 8

August 14, 2025 Data Mining: Concepts and Techniques 82

 Clustering

 Clustering techniques consider data tuples as objects.

 They partition the objects into groups or clusters, so that
objects within a cluster are “similar" to one another and
“dissimilar" to objects in other clusters.
 Similarity is commonly defined in terms of how “close" the
objects are in space, based on a distance function.
 The “quality" of a cluster may be represented by its
diameter, the maximum distance between any two
objects in the cluster.
August 14, 2025 Data Mining: Concepts and Techniques 83
August 14, 2025 Data Mining: Concepts and Techniques 84
 Cluster Analysis

Figure 3.9: A 2-D plot of customer data with respect to

customer locations in a city, showing three data clusters. Each
cluster centroid is marked with a “+".

August 14, 2025 Data Mining: Concepts and Techniques 85

 Clustering

• In data reduction, the cluster

representations of the data are used to
replace the actual data.
• The effectiveness of this technique depends on
the nature of the data.
• It is much more effective for data that can be
organized into distinct clusters.
• In database systems, multidimensional index
trees are primarily used for providing fast data
access.

August 14, 2025 Data Mining: Concepts and Techniques 86

 Clustering

• They can also be used for hierarchical data

reduction, providing a multiresolution clustering
of the data.
• Each parent node contains keys and pointers to
child nodes that, collectively, represent the
space represented by the parent node.
• Each leaf node contains pointers to the data
tuples they represent

August 14, 2025 Data Mining: Concepts and Techniques 87

 An index tree

• An index tree can therefore store aggregate and

detail data at varying levels of resolution or
abstraction.
• It provides a hierarchy of clusterings of the data
set, where each cluster has a label that holds
for the data contained in the cluster.
• If we consider each child of a parent node as a
bucket, then an index tree can be considered as
a hierarchical histogram.

August 14, 2025 Data Mining: Concepts and Techniques 88

 An index tree

• For example, consider the root of a B+-tree as

shown in Figure 3.10, with pointers to the data
keys 986, 3396, 5411, 8392, and 9544. Suppose
that the tree contains 10,000 tuples with keys
ranging from 1 to 9,999. The data in the tree
can be approximated by an equi-depth
histogram of 6 buckets for the key ranges 1 to
985, 986 to 3395, 3396 to 5410, 5411 to 8392,
8392 to 9543, and 9544 to 9999. Each bucket
contains roughly 10,000/6 items.

August 14, 2025 Data Mining: Concepts and Techniques 89

 Index tree

August 14, 2025 Data Mining: Concepts and Techniques 90

 Sampling

Sampling can be used as a data reduction

technique since it allows a large data set to be
represented by a much smaller random sample (or
subset) of the data. Suppose that a large data set,
D, contains N tuples. Let's have a look at some
possible samples for D.
1 Simple random sample without
replacement (SRSWOR) of size n: This is created
by drawing n of the N tuples from D (n<N) i.e., all
tuples are equally likely.

August 14, 2025 Data Mining: Concepts and Techniques 91

 Sampling

 Simple random sample with replacement

(SRSWR) of size n:
 This is similar to SRSWOR, except that each time
a tuple is drawn from D, it is recorded and then
replaced. That is, after a tuple is drawn, it is
placed back in D so that it may be drawn again.
 Cluster sample: If the tuples in D are grouped
into M mutually disjoint “clusters", then a SRS of
m clusters can be obtained, where m<M

August 14, 2025 Data Mining: Concepts and Techniques 92

 Sampling
 Stratified sample:
 If D is divided into mutually disjoint parts called
“strata", a stratified sample of D is generated by
obtaining a SRS at each stratum.
 This helps to ensure a representative sample,
especially when the data are skewed.
 For example, a stratified sample may be
obtained from customer data, where stratum is
created for each customer age group. In this
way, the age group having the smallest number
of customers will be sure to be represented.
August 14, 2025 Data Mining: Concepts and Techniques 93
 Sampling

 Choose a representative subset of the data

 Simple random sampling may have very poor

performance in the presence of skew

 Develop adaptive sampling methods
 Stratified sampling:

 Approximate the percentage of each class in

the overall database

 Used in conjunction with skewed data

August 14, 2025 Data Mining: Concepts and Techniques 94

 [Link]
[Link]

August 14, 2025 Data Mining: Concepts and Techniques 95

 Sampling

August 14, 2025 Data Mining: Concepts and Techniques 96

 Sampling

August 14, 2025 Data Mining: Concepts and Techniques 97

 Sampling

August 14, 2025 Data Mining: Concepts and Techniques 98

 Sampling

Raw Data
August 14, 2025 Data Mining: Concepts and Techniques 99
 Sampling

Raw Data Cluster/Stratified Sample

August 14, 2025 Data Mining: Concepts and Techniques 100

 Hierarchical Reduction

 Use multi-resolution structure with different degrees of

reduction
 Hierarchical clustering is often performed but tends to
define partitions of data sets rather than “clusters”
 Hierarchical aggregation
 An index tree hierarchically divides a data set into

partitions by value range of some attributes

 Each partition can be considered as a bucket

 Thus an index tree with aggregates stored at each

node is a hierarchical histogram

August 14, 2025 Data Mining: Concepts and Techniques 101

 Discretization and Concept hierachy

 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
 Concept hierarchies
 reduce the data by collecting and replacing low level
concepts (such as numeric values for the attribute
age) by higher level concepts (such as young, middle-
aged, or senior)

August 14, 2025 Data Mining: Concepts and Techniques 102

An example of a concept hierarchy for the attribute price is given
in Figure 3.12. More than one concept hierarchy can be defined
for the same attribute in order to accommodate the needs of the
various users.
August 14, 2025 Data Mining: Concepts and Techniques 103
 Discretization and Concept Hierarchy
Generation for Numeric Data

 Binning (see sections before)

 Histogram analysis (see sections before)

 Clustering analysis (see sections before)

 Entropy-based discretization

 Segmentation by natural partitioning

August 14, 2025 Data Mining: Concepts and Techniques 104

August 14, 2025 Data Mining: Concepts and Techniques 105
 Histogram analysis

 Histograms can also be used for discretization.

 For example, the most frequent price range is roughly
$300-$325.
 Partitioning rules can be used to define the ranges of
values.
 For instance, in an equi-width histogram, the values are
partitioned into equal sized partions or ranges

 (e.g., ($0-$100], ($100-$200], . . . , ($900-$1,000]).

August 14, 2025 Data Mining: Concepts and Techniques 106

 Histogram analysis

 The histogram analysis algorithm can be applied

recursively to each partition in order to automatically
generate a multilevel concept hierarchy, with the
procedure terminating once a pre-specfied number of
concept levels has been reached.
 A concept hierarchy for price, generated from the data of
Figure 3.13 is shown in Figure 3.12.

August 14, 2025 Data Mining: Concepts and Techniques 107

 Clustering analysis.

 A clustering algorithm can be applied to partition

data into clusters or groups.
 Each cluster forms a node of a concept hierarchy,
where all nodes are at the same conceptual level.
 Each cluster may be further decomposed into
several subclusters, forming a lower level of the
hierarchy.
 Clusters may also be grouped together in order
to form a higher conceptual level of the
hierarchy.

August 14, 2025 Data Mining: Concepts and Techniques 108

 Entropy-Based Discretization
 An information-based measure called “ entropy" can be
used to recursively partition the values of a numeric
attribute A, resulting in a hierarchical discretization.
 Such a discretization forms a numerical concept hierarchy
for the attribute.
 Given a set of data tuples, S, the basic method for
entropy-based discretization of A is as follows.
 Each value of A can be considered a potential interval
boundary or threshold T .
 For example, a value v of A can partition the samples in S
into two subsets satisfying the conditions A <v and A
>=v, respectively, thereby creating a binary discretization

August 14, 2025 Data Mining: Concepts and Techniques 109

 Entropy-Based Discretization

 Given S, the threshold value selected is the one that

maximizes the information gain resulting from the
subsequent partitioning. The information gain is:
| S1| |S 2|
E (S ,T )  Ent ( S1)  Ent ( S 2)
| S| | S|
 where S1 and S2 correspond to the samples in S
satisfying the conditions A < T and A>=T
 The entropy function Ent for a given set is calculated
based on the class distribution of the samples in the set.
For example, given m classes, the entropy of S1 is:

August 14, 2025 Data Mining: Concepts and Techniques 110

 Entropy-Based Discretization

Ent ( S )  E (T , S )  

August 14, 2025 Data Mining: Concepts and Techniques 111

 Entropy-Based Discretization

 Given a set of samples S, if S is partitioned into two

intervals S1 and S2 using boundary T, the entropy after
partitioning is E ( S , T )  | S1| Ent ( )  | S 2 | Ent ( )
| S| S1 | S| S2
 The boundary that minimizes the entropy function over all
possible boundaries is selected as a binary discretization.
 The process is recursively applied to partitions obtained
until some stopping criterion is met, e.g.,
Ent ( S )  E (T , S )  
 Experiments show that it may reduce data size and
improve classification accuracy

August 14, 2025 Data Mining: Concepts and Techniques 112

Example 1
ID 1 2 3 4 5 6 7 8 9
Age 21 22 24 25 27 27 27 35 41
Grade F F P F P P P P P
 Let Grade be the class attribute. Use entropy-based
discretization to divide the range of ages into different
discrete intervals. (22+24) / 2 =
23
 There are 6 possible boundaries. They are 21.5, 23, 24.5,
(21+22)
26, / 238.
31, and =
21.5
 Let us consider the boundary at T = 21.5.
Let S1 = {21}
Let S2 = {22, 24, 25, 27, 27, 27, 35, 41}
Example 1 (cont’)
ID 1 2 3 4 5 6 7 8 9
Age 21 22 24 25 27 27 27 35 41
Grade F F P F P P P P P

 The number of elements in S1 and S2 are:

|S1| = 1
|S2| = 8
 The entropy of S1 is
Ent ( S1 )   P (Grade  F)  log 2 P (Grade  F)  P (Grade  P)  log 2 P(Grade  P)
 (1)  log 2 (1)  (0)  log 2 (0)


 The entropy of S2 is
Ent ( S 2 )   P(Grade  F)  log 2 P(Grade  F)  P(Grade  P)  log 2 P(Grade  P)
 (2)  log 2 (2)  (6)  log 2 (6)

 Example 1 (cont’)

 Hence, the entropy after partitioning at T = 21.5

is
| S1 | | S2 |
E (S , T )  Ent ( S1 )  Ent ( S 2 )
|S| |S|
|1| |8|
 Ent ( S1 )  Ent ( S 2 )
|9| |9|
 ...
 Example 1 (cont’)
 The entropies after partitioning for all the boundaries are:
T = 21.5 = E(S,21.5)
T = 23 = E(S,23)
Now recursively apply entropy
.
discretization upon both
.
partitions
T = 38 = E(S,38)

Select the boundary with the smallest entropy

Suppose best is T = 23

ID 1 2 3 4 5 6 7 8 9
Age 21 22 24 25 27 27 27 35 41
Grade F F P F P P P P P
 Segmentation by Natural Partitioning

 Although binning, histogram analysis, clustering

and entropy-based discretization are useful in the
generation of numerical hierarchies,
 many users would like to see numerical ranges
partitioned into relatively uniform, easy-to-read
intervals that appear intuitive or “natural".
 For example, annual salaries broken into ranges
like [$50,000, $60,000) are often more desirable
than ranges like [$51263.98, $60872.34),
obtained by some sophisticated clustering analys

August 14, 2025 Data Mining: Concepts and Techniques 117

 Segmentation by Natural Partitioning

 A simply 3-4-5 rule can be used to segment numeric

data into relatively uniform, “natural” intervals.
 If an interval covers 3, 6, 7 or 9 distinct values at the
most significant digit, partition the range into 3 equi-
width intervals
 If it covers 2, 4, or 8 distinct values at the most
significant digit, partition the range into 4 intervals
 If it covers 1, 5, or 10 distinct values at the most
significant digit, partition the range into 5 intervals
August 14, 2025 Data Mining: Concepts and Techniques 118
 Example of 3-4-5 Rule
count

Step 1: -$351 -$159 profit $1,838 $4,700

Min Low (i.e, 5%-tile) High(i.e, 95%-0 tile) Max
Step 2: msd=1,000 Low=-$1,000 High=$2,000

(-$1,000 - $2,000)
Step 3:

(-$1,000 - 0) (0 -$ 1,000) ($1,000 - $2,000)

(-$4000 -$5,000)
Step 4:

($2,000 - $5, 000)

(-$400 - 0) (0 - $1,000) ($1,000 - $2, 000)
(0 -
($1,000 -
(-$400 - $200)
$1,200) ($2,000 -
-$300) $3,000)
($200 -
($1,200 -
$400)
(-$300 - $1,400)
($3,000 -
-$200)
($400 - ($1,400 - $4,000)
(-$200 - $600) $1,600) ($4,000 -
-$100) ($600 - ($1,600 - $5,000)
$800) ($800 - ($1,800 -
$1,800)
(-$100 - $1,000) $2,000)
0)
August 14, 2025 Data Mining: Concepts and Techniques 119
 Example 3.5

Suppose that profits at different branches of Al lElectronics

for the year 1997 cover a wide range, from $351,976.00 to
$4,700,896.50.
A user wishes to have a concept hierarchy for profit
automatically generated. For improved readability, we use
the notation (l - r] to represent the interval (l, r]. For
example, (-$1,000,000 - $0] denotes the range from
- $1,000,000 (exclusive) to $0 (inclusive).
Suppose that the data within the 5%-tile and 95%-tile are
between $159,876 and $1,838,761. The results of applying
the 3-4-5 rule are shown in Figure 3.14

August 14, 2025 Data Mining: Concepts and Techniques 120

Step 1: Based on the above information, the minimum
and maximum values are:
MIN = -$351, 976.00, and MAX = $4, 700, 896.50.
The low (5%-tile) and high (95%-tile) values to be
considered for the top or first level of segmentation are:
LOW = -$159, 876, and H IGH = $1, 838,761;
.Step 2: Given LOW and HIGH, the most significant
digit is at the million dollar digit position (i.e., msd =
1,000,000).
Rounding LOW down to the million dollar digit, we get
LOW’ = -$1, 000, 000; and rounding HIGH up to the
million dollar digit, we get H IGH’ = +$2, 000,000

August 14, 2025 Data Mining: Concepts and Techniques 121



August 14, 2025 Data Mining: Concepts and Techniques 122

 Since the first interval, (-$1, 000, 000 - $0] covers the
MIN value, i.e., LOW’ < MIN, we can adjust the left
boundary of this interval to make the interval smaller.
The most significant digit of MIN is the hundred
thousand digit position.
Rounding MIN down to this position,
we get MIN’ = -$400, 000.
Therefore, the first interval is redefined as
(-$400,000 -0)

August 14, 2025 Data Mining: Concepts and Techniques 123

 Since the last interval, ($1,000,000 -$2,000,000] does
not cover the MAX value, i.e., MAX > HIGH’, we need to
create a new interval to cover it. Rounding up MAX at
its most significant digit position, the new interval is
($2,000,000 - $5,000,000].
Hence, the top most level of the hierarchy contains four
partitions,
(-$400,000 -$0],
($0 -$1,000,000],
($1,000,000 - $2,000,000], and
($2,000,000 - $5,000,000 ]

August 14, 2025 Data Mining: Concepts and Techniques 124

August 14, 2025 Data Mining: Concepts and Techniques 125
 Concept Hierarchy Generation for
Categorical Data

 Specification of a partial ordering of attributes explicitly

at the schema level by users or experts
 street<city<state<country

 Specification of a portion of a hierarchy by explicit data

grouping
 {Urbana, Champaign, Chicago}<Illinois

 Specification of a set of attributes.

 System automatically generates partial ordering by
analysis of the number of distinct values
E.g., street < city <state < country
 Specification of only a partial set of attributes
 E.g., only street < city, not others

August 14, 2025 Data Mining: Concepts and Techniques 126

 Automatic Concept Hierarchy
Generation
 Some concept hierarchies can be automatically
generated based on the analysis of the number of
distinct values per attribute in the given data set
 The attribute with the most distinct values is placed
at the lowest level of the hierarchy
 Note: Exception—weekday, month, quarter, year

country 15 distinct values

province_or_ state 65 distinct values

city 3567 distinct values

street 674,339 distinct values

August 14, 2025 Data Mining: Concepts and Techniques 127
 Chapter 3: Data Preprocessing

 Why preprocess the data?

 Data cleaning
 Data integration and transformation
 Data reduction
 Discretization and concept hierarchy
generation
 Summary
August 14, 2025 Data Mining: Concepts and Techniques 128
 Summary

 Data preparation is a big issue for both warehousing

and mining
 Data preparation includes
 Data cleaning and data integration
 Data reduction and feature selection
 Discretization
 A lot a methods have been developed but still an active
area of research

August 14, 2025 Data Mining: Concepts and Techniques 129

 References

 E. Rahm and H. H. Do. Data Cleaning: Problems and Current Approaches. IEEE Bulletin of
the Technical Committee on Data Engineering. Vol.23, No.4
 D. P. Ballou and G. K. Tayi. Enhancing data quality in data warehouse environments.
Communications of ACM, 42:73-78, 1999.
 H.V. Jagadish et al., Special Issue on Data Reduction Techniques. Bulletin of the Technical
Committee on Data Engineering, 20(4), December 1997.
 A. Maydanchik, Challenges of Efficient Data Cleansing (DM Review - Data Quality resource
portal)
 D. Pyle. Data Preparation for Data Mining. Morgan Kaufmann, 1999.
 D. Quass. A Framework for research in Data Cleaning. (Draft 1999)
 V. Raman and J. Hellerstein. Potters Wheel: An Interactive Framework for Data Cleaning
and Transformation, VLDB’2001.
 T. Redman. Data Quality: Management and Technology. Bantam Books, New York, 1992.
 Y. Wand and R. Wang. Anchoring data quality dimensions ontological foundations.
Communications of ACM, 39:86-95, 1996.
 R. Wang, V. Storey, and C. Firth. A framework for analysis of data quality research. IEEE
Trans. Knowledge and Data Engineering, 7:623-640, 1995.
 [Link]
August 14, 2025 Data Mining: Concepts and Techniques 130
 [Link]/~hanj

Thank you !!!

August 14, 2025 Data Mining: Concepts and Techniques 131