Chapter 2 Data Preprocessing part3.ppt

Data Preprocessing

1. Data Preprocessing part3

2. Knowledge Discovery (KDD) Process
Data mining—core of
knowledge discovery
process
Data Cleaning
Data Integration
Databases
Data Warehouse
Task-relevant Data
Selection
Data Mining
Pattern Evaluation

3. Forms of Data Preprocessing

4. Data Transformation
Data transformation –the data are
transformed or consolidated into forms
appropriate for mining

5. Data Transformation
Data Transformation can involve the
following:
Smoothing: remove noise from the data,
including binning, regression and clustering
Aggregation
Generalization
Normalization
Attribute construction

6. Normalization
Min-max normalization
Z-score normalization
Decimal normalization

7. Min-max normalization
Min-max normalization: to [new_min
A,
new_max
A]
Ex. Let income range $12,000 to $98,000
normalized to [0.0, 1.0]. Then $73,000 is
mapped to AAA
AA
A
minnewminnewmaxnew
minmax
minv
v _)__(' 


 716.00)00.1(
000,12000,98
000,12600,73




8. Z-score normalization
Z-score normalization (μ: mean, σ:
standard deviation):
Ex. Let μ= 54,000, σ= 16,000. ThenA
Av
v


' 225.1
000,16
000,54600,73



9. Decimal normalization
Normalization by decimal scaling
Suppose the recorded value of A range from
-986 to 917, the max absolute value is 986,
so j = 3j
v
v
10
'
Where jis the smallest integer such that Max(|ν’|) < 1

10. Data Reduction
Why data reduction?
A database/data warehouse may store
terabytes of data
Complex data analysis/mining may take a
very long time to run on the complete data
set

11. Data Reduction
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

12. Data Reduction
Data reduction strategies
Data cube aggregation-aggregation operation are
applied
Attribute subset selection-irrelevant / weakly
relevant or redundant or dimension attribute is
removed
Dimensionality reduction —e.g.,remove
unimportant attributes
Numerosity reduction —e.g.,fit data into models
Discretization and concept hierarchy generation-
low to high

13. Data cube aggregation

14. Data cube aggregation
Data cube store multidimensional
aggregated information
Data cube the lowest level called as
base cuboid and highest level is apex
cuboid (represent the total sale for all
the year)

15. Attribute subset selection
Dimensionality reduction
Feature selection (i.e., attribute subset
selection):
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
reduce # of patterns in the patterns, easier to
understand

16. Attribute subset selection
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

17. Attribute subset selection
Dimensionality reduction
Initial attribute set:
{A1, A2, A3, A4, A5, A6}
A4 ?
A1? A6?
Class 1Class 2Class 1Class 2
>Reduced attribute set: {A1, A4, A6}

18. Numerosity reduction
Reduce data volume by choosing
alternative, smaller forms of data
representation
Major families: histograms, clustering,
sampling

19. Data Reduction Method:
Histograms0
5
10
15
20
25
30
35
40
10000 20000 30000 40000 50000 60000 70000 80000 90000
100000

20. Data Reduction Method:
Histograms
Divide data into buckets and store average (sum) for
each bucket
Partitioning rules:
Equal-width: equal bucket range
Equal-frequency (or equal-depth)
V-optimal: with the least histogram variance(weighted sum
of the original values that each bucket represents)
MaxDiff: set bucket boundary between each pair for pairs
have the β–1 largest differences

21. Data Reduction Method:
Clustering
Partition data set into clusters based on similarity,
and store cluster representation (e.g., centroid and
diameter) only
There are many choices of clustering definitions and
clustering algorithms
Cluster analysis will be studied in depth in Chapter 7

22. Data Reduction Method:
Sampling
Sampling: obtaining a small sample sto
represent the whole data set N
Simple random sample without replacement
Simple random sample with replacement
Cluster sample: if the tuples in D are grouped
into M mutually disjoint clusters, then an Simple
Random Sample can be obtained, where s < M
Stratified sample

23. Sampling: with or without
Replacement
Raw Data

24. Sampling: Cluster or Stratified
Sampling
Raw Data Cluster/Stratified Sample