UNIT –II

Data Pre-processing: Data Preprocessing: An Overview, Data Cleaning, Data Integration,

Data Reduction, Data Transformation and Data Discretization

Data preprocessing
Data preprocessing describes any type of processing performed on raw data to prepare it for
another processing procedure. Commonly used as a preliminary data mining practice, data
preprocessing transforms the data into a format that will be more easily and effectively
processed for the purpose of the user.

2.1 Why Data Preprocessing?

Data in the real world is dirty. It can be in incomplete, noisy and inconsistent from. These
data needs to be preprocessed in order to help improve the quality of the data, and quality of
the mining results.
 If no quality data , then no quality mining results. The quality decision is always
based on the quality data.
 If there is much irrelevant and redundant information present or noisy and unreliable
data, then knowledge discovery during the training phase is more difficult
Incomplete data: lacking attribute values, lacking certain attributes of interest, or containing
only aggregate data. e.g., occupation=“ ”.
Noisy data: containing errors or outliers data. e.g., Salary=“-10”
Inconsistent data: containing discrepancies in codes or names. e.g., Age=“42”
Birthday=“03/07/1997”
 Incomplete data may come from
 “Not applicable” data value when collected
 Different considerations between the time when the data was collected and
when it is analyzed.
 Human/hardware/software problems
 Noisy data (incorrect values) may come from
 Faulty data collection by instruments
 Human or computer error at data entry
 Errors in data transmission
 Inconsistent data may come from
 Different data sources
 Functional dependency violation (e.g., modify some linked data)

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

1
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

Forms of Data Preprocessing

2.2 Data Cleaning

Data cleaning routines attempt to fill in missing values, smooth out noise while identifying
outliers, and correct inconsistencies in the data.

Various methods for handling this problem

2.2.1 Missing Values

The various methods for handling the problem of missing values in data tuples include:
(a) Ignoring the tuple: This is usually done when the class label is missing (assuming the
mining task involves classification or description). This method is not very effective unless
the tuple contains several attributes with missing values. It is especially poor when the
percentage of missing values per attribute varies considerably.
(b) Manually filling in the missing value: In general, this approach is time-consuming and
may not be a reasonable task for large data sets with many missing values, especially when
the value to be filled in is not easily determined.
(c) Using a global constant to fill in the missing value: Replace all missing attribute values
by the same constant, such as a label like “Unknown,” or −∞. If missing values are replaced
by, say, “Unknown,” then the mining program may mistakenly think that they form an
interesting concept, since they all have a value in common — that of “Unknown.” Hence,
although this method is simple, it is not recommended.
(d) Using the attribute mean for quantitative (numeric) values or attribute mode for
categorical (nominal) values, for all samples belonging to the same class as the given
tuple: 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.

2
(e) Using the most probable value to fill in the missing value: This may be determined
with regression, inference-based tools using Bayesian formalism, or decision tree induction.
For example, using the other customer attributes in your data set, you may construct a
decision tree to predict the missing values for income

2.2.2 Noisy data:

Noise is a random error or variance in a measured variable. Data smoothing tech is used for
removing such noisy data.

Several Data smoothing techniques:

1 Binning methods: Binning methods smooth a sorted data value by consulting the
neighborhood", or values around it. The sorted values are distributed into a number of
'buckets', or bins. Because binning methods consult the neighborhood of values, they perform
local smoothing.
In this technique,
1. The data for first sorted
2. Then the sorted list partitioned into equi-depth of bins.
3. Then one can smooth by bin means, smooth by bin median, smooth by binboundaries, etc.
a. Smoothing by bin means: Each value in the bin is replaced by the mean value of
the bin.
b. Smoothing by bin medians: Each value in the bin is replaced by the bin median.
c. Smoothing by boundaries: The min and max values of a bin are identified as the
bin boundaries. Each bin value is replaced by the closest boundary value.

Example:- Smooth out the following prices 21, 8, 28, 4, 34, 21, 15, 25, 24.
Data for price are first sorted and then partitioned into equidepth bins of depth 3.
Sorted data for price (in dollars): 4, 8, 15, 21, 21, 24, 25, 28, 34

Partition into (equi-width) bins:

Bin 1: 4, 8, 15
Bin 2: 21, 21, 24
Bin 3: 25, 28, 34
Smoothing by bin means:
Bin 1: 9, 9, 9,
Bin 2: 22, 22, 22
Bin 3: 29, 29, 29
Smoothing by bin median:
Bin 1: 8, 8, 8
Bin 2: 21, 21, 21
Bin 3: 28, 28, 28
Smoothing by bin boundaries:
Bin 1: 4, 4, 15
Bin 2: 21, 21, 24
Bin 3: 25, 25, 34

2 Clustering: Outliers in the data may be detected by clustering, where similar values are
organized into groups, or ‘clusters’. Values that fall outside of the set of clusters may be
considered outliers.

3
3 Regression : smooth by fitting the data into regression functions.
 Linear regression involves finding the best of 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.

2.2.3 Inconsistent data:-

Data inconsistencies may be corrected manually using external references. For example,
errors made at data entry may be corrected by performing a paper trace. Knowledge
engineering tools may also be used to detect the violation of known data constraints.

2.3 Data Cleaning as a Process

Handling missing data & noisy data is not all about data cleaning,
but it is a big process.
1) First step in data cleaning is Discrepancy Detection
2) Second Step in Data Cleaning is Data Transformation

Discrepancies can be caused by several factors,

 including poorly designed data entry forms that have many optional fields, human
error in data entry,
 deliberate errors (e.g.,respondents not wanting to divulge information about
themselves), and
 data decay (e.g., outdated addresses).
 Discrepancies may also arise from inconsistent data representations
 and the inconsistent use of codes.
 Errors in instrumentation devices that record data, and system errors, are an other
source of discrepancies.
 Errors can also occur when the data are (inadequately) used for purposes other than
originally intended.

4
  There may also be inconsistencies due to data integration (e.g.,where a given attribute
can have different names in different databases).

Discrepancy Detection
a) Using Meta Data
 Discrepancy can be detected by using metadata. For example, what are the domain
and data type of each attribute? What are the acceptable values for each attribute?
What is the range of the length of values? Do all values fall within the expected
range? Are there any known dependencies between attributes? E.t.c

b) Using Field Overloading

 Eg. 20004 entered instead of 2004

c)Using Unique Rule

 A unique rule says that each value of the given attribute must be different from all
other values for that attribute.
d) Using Consecutive Rule
 A consecutive rule says that there can be no missing values between the lowest and
highest values for the attribute, and that all values must also be unique (e.g., as in
check numbers).
e) Using Null Rule
 A null rule specifies the use of blanks, question marks, special characters, or other
strings that may indicate the null condition (e.g., where a value for a given attribute is
not available)
f)Commercial tools to aid in discrepancy detection
 Data scrubbing tools use simple domain knowledge (e.g., knowledge of postal
addresses, and spell-checking) to detect errors and make corrections in the data. These
tools rely on parsing and fuzzy matching techniques when cleaning data from multiple
sources.
 Data auditing tools find discrepancies by analyzing the data to discover rules and
relationships, and detecting data that violate such conditions. They are variants of data
mining tools. For example, they may employ statistical analysis to find correlations,or
clustering to identify outliers.

2) Second Step in Data Cleaning is Data Transformation

 once we find discrepancies, we typically need to define and apply (a series of)
transformations to correct them. Commercial tools can assist in the data
transformation step.
 Data migration tools allow simple transformations to be specified, such as to replace
the string “gender” by “sex”.
 ETL (extraction/transformation/loading) tools allow users to specify transforms
through a graphical user interface (GUI). These tools typically support only a
restricted set of transforms so that, often, we may also choose to write custom scripts
for this step of the data cleaning process.

5
2.3 Data Integration
It combines data from multiple sources into a coherent store. There are number of issues to
consider during data integration.

Issues:
 Schema integration: refers integration of metadata from different sources.
 Entity identification problem: Identifying entity in one data source similar to entity
in another table. For example, customer_id in one db and customer_no in another db
refer to the same entity
 Detecting and resolving data value conflicts: Attribute values from different
sources can be different due to different representations, different scales. E.g. metric
vs. British units
 Redundancy: is another issue while performing data integration. Redundancy can
occur due to the following reasons:
 Object identification: The same attribute may have different names in different db
 Derived Data: one attribute may be derived from another attribute

Handling redundant data in data integration

1. Correlation analysis for Numeric Data
Some redundancy can be identified by correlation analysis. The correlation between two
variables A and B can be measured by

where n is the number of tuples,

ai and bi are the respective values of A and B in tuple i,
A and B are the respective mean values of A and B,
and A are B the respective standard deviations of A and B ,
and (aibi) is the sum of the AB cross-product (i.e., for each tuple, the value for A is
multiplied by the value for B in that tuple). Note that -1 ≤ rA,B ≤ 1.

 The result of the equation is > 0, then A and B are positively correlated, which means
the value of A increases as the values of B increases. The higher value may indicate
redundancy that may be removed.
 The result of the equation is = 0, then A and B are independent and there is no
correlation between them.
 If the resulting value is < 0, then A and B are negatively correlated where the values
of one attribute increase as the value of one attribute decrease which means each
attribute may discourages each other.
 rA,B also called Pearson’s product moment coefficient

[Link] of Numeric Data

In probability theory and statistics, correlation and covariance are two similar measures
for assessing howmuch two attributes change together. Consider two numeric attributes
A and B, and a set of n observations {(a1,b1), : : : , (an,bn)}. The mean values of A and B,
respectively, are also known as the expected values on A and B, that is,

6
[Link] Analysis for Nominal or Categorical Data:
 Applicable for data where values of each attribute are divided into different
categories.
 Suppose A has c distinct values, namely a1,a2, : : :ac .
 B has r distinct values, namely b1,b2, : : :br
 The data tuples described by A and B can be shown as a contingency table, with the
c values of A making up the columns and the r values of B making up the rows.
 For nominal data, a correlation relationship between two attributes, A and B, can be
discovered by a 2(chi-square) test (using the below formula)

7
  Eg3.1. Consider a sample population of 1500 people who are surveyed to see if they
Play Chess or not and if they Like Science Fiction books are not.
 The counts given within parenthesis are expected frequency and the remaining one is
the observed frequency.
 For Example the Expected frequency for the cell (Play Chess, Like Science Fiction)
is:
= (Count (Play Chess) * Count (Like Science Fiction)) / Total sample population
= (300 * 450) / 1500 = 90

2.4 Data Reduction techniques

These techniques can be applied to obtain a reduced representation of the data set that is
much smaller in volume, yet closely maintains the integrity of the original data.
Data Reduction Strategies
Data reduction strategies include dimensionality reduction, numerosity reduction, and
data compression.

2.4.1 Dimensionality reduction is the process of reducing the number of randomvariables

or attributes under consideration. Dimensionality reduction methods include wavelet
transforms and principal components analysis , Attribute subset selection
Wavelet Transformation is a form of data compression well suited for image compression.
The discrete wavelet transform (DWT) is a linear signal processing technique that, when
applied to a data vector D, transforms it to a numerically different vector, D0, of wavelet
coefficients.
“How can this technique be useful for data reduction if the wavelet transformed data are
of the same length as the original data?” The usefulness lies in the fact that the wavelet
transformed data can be truncated. A compressed approximation of the data can be

8
retained by storing only a small fraction of the strongest of the wavelet coefficients.
 The DWT is closely related to the discrete Fourier transform(DFT), a signal
processing technique involving sines and cosines. In general, however, the DWT
achieves better lossy compression. That is, if the same number of coefficients is
retained for a DWT and a DFT of a given data vector, the DWT version will provide a
more accurate approximation of the original data. Hence, for an equivalent
approximation, the DWT requires less space than the DFT. Unlike the DFT, wavelets
are quite localized in space, contributing to the conservation of local detail.
 The general procedure for applying a discrete wavelet transform uses a hierarchical
pyramid algorithm that halves the data at each iteration, resulting in fast
computational speed.
 The method is as follows:

1. The length, L, of the input data vector must be an integer power of 2. This condition can be
met by padding the data vector with zeros as necessary (L ≥ n).
2. Each transform involves applying two functions. The first applies some data smoothing,
such as a sum or weighted average. The second performs a weighted difference, which acts to
bring out the detailed features of the data.
3. The two functions are applied to pairs of data points in X, that is, to all pairs of
measurements (x2i , x2i+1). This results in two sets of data of length L=2. In general, these
represent a smoothed or low-frequency version of the input data and the high frequency
content of it, respectively.
4. The two functions are recursively applied to the sets of data obtained in the previous loop,
until the resulting data sets obtained are of length 2.
5. Selected values from the data sets obtained in the above iterations are designated the
wavelet coefficients of the transformed data.

Haar2 and Daubechie4

are two popular wavelet
transforms.

Principal Component Analysis (PCA)

-also called as Karhunen-Loeve (K-L) method Procedure
Suppose that the data to be reduced consist of tuples or data vectors described by n attributes
or dimensions. Principal components analysis, or PCA (also called the Karhunen-Loeve, or
K-L, method), searches for k n-dimensional orthogonal vectors that can best be used to
represent the data, where k _ n. The original data are thus projected onto a much smaller
space, resulting in dimensionality reduction. Unlike attribute subset selection, which reduces
the attribute set size by retaining a subset of the initial set of attributes, PCA “combines” the
essence of attributes by creating an alternative, smaller set of variables. The initial data can
then be projected onto this smaller set. PCA often reveals relationships that were not
previously suspected and thereby allows interpretations that would not ordinarily result.
The basic procedure is as follows:

9
1. The input data are normalized, so that each attribute falls within the same range. This step
helps ensure that attributes with large domains will not dominate attributes with smaller
domains.
2. PCA computes k orthonormal vectors that 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 components.
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. For
example, Figure shows the first two principal components, Y1 and Y2, for the given set of
data originally mapped to the axes X1 and X2. This information helps identify groups or
patterns within the data.
4. Because the components are sorted according to decreasing order of “significance,” the
size of the data can be reduced by eliminating the weaker components, that is, those with low
variance. Using the strongest principal components, it should be possible to reconstruct a
good approximation of the original data.

Attribute sub selection / Feature selection

 Feature selection is a must for any data mining product. That is because, when you
build a data mining model, the dataset frequently contains more information than is
needed to build the model.
 For example, a dataset may contain 500 columns that describe characteristics of
customers, but perhaps only 50 of those columns are used to build a particular model.
 If you keep the unneeded columns while building the model, more CPU and memory
are required during the training process, and more storage space is required for the
completed model.
 select a minimum set of features such that the probability distribution of different
classes given the values for those features is as close as possible to the original
distribution given the values of all features

Basic heuristic methods of attribute subset selection include the following techniques, some
of which are illustrated below:

10
 1. Step-wise forward selection: The procedure starts with an empty set of attributes.
The best of the original attributes is determined and added to the set. At each
subsequent iteration or step, the best of the remaining original attributes is added to
the set.

2. Step-wise backward elimination: The procedure starts with the full set of attributes.
At each step, it removes the worst attribute remaining in the set

3. Combination forward selection and backward elimination: The step-wise forward

selection and backward elimination methods can be combined, where at each step one
selects the best attribute and removes the worst from among the remaining attributes.

4. Decision tree induction: 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. 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.

2.4.2 Numerosity reduction techniques replace the original data volume by alternative,
smaller forms of data representation. These techniques may be parametric or nonparametric.

For parametric methods, a model is used to estimate the data, so that typically only the data
parameters need to be stored, instead of the actual data. (Outliers may also be stored.)
Regression and log-linear models are examples.

11
Nonparametric methods for storing reduced representations of the data include histograms
clustering , sampling , and data cube aggregation .

Parametric: Assume the data fits some model, then estimate model parameters, and store
only the parameters, instead of actual data.
Regression and Log-Linear Models:
Linear Regression data are modeled to fit in a straight line.
 That is data can be modeled to the mathematical equation:
Y = α + β X, where α, β are coefficients
 Where X is called the “Response Variable” and Y is called “Predictor Variable”.
 Alpha and beta are called the regression coefficients.
 Alpha is the Y-intercept and Beta is the Slope of the equation.
 These regression coefficients can be solved by using “method of least squares”.
Multiple Regression
 Extension of linear regression
 Response variable Y is modeled as a multidimensional vector.
Log-Linear Models:
Log-linear models approximate discrete multidimensional probability distributions.
Given a set of tuples in n dimensions (e.g., described by n attributes), we can consider each
tuple as a point in an n-dimensional space. Log-linear models can be used to estimate the
probability of each point in a multidimensional space for a set of discretized attributes, based
on a smaller subset of dimensional combinations. This allows a higher-dimensional data
space to be constructed from lower-dimensional spaces.

Non parametric: In which histogram, clustering ,sampling and data cube aggregation is used
to store reduced form of data.

Histogram
 Divide data into buckets and store average (sum) for each bucket
 A bucket represents an attribute-value/frequency pair
 It can be constructed optimally in one dimension using dynamic programming
 It divides up the range of possible values in a data set into classes or groups.
 For each group, a rectangle (bucket) is constructed with a base length equal to the
range of values in that specific group, and an area proportional to the number of
observations falling into that group.
 The buckets are displayed in a horizontal axis while height of a bucket represents the
average frequency of the values.

12
Example:
The following data are a list of prices of commonly sold items. 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.
Draw histogram plot for price where each bucket should have equi-width of 10

The buckets can be determined based on the following partitioning rules, including the
following.
1. Equi-width: histogram with bars having the same width
2. Equi-depth or equi-frequency: histogram with bars having the same height
3. V-Optimal: histogram with least variance (count b * value b)
4. MaxDiff: bucket boundaries defined by user specified threshold
V-Optimal and MaxDiff histograms tend to be the most accurate and practical. Histograms
are highly effective at approximating both sparse and dense data, as well as highly skewed,
and uniform data.

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

Quality of clusters measured by their diameter (max distance between any two objects in the
cluster) or centroid distance (avg. distance of each cluster object from its centroid)

13
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), where the probably of drawing any tuple in D is
1=N, i.e., all tuples are equally likely.
2. 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.
3. 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. For example, tuples in a database are
usually retrieved a page at a time, so that each page can be considered a cluster. A reduced
data representation can be obtained by applying, say, SRSWOR to the pages, resulting in a
cluster sample of the tuples.
4. 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.

14
Data cube aggregation: Reduce the data to the concept level needed in the analysis. Queries
regarding aggregated information should be answered using data cube when possible. Data
cubes store multidimensional aggregated information. The following figure shows a data
cube for multidimensional analysis of sales data with respect to annual sales per item type for
each branch.

Each cells holds an aggregate data value, corresponding to the data point in multidimensional
space.
Data cubes provide fast access to pre computed, summarized data, thereby benefiting on-line
analytical processing as well as data mining.

The cube created at the lowest level of abstraction is referred to as the base cuboid. A cube
for the highest level of abstraction is the apex cuboid. The lowest level of a data cube (base
cuboid). Data cubes created for varying levels of abstraction are sometimes referred to as
cuboids, so that a “data cube" may instead refer to a lattice of cuboids. Each higher level of
abstraction further reduces the resulting data size.

The following database consists of sales per quarter for the years 2002-2004.

15
Suppose, the analyzer interested in the annual sales rather than sales per quarter, the above
data can be aggregated so that the resulting data summarizes the total sales per year instead of
per quarter. The resulting data in smaller in volume, without loss of information necessary for
the analysis task.

2.4.3 Data Compression

Data Compression, 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 information
loss, the data reduction is called lossless.
If, instead, we can reconstruct only an approximation of the original data, then the data
reduction is called lossy.
There are several lossless algorithms for string compression; however, they typically allow
only limited data manipulation.
Dimensionality reduction and numerosity reduction techniques can also be considered
forms of data compression.

2.5 Data Transformation and Data Discretization

This section presents methods of data transformation. In this preprocessing step, the data are
transformed or consolidated so that the resulting mining process may be more efficient, and
the patterns found may be easier to understand. Data discretization, a form of data
transformation, is also discussed
Data Transformation Strategies
Strategies for data transformation include the following:
1. Smoothing, which works to remove noise from the data. Techniques include binning,
regression, and clustering.
2. Attribute construction (or feature construction), where new attributes are constructed
and added from the given set of attributes to help the mining process.
3. 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 data analysis
at multiple abstraction levels.
4. Normalization, where the attribute data are scaled so as to fall within a smaller range,
such as -1.0 to 1.0, or 0.0 to 1.0.
5. Discretization, where the raw values of a numeric attribute (e.g., age) are replaced by
interval labels (e.g., 0–10, 11–20, etc.) or conceptual labels (e.g., youth, adult, senior).
The labels, in turn, can be recursively organized into higher-level concepts, resulting
in a concept hierarchy for the numeric attribute More than one concept hierarchy can be
defined for the same attribute to accommodate the needs of various users.
6. Concept hierarchy generation for nominal data, where attributes such as street can
be generalized to higher-level concepts, like city or country. Many hierarchies for nominal
attributes are implicit within the database schema and can be automatically defined at the
schema definition level.

16
Normalization
In which data are scaled to fall within a small, specified range, useful for classification
algorithms involving neural networks, distance measurements such as nearest neighbor
classification and clustering. There are 3 methods for data normalization. They are:
1) min-max normalization
2) z-score normalization
3) normalization by decimal scaling

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 v1
v - minA
1
v = ------------- (new_maxA – new_minA) + new_minA
maxA - minA
Example:- Suppose that the maximum and minimum values for the attribute income are
$98,000 and $12,000,respectively. Map the income to the range [0; 1]. By min-max
normalization, a value of $73,600 for income is transformed to
73,600 - 12,000
1
v = ----------------------- (1.0 - 0) + 0 = 0.716
98,000 – 12,000
In z-score normalization (or zero-mean normalization), the values for an attribute A are
normalized based on the mean and standard deviation of A. A value v of A is normalized to
v1 by computing
v–A
1
v = --------
σA
where A stands for mean of A and σ A for standard deviation. 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 normalization.

A variation of this z-score normalization replaces the standard deviation of above equation
by the mean absolute deviation of A. The mean absolute deviation of A, denoted sA, is

Thus, z-score normalization using the mean absolute deviation is

v–A
1
v = --------
SA

17
Example :- Suppose that the mean and standard deviation of the values for the attribute
income are $54,000 and $16,000, respectively. With z-score normalization, a value of
$73,600 for income is transformed to
73,600 – 54,000
1
v = --------------------- = 1.225
16,000

Normalization by decimal scaling normalizes by moving the decimal point of values of

attribute A. The number of decimal points moved depends on the maximum absolute value of
A. A value v of A is normalized to v1 by computing
v
1
v = -----
10j
where j is the smallest integer such that Max(|v1|) < 1.
Example:- 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, divide each value by 1,000 (i.e.,
j = 3) so that -986 normalizes to -0.986

Discretization:
 Discretization techniques can be used to 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.
Types of Data Discretization Techniques:
1. Supervised Discretization
a. Uses Class information of the data
2. Unsupervised Discretization
a. Does not uses Class information of the data
3. Top-down Discretization (splitting)
a. Identifies ‘Split-Points’ or ‘Cut-Points’ in data values
b. Splits attribute values into intervals at split-points
c. Repeats recursively on resulting intervals
d. Stops when specified number of intervals reached or some stop criteria is
reached.
4. Bottom-up Discretization (merging)
a. Divide the attribute values into intervals where each interval has a distinct
attribute value.
b. Merge two intervals based on some merging criteria
c. Repeats recursively on resulting intervals
d. Stops when specified number of intervals reached or some stop criteria is
reached.

Methods For Discretization.

These include:
1. Discretization by Binning
2. Discretization by Histogram Analysis,

18
3. Discretization by Cluster, Decision Tree, and Correlation Analyses.

Binning:
 Top-Down Discretization Technique Used
 Un Supervised Discretization Technique
 No Class Information Used
 User specified number of bins is used.
 Same technique as used for Smoothing and Numerosity reduction
 Data Discretized using Equi-Width or Equi-Depth method
 Replace each bin value by bin mean or bin median.
 Same technique applied recursively on resulting bins or partitions to generate Concept
Hierarchy
 Outliers are also fitted in separate bins or partitions or intervals
Histogram Analysis:
 Un Supervised Discretization; Top-Down Discretization Technique.
 Data Values split into buckets – Equi-Width or Equi-Frequency
 Repeats recursively on resulting buckets to generate multi-level Concept Hierarchies.
 Stops when user specified numbers of Concept Hierarchy Levels are generated.
Cluster Analysis:
 Uses Top-Down Discretization or Bottom-up Discretization
 Data values of an attribute are partitioned into clusters
 Uses the closeness of data values Produces high quality discretization results.
 Each cluster is a node in the concept hierarchy
 Each cluster further sub-divided into sub-clusters in case of Top-down approach to
create lower level clusters or concepts.
 Clusters are merged in Bottom-up approach to create higher level cluster or concepts.
Decision Tree
 Techniques to generate decision trees for classification can be applied to
discretization.
 Employ a top-down splitting approach
 Decision tree approaches to discretization are supervised, that is, they make use of
class label information
 Because decision tree–based discretization uses class information, it is more likely
that the interval boundaries (split-points) are defined to occur in places that may help
improve classification accuracy.

Correlation Analyses

 Measures of correlation can be used for discretization.

 ChiMerge is a 2-based discretization method
 ChiMerge, which employs a bottom-up approach by finding the best neighboring
intervals and then merging them to form larger intervals, recursively.
 ChiMerge is supervised in that it uses class information.
 ChiMerge proceeds as follows.
1. Initially, each distinct value of a numeric attribute A is considered to be one
interval.
2. 2 tests are performed for every pair of adjacent intervals.

19
 3. Adjacent intervals with the least 2values are merged together, because low
2 values for a pair indicate similar class distributions.
4. This merging process proceeds recursively until a predefined stopping
criterion is met.

Concept Hierarchy Generation for Nominal Data or Categorical Data:

 Nominal attributes have a finite (but possibly large) number of distinct values, with no
ordering among the values. Examples include geographic location, job category, and
item type.
 Manual definition of concept hierarchies can be a tedious and time-consuming task
for a user or a domain expert.
 Fortunately, many hierarchies are implicit within the database schema and can be
automatically defined at the schema definition level.
 The concept hierarchies can be used to transform the data into multiple levels of
granularity.
 Methods Used:

1. Specification of partial ordering of attributes explicitly at the schema level by users or

Experts.
2. Specification of a portion of a hierarchy by explicit data grouping.
3. Specification of the set of attributes that form the concept hierarchy, but not their
partial ordering.
4. Specification of only a partial set of attributes.

1. Specification of a partial set of attributes at the schema level by the users or domain
experts:
 A user or expert can easily define a concept hierarchy by specifying a partial or total
ordering of the attributes at the schema level
 Eg. Dimension ‘Location’ in a Data warehouse has attributes ‘Street’, ‘City’, ‘State’
& ‘Country’.
 Hierarchical definition of these attributes obtained by ordering these attributes as:
 Street < City < State < Country at the schema level itself by user or expert.

2. Specification of a portion of the hierarchy by explicit data grouping:

 Manual definition of concept hierarchy.
 In real time large databases it is unrealistic to define the concept hierarchy for the
entire database manually by value enumeration.
 But we can easily specify intermediate-level grouping of data - a small portion of
hierarchy.
 For Eg. Consider the attribute State where we can specify as below:
 {Chennai, Madurai, Trichy}  (Belongs to) Tamilnadu
 {Bangalore, Mysore, Mangalore}  (Belongs to) Karnataka

3. Specification of a set of attributes but not their partial ordering:

 User specifies set of attributes of the concept hierarchy; but omits to specify their
ordering
 Automatic concept hierarchy generation or attribute ordering can be done in such
cases.

20
  This is done using the rule that counts and uses the distinct values of each attribute
 The attribute that has the most distinct values is placed at the bottom of the hierarchy
 And the attribute that has the least distinct values is placed at the top of the hierarchy
 This heuristic rule applies for most cases but it fails of some.
 Users or experts can examine the concept hierarchy and COUNTRY
can perform manual adjustment.
 Eg. Concept Hierarchy for ‘Location’ dimension:
 Country (10); State (508), City (10,804), Street (1,234,567) STATE
 Street < City < State < Country
 In this case user need not modify the generated order / concept hierarchy.
 But this heuristic rule may fail for the ‘Time’ dimension.
 Distinct Years (100); Distinct Months (12); Distinct Days-of-week (7) CITY
 So in this case the attribute ordering or the concept hierarchy is:
 Year < Month < Days-of-week
 This is not correct.
STREET
4. Specification of only partial set of attributes:
 User may have vague idea of the concept hierarchy
 So they just specify only few attributes that form the concept hierarchy.
 Eg. User specifies just the Attributes Street and City.
 To get the complete concept hierarchy in this case we have to link these user specified
attributes with the data semantics specified by the domain experts.
 Users have the authority to modify this generated hierarchy.
 The domain expert may have defined that the attributes given below are semantically
linked
 Number, Street, City, State, Country.
 Now the newly generated concept hierarchy by linking the domain expert
specification and the users specification will be that:
 Number < Street < City < State < Country
 Here the user can inspect this concept hierarchy and can remove the unwanted
attribute ‘Number’ to generate the new Concept Hierarchy as below:
 Street < City < State < Country

21