Data Preprocessing

 Data Preprocessing: An Overview

 Data Quality
 Major Tasks in Data Preprocessing
 Data Cleaning
 Data Integration
 Data Reduction
 Data Transformation and Data Discretization
 Summary
1
 Data Quality: Why Preprocess the
Data?

 Measures for data quality: A multidimensional view

 Accuracy: correct or wrong, accurate or not
 Completeness: not recorded, unavailable, …
 Consistency: some modified but some not,
dangling, …
 Timeliness: timely update?
 Believability: how trustable the data are correct?
 Interpretability: how easily the data can be
understood?
2
 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 reduction
 Dimensionality reduction
 Numerosity reduction
 Data compression
 Data transformation and data discretization
 Normalization
 Concept hierarchy generation

3
 Data Preprocessing

 Data Preprocessing: An Overview

 Why ? Ans: Data Quality
 Major Tasks in Data Preprocessing
 Data Cleaning
 Data Integration
 Data Reduction
 Data Transformation and Data Discretization
 Summary
4
 Data Cleaning
 Data in the Real World Is Dirty: Lots of potentially incorrect
data, e.g., instrument faulty, human or computer error,
transmission error
 incomplete: lacking attribute values, lacking certain
attributes of interest, or containing only aggregate data

e.g., Occupation=“ ” (missing data)
 noisy: containing noise, errors, or outliers

e.g., Salary=“−10” (an error)
 inconsistent: containing discrepancies in codes or names,
e.g.,

Age=“42”, Birthday=“03/07/2010”

Was rating “1, 2, 3”, now rating “A, B, C”

discrepancy between duplicate records
 Intentional (e.g., disguised missing data)
5
 Incomplete (Missing) Data
 Data is not always available
 E.g., many tuples have no recorded value for
several attributes, such as customer income in
sales data
 Missing data may be due to
 equipment malfunction
 inconsistent with other recorded data and thus
deleted
 data not entered due to misunderstanding
 certain data may not be considered important
at the time of entry
 not register history or changes of the data
6
 How to Handle Missing
Data?
 Ignore the tuple: usually done when class label is
missing (when doing classification)—not effective
when the % of missing values per attribute varies
considerably
 Fill in the missing value manually: tedious +
infeasible?
 Fill in it automatically with
 a global constant : e.g., “unknown”, a new
class?!
 the attribute mean
 the attribute mean for all samples belonging to
the same class: smarter 7
 Noisy Data
 Noise: random error or variance in a measured
variable
 Incorrect attribute values may be due to
 faulty data collection instruments

 data entry problems

 data transmission problems

 technology limitation

 inconsistency in naming convention

 Other data problems which require data cleaning

 duplicate records

 incomplete data

 inconsistent data

8
 How to Handle Noisy Data?
 Binning
 first sort data and partition into (equal-

frequency) bins
 then one can smooth by bin means, smooth by

bin median, smooth by bin boundaries, etc.

 Regression
 smooth by fitting the data into regression

functions
 Clustering
 detect and remove outliers

 Combined computer and human inspection

 detect suspicious values and check by human

(e.g., deal with possible outliers)

9
 Data Cleaning as a Process
 Data discrepancy detection
 Use metadata (e.g., domain, range, dependency,

distribution)
 Check field overloading

 Check uniqueness rule, consecutive rule and null rule


Data scrubbing: use simple domain knowledge (e.g.,
postal code, spell-check) to detect errors and make
corrections

Data auditing: by analyzing data to discover rules and
relationship to detect violators (e.g., correlation and
clustering to find outliers)
 Data migration and integration
 Data migration tools: allow transformations to be specified

 ETL (Extraction/Transformation/Loading) tools: allow users

to specify transformations through a graphical user

interface

10
 Data Preprocessing

 Data Preprocessing: An Overview

 Data Quality
 Major Tasks in Data Preprocessing
 Data Cleaning
 Data Integration
 Data Reduction
 Data Transformation and Data Discretization
 Summary
11
 Data Integration
 Data integration:
 Combines data from multiple sources into a coherent store
 Schema integration: e.g., A.cust-id  B.cust-#
 Integrate metadata from different sources
 Entity identification problem:
 Identify real world entities from multiple data sources, e.g.,
Bill Clinton = William Clinton
 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
12
 Handling Redundancy in Data
Integration

 Redundant data occur often when integration of

multiple databases
 Object identification: The same attribute or
object may have different names in different
databases
 Derivable data: One attribute may be a
“derived” attribute in another table, e.g.,
annual revenue
 Redundant attributes may be able to be detected
by correlation analysis and covariance analysis
 Careful integration of the data from multiple
sources may help reduce/avoid redundancies and 13
 Data Preprocessing

 Data Preprocessing: An Overview

 Data Quality
 Major Tasks in Data Preprocessing
 Data Cleaning
 Data Integration
 Data Reduction
 Data Transformation and Data Discretization
 Summary

14
 Data Reduction Strategies
 Data reduction: Obtain a reduced representation of the data
set that is much smaller in volume but yet produces the same
(or almost the same) analytical results
 Why data reduction? — A database/data warehouse may store
terabytes of data. Complex data analysis may take a very
long time to run on the complete data set.

 Data reduction strategies

 Dimensionality reduction, e.g., remove unimportant

attributes

Feature subset selection, feature creation
 Numerosity reduction (some simply call it: Data Reduction)


Regression and Log-Linear Models

Histograms, clustering, sampling

Data cube aggregation
 Data compression

15
Data Reduction 1: Dimensionality
Reduction
 Curse of dimensionality
 When dimensionality increases, data becomes increasingly sparse
 Density and distance between points, which is critical to
clustering, outlier analysis, becomes less meaningful
 The possible combinations of subspaces will grow exponentially
 Dimensionality reduction
 Avoid the curse of dimensionality
 Help eliminate irrelevant features and reduce noise
 Reduce time and space required in data mining
 Allow easier visualization
 Dimensionality reduction techniques
 Wavelet transforms
 Principal Component Analysis
 Supervised and nonlinear techniques (e.g., feature selection)

16
 Attribute Creation (Feature
Generation)
 Create new attributes (features) that can capture
the important information in a data set more
effectively than the original ones
 Three general methodologies
 Attribute extraction


Domain-specific
 Mapping data to new space (see: data

reduction)

E.g., Fourier transformation, wavelet
transformation, manifold approaches (not
covered)
 Attribute construction


Combining features
 17
 Data Reduction 2: Numerosity
Reduction
 Reduce data volume by choosing alternative,
smaller forms of data representation

 Parametric methods Assume the data fits some

model, estimate model parameters, store only the
parameters, and discard the data (except
possible outliers)
 Non-parametric methods
 Do not assume models

 Major families: histograms, clustering,

sampling, …

18
 Histogram Analysis
 Divide data into buckets 40
and store average (sum) 35
for each bucket 30
 Partitioning rules: 25
 Equal-width: equal 20
bucket range
15
 Equal-frequency (or 10
equal-depth)
5
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
19
 Data Reduction 3: 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

 Time sequence is not audio
 Typically short and vary slowly with time

 Dimensionality and numerosity reduction may also

Data Compression

Original Data Compressed

Data
lossless

os sy
l
Original Data
Approximated

21
 Data Preprocessing

 Data Preprocessing: An Overview

 Data Quality
 Major Tasks in Data Preprocessing
 Data Cleaning
 Data Integration
 Data Reduction
 Data Transformation and Data Discretization
 Summary

22
 Data Transformation
 A function that maps the entire set of values of a given
attribute to a new set of replacement values s.t. each old
value can be identified with one of the new values
 Methods
 Smoothing: Remove noise from data
 Attribute/feature construction

New attributes constructed from the given ones
 Aggregation: Summarization, data cube construction
 Normalization: Scaled to fall within a smaller, specified
range

min-max normalization

z-score normalization

normalization by decimal scaling
23
 Normalization
 Min-max normalization:
v  minA
v'  (new _ maxA  new _ minA)  new _ minA
maxA  minA

 Z-score normalization (μ: mean, σ: standard deviation):

v  A
v' 
 A

 Normalization by decimal scaling

v
v'  j Where j is the smallest integer such that Max(|ν’|) < 1
10
24
25
 Discretization
 Discretization: Divide the range of a continuous attribute into
intervals
 Interval labels can then be used to replace actual data
values
 Reduce data size by discretization

 Typical methods: All the methods can be applied

recursively
 Binning
 Histogram analysis
 Clustering analysis
 Decision-tree analysis
26
 Simple Discretization: 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.
 The most straightforward, but outliers may dominate
presentation
 Skewed data is not handled well
 Equal-depth (frequency) partitioning
 Divides the range into N intervals, each containing
approximately same number of samples
 Good data scaling 27
 Concept Hierarchy Generation
for Nominal Data
 Specification of a partial/total ordering of attributes
explicitly at the schema level by users or experts
 street < city < state < country
 Specification of a hierarchy for a set of values by
explicit data grouping
 {Urbana, Champaign, Chicago} < Illinois
 Specification of only a partial set of attributes
 E.g., only street < city, not others
 Automatic generation of hierarchies (or attribute
levels) by the analysis of the number of distinct
values
 E.g., for a set of attributes: {street, city, state,
28
 Automatic Concept Hierarchy
Generation
 Some hierarchies can be automatically generated based on
the analysis of the number of distinct values per attribute in
the data set
 The attribute with the most distinct values is placed at

the lowest level of the hierarchy

 Exceptions, e.g., weekday, month, quarter, year

country 15 distinct values

province_or_ state 365 distinct values

city 3567 distinct values

street 674,339 distinct values

29
 Data Preprocessing

 Data Preprocessing: An Overview

 Data Quality
 Major Tasks in Data Preprocessing
 Data Cleaning
 Data Integration
 Data Reduction
 Data Transformation and Data Discretization
 Summary

30
 Summary
 Data quality: accuracy, completeness, consistency,
timeliness, believability, interpretability
 Data cleaning: e.g. missing/noisy values, outliers
 Data integration from multiple sources:
 Entity identification problem

 Remove redundancies

 Detect inconsistencies

 Data reduction
 Dimensionality reduction

 Numerosity reduction

 Data compression

 Data transformation and data discretization

 Normalization

 Concept hierarchy generation

31
 Binary Classifier
 A binary classifier produces output with two class values or
labels, such as Yes/No, 1/0, Positive/Negative for given input
data
 A dataset used for performance evaluation is called a test
dataset. Observed labels are used to compare with the
predicted labels for performance evaluation after
classification
 The predicted labels will be exactly the same if the
performance of a classifier is perfect, But it is uncommon to
be able to develop a perfect classifier

32
33
 Confusion Matrix
 A confusion matrix is formed from the four outcomes
produced as a result of binary classification
 True positive (TP): correct positive prediction
 False positive (FP): incorrect positive prediction
 True negative (TN): correct negative prediction
 False negative (FN): incorrect negative prediction

34
35
Accuracy

36
Precision

37
Recall (Probability of detection)

TPR – True positive Rate

38
39