Chapter6:DataPreprocessingReview什么是數據挖掘數據挖掘的主要方法基于集合論的數據挖掘方法：關聯分析基于信息論的數據挖掘方法：決策樹Moretocome..數據挖掘的步驟三部曲數據準備數據選擇：目標數據數據預處理：

消除噪聲，不一致，冗余等

數據變換：連續數據離散化，數據轉化

數據歸約：特征選擇和抽取數據挖掘結果的解釋評估數據的預處理為什么要進行預處理數據清理：60%的工作量數據集成數據變換數據歸約數據離散化為什么要預處理數據現實世界的數據是“骯臟的”–數據多了什么問題都會出現不完整的：有些感興趣的屬性缺少屬性值e.g.,occupation=“”含噪聲的：包含錯誤的，或者孤立點e.g.,Salary=“-10”不一致的：在編碼或者命名上存在差異e.g.,Age=“42”Birthday=“03/07/1997”e.g.,Wasrating“1,2,3”,nowrating“A,B,C”e.g.,discrepancybetweenduplicaterecordsWhyIsDataPreprocessingImportant?6Noqualitydata,noqualityminingresults!Qualitydecisionsmustbebasedonqualitydatae.g.,duplicateormissingdatamaycauseincorrectorevenmisleadingstatistics.DatawarehouseneedsconsistentintegrationofqualitydataDataextraction,cleaning,andtransformationcomprisesthemajorityoftheworkofbuildingadatawarehouse重要性Importance“Datacleaningisoneofthethreebiggestproblemsindatawarehousing”—RalphKimball“Datacleaningisthenumberoneproblemindatawarehousing”—DCIsurvey數據質量的多維度量一個廣為認可的多維度量觀點精確度完整度一致性可信度附加價值可訪問性根數據本身的含義相關的Intrinsic,contextual,representational,andaccessibility數據預處理的主要任務數據清理填寫空缺的值，平化噪聲數據，識別、刪除孤立點，消除不一致性數據集成集成多個數據庫、數據立方體或文件數據變換規范化和聚集數據歸約得到數據集的壓縮表示，它小得多，但可以得到相同或近似的結果數據離散化數據歸約的一部分，通過概念分層和數據的離散化來規約數據，對數字型數據特別重要FormsofDataPreprocessing

10數據的預處理為什么要進行預處理數據清理：60%的工作量數據集成數據變換數據歸約數據離散化空缺值數據并不總是完整的E.g.數據庫表中，很多條記錄的對應字段沒有相應值，比如銷售表中的顧客收入引起空缺值的原因設備異常與其他已有的數據不一致而被刪除因為誤解而沒有被輸入的數據對數據的改變沒有進行日志記載如何處理空缺值忽略元組：當類標號缺少時通常會這么做人工填寫空缺值：工作量大，可行性低使用一個全局變量填充空缺值：如unknown,N/Aminingroutinesmaymistakenlythinkthefilledvalueformaninterestingconcept使用屬性的平均值填充空缺值使用與給定元組屬同一類的所有樣本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定樹這樣的基于推斷的方法smarterstrategy,whichusesthemostinformationcontainedinthepresentdataHowtoHandleMissingData?AgeIncomeReligionGender2324,200MuslimM39?ChristianF4545,390?F??Fillmissingvaluesusingaggregatefunctions(e.g.,average)orprobabilisticestimatesonglobalvaluedistributionE.g.,puttheaverageincomehere,orputthemostprobableincomebasedonthefactthatthepersonis39yearsoldE.g.,putthemostfrequentreligionhere噪聲數據噪聲：一個測量變量中的隨機錯誤或偏差引起不正確屬性值的原因數據收集工具的問題數據輸入錯誤數據傳輸錯誤技術限制命名規則的不一致其他需要數據清理的數據問題重復紀錄不完整的數據不一致的數據如何處理噪聲數據分箱（Binning）首先排序，并將他們分到等深的箱中然后可以按箱的平均值平滑，按箱中值平滑，按箱的邊界平滑等聚類檢測并且去除孤立點計算機和人工檢查結合計算機檢測可疑數據，然后對他們進行人工判斷回歸通過讓數據適應回歸函數來平滑數據SimpleDiscretizationMethods:Binning17Equal-width(distance)partitioning：DividestherangeintoNintervalsofequalsize:uniformgridifAandBarethelowestandhighestvaluesoftheattribute,thewidthofintervalswillbe:W=(B–A)/N.Themoststraightforward,butoutliersmaydominatepresentationSkeweddataisnothandledwellEqual-depth(frequency)partitioningDividestherangeintoNintervals,eachcontainingapproximatelysamenumberofsamplesGooddatascalingManagingcategoricalattributescanbetrickySimpleDiscretizationMethods:BinningExample:customerages0-1010-2020-3030-4040-5050-6060-7070-80Equi-widthbinning:number

ofvalues0-2222-3144-4832-3838-4448-5555-6262-80Equi-depthbinning:數據平滑的分箱方法Price的排序后數據：4,8,15,21,21,24,25,28,34劃分為（等深的）箱箱14815箱2212124箱3252834平滑方法用箱的平均值平滑箱1999箱2222222箱3292929用箱邊界平滑箱14415箱2212124箱3252534劃分為（等深的）箱箱14815箱2212124箱3252834聚類消除噪聲分析查找孤立點回歸消除噪音通過構造函數來符合數據變化的趨勢，這樣可以用一個變量預測另一個變量線性回歸非線性回歸xyy=x+1X1Y1Y1’數據的預處理為什么要進行預處理數據清理：60%的工作量數據集成數據變換數據歸約數據離散化數據集成數據集成功能：將來自不同數據源的數據整合成一致的數據存儲。元數據、相關分析、數據沖突檢測和語義異種性的解析都有助于數據集成。問題和解決辦法：問題1：模式集成來自多個信息源的現實世界的實體如何“匹配”？--實體識別問題E.g.,數據分析者或計算機如何才能確信一個數據庫中的customer_id和另一個數據庫中的cust_number指的是同一個實體？E.g.familynamevs.surname解決方法：利用數據庫的元數據--一種關于數據的數據。這種元數據可以幫助避免模式集成中的錯誤。問題2：冗余一個屬性若能由另一個表導出，它便是冗余的。例如年薪。屬性或維命名的不一致也可能導致數據集中的冗余。解決方法：可利用相關分析的方法檢測冗余。除了檢測屬性間的冗余外，“重復”也當在元組級進行檢測。所謂重復是指對于同一數據，存在兩個或多個相同的元組。CorrelationAnalysis(NumericalData)Correlationcoefficient(alsocalledPearson’sproductmomentcoefficient)wherenisthenumberoftuples,andaretherespectivemeansofAandB,σAandσBaretherespectivestandarddeviationofAandB,andΣ(AB)isthesumoftheABcross-product.IfrA,B>0,AandBarepositivelycorrelated(A’svaluesincreaseasB’s).Thehigher,thestrongercorrelation.rA,B=0:rA,B<0:negativelycorrelated27舉例cor=0AandBarenotcorrelatede.g.A:rainB:goodTVprogramnote:notcorrelatedisnotequaltoindependentcor>0AandBarepositivelycorrelatede.g.A:rainB:cloudycor<0AandBarenegativelycorrelatede.g.A:rainB:sunshinePositivelyandNegativelyCorrelatedData2902February202330NotCorrelatedData問題3：數據值沖突的檢測和處理對于現實世界的同一實體，來自不同數據源的屬性值可能不同。這可能是因為表示、比例或編碼的不同。例如重量屬性可能在一個系統中以公制單位存放，而在另一個系統中以英制單位存放。數據這種語義上的異種性，是數據集成的巨大挑戰。數據的預處理為什么要進行預處理數據清理：60%的工作量數據集成數據變換數據歸約數據離散化數據變換數據變換將數據轉換成適合挖掘的形式。平滑：去掉數據中的噪聲。這種技術包括分箱、聚類和回歸。聚集：對數據進行匯總和聚集。例如可以聚集日銷售數據，計算年銷售額。通常這一步用來為多粒度數據分析構造數據立方體。數據變換數據概化：使用概念分層，用高層次的概念替換低層次的“原始”數據。如分類的屬性street可以概化為較高層的概念，如city或country。規范化：將屬性數據按比例縮放，使之落入一個小的特定區間，如-1.0到1.0或0.0到1.0最小----最大規范化：對原始數據進行線形變換。假定屬性A的最小和最大值分別為minA和maxA,計算Ex.Letincomerange$12,000to$98,000normalizedto[0.0,1.0].Then$73,000ismappedto數據變換

將A的值映射到區間[new_minA,new_maxA]中的v’

z-score規范化：屬性A的值基于A的平均值和標準差規范化，計算Ex.Letμ=54,000,σ=16,000.Then小數定標規范化：通過移動屬性A的小數點位置進行規范化，計算數據變換屬性構造：由給定的屬性構造和添加新的屬性，以幫助提高精度和對高維數據結構的理解。例如，我們可能根據屬性height和width添加屬性area。通過組合屬性，屬性構造可以發現關于數據屬性間聯系的丟失信息，這對知識發現是有用的。數據的預處理為什么要進行預處理數據清理：60%的工作量數據集成數據變換數據歸約數據離散化數據歸約數據倉庫中往往存有海量數據，在其上進行數據分析與挖掘需要很長時間數據歸約數據歸約可以用來得到數據集的歸約表示，它小得多，卻可以產生相同的或幾乎相同的分析結果數據歸約策略數據立方體聚集：聚集操作用于數據立方體中的數據。維歸約：通過刪除不相關的屬性（或）維減少數據量。通常使用屬性子集選擇方法。數據壓縮數值歸約離散化和概念分層產生用于數據歸約的時間不應當超過或抵消歸約后的數據上挖掘節省的時間數據立方體聚集最底層的方體對應于基本方體基本方體對應感興趣的實體在數據立方體中存在著不同級別的匯總數據立方體可以看成方體的格每個較高層次的抽象將進一步減少結果數量數據立方體提供了對于計算的匯總數據的快速訪問使用與給定任務相關的最小方體在可能的情況下，對于匯總數據的查詢應當使用數據立方體維歸約通過刪除不相干的屬性或維減少數據量屬性子集選擇目標：找出最小屬性集，使得數據類的概率分布盡可能地接近使用所有屬性的原分布。優點：減少了出現在發現模式上的屬性的數目，使得模式更易于理解。維歸約啟發式的方法屬性子集選擇方法包括以下技術：逐步向前選擇：由空屬性集開始，每次都選擇原屬性集中最好的屬性，將其添加到集合中。逐步向后刪除：由整個屬性集開始，在每一步，刪除掉尚在屬性集中的最壞屬性。向前選擇和向后刪除的結合：每一步選擇一個最好的屬性，并在剩余屬性中刪除一個最壞的屬性。判定樹歸納：用判定樹算法選擇“最好”的屬性，將數據劃分成類。逐步向前選擇Step-wiseforwardselectionselectthebestoftheoriginalattributesselectthebestoftheremainingoriginalattributes……initialattributeset:{A1,A2,A3,A4,A5,A6}initialreducedset:{}step1:{A1}step2:{A1,A4}step3:{A1,A4,A6}逐步向后刪除Step-wisebackwardeliminationeliminatetheworstoftheoriginalattributeseliminatetheworstoftheremainingoriginalattributes……initialattributeset:{A1,A2,A3,A4,A5,A6}initialreducedset:{A1,A2,A3,A4,A5,A6}step1:{A1,A3,A4,A5,A6}step2:{A1,A4,A5,A6}step3:{A1,A4,A6}向前選擇和向后刪除的結合Combinedforwardselectionandbackwardeliminationselectthebestoftheoriginalattributesandeliminatetheworstoftheremainingoriginalattributes……initialattributeset:{A1,A2,A3,A4,A5,A6}initialreducedset:{A1,A2,A3,A4,A5,A6}step1:{A1,A3,A4,A5,A6}step2:{A1,A4,A5,A6}step3:{A1,A4,A6}46ExampleofDecisionTreeInductionInitialattributeset:{A1,A2,A3,A4,A5,A6}A4?A1?A6?Class1Class2Class1Class2>Reducedattributeset:{A1,A4,A6}數據壓縮有損壓縮vs.無損壓縮字符串壓縮有廣泛的理論基礎和精妙的算法通常是無損壓縮在解壓縮前對字符串的操作非常有限音頻/視頻壓縮通常是有損壓縮，壓縮精度可以遞進選擇有時可以在不解壓整體數據的情況下，重構某個片斷兩種有損數據壓縮的方法：小波變換和主要成分分析DataCompression48OriginalDataCompressedDatalosslessOriginalDataApproximatedlossyPrincipalComponentAnalysis(PCA)49GivenNdatavectorsfromn-dimensions,findk≤northogonalvectors(principalcomponents)thatcanbebestusedtorepresentdataStepsNormalizeinputdata:EachattributefallswithinthesamerangeComputekorthonormal(unit)vectors,i.e.,principalcomponentsEachinputdata(vector)isalinearcombinationofthekprincipalcomponentvectorsTheprincipalcomponentsaresortedinorderofdecreasing“significance”orstrengthSincethecomponentsaresorted,thesizeofthedatacanbereducedbyeliminatingtheweakcomponents,i.e.,thosewithlowvariance.(i.e.,usingthestrongestprincipalcomponents,itispossibletoreconstructagoodapproximationoftheoriginaldataWorksfornumericdataonlyUsedwhenthenumberofdimensionsislargeX1X2Y1Y2PrincipalComponentAnalysisX1,X2:originalaxes(attributes)Y1,Y2:principalcomponentssignificantcomponent(highvariance)Orderprincipalcomponentsbysignificanceandeliminateweakerones數值歸約通過選擇替代的較小的數據表示形式來減少數據量有參方法：使用一個參數模型來估計數據，最后只要存儲參數即可線性回歸方法：無參方法：直方圖聚類選樣數據歸約：直方圖一種流行的數據歸約技術將某屬性的數據劃分成不相交的子集，或桶，桶中放置該值得出現頻率桶和屬性值得劃分規則等深：

equalbucketrange等寬：

orequal-depthV-最優withtheleasthistogramvariance(weightedsumoftheoriginalvaluesthateachbucketrepresents)MaxDiffsetbucketboundarybetweeneachpairforpairshavetheβ–1largestdifferencesβdeterminesthenumberofbuckets直方圖數據歸約：聚類將數據集劃分為聚類，然后通過聚類來表示數據集如果數據可以組成各種不同的聚類，則該技術非常有效，反之如果數據界限模糊，則方法無效數據可以分層聚類，并被存儲在多層索引書中聚類的定義和算法都有很多選擇數據歸約：選樣允許用數據的較小的隨機樣本來表示大的數據集對數據集D的樣本選擇簡單隨機選取n各樣本，不放回：由D的N個元組中抽取n個樣本簡單隨機選擇n各樣本，放回，過程同上聚類選樣：D中元組被分入M個互不相交的聚類中，可在其中的m個聚類上進行簡單隨機選擇(m<M)分層選樣：D被劃分為互不相交的層，則可通過對每一層的簡單隨機選樣得到D的分層選樣選樣SRSWOR(simplerandomsamplewithoutreplacement)SRSWRRawData選樣–聚類/分層選樣RawDataCluster/StratifiedSamplerandomsamplingwithoutreplacement--〉randomsamplingwithreplacement(bootstrapsampling)ClustersamplingStratifiedsampling數據的預處理為什么要進行預處理數據清理：60%的工作量數據集成數據變換數據歸約數據離散化離散化三種類型的屬性值名稱型–無序集合中的值序數–有序集合中的值連續值離散化將連續屬性的范圍劃分為區間有效的歸約數據基于判定樹的分類挖掘離散化的數值用于進一步分析離散化和概念分層離散化通過將屬性域劃分為區間，減少給定連續數值的個數。區間的標號可以代替實際的數據值。概念分層通過使用高層的概念（青年、中年、老年）來代替底層的屬性值（實際的年齡）來歸約數據數據數值的離散化和概念分層生成分箱（Binning）分箱技術遞歸的用于結果劃分，可以產生概念分層Top-downsplit,unsupervised,直方圖分析直方圖分析方法遞歸用于每一部分，可以自動的產生多級概念分層Top-downsplit,unsupervised聚類分析將數據劃分成簇，每個簇形成同一個概念層上的一個節點，每個簇可再分成多個簇，形成子節點Eithertop-downsplitorbottom-upmerge,unsupervised基于熵的離散化supervised,top-downsplit通過自然劃分分段top-downsplit,unsupervisedEntropy-BasedDiscretizationGivenasetofsamplesS,ifSispartitionedintotwointervalsS1andS2usingboundaryT,theinformationgainI(S,T)afterpartitioningisTheboundarythatmaximizestheinformationgainoverallp