Module 3 Data Pre-processing

• Introduction
• Types
Data Science • Data Cleaning
• Data Integration
OE (6CS372)
• Data Reduction
• Data Transformation and Data Discretization

Introduction Data Quality

• What is data pre-processing? • Accuracy- faulty instruments, human error
• Removing of noise, missing values, duplicate values, performing • Completeness- customer info. In transaction data missing
transformation and reduction for maintaining the quality of data. • Consistency- data not consistent with respect to requirement.
• Timeliness- E.g reports not submitted by sales rep. at end of month.
• What’s the goal or purpose of this activity? • Believability- how much data are trusted by user.
• To maintain quality of data. • Interpretability-how easy data are understood.
• If quality will compromise then result will be compromised.
Forms of data Pre-processing Data Pre-processing steps/tasks
• Data Cleaning- remove noise and correct inconsistencies in data.
• Data integration- merges data from multiple sources into a coherent
data store such as a data warehouse.
• Data reduction- can reduce data size by, for instance, aggregating,
eliminating redundant features, or clustering.
• Data transformations- (e.g., normalization) may be applied, where
data are scaled to fall within a smaller range like 0.0 to 1.0.

Data Cleaning Data Cleaning

• Clean the data by filling in missing values, smoothing noisy data, • a. Missing Values
identifying or removing outliers, and resolving inconsistencies. • 1. Ignore the tuple
• Naming inconsistencies may also occur for attribute values. • 2. Fill in the missing value manually
• E.g Customer_id in one data store and cust_id in another. • 3. Use a global constant to fill in the missing value
• Data cleaning and data integration are performed as a preprocessing • 4. Use a measure of central tendency for the attribute (e.g., the mean
step when preparing data for a data warehouse. or median) to fill in the missing value
• Additional data cleaning can be performed to detect and remove • 5. Use the attribute mean or median for all samples belonging to the
redundancies that may have resulted from data integration. same class as the given tuple
• Data cleaning (or data cleansing) routines attempt to fill in missing • 6. Use the most probable value to fill in the missing value
values, smooth out noise while identifying outliers, and correct
inconsistencies in the data.
Data Cleaning
Binning methods for data smoothing.
• b. Noisy data
• Noise is a random error or variance in a measured variable. Noise can
be removed using smoothing techniques.
• Data smoothing techniques
• 1. Binning:
• Binning methods smooth a sorted data value by consulting its
“neighborhood,” that is, the 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 smoothing by bin means, each value in a bin is replaced by the

mean value of the bin. For example, the mean of the values 4, 8, and Data Smoothing methods
15 in Bin 1 is 9. Therefore, each original value in this bin is replaced by
the value 9.
• 2. Regression: Data smoothing can also be done by regression, a
• Similarly, smoothing by bin medians can be employed, in which each technique that conforms data values to a function.
bin value is replaced by the bin median.
• Linear regression involves finding the “best” line to fit two attributes
• In smoothing by bin boundaries, the minimum and maximum values (or variables) so that one attribute can be used to predict the other.
in a given bin are identified as the bin boundaries. Each bin value is
then replaced by the closest boundary value. • Multiple linear regression is an extension of linear regression, where
more than two attributes are involved and the data are fit to a
• In general, the larger the width, the greater the effect of the multidimensional surface.
smoothing.
Data Smoothing methods Data Integration
• 3. Outlier analysis: Outliers may be detected by clustering, for • The merging of data from multiple data stores.
example, where similar values are organized into groups, or “clusters.” • Careful integration can help reduce and avoid redundancies and
Intuitively, values that fall outside of the set of clusters may be inconsistencies in the resulting dataset.
considered outliers.
• The semantic heterogeneity and structure of data pose great
challenges in data integration.
• How can we match schema and objects from different sources? This is
the essence of the entity identification problem.

Data Integration Data Integration

• 1. Entity Identification Problem • 1. Entity Identification Problem
• How can equivalent real-world entities from multiple data sources be • Structure of the data is also important- functional dependencies and
matched up? This is referred to as the entity identification problem. referential constraints.
• How can the data analyst or the computer be sure that customer id in • This is to ensure that any attribute functional dependencies and
referential constraints in the source system match those in the target
one database and cust number in another refer to the same attribute. system.
• Above problem can be solved using metadata (it include the name, • For example, in one system, a discount may be applied to the order,
meaning, data type, and range of values permitted for the attribute, whereas in another system it is applied to each individual line item
and null rules for handling blank, zero, or null values). within the order.
• Structure of the data is also important- functional dependencies and • If this is not caught before integration, items in the target system may
referential constraints. be improperly discounted.
• 2. Redundancy and Correlation Analysis
• An attribute (such as annual revenue, for instance) may be redundant
Correlation Test for Nominal Data (Chi-square)
if it can be “derived” from another attribute or set of attributes.
• Detected by correlation analysis. • Hypothesis: Objective, Null and Alternate hypothesis.
• Given two attributes, such analysis can measure how strongly one • Degree of freedom: Number of values that are free to vary. (N-1)
attribute implies the other, based on the available data. • Level of significance: Maximum probability of rejecting null
• For nominal data, we use the (chi-square) test. For numeric hypothesis.
attributes, we can use the correlation coefficient and covariance.

Correlation Test for Nominal Data (Chi-square) Correlation Test for Nominal Data (Chi-square)
• Suppose A has c distinct values a1,a2,---,ac. • The χ 2 value (also known as the Pearson χ 2 statistic) is computed as
• B has r distinct values b1,b2,----,br.
• Contingency table, with the c values of A making up the columns and
the r values of B making up the rows.
• Let (Ai ,Bj) denote the joint event that attribute A takes on value ai • where oij is the observed frequency (i.e., actual count) of the joint
and attribute B takes on value bj , that is, where (A = ai ,B = bj). event (Ai ,Bj) and eij is the expected frequency of (Ai ,Bj), which can
• Each and every possible (Ai ,Bj) joint event has its own cell (or slot) in be computed as
the table.
 • The chi-square statistic tests the hypothesis that A and B are
Correlation Test for Nominal Data (Chi-square) independent, that is, there is no correlation between them.
• The test is based on a significance level, with (r-1)*(c-1) degrees of
• where n is the number of data tuples, count(A = ai) is the number of freedom.
tuples having value ai for A, and count(B = bj) is the number of tuples
having value bj for B. • If the hypothesis can be rejected, then we say that A and B are
statistically correlated.
• The sum in Eq. is computed over all of the r × c cells.
• Note that the cells that contribute the most to the χ 2 value are those
for which the actual count is very different from that expected.

Example
• Correlation analysis of nominal attributes using 2. Suppose that a
group of 1500 people was surveyed. The gender of each person was
noted. Each person was polled as to whether his or her preferred type
of reading material was fiction or nonfiction. Thus, we have two
attributes, gender and preferred reading. The observed frequency (or
count) of each possible joint event is summarized in the contingency
table shown in Table 3.1, where the numbers in parentheses are the
expected frequencies. The expected frequencies are calculated based
on the data distribution for both attributes using Eq. (3.2). Using Eq.
(3.2), we can verify the expected frequencies for each cell.
 Correlation Coefficient for Numeric Data
• For numeric attributes, we can evaluate the correlation between two
attributes, A and B, by computing the correlation coefficient (also known
as Pearson’s product moment coefficient, named after its inventor, Karl
Pearson).

• Range from -1 to 1.
• -1 strongly –ve correlation
• +1 Strong +ve correlation
• 0- no relation

Covariance of Numeric Data

• For assessing how much two attributes change together. • For two attributes A and B that tend to change together, if A is larger
• Consider two numeric attributes than mean(A) (the expected value of A), then B is likely to be larger
than mean(B) (the expected value of B).Therefore, the covariance
• A and B, and a set of n observations {a1,b1, : : : , an,bn} between A and B is positive.
• On the other hand, if one of the attributes tends to be above its
expected value when the other attribute is below its expected value,
then the covariance of A and B is negative.
• If A and B are independent then covariance is 0.
 • 3. Tuple Duplication
• Data duplicated among all columns except any one attribute.
• 4. Data Value Conflict Detection and Resolution
• Unit representation – grades in one university and marks in another
university.

2. Attribute Subset Selection

Data Reduction
• It reduces the data set size by removing irrelevant or redundant
attributes (or dimensions).
• 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.
 • 1. Stepwise forward selection: The procedure starts with an empty set of
attributes as the reduced set. The best of the original attributes is
determined and added to the reduced set. At each subsequent iteration or
step, the best of the remaining original attributes is added to the set.
• 2. Stepwise 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 of forward selection and backward elimination: The
stepwise forward selection and backward elimination methods can be
combined so that, at each step, the procedure selects the best attribute
and removes the worst from among the remaining attributes.
• 4. Decision tree induction: Decision tree algorithms (e.g., ID3, C4.5, and
CART) were originally intended for classification. Decision tree induction
constructs a flowchart like structure where each internal (nonleaf) 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.

Example
1. Histograms (non-parametric)
• The following data are a list of AllElectronics prices for commonly sold
• Histograms use binning to approximate data distributions and are a • items (rounded to the nearest dollar). The numbers have been sorted:
popular form of data reduction. 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,
• A histogram for an attribute, A, partitions the data distribution of A 21, 25, 25, 25, 25, 25, 28, 28, 30, 30, 30.
into disjoint subsets, referred to as buckets or bins.
• If each bucket represents only a single attribute–value/frequency pair,
the buckets are called singleton buckets.
• Often, buckets instead represent continuous ranges for the given
attribute.
 [Link]
• “How are the buckets determined and the attribute values • They partition the objects into groups, or clusters, so that objects
partitioned?” There are several partitioning rules, including the within a cluster are “similar” to one another and “dissimilar” to
following: objects in other clusters.
• Equal-width: In an equal-width histogram, the width of each bucket • The “quality” of a cluster may be represented by its diameter, the
range is uniform (e.g., the width of $10 for the buckets). maximum distance between any two objects in the cluster.
• Equal-frequency (or equal-depth): In an equal-frequency histogram, • Centroid distance is an alternative measure of cluster quality and is
the buckets are created so that, roughly, the frequency of each bucket defined as the average distance of each cluster object from the
is constant (i.e., each bucket contains roughly the same number of cluster centroid.
contiguous data samples).

3. Sampling • Cluster sample: If the tuples in D are grouped into M mutually disjoint
“clusters,” then an SRS of s clusters can be obtained, where s < 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.
Other clustering criteria conveying rich semantics can also be
explored. For example, in a spatial database, we may choose to define
clusters geographically based on how closely different areas are
located.
• Stratified sample: If D is divided into mutually disjoint parts called
strata, a stratified sample of D is generated by obtaining an SRS at Data Transformation and Data Discretization
each stratum. This helps ensure a representative sample, especially
when the data are skewed. • In data transformation, the data are transformed or consolidated into
• For example, a stratified sample may be obtained from customer forms appropriate for mining.
data, where a stratum is created for each customer age group. In this • 1. Normalization, where the attribute data are scaled so as to fall
way, the age group having the smallest number of customers will be within a smaller range,
sure to be represented. such as -1.0 to 1.0, or 0.0 to 1.0.

1. Data Transformation by Normalization

• To avoid dependence on the choice of measurement units, the data
should be normalized or standardized.
• Normalizing the data attempts to give all attributes an equal weight. • In z-score normalization (or zero-mean normalization), the values for
an attribute, A, are normalized based on the mean (i.e., average) and
• Min-max normalization performs a linear transformation on the standard deviation of A.
original data.
• A value, vi , of A is normalized to vi’ by computing
• Suppose that minA and maxA are the minimum and maximum values
of an attribute, A.
• Min-max normalization maps a value, vi , of A to vi’ in the range
[new_minA,new_maxA] by computing
 Data Discretization
• Discretization, where the raw values of a numeric attribute (e.g., age)
• Normalization by decimal scaling normalizes by moving the decimal are replaced by interval labels (e.g., 0–10, 11–20, etc.) or conceptual
point of values of attribute A. The number of decimal points moved labels (e.g., youth, adult, senior).
depends on the maximum absolute value of A. • The labels, in turn, can be recursively organized into higher-level
• A value, vi , of A is normalized to vi’ by computing concepts, resulting in a concept hierarchy for the numeric attribute.
• Concept hierarchy generation for nominal data, where attributes
such as street can be generalized to higher-level concepts, like city or
country.

• 2. Discretization by Binning
A concept hierarchy for the attribute price • 3. Discretization by Histogram Analysis
• 4. Discretization by Cluster, Decision Tree, and Correlation Analyses
• 5. Concept Hierarchy Generation for Nominal Data