数据挖掘概念和技术—Chapter3DataPreprocessing精选课件

《数据挖掘概念和技术—Chapter3DataPreprocessing精选课件》由会员分享，可在线阅读，更多相关《数据挖掘概念和技术—Chapter3DataPreprocessing精选课件（57页珍藏版）》请在装配图网上搜索。

1、Data Mining:Concepts and Techniques Slides for Textbook Chapter 3 Jiawei Han and Micheline KamberDepartment of Computer Science University of Illinois at Urbana-Champaigncs.uiuc.edu/hanj8/19/20231Data Mining:Concepts and TechniquesChapter 3:Data PreprocessingnWhy preprocess the data?nData cleaning n

2、Data integration and transformationnData reductionnDiscretization and concept hierarchy generationnSummary8/19/20232Data Mining:Concepts and TechniquesWhy Data Preprocessing?nData in the real world is dirtynincomplete:lacking attribute values,lacking certain attributes of interest,or containing only

3、 aggregate datane.g.,occupation=“”nnoisy:containing errors or outliersne.g.,Salary=“-10”ninconsistent:containing discrepancies in codes or namesne.g.,Age=“42”Birthday=“03/07/2019”ne.g.,Was rating“1,2,3”,now rating“A,B,C”ne.g.,discrepancy between duplicate records8/19/20233Data Mining:Concepts and Te

4、chniquesWhy Is Data Dirty?nIncomplete data comes fromnn/a data value when collectedndifferent consideration between the time when the data was collected and when it is analyzed.nhuman/hardware/software problemsnNoisy data comes from the process of datancollectionnentryntransmissionnInconsistent data

5、 comes fromnDifferent data sourcesnFunctional dependency violation8/19/20234Data Mining:Concepts and TechniquesWhy Is Data Preprocessing Important?nNo quality data,no quality mining results!nQuality decisions must be based on quality datane.g.,duplicate or missing data may cause incorrect or even mi

6、sleading statistics.nData warehouse needs consistent integration of quality datanData extraction,cleaning,and transformation comprises the majority of the work of building a data warehouse.Bill Inmon 8/19/20235Data Mining:Concepts and TechniquesMulti-Dimensional Measure of Data QualitynA well-accept

7、ed multidimensional view:nAccuracynCompletenessnConsistencynTimelinessnBelievabilitynValue addednInterpretabilitynAccessibilitynBroad categories:nintrinsic,contextual,representational,and accessibility.8/19/20236Data Mining:Concepts and TechniquesMajor Tasks in Data PreprocessingnData cleaningnFill

8、in missing values,smooth noisy data,identify or 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 simila

9、r analytical resultsnData discretizationnPart of data reduction but with particular importance,especially for numerical data8/19/20237Data Mining:Concepts and TechniquesForms of data preprocessing 8/19/20238Data Mining:Concepts and TechniquesChapter 3:Data PreprocessingnWhy preprocess the data?nData

10、 cleaning nData integration and transformationnData reductionnDiscretization and concept hierarchy generationnSummary8/19/20239Data Mining:Concepts and TechniquesData CleaningnImportancen“Data cleaning is one of the three biggest problems in data warehousing”Ralph Kimballn“Data cleaning is the numbe

11、r one problem in data warehousing”DCI surveynData cleaning tasksnFill in missing valuesnIdentify outliers and smooth out noisy data nCorrect inconsistent datanResolve redundancy caused by data integration8/19/202310Data Mining:Concepts and TechniquesMissing DatanData is not always availablenE.g.,man

12、y tuples have no recorded value for several attributes,such as customer income in sales datanMissing data may 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 e

13、ntrynnot register history or changes of the datanMissing data may need to be inferred.8/19/202311Data Mining:Concepts and TechniquesHow to Handle Missing Data?nIgnore the tuple:usually done when class label is missing(assuming the tasks in classificationnot effective when the percentage of missing v

14、alues per attribute varies considerably.nFill in the missing value manually:tedious+infeasible?nFill in it automatically withna global constant:e.g.,“unknown”,a new class?!nthe attribute meannthe attribute mean for all samples belonging to the same class:smarternthe most probable value:inference-bas

15、ed such as Bayesian formula or decision tree8/19/202312Data Mining:Concepts and TechniquesNoisy DatanNoise:random error or variance in a measured variablenIncorrect attribute values may due tonfaulty data collection instrumentsndata entry problemsndata transmission problemsntechnology limitationninc

16、onsistency in naming convention nOther data problems which requires data cleaningnduplicate recordsnincomplete dataninconsistent data8/19/202313Data Mining:Concepts and TechniquesHow to Handle Noisy Data?nBinning method:nfirst sort data and partition into(equi-depth)binsnthen one can smooth by bin m

17、eans,smooth by bin median,smooth by bin boundaries,etc.nClusteringndetect and remove outliersnCombined computer and human inspectionndetect suspicious values and check by human(e.g.,deal with possible outliers)nRegressionnsmooth by fitting the data into regression functions8/19/202314Data Mining:Con

18、cepts and TechniquesSimple Discretization Methods:BinningnEqual-width(distance)partitioning:nDivides the range into N intervals of equal size:uniform gridnif A and B are the lowest and highest values of the attribute,the width of intervals will be:W=(B A)/N.nThe most straightforward,but outliers may

19、 dominate presentationnSkewed data is not handled well.nEqual-depth(frequency)partitioning:nDivides the range into N intervals,each containing approximately same number of samplesnGood data scalingnManaging categorical attributes can be tricky.8/19/202315Data Mining:Concepts and TechniquesBinning Me

20、thods 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 -Bin 2:23,23,23,23 -Bin 3:29,29,29,29*Smoothing by bin boundaries:-Bin 1:4,4,4,15 -Bi

21、n 2:21,21,25,25 -Bin 3:26,26,26,348/19/202316Data Mining:Concepts and TechniquesCluster Analysis8/19/202317Data Mining:Concepts and TechniquesRegressionxyy=x+1X1Y1Y18/19/202318Data Mining:Concepts and TechniquesChapter 3:Data PreprocessingnWhy preprocess the data?nData cleaning nData integration and

22、 transformationnData reductionnDiscretization and concept hierarchy generationnSummary8/19/202319Data Mining:Concepts and TechniquesData IntegrationnData integration:ncombines data from multiple sources into a coherent storenSchema integrationnintegrate metadata from different sourcesnEntity identif

23、ication problem:identify real world entities from multiple 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

24、.British units8/19/202320Data Mining:Concepts and TechniquesHandling Redundancy in Data IntegrationnRedundant 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.,annu

25、al revenuenRedundant data may be able to be detected by correlational analysisnCareful integration of the data from multiple sources may help reduce/avoid redundancies and inconsistencies and improve mining speed and quality8/19/202321Data Mining:Concepts and TechniquesData TransformationnSmoothing:

26、remove noise from datanAggregation:summarization,data cube constructionnGeneralization:concept hierarchy climbingnNormalization:scaled to fall within a small,specified rangenmin-max normalizationnz-score normalizationnnormalization by decimal scalingnAttribute/feature constructionnNew attributes con

27、structed from the given ones8/19/202322Data Mining:Concepts and TechniquesData Transformation:Normalizationnmin-max normalizationnz-score normalizationnnormalization by decimal scalingWhere j is the smallest integer such that Max(|)Reduced attribute set:A1,A4,A68/19/202328Data Mining:Concepts and Te

28、chniquesData CompressionnString compressionnThere are extensive theories and well-tuned algorithmsnTypically losslessnBut only limited manipulation is possible without expansionnAudio/video compressionnTypically lossy compression,with progressive refinementnSometimes small fragments of signal can be

29、 reconstructed without reconstructing the wholenTime sequence is not audionTypically short and vary slowly with time8/19/202330Data Mining:Concepts and TechniquesData CompressionOriginal DataCompressed DatalosslessOriginal DataApproximated lossy8/19/202331Data Mining:Concepts and TechniquesWavelet T

30、ransformation nDiscrete wavelet transform(DWT):linear signal processing,multiresolutional analysisnCompressed 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:nLeng

31、th,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 Haar2Daubechie48/19/202332Data Mining:Concepts

32、 and TechniquesDWT for Image CompressionnImage Low Pass High Pass Low Pass High PassLow Pass High Pass8/19/202333Data Mining:Concepts and TechniquesnGiven N data vectors from k-dimensions,find c=k orthogonal vectors that can be best used to represent data nThe original data set is reduced to one con

33、sisting 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 data onlynUsed when the number of dimensions is largePrincipal Component Analysis 8/19/202334Data Mining:Concepts and TechniquesX1X2

34、Y1Y2Principal Component Analysis8/19/202335Data Mining:Concepts and TechniquesNumerosity ReductionnParametric methodsnAssume the data fits some model,estimate model parameters,store only the parameters,and discard the data(except possible outliers)nLog-linear models:obtain value at a point in m-D sp

35、ace as the product on appropriate marginal subspaces nNon-parametric methods nDo not assume modelsnMajor families:histograms,clustering,sampling 8/19/202336Data Mining:Concepts and TechniquesRegression and Log-Linear ModelsnLinear regression:Data are modeled to fit a straight linenOften uses the lea

36、st-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 distributions8/19/202337Data Mining:Concepts and TechniquesnLinear regression:Y=

37、+XnTwo parameters,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

38、 joint probabilities is approximated by a product of lower-order tables.nProbability:p(a,b,c,d)=ab acad bcdRegress Analysis and Log-Linear ModelsHistogramsnA popular data reduction techniquenDivide data into buckets and store average(sum)for each bucketnCan be constructed optimally in one dimension

39、using dynamic programmingnRelated to quantization problems.8/19/202339Data Mining:Concepts and TechniquesClusteringnPartition 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 have hierarchical clustering a

40、nd be stored in multi-dimensional index tree structuresnThere are many choices of clustering definitions and clustering algorithms,further detailed in Chapter 88/19/202340Data Mining:Concepts and TechniquesSamplingnAllow a mining algorithm to run in complexity that is potentially sub-linear to the s

41、ize of 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 conju

42、nction with skewed datanSampling may not reduce database I/Os(page at a time).8/19/202341Data Mining:Concepts and TechniquesSamplingSRSWOR(simple random sample without replacement)SRSWRRaw Data8/19/202342Data Mining:Concepts and TechniquesSamplingRaw Data Cluster/Stratified Sample8/19/202343Data Min

43、ing:Concepts and TechniquesHierarchical ReductionnUse multi-resolution structure with different degrees of reductionnHierarchical clustering is often performed but tends to define partitions of data sets rather than“clusters”nParametric methods are usually not amenable to hierarchical representation

44、nHierarchical aggregation nAn index tree hierarchically divides a data set into partitions by value range of some attributesnEach partition can be considered as a bucketnThus an index tree with aggregates stored at each node is a hierarchical histogram8/19/202344Data Mining:Concepts and TechniquesCh

45、apter 3:Data PreprocessingnWhy preprocess the data?nData cleaning nData integration and transformationnData reductionnDiscretization and concept hierarchy generationnSummary8/19/202345Data Mining:Concepts and TechniquesDiscretizationnThree types of attributes:nNominal values from an unordered setnOr

46、dinal values from an ordered setnContinuous real numbersnDiscretization:ndivide the range of a continuous attribute into intervalsnSome classification algorithms only accept categorical attributes.nReduce data size by discretizationnPrepare for further analysis8/19/202346Data Mining:Concepts and Tec

47、hniquesDiscretization 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 actual data valuesnConcept hierarchies nreduce the data by collecting and replacin

48、g low level concepts(such as numeric values for the attribute age)by higher level concepts(such as young,middle-aged,or senior)8/19/202347Data Mining:Concepts and TechniquesDiscretization and Concept Hierarchy Generation for Numeric DatanBinning(see sections before)nHistogram analysis(see sections b

49、efore)nClustering analysis(see sections before)nEntropy-based discretizationnSegmentation by natural partitioning8/19/202348Data Mining:Concepts and TechniquesEntropy-Based DiscretizationnGiven a set of samples S,if S is partitioned into two intervals S1 and S2 using boundary T,the entropy after par

50、titioning 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 classifica

51、tion accuracy8/19/202349Data Mining:Concepts and TechniquesSegmentation by Natural PartitioningnA simply 3-4-5 rule can be used to segment numeric data into relatively uniform,“natural”intervals.nIf an interval covers 3,6,7 or 9 distinct values at the most significant digit,partition the range into

52、3 equi-width intervalsnIf it covers 2,4,or 8 distinct values at the most significant digit,partition the range into 4 intervalsnIf it covers 1,5,or 10 distinct values at the most significant digit,partition the range into 5 intervals8/19/202350Data Mining:Concepts and TechniquesExample of 3-4-5 Rule

53、(-$4000-$5,000)(-$400-0)(-$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,000)msd=1,000Low=-$1,

54、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)8/19/202351Data Mining:Concepts and TechniquesConcept Hierarchy Generation for Categorical DatanSpecification of a partial order

55、ing of attributes explicitly at the schema level by users or expertsnstreetcitystatecountrynSpecification of a portion of a hierarchy by explicit data groupingnUrbana,Champaign,ChicagoIllinoisnSpecification of a set of attributes.nSystem automatically generates partial ordering by analysis of the nu

56、mber of distinct valuesnE.g.,street city state countrynSpecification of only a partial set of attributesnE.g.,only street city,not others8/19/202352Data Mining:Concepts and TechniquesAutomatic Concept Hierarchy GenerationnSome concept hierarchies can be automatically generated based on the analysis

57、of the number of distinct values per attribute in the given data set nThe attribute with the most distinct values is placed at the lowest level of the hierarchynNote:Exceptionweekday,month,quarter,yearcountryprovince_or_ statecitystreet15 distinct values65 distinct values3567 distinct values674,339

58、distinct values8/19/202353Data Mining:Concepts and TechniquesChapter 3:Data PreprocessingnWhy preprocess the data?nData cleaning nData integration and transformationnData reductionnDiscretization and concept hierarchy generationnSummary8/19/202354Data Mining:Concepts and TechniquesSummarynData prepa

59、ration is a big issue for both warehousing and miningnData preparation includesnData cleaning and data integrationnData reduction and feature selectionnDiscretizationnA lot a methods have been developed but still an active area of research8/19/202355Data Mining:Concepts and TechniquesReferencesnE.Ra

60、hm and H.H.Do.Data Cleaning:Problems and Current Approaches.IEEE Bulletin of the Technical Committee on Data Engineering.Vol.23,No.4nD.P.Ballou and G.K.Tayi.Enhancing data quality in data warehouse environments.Communications of ACM,42:73-78,2019.nH.V.Jagadish et al.,Special Issue on Data Reduction

61、Techniques.Bulletin of the Technical Committee on Data Engineering,20(4),December 2019.nA.Maydanchik,Challenges of Efficient Data Cleansing(DM Review-Data Quality resource portal)nD.Pyle.Data Preparation for Data Mining.Morgan Kaufmann,2019.nD.Quass.A Framework for research in Data Cleaning.(Draft 2

62、019)nV.Raman and J.Hellerstein.Potters Wheel:An Interactive Framework for Data Cleaning and Transformation,VLDB2019.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,

63、2019.nR.Wang,V.Storey,and C.Firth.A framework for analysis of data quality research.IEEE Trans.Knowledge and Data Engineering,7:623-640,2019.ncs.ucla.edu/classes/spring01/cs240b/notes/data-integration1.pdf8/19/202356Data Mining:Concepts and Techniquescs.uiuc.edu/hanjThank you!8/19/202357Data Mining:Concepts and Techniques