Chapter-3-Data-Preprocessing-数据挖掘双语教学课件

1、Data Mining: Concepts and Techniques Slides for Textbook Chapter 3 Jiawei Han and Micheline KamberIntelligent Database Systems Research LabSchool of Computing Science Simon Fraser University, Canadahttp:/www.cs.sfu.ca10/2/20221Data Mining: Concepts and TechniquesData Mining: Concepts and TecChapter

2、3: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reductionDiscretization and concept hierarchy generationSummary10/2/20222Data Mining: Concepts and TechniquesChapter 3: Data PreprocessingWWhy Data Preprocessing?Data in the real world is dirtyincomple

3、te: lacking attribute values, lacking certain attributes of interest, or containing only aggregate datanoisy: containing errors or outliersinconsistent: containing discrepancies in codes or namesNo quality data, no quality mining results!Quality decisions must be based on quality dataData warehouse

4、needs consistent integration of quality data10/2/20223Data Mining: Concepts and TechniquesWhy Data Preprocessing?Data inChapter-3-Data-Preprocessing-数据挖掘双语教学课件Chapter-3-Data-Preprocessing-数据挖掘双语教学课件Forms of data preprocessing 10/2/20226Data Mining: Concepts and TechniquesForms of data preprocessing

5、10Chapter 3: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reductionDiscretization and concept hierarchy generationSummary10/2/20227Data Mining: Concepts and TechniquesChapter 3: Data PreprocessingWData CleaningData cleaning tasksFill in missing valu

6、esIdentify outliers and smooth out noisy data Correct inconsistent data10/2/20228Data Mining: Concepts and TechniquesData CleaningData cleaning tasMissing DataData is not always availableE.g., many tuples have no recorded value for several attributes, such as customer income in sales dataMissing dat

7、a may be due to equipment malfunctioninconsistent with other recorded data and thus deleteddata not entered due to misunderstandingcertain data may not be considered important at the time of entrynot register history or changes of the dataMissing data may need to be inferred.10/2/20229Data Mining: C

8、oncepts and TechniquesMissing DataData is not alwaysHow to Handle Missing Data?Ignore the tuple: usually done when class label is missing (assuming the tasks in classificationnot effective when the percentage of missing values per attribute varies considerably.Fill in the missing value manually: ted

9、ious + infeasible?Use a global constant to fill in the missing value: e.g., “unknown”, a new class?! Use the attribute mean to fill in the missing valueUse the attribute mean for all samples belonging to the same class to fill in the missing value: smarterUse the most probable value to fill in the m

10、issing value: inference-based such as Bayesian formula or decision tree10/2/202210Data Mining: Concepts and TechniquesHow to Handle Missing Data?IgnNoisy DataNoise: random error or variance in a measured variableIncorrect attribute values may due tofaulty data collection instrumentsdata entry proble

11、msdata transmission problemstechnology limitationinconsistency in naming convention Other data problems which requires data cleaningduplicate recordsincomplete datainconsistent data10/2/202211Data Mining: Concepts and TechniquesNoisy DataNoise: random error How to Handle Noisy Data?Binning method:fi

12、rst sort data and partition into (equi-depth) binsthen one can smooth by bin means, smooth by bin median, smooth by bin boundaries, etc.Clusteringdetect and remove outliersCombined computer and human inspectiondetect suspicious values and check by humanRegressionsmooth by fitting the data into regre

13、ssion functions10/2/202212Data Mining: Concepts and TechniquesHow to Handle Noisy Data?BinniSimple Discretization Methods: BinningEqual-width (distance) partitioning:It divides the range into N intervals of equal size: uniform gridif A and B are the lowest and highest values of the attribute, the wi

14、dth of intervals will be: W = (B-A)/N.The most straightforwardBut outliers may dominate presentationSkewed data is not handled well.Equal-depth (frequency) partitioning:It divides the range into N intervals, each containing approximately same number of samplesGood data scalingManaging categorical at

15、tributes can be tricky.10/2/202213Data Mining: Concepts and TechniquesSimple Discretization Methods:Binning Methods for Data Smoothing* Sorted data for price (in dollars): 4, 8, 9, 15, 21, 21, 24, 25, 26, 28, 29, 34* Partition into (equi-depth) bins: - Bin 1: 4, 8, 9, 15 - Bin 2: 21, 21, 24, 25 - Bi

16、n 3: 26, 28, 29, 34* Smoothing by bin means: - Bin 1: 9, 9, 9, 9 - Bin 2: 23, 23, 23, 23 - Bin 3: 29, 29, 29, 29* Smoothing by bin boundaries: - Bin 1: 4, 4, 4, 15 - Bin 2: 21, 21, 25, 25 - Bin 3: 26, 26, 26, 3410/2/202214Data Mining: Concepts and TechniquesBinning Methods for Data SmootCluster Anal

17、ysis10/2/202215Data Mining: Concepts and TechniquesCluster Analysis10/1/202215DatRegressionxyy = x + 1X1Y1Y110/2/202216Data Mining: Concepts and TechniquesRegressionxyy = x + 1X1Y1Y110Chapter 3: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reduction

18、Discretization and concept hierarchy generationSummary10/2/202217Data Mining: Concepts and TechniquesChapter 3: Data PreprocessingWData IntegrationData integration: combines data from multiple sources into a coherent storeSchema integrationintegrate metadata from different sourcesEntity identificati

19、on problem: identify real world entities from multiple data sources, e.g., A.cust-id B.cust-#Detecting and resolving data value conflictsfor the same real world entity, attribute values from different sources are differentpossible reasons: different representations, different scales, e.g., metric vs

20、. British units10/2/202218Data Mining: Concepts and TechniquesData IntegrationData integratiHandling Redundant Data in Data IntegrationRedundant data occur often when integration of multiple databasesThe same attribute may have different names in different databasesOne attribute may be a “derived” a

21、ttribute in another table, e.g., annual revenueRedundant data may be able to be detected by correlational analysisCareful integration of the data from multiple sources may help reduce/avoid redundancies and inconsistencies and improve mining speed and quality10/2/202219Data Mining: Concepts and Tech

22、niquesHandling Redundant Data in DatData TransformationSmoothing: remove noise from dataAggregation: summarization, data cube constructionGeneralization: concept hierarchy climbingNormalization: scaled to fall within a small, specified rangemin-max normalizationz-score normalizationnormalization by

23、decimal scalingAttribute/feature constructionNew attributes constructed from the given ones10/2/202220Data Mining: Concepts and TechniquesData TransformationSmoothing: Data Transformation: Normalizationmin-max normalizationz-score normalizationnormalization by decimal scalingWhere j is the smallest

24、integer such that Max(| |)Reduced attribute set: A1, A4, A610/2/202226Data Mining: Concepts and TechniquesExample of Decision Tree InducHeuristic Feature Selection MethodsThere are 2d possible sub-features of d featuresSeveral heuristic feature selection methods:Best single features under the featur

25、e independence assumption: choose by significance tests.Best step-wise feature selection: The best single-feature is picked firstThen next best feature condition to the first, .Step-wise feature elimination:Repeatedly eliminate the worst featureBest combined feature selection and elimination:Optimal

26、 branch and bound:Use feature elimination and backtracking10/2/202227Data Mining: Concepts and TechniquesHeuristic Feature Selection MeData CompressionString compressionThere are extensive theories and well-tuned algorithmsTypically losslessBut only limited manipulation is possible without expansion

27、Audio/video compressionTypically lossy compression, with progressive refinementSometimes small fragments of signal can be reconstructed without reconstructing the wholeTime sequence is not audioTypically short and vary slowly with time10/2/202228Data Mining: Concepts and TechniquesData CompressionSt

28、ring compresData CompressionOriginal DataCompressed DatalosslessOriginal DataApproximated lossy10/2/202229Data Mining: Concepts and TechniquesData CompressionOriginal DataCWavelet Transforms Discrete wavelet transform (DWT): linear signal processing Compressed approximation: store only a small fract

29、ion of the strongest of the wavelet coefficientsSimilar to discrete Fourier transform (DFT), but better lossy compression, localized in spaceMethod:Length, L, must be an integer power of 2 (padding with 0s, when necessary)Each transform has 2 functions: smoothing, differenceApplies to pairs of data,

30、 resulting in two set of data of length L/2Applies two functions recursively, until reaches the desired length Haar2Daubechie410/2/202230Data Mining: Concepts and TechniquesWavelet Transforms Discrete waGiven N data vectors from k-dimensions, find c = k orthogonal vectors that can be best used to re

31、present data The original data set is reduced to one consisting of N data vectors on c principal components (reduced dimensions) Each data vector is a linear combination of the c principal component vectorsWorks for numeric data onlyUsed when the number of dimensions is largePrincipal Component Anal

32、ysis 10/2/202231Data Mining: Concepts and TechniquesGiven N data vectors from k-diX1X2Y1Y2Principal Component Analysis10/2/202232Data Mining: Concepts and TechniquesX1X2Y1Y2Principal Component AnNumerosity ReductionParametric methodsAssume the data fits some model, estimate model parameters, store o

33、nly the parameters, and discard the data (except possible outliers)Log-linear models: obtain value at a point in m-D space as the product on appropriate marginal subspaces Non-parametric methods Do not assume modelsMajor families: histograms, clustering, sampling 10/2/202233Data Mining: Concepts and

34、 TechniquesNumerosity ReductionParametricRegression and Log-Linear ModelsLinear regression: Data are modeled to fit a straight lineOften uses the least-square method to fit the lineMultiple regression: allows a response variable Y to be modeled as a linear function of multidimensional feature vector

35、Log-linear model: approximates discrete multidimensional probability distributions10/2/202234Data Mining: Concepts and TechniquesRegression and Log-Linear ModeLinear regression: Y = + XTwo parameters , and specify the line and are to be estimated by using the data at hand.using the least squares cri

36、terion to the known values of Y1, Y2, , X1, X2, .Multiple regression: Y = b0 + b1 X1 + b2 X2.Many nonlinear functions can be transformed into the above.Log-linear models:The multi-way table of joint probabilities is approximated by a product of lower-order tables.Probability: p(a, b, c, d) = ab acad

37、 bcdRegress Analysis and Log-Linear ModelsLinear regression: Y = + XHistogramsA popular data reduction techniqueDivide data into buckets and store average (sum) for each bucketCan be constructed optimally in one dimension using dynamic programmingRelated to quantization problems.10/2/202236Data Mini

38、ng: Concepts and TechniquesHistogramsA popular data reducClusteringPartition data set into clusters, and one can store cluster representation onlyCan be very effective if data is clustered but not if data is “smeared”Can have hierarchical clustering and be stored in multi-dimensional index tree stru

39、cturesThere are many choices of clustering definitions and clustering algorithms, further detailed in Chapter 810/2/202237Data Mining: Concepts and TechniquesClusteringPartition data set iSamplingAllow a mining algorithm to run in complexity that is potentially sub-linear to the size of the dataChoo

40、se a representative subset of the dataSimple random sampling may have very poor performance in the presence of skewDevelop adaptive sampling methodsStratified sampling: Approximate the percentage of each class (or subpopulation of interest) in the overall database Used in conjunction with skewed dat

41、aSampling may not reduce database I/Os (page at a time).10/2/202238Data Mining: Concepts and TechniquesSamplingAllow a mining algoritSamplingSRSWOR(simple random sample without replacement)SRSWRRaw Data10/2/202239Data Mining: Concepts and TechniquesSamplingSRSWORSRSWRRaw Data10/SamplingRaw Data Clus

42、ter/Stratified Sample10/2/202240Data Mining: Concepts and TechniquesSamplingRaw Data Cluster/StratHierarchical ReductionUse multi-resolution structure with different degrees of reductionHierarchical clustering is often performed but tends to define partitions of data sets rather than “clusters”Param

43、etric methods are usually not amenable to hierarchical representationHierarchical aggregation An index tree hierarchically divides a data set into partitions by value range of some attributesEach partition can be considered as a bucketThus an index tree with aggregates stored at each node is a hiera

44、rchical histogram10/2/202241Data Mining: Concepts and TechniquesHierarchical ReductionUse multChapter 3: Data PreprocessingWhy preprocess the data?Data cleaning Data integration and transformationData reductionDiscretization and concept hierarchy generationSummary10/2/202242Data Mining: Concepts and

45、 TechniquesChapter 3: Data PreprocessingWDiscretizationThree types of attributes:Nominal values from an unordered setOrdinal values from an ordered setContinuous real numbersDiscretization: divide the range of a continuous attribute into intervalsSome classification algorithms only accept categorica

46、l attributes.Reduce data size by discretizationPrepare for further analysis10/2/202243Data Mining: Concepts and TechniquesDiscretizationThree types of aDiscretization and Concept hierachyDiscretization reduce the number of values for a given continuous attribute by dividing the range of the attribut

47、e into intervals. Interval labels can then be used to replace actual data values.Concept hierarchies reduce the data by collecting and replacing low level concepts (such as numeric values for the attribute age) by higher level concepts (such as young, middle-aged, or senior).10/2/202244Data Mining:

48、Concepts and TechniquesDiscretization and Concept hieDiscretization and concept hierarchy generation for numeric dataBinning (see sections before)Histogram analysis (see sections before)Clustering analysis (see sections before)Entropy-based discretizationSegmentation by natural partitioning10/2/2022

49、45Data Mining: Concepts and TechniquesDiscretization and concept hieEntropy-Based DiscretizationGiven a set of samples S, if S is partitioned into two intervals S1 and S2 using boundary T, the entropy after partitioning isThe boundary that minimizes the entropy function over all possible boundaries

50、is selected as a binary discretization.The process is recursively applied to partitions obtained until some stopping criterion is met, e.g.,Experiments show that it may reduce data size and improve classification accuracy10/2/202246Data Mining: Concepts and TechniquesEntropy-Based DiscretizationGiSe

51、gmentation by natural partitioning3-4-5 rule can be used to segment numeric data into relatively uniform, “natural” intervals.* If an interval covers 3, 6, 7 or 9 distinct values at the most significant digit, partition the range into 3 equi-width intervals* If it covers 2, 4, or 8 distinct values a

52、t the most significant digit, partition the range into 4 intervals* If it covers 1, 5, or 10 distinct values at the most significant digit, partition the range into 5 intervals10/2/202247Data Mining: Concepts and TechniquesSegmentation by natural partitExample of 3-4-5 rule(-$4000 -$5,000)(-$400 - 0

53、)(-$400 - -$300)(-$300 - -$200)(-$200 - -$100)(-$100 - 0)(0 - $1,000)(0 - $200)($200 - $400)($400 - $600)($600 - $800)($800 - $1,000)($2,000 - $5, 000)($2,000 - $3,000)($3,000 - $4,000)($4,000 - $5,000)($1,000 - $2, 000)($1,000 - $1,200)($1,200 - $1,400)($1,400 - $1,600)($1,600 - $1,800)($1,800 - $2

54、,000) msd=1,000Low=-$1,000High=$2,000Step 2:Step 4:Step 1: -$351-$159profit $1,838 $4,700 Min Low (i.e, 5%-tile) High(i.e, 95%-0 tile) Maxcount(-$1,000 - $2,000)(-$1,000 - 0)(0 -$ 1,000)Step 3:($1,000 - $2,000)10/2/202248Data Mining: Concepts and TechniquesExample of 3-4-5 rule(-$4000 -Concept hiera

55、rchy generation for categorical dataSpecification of a partial ordering of attributes explicitly at the schema level by users or expertsSpecification of a portion of a hierarchy by explicit data groupingSpecification of a set of attributes, but not of their partial orderingSpecification of only a partial set of attributes10/2/202249Data Mining: Concepts and TechniquesConcept hierarchy generation fSpecification of a set of attributesConc