程序代写代做代考 data mining case study algorithm Hive database data structure decision tree Bayesian COMP9318: Data Warehousing and Data Mining 1

COMP9318: Data Warehousing and Data Mining 1

COMP9318: Data Warehousing
and Data Mining

— L3: Data Preprocessing and Data Cleaning —

COMP9318: Data Warehousing and Data Mining 2

n  Why preprocess the data?

COMP9318: Data Warehousing and Data Mining 3

Why Data Preprocessing?

n  Data in the real world is dirty
n  incomplete: lacking attribute values, lacking certain

attributes of interest, or containing only aggregate
data

n  e.g., occupation=“”

n  noisy: containing errors or outliers
n  e.g., Salary=“-10”

n  inconsistent: containing discrepancies in codes or
names

n  e.g., Age=“42” Birthday=“03/07/1997”
n  e.g., Was rating “1,2,3”, now rating “A, B, C”
n  e.g., discrepancy between duplicate records

COMP9318: Data Warehousing and Data Mining 4

Why Is Data Dirty?

n  Incomplete data comes from
n  n/a data value when collected
n  different consideration between the time when the data was

collected and when it is analyzed.
n  human/hardware/software problems

n  Noisy data comes from the process of data
n  collection
n  entry
n  transmission

n  Inconsistent data comes from
n  Different data sources
n  Functional dependency violation

COMP9318: Data Warehousing and Data Mining 5

Why Is Data Preprocessing Important?

n  No quality data, no quality mining results!
n  Quality decisions must be based on quality data

n  e.g., duplicate or missing data may cause incorrect or even
misleading statistics.

n  Data warehouse needs consistent integration of quality
data

n  Data extraction, cleaning, and transformation comprises
the majority of the work of building a data warehouse. —
Bill Inmon

n  Also a critical step for data mining.

COMP9318: Data Warehousing and Data Mining 6

Major Tasks in Data Preprocessing

n  Data cleaning
n  Fill in missing values, smooth noisy data, identify or remove

outliers, and resolve inconsistencies

n  Data integration
n  Integration of multiple databases, data cubes, or files

n  Data transformation
n  Normalization and aggregation

n  Data reduction
n  Obtains reduced representation in volume but produces the

same or similar analytical results

n  Data discretization & Data Type Conversion

COMP9318: Data Warehousing and Data Mining 7

n  Data cleaning

COMP9318: Data Warehousing and Data Mining 8

Data Cleaning

n  Importance
n  “Data cleaning is one of the three biggest problems

in data warehousing”—Ralph Kimball
n  “Data cleaning is the number one problem in data

warehousing”—DCI survey

n  Data cleaning tasks

n  Fill in missing values

n  Identify outliers and smooth out noisy data

n  Correct inconsistent data

n  Resolve redundancy caused by data integration

9

Missing Data

n  Data is not always available

n  E.g., many tuples have no recorded value for several
attributes, such as customer income in sales data

n  Missing data may be due to

n  equipment malfunction

n  inconsistent with other recorded data and thus deleted

n  data not entered due to misunderstanding

n  certain data may not be considered important at the time of
entry

n  not register history or changes of the data

n  Missing data may need to be inferred.

n  Many algorithms need a value for all attributes

n  Tuples with missing values may have different true values

COMP9318: Data Warehousing and Data Mining 10

How to Handle Missing Data?

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

n  Fill in the missing value manually: tedious + infeasible?

n  Fill in it automatically with

n  a global constant : e.g., “unknown”, a new class?!

n  the attribute mean

n  the attribute mean for all samples belonging to the same class:

smarter

n  the most probable value: inference-based such as Bayesian

formula or decision tree

COMP9318: Data Warehousing and Data Mining 11

Noisy Data

n  Noise: random error or variance in a measured variable
n  Incorrect attribute values may due to

n  faulty data collection instruments
n  data entry problems
n  data transmission problems
n  technology limitation
n  inconsistency in naming convention

n  Other data problems which requires data cleaning
n  duplicate records
n  incomplete data
n  inconsistent data

COMP9318: Data Warehousing and Data Mining 12

How to Handle Noisy Data?

n  Binning method:
n  first sort data and partition into (equi-depth) bins
n  then one can smooth by bin means, smooth by bin

median, smooth by bin boundaries, etc.
n  Clustering

n  detect and remove outliers
n  Combined computer and human inspection

n  detect suspicious values and check by human (e.g.,
deal with possible outliers)

n  Regression
n  smooth by fitting the data into regression functions

To be
discussed in
discretization

13

Regression

X1

X2

X2 = 1.1X1 + 0.7

2

6

2.9

Suburb #Residents Usage Charge

Kingsford 2 1502 3047

Kensington 3 987 265.6

Maroubra 1 568 198.3

… … … …

COMP9318: Data Warehousing and Data Mining 14

n  Data integration and transformation

COMP9318: Data Warehousing and Data Mining 15

Data Integration

n  Data integration:
n  combines data from multiple sources into a coherent

store
n  Schema integration

n  integrate metadata from different sources
n  Entity identification problem: identify real world entities

from multiple data sources, e.g., A.cust-id ≡ B.cust-#
n  Detecting and resolving data value conflicts

n  for the same real world entity, attribute values from
different sources are different

n  possible reasons: different representations, different
scales, e.g., metric vs. British units

Example

n  Data source 1:
n  Book(bid, title, isbn)
n  Author(aid, fname, lname, birthdate)
n  Writes(bid, aid, order)

n  Data source 2:
n  Book(isbn, title, year, author1, author2, …,

author10)
n  Data source 3:

n  Author(name, bornInYear, description, book1,
book2, …, book5)

COMP9318: Data Warehousing and Data Mining 16

COMP9318: Data Warehousing and Data Mining 17

Handling Redundancy in Data Integration

n  Redundant data occur often when integration of multiple
databases

n  The same attribute may have different names in
different databases

n  One attribute may be a “derived” attribute in another
table, e.g., annual revenue

n  Redundant data may be able to be detected by
correlational analysis

n  Careful integration of the data from multiple sources may
help reduce/avoid redundancies and inconsistencies and
improve mining speed and quality

COMP9318: Data Warehousing and Data Mining 18

Data Transformation

n  Smoothing: remove noise from data
n  Aggregation: summarization, data cube construction

n  Generalization: concept hierarchy climbing
n  Normalization: scaled to fall within a small, specified

range
n  min-max normalization

n  z-score normalization
n  normalization by decimal scaling

n  Attribute/feature construction
n  New attributes constructed from the given ones

Also see other transformations later in the Clustering part

19

Data Transformation: Normalization

n  min-max normalization

n  z-score normalization

n  normalization by decimal scaling

min
‘ ( _ max _min ) _min
max min

A
A A A

A A

v
v new new new


= − +

j

v
v
10

‘= Where j is the smallest integer such that max( ‘ ) 1v < MinMaxScaler StandardScaler; sklearn uses biased variance estimate In scikit-learn, they are called Scaling. Normalization means converting vectors to unit vectors. COMP9318: Data Warehousing and Data Mining 20 n  Data reduction 21 Data Reduction Strategies n  Modern datasets may be very large n  Ratings of millions of customers on millions of items n  Many ML algorithms have high time and space complexities. n  Even learned models could be very large. n  E.g., learned word embeddings (300 dims) for 1M words è at least 1.2GB memory n  Data reduction n  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 n  Data reduction strategies n  Dimensionality reduction—remove unimportant attributes n  Data Compression n  Numerosity reduction—fit data into models n  Discretization and concept hierarchy generation High-dimensional Features n  It is common for many datasets to contain many features n  More is better at data capturing/creation n  561 features for human activity recognition using smartphone dataset: https://archive.ics.uci.edu/ml/datasets/Human +Activity+Recognition+Using+Smartphones n  GIST: 128 dimensional feature n  Mandated by some model n  A document is converted into a high-dimensional feature vector. #dims = |vocabulary| COMP9318: Data Warehousing and Data Mining 22 The Curse of Dimensionality n  Data in only one dimension is relatively packed n  Adding a dimension “stretches” the points across that dimension, making them further apart n  Adding more dimensions will make the points further apart—high dimensional data is extremely sparse è hard to learn n  Distance measure tends to become meaningless (graphs from Parsons et al. KDD Explorations 2004) High-dimensional space n  High-dimensional space is totally different from low- dimensional space (e.g., 3D) n  Many counter-intuitive facts about the high-dimensional space n  Two random vectors are almost surely orthogonal n  Random sample n points within a unit hypercube è most points are on a thin layer of the surface (annulus) 24 http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/ Goals n  Reduce dimensionality of the data, yet still maintain the meaningfulness of the data Dimensionality reduction n  Dataset X consisting of n points in a d- dimensional space n  Data point xi є Rd (d-dimensional real vector): xi = [xi1, xi2,…, xid]T n  Dimensionality reduction methods: n  Feature selection: choose a subset of the features n  Feature extraction: create new features by combining new ones COMP9318: Data Warehousing and Data Mining 27 Feature Selection n  Feature selection (i.e., attribute subset selection): n  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 n  reduce # of patterns in the patterns, easier to understand n  Heuristic methods (due to exponential # of choices): n  step-wise forward selection n  step-wise backward elimination n  combining forward selection and backward elimination n  decision-tree induction COMP9318: Data Warehousing and Data Mining 28 Heuristic Feature Selection Methods n  There are 2d possible sub-features of d features n  Several heuristic feature selection methods: n  Best single features under the feature independence assumption: choose by significance tests. n  Best step-wise feature selection: n  The best single-feature is picked first n  Then next best feature condition to the first, ... n  Step-wise feature elimination: n  Repeatedly eliminate the worst feature n  Best combined feature selection and elimination: n  Optimal branch and bound: n  Use feature elimination and backtracking 29 n  Original dataset: N d-dimensional vectors X = {xi}i=1..n n  Find k ≤ d orthogonal basis vectors that can be best used to represent data n  Preserves maximum “information” (i.e., variance under the orthogonal constraint) if projected onto these k basis vectors n  Reduced data set: Project each xi to the k basis vectors (aka., principal components) n  xi’ = [b1…bk]T xi n  X’ = [b1…bk]T X (en masse) n  Closed related to Singular Vector Decomposition (SVD) Principal Component Analysis (PCA) b1 b2 … bk x1 x2 x3 Projection 30 https://gist.github.com/anonymous/7d888663c6ec679ea65428715b99bfdd n  bT x: projection of x onto the basis vector b n  What about x’ = BT x, where B consists of another set of d-dim basis vectors? JL Lemma n  Johnson-Lindenstrauss Flattening Lemma ‘84: n  Given ε>0, and an integer n, let k be a positive

integer such that k ≥ k0=O(ε-2 logn). For every
set X of n points in Rd there exists F: Rd à Rk
such that for all xi, xj in X

n  What is the intuitive interpretation of the Lemma?

COMP9318: Data Warehousing and Data Mining 31

kF (xi)� F (xj)k2 2 (1± “)kxi � xjk2

Distributional JL Lemma

n  Given ε in (0, ½], δ > 0, there is a random linear
mapping F: Rd à Rk with k = O(ε-2 logδ-1) such
that for any unit vector x in Rd,

n  Take δ = n-2, so k = O(ε-2 log(n)), and then for
for all xi, xj є X,

n  Hence, by a simple union bound, the same
statement holds for all pairs from X
simultaneously with probability at least ½.
n  There exists a deterministic linear mapping which is an

approximate isometry. ç Why/How?
32

Pr[kF (x)k2 2 1± “] � 1� �

Pr[kF (xi)� F (xj)k2 2 (1± “)kxi � xjk2] � 1�
1

n

2


n

2

Explicit Mapping

n  F(x) = k-½ * Ux, where Uij ~ N(0, 1), i.e., i.i.d. samples
from the standard Gaussian distribution.

33

yj = hU⇤j , xi =
dX

i=1

xiUij ⇠ N (0, kxk2)

kyk2 ⇠ kxk2 · �2k

U*1
U*1

U*k

x F(x) = y1 y2 … yk
=

V ar[kyk2] = 2k

if z ⇠ �2k

Quick proof:

Concentration bound of chisquared distribution:
Pr[|

z

k
� 1| < "] � 1� exp ✓ � 3 16 k"2 ◆ E[kyk2] = kxk2 · k Approximating Inner Product 34 n  20 news groups n  Origin dim: 5000 COMP9318: Data Warehousing and Data Mining 35 Non-linear Dimensionality Reduction n  There are many advanced non-linear dimensionality reduction methods n  Hypothesis: real high-dimensional data live in a manifold with low intrinsic dimensionality Digits dataset (d = 64, Class = 0..5) COMP9318: Data Warehousing and Data Mining 36 PCA (time = 0.01s) COMP9318: Data Warehousing and Data Mining 37 t-SNE (time = 5.69s) COMP9318: Data Warehousing and Data Mining 38 39 Data Compression n  String compression n  There are extensive theories and well-tuned algorithms n  Typically lossless n  But only limited manipulation is possible without expansion n  Audio/video compression n  Typically lossy compression, with progressive refinement n  Sometimes small fragments of signal can be reconstructed without reconstructing the whole n  Time sequence is not audio n  Typically short and vary slowly with time COMP9318: Data Warehousing and Data Mining 40 Numerosity Reduction n  Parametric methods n  Assume the data fits some model, estimate model parameters, store only the parameters, and discard the data (except possible outliers) n  Log-linear analysis: obtain value at a point in m-D space as the product on appropriate marginal subspaces n  Non-parametric methods n  Do not assume models n  Major families: histograms (binning), clustering, sampling COMP9318: Data Warehousing and Data Mining 41 Random Sampling 8000 points 2000 Points 500 Points n  Allow a mining algorithm to run in complexity that is potentially sub-linear to the size of the data n  For approximately evaluating models/parameters, etc. n  Then run the “best” model/parameters on large dataset 42 Other Sampling Methods n  Simple random sampling may have very poor performance in the presence of skew n  Adaptive sampling methods n  Stratified sampling: n  Approximate the percentage of each class (or subpopulation of interest) in the overall database n  Used in conjunction with skewed data n  Sketch/synopsis based methods n  E.g., count-min sketch n  A simple and versatile data structure to remember the frequency of elements approximately COMP9318: Data Warehousing and Data Mining 43 n  Conversion of data types: n  Discretization n  Kernel density estimation COMP9318: Data Warehousing and Data Mining 44 Discretization n  Three types of simple attributes: n  Nominal/categorical — values from an unordered set n  Profession: clerk, driver, teacher, … n  Ordinal — values from an ordered set n  WAM: HD, D, CR, PASS, FAIL n  Continuous — real numbers, including Boolean values n  Other types: n  Array n  String n  Objects Discrete values è Continuous values n  Here we focus on n  Continuous values è discrete values n  Removes noise n  Some ML methods only work with discrete valued features n  Reduce the number of distinct values on features, which may improve the performance of some ML models n  Reduce data size n  Discrete values è continuous values n  Smooth the distribution n  Reconstruct probability density distribution from samples, which helps generalization 45 COMP9318: Data Warehousing and Data Mining 46 Discretization n  Discretization n  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 n  Methods n  Binning/Histogram analysis n  Clustering analysis n  Entropy-based discretization COMP9318: Data Warehousing and Data Mining 47 Simple Discretization Methods: Binning n  Equal-width (distance) partitioning: n  Divides the range into N intervals of equal size: uniform grid n  if A and B are the lowest and highest values of the attribute, the width of intervals will be: W = (B –A)/N. n  The most straightforward, but outliers may dominate presentation n  Skewed data is not handled well. n  Equal-depth (frequency) partitioning: n  Divides the range into N intervals, each containing approximately same number of samples n  Good data scaling n  Managing categorical attributes can be tricky. Optimal Binning Problem n  After binning, the educated guess or the smoothed value is E(xi), where xi are all the values in the same bin n  cost(bin) = SSE([x1, …, xm]) = ∑i=1m (xi – E(xi))2 n  cost of B bins = sum(cost(bin1), …, cost(binB)) n  Problem: find the B-1 bin boundaries such that the cost of the resulting bins is minimized n  Alg( {x1, ..., xn}, B ) n  Optimal Binning: Solve the problem optimally in O(B*n2) time and O(n2) space. n  MaxDiff: Solve the problem heuristically in O(n*log(n)) time and O(n) space. n  Note: both algorithms do not sort input data n  Send in sorted({x1, ..., xn}) if necessary 48 COMP9318: Data Warehousing and Data Mining 49 Recursive Formulation •  Observation OPT(x[1.. n], B) = mini in [n]{SSE(x[1 .. i]) + OPT(x[i+1 .. n], B-1)} •  Example •  n=4, B=3 x[1] x[2] X[3] x[4] 7 9 13 5 (7,9,13,5)3 (7)1+(9,13,5)2 (7,9)1+(13,5)2 (7)1+(9)1+(13,5)1 (7)1+(9,13)1+(5)1 (7,9)1+(13)1+(5)1 0 + (42+42) (22+22) + 0 0 + 0 0 + 8 (12+12) + 0 2 what about (7,9, 13)1+(5)2 For simplicity, we use integers, rather than real numbers, for the examples here. 22/03/17 50 Problem Caused by Overlapping Sub- problems n  Consider calculating Fibonacci function n  fib(0)=0 n  fib(1)=1 n  fib(n) = fib(n-1) + fib(n-2), for n>1

n  Naïve D&C implementation is
in efficient

fib(4)

fib(3) fib(2)

fib(1) fib(0) fib(2)

fib(1) fib(0)

fib(1)

Boundary Condition

22/03/17 51

Memoization

n  Remember solutions of all the sub-problems
n  Trade space for time

fib(4)

fib(3)

fib(2)

fib(1) fib(0)

Sub-problem solution
fib(4)
fib(3)
fib(2)
fib(1) 1
fib(0) 0

1
2
3

Dynamic Programming

Sub-problem solution

n  Ideas
n  Ensure all needed recursive calls are already computed

and memorized è a good schedule of computation
n  (Optional) Reused space to store previous recursive call

results fib(4)

fib(3) fib(2)

fib(1) fib(0) fib(2)

fib(1) fib(0)

fib(1)

2D Dynamic Programming

n  OPT(x[1.. n], B) = mini in [n]{SSE(x[1 .. i]) +
OPT(x[i+1 .. n], B-1)}
n  OPT(S1, B) = mini in [n]{… + OPT(Si+1, B-1)}
n  Goal:

53

OPT(Sj, )

OPT(Sj+1, )

… … OPT(Sn, )

OPT(S1, )

… OPT(Sn, )

How to schedule the computations?

Pseudocode

54

OPT(Sj, )

OPT(Sj+1, )

… … OPT(Sn, )

OPT(S1, )

… OPT(Sn, )

Example

n  X = [7, 9, 13, 5], B = 3

n  (B=2, S2)
n  What’s the problem?
n  How to calculate it?

COMP9318: Data Warehousing and Data Mining 55

B S1 S2 S3 S4
1 32 0

2 ?? 0 –

3 *** – –

COMP9318: Data Warehousing and Data Mining 56

MaxDiff

•  Complexity of the DP algorithm:
•  O(n2*B) running time!

•  Consider a heuristic method: MaxDiff
•  Idea: use the top-(B-1) max “gaps” in the data as the

bin/bucket boundary
•  Example:

x[1] x[2] X[3] x[4]
7 9 13 5 n=4, B=3

gap(1-2) gap(2-3) gap(3-4)
2 4 8

(7,9)1 (13)1 (5)1

Discretization via Clustering

n  Can consider multiple attributes together

57

An example where univariate discretization does not work well

Supervised Discretization Methods

n  MDLPC [Fayyad & Irani, 1993]

COMP9318: Data Warehousing and Data Mining 58

59

Entropy measures uncertainty

n  Two classes:
n  Give a set S of instances with binary classes {+,-}.

Let the proportions of + and – be p+ and p-.
n  Ent(S) = – (p+ log2 p+ + p- log2 p-) (Note: log 0 ≣ 0)

n  m classes:

0 1 0.5

1
Ent(S) From information

theory, number of
bits to encode the
class label.

p+

Ent(S) = �
mX

i=1

pi log pi

n  Consider drawing a random
sample from S. What can you
tell about its label?
n  If Ent(S) = 0:
n  If Ent(S) = log(m):

60

Entropy After Splitting T

n  Split S into two subsets: S1 and S2.
n  What about the label of a random sample given that you

know which subset it is drawn from?
n 

n 

n  Define

n  Intuitive meaning of Gain?

E(T ;S) =
|S1|
|S|

Ent(S1) +
|S2|
|S|

Ent(S2)

Gain(T ) = Ent(S)� E(T ;S)

Can be generalized to n-ary split

COMP9318: Data Warehousing and Data Mining 61

Entropy-Based Discretization: MDLPC

n  Given a set of samples S, if S is partitioned into two
intervals S1 and S2 using boundary T, the entropy after
partitioning is

n  The boundary that minimizes the entropy function over all
possible boundaries is selected as a binary discretization.

n  The process is recursively applied to partitions obtained
until some stopping criterion is met, e.g.,

n  Experiments show that it may reduce data size and
improve classification accuracy

Ent S E T S( ) ( , )− >δbefore after

These functions are also used in Decision Trees.

E(T ;S) =
|S1|
|S|

Ent(S1) +
|S2|
|S|

Ent(S2)

Stopping Condition of MDLPC

n  Stop when

COMP9318: Data Warehousing and Data Mining 62

Not needed. Just for the sake of completeness.

Comments

n  Understanding the underlying data distribution is
important
n  e.g., via visualization

n  Supervised methods usually works well
n  More advanced methods exist

n  After learning some ML models, you need to
rethink
n  Why discretization?
n  Why different method/parameters affects the

model performance? 63

Continuous values è Discrete values

n  After repeating the experiments (e.g., measuring
customers arriving 3-4pm), we observed the
following random variable xi (e.g., #customers):
n  xi = 2, 3, 3, 3, 3, 1, 5
n  What’s the probability to see x = 3 in a new

experiment? What about x = 4?
n  Naive estimation

n  P(x = 3) = 4/7 P(x = 4) = 0 / 7
n  Assume x follows the Poisson distribution

n  MLE estimation of
n  MAP estimation with a prior (typically Gamma)

64

� P (x;�) =

x

e

��

x!

Non-parametric Estimation

n  Kernel density estimation (KDE)
n  Let {xi}i=1:n be n i.i.d. sample of an unknown

f(x)
n  We can estimate f(x) as

n  K(z) controls the weight given to f(xi) to influence
f(x)

n  May think K(x, xi) as measuring their similarity

n  h is the bandwidth parameter

n  Gaussian kernel:

65

f(x;h) =
1

n

nX

i=1

K


x� xi

h

K(x;h) / exp

x

2

2h

2

Impact of h

COMP9318: Data Warehousing and Data Mining 66

Categorical Values

n  One hot encoding is widely used in ML
n  Let there be m distinct values for the attribute
n  The i-th (category) value is converted into a m-

dimensional binary vector v, where
n  vj = 0, if j !=1
n  vj = 1, otherwise

n  scikit-learn: OneHotEncoder
n  Disadvantages:

n  Ignores similarity between values
n  Embedding-based methods can learn better (real)

vectors
67

n  Case Study
n  c.f., TUN_datacleansing.ppt

COMP9318: Data Warehousing and Data Mining 68

Posted in Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *