数据挖掘概念与技术英文3prepPPT课件

《数据挖掘概念与技术英文3prepPPT课件》由会员分享，可在线阅读，更多相关《数据挖掘概念与技术英文3prepPPT课件（55页珍藏版）》请在装配图网上搜索。

1、2021/6/71Data 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.ca2021/6/72Chapter 3:Data PreprocessingnWhy preprocess the data?nData cleaning

2、 nData integration and transformationnData reductionnDiscretization and concept hierarchy generationnSummary2021/6/73Why Data Preprocessing?nData in the real world is dirtynincomplete:lacking attribute values,lacking certain attributes of interest,or containing only aggregate datannoisy:containing e

3、rrors or outliersninconsistent:containing discrepancies in codes or namesnNo quality data,no quality mining results!nQuality decisions must be based on quality datanData warehouse needs consistent integration of quality data2021/6/74Multi-Dimensional Measure of Data QualitynA well-accepted multidime

4、nsional view:nAccuracynCompletenessnConsistencynTimelinessnBelievabilitynValue addednInterpretabilitynAccessibilitynBroad categories:nintrinsic,contextual,representational,and accessibility.2021/6/75Major Tasks in Data PreprocessingnData cleaningnFill in missing values,smooth noisy data,identify or

5、remove outliers,and resolve inconsistenciesnData integrationnIntegration of multiple databases,data cubes,or filesnData transformationnNormalization and aggregationnData reductionnObtains reduced representation in volume but produces the same or similar analytical resultsnData discretizationnPart of

6、 data reduction but with particular importance,especially for numerical data2021/6/76Forms of data preprocessing 2021/6/77Chapter 3:Data PreprocessingnWhy preprocess the data?nData cleaning nData integration and transformationnData reductionnDiscretization and concept hierarchy generationnSummary202

7、1/6/78Data CleaningnData cleaning tasksnFill in missing valuesnIdentify outliers and smooth out noisy data nCorrect inconsistent data2021/6/79Missing DatanData is not always availablenE.g.,many tuples have no recorded value for several attributes,such as customer income in sales datanMissing data ma

8、y be due to nequipment malfunctionninconsistent with other recorded data and thus deletedndata not entered due to misunderstandingncertain data may not be considered important at the time of entrynnot register history or changes of the datanMissing data may need to be inferred.2021/6/710How to Handl

9、e Missing Data?nIgnore 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.nFill in the missing value manually:tedious+infeasible?nUse a global constant to fill in the missing val

10、ue:e.g.,“unknown”,a new class?!nUse the attribute mean to fill in the missing valuenUse the attribute mean for all samples belonging to the same class to fill in the missing value:smarternUse the most probable value to fill in the missing value:inference-based such as Bayesian formula or decision tr

11、ee2021/6/711Noisy DatanNoise:random error or variance in a measured variablenIncorrect attribute values may due tonfaulty data collection instrumentsndata entry problemsndata transmission problemsntechnology limitationninconsistency in naming convention nOther data problems which requires data clean

12、ingnduplicate recordsnincomplete dataninconsistent data2021/6/712How to Handle Noisy Data?nBinning method:nfirst sort data and partition into(equi-depth)binsnthen one can smooth by bin means,smooth by bin median,smooth by bin boundaries,etc.nClusteringndetect and remove outliersnCombined computer an

13、d human inspectionndetect suspicious values and check by humannRegressionnsmooth by fitting the data into regression functions2021/6/713Simple Discretization Methods:BinningnEqual-width(distance)partitioning:nIt divides the range into N intervals of equal size:uniform gridnif A and B are the lowest

14、and highest values of the attribute,the width of intervals will be:W=(B-A)/N.nThe most straightforwardnBut outliers may dominate presentationnSkewed data is not handled well.nEqual-depth(frequency)partitioning:nIt divides the range into N intervals,each containing approximately same number of sample

15、snGood data scalingnManaging categorical attributes can be tricky.2021/6/714Binning 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 -Bin 3:26,28,29,34*Smoothing by bin means:-Bin 1:9,9,9,9

16、 -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,342021/6/715Cluster Analysis2021/6/716Regressionxyy=x+1X1Y1Y12021/6/717Chapter 3:Data PreprocessingnWhy preprocess the data?nData cleaning nData integration and transformationnData r

17、eductionnDiscretization and concept hierarchy generationnSummary2021/6/718Data IntegrationnData integration:ncombines data from multiple sources into a coherent storenSchema integrationnintegrate metadata from different sourcesnEntity identification problem:identify real world entities from multiple

18、 data sources,e.g.,A.cust-id B.cust-#nDetecting and resolving data value conflictsnfor the same real world entity,attribute values from different sources are differentnpossible reasons:different representations,different scales,e.g.,metric vs.British units2021/6/719Handling Redundant Data in Data In

19、tegrationnRedundant data occur often when integration of multiple databasesnThe same attribute may have different names in different databasesnOne attribute may be a“derived”attribute in another table,e.g.,annual revenuenRedundant data may be able to be detected by correlational analysisnCareful int

20、egration of the data from multiple sources may help reduce/avoid redundancies and inconsistencies and improve mining speed and quality2021/6/720Data TransformationnSmoothing:remove noise from datanAggregation:summarization,data cube constructionnGeneralization:concept hierarchy climbingnNormalizatio

21、n:scaled to fall within a small,specified rangenmin-max normalizationnz-score normalizationnnormalization by decimal scalingnAttribute/feature constructionnNew attributes constructed from the given ones2021/6/721Data Transformation:Normalizationnmin-max normalizationnz-score normalizationnnormalizat

22、ion by decimal scalingAAAAAAminnewminnewmaxnewminmaxminvv_)_(AAdevstandmeanvv_jvv10Where j is the smallest integer such that Max(|)Reduced attribute set:A1,A4,A62021/6/727Heuristic Feature Selection MethodsnThere are 2d possible sub-features of d featuresnSeveral heuristic feature selection methods:

23、nBest single features under the feature independence assumption:choose by significance tests.nBest step-wise feature selection:nThe best single-feature is picked firstnThen next best feature condition to the first,.nStep-wise feature elimination:nRepeatedly eliminate the worst featurenBest combined

24、feature selection and elimination:nOptimal branch and bound:nUse feature elimination and backtracking2021/6/728Data CompressionnString compressionnThere are extensive theories and well-tuned algorithmsnTypically losslessnBut only limited manipulation is possible without expansionnAudio/video compres

25、sionnTypically lossy compression,with progressive refinementnSometimes small fragments of signal can be reconstructed without reconstructing the wholenTime sequence is not audionTypically short and vary slowly with time2021/6/729Data CompressionOriginal DataCompressed DatalosslessOriginal DataApprox

26、imated lossy2021/6/730Wavelet Transforms nDiscrete wavelet transform(DWT):linear signal processing nCompressed approximation:store only a small fraction of the strongest of the wavelet coefficientsnSimilar to discrete Fourier transform(DFT),but better lossy compression,localized in spacenMethod:nLen

27、gth,L,must be an integer power of 2(padding with 0s,when necessary)nEach transform has 2 functions:smoothing,differencenApplies to pairs of data,resulting in two set of data of length L/2nApplies two functions recursively,until reaches the desired length Haar2Daubechie42021/6/731nGiven N data vector

28、s from k-dimensions,find c=k orthogonal vectors that can be best used to represent data nThe original data set is reduced to one consisting of N data vectors on c principal components(reduced dimensions)nEach data vector is a linear combination of the c principal component vectorsnWorks for numeric

29、data onlynUsed when the number of dimensions is largePrincipal Component Analysis 2021/6/732X1X2Y1Y2Principal Component Analysis2021/6/733Numerosity ReductionnParametric methodsnAssume the data fits some model,estimate model parameters,store only the parameters,and discard the data(except possible o

30、utliers)nLog-linear models:obtain value at a point in m-D space as the product on appropriate marginal subspaces nNon-parametric methods nDo not assume modelsnMajor families:histograms,clustering,sampling 2021/6/734Regression and Log-Linear ModelsnLinear regression:Data are modeled to fit a straight

31、 linenOften uses the least-square method to fit the linenMultiple regression:allows a response variable Y to be modeled as a linear function of multidimensional feature vectornLog-linear model:approximates discrete multidimensional probability distributions2021/6/735nLinear regression:Y=+XnTwo param

32、eters,and specify the line and are to be estimated by using the data at hand.nusing the least squares criterion to the known values of Y1,Y2,X1,X2,.nMultiple regression:Y=b0+b1 X1+b2 X2.nMany nonlinear functions can be transformed into the above.nLog-linear models:nThe multi-way table of joint proba

33、bilities is approximated by a product of lower-order tables.nProbability:p(a,b,c,d)=ab acad bcdRegress Analysis and Log-Linear Models2021/6/736HistogramsnA popular data reduction techniquenDivide data into buckets and store average(sum)for each bucketnCan be constructed optimally in one dimension us

34、ing dynamic programmingnRelated to quantization problems.05101520253035401000020000300004000050000600007000080000900001000002021/6/737ClusteringnPartition data set into clusters,and one can store cluster representation onlynCan be very effective if data is clustered but not if data is“smeared”nCan h

35、ave hierarchical clustering and be stored in multi-dimensional index tree structuresnThere are many choices of clustering definitions and clustering algorithms,further detailed in Chapter 82021/6/738SamplingnAllow a mining algorithm to run in complexity that is potentially sub-linear to the size of

36、the datanChoose a representative subset of the datanSimple random sampling may have very poor performance in the presence of skewnDevelop adaptive sampling methodsnStratified sampling:nApproximate the percentage of each class(or subpopulation of interest)in the overall database nUsed in conjunction

37、with skewed datanSampling may not reduce database I/Os(page at a time).2021/6/739SamplingSRSWOR(simple random sample without replacement)SRSWRRaw Data2021/6/740SamplingRaw Data Cluster/Stratified Sample2021/6/741Hierarchical ReductionnUse multi-resolution structure with different degrees of reductio

38、nnHierarchical clustering is often performed but tends to define partitions of data sets rather than“clusters”nParametric methods are usually not amenable to hierarchical representationnHierarchical aggregation nAn index tree hierarchically divides a data set into partitions by value range of some a

39、ttributesnEach partition can be considered as a bucketnThus an index tree with aggregates stored at each node is a hierarchical histogram2021/6/742Chapter 3:Data PreprocessingnWhy preprocess the data?nData cleaning nData integration and transformationnData reductionnDiscretization and concept hierar

40、chy generationnSummary2021/6/743DiscretizationnThree types of attributes:nNominal values from an unordered setnOrdinal values from an ordered setnContinuous real numbersnDiscretization:*divide the range of a continuous attribute into intervalsnSome classification algorithms only accept categorical a

41、ttributes.nReduce data size by discretizationnPrepare for further analysis2021/6/744Discretization and Concept hierachynDiscretization nreduce 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 actua

42、l data values.nConcept hierarchies nreduce 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).2021/6/745Discretization and concept hierarchy generation for numeric datanBinning(see section

43、s before)nHistogram analysis(see sections before)nClustering analysis(see sections before)nEntropy-based discretizationnSegmentation by natural partitioning2021/6/746Entropy-Based DiscretizationnGiven a set of samples S,if S is partitioned into two intervals S1 and S2 using boundary T,the entropy af

44、ter partitioning isnThe boundary that minimizes the entropy function over all possible boundaries is selected as a binary discretization.nThe process is recursively applied to partitions obtained until some stopping criterion is met,e.g.,nExperiments show that it may reduce data size and improve cla

45、ssification accuracyE S TSEntSEntSSSS(,)|()|()1122Ent SE T S()(,)2021/6/747Segmentation 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

46、 into 3 equi-width intervals*If it covers 2,4,or 8 distinct values at 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 intervals2021/6/748Example of 3-4-5 rule(-$4000-$5,000)(-$400-0)(-$400

47、-$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,000)msd=1,000Low=-$1,000High=$2,000Step 2:Step 4:St

48、ep 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)2021/6/749Concept hierarchy generation for categorical datanSpecification of a partial ordering of attributes explicitly at the schema level by users or exper

49、tsnSpecification of a portion of a hierarchy by explicit data groupingnSpecification of a set of attributes,but not of their partial orderingnSpecification of only a partial set of attributes2021/6/750Specification of a set of attributesConcept hierarchy can be automatically generated based on the n

50、umber of distinct values per attribute in the given attribute set.The attribute with the most distinct values is placed at the lowest level of the hierarchy.countryprovince_or_ statecitystreet15 distinct values65 distinct values3567 distinct values674,339 distinct values2021/6/751Chapter 3:Data Prep

51、rocessingnWhy preprocess the data?nData cleaning nData integration and transformationnData reductionnDiscretization and concept hierarchy generationnSummary2021/6/752SummarynData preparation is a big issue for both warehousing and miningnData preparation includesnData cleaning and data integrationnD

52、ata reduction and feature selectionnDiscretizationnA lot a methods have been developed but still an active area of research2021/6/753ReferencesnD.P.Ballou and G.K.Tayi.Enhancing data quality in data warehouse environments.Communications of ACM,42:73-78,1999.nJagadish et al.,Special Issue on Data Red

53、uction Techniques.Bulletin of the Technical Committee on Data Engineering,20(4),December 1997.nD.Pyle.Data Preparation for Data Mining.Morgan Kaufmann,1999.nT.Redman.Data Quality:Management and Technology.Bantam Books,New York,1992.nY.Wand and R.Wang.Anchoring data quality dimensions ontological foundations.Communications of ACM,39:86-95,1996.nR.Wang,V.Storey,and C.Firth.A framework for analysis of data quality research.IEEE Trans.Knowledge and Data Engineering,7:623-640,1995.2021/6/754http:/www.cs.sfu.ca/han部分资料从网络收集整理而来，供大家参考，感谢您的关注！