web數(shù)據(jù)挖掘-6數(shù)據(jù)挖掘的預(yù)處理技術(shù)

Chapter6:DataPreprocessingReview什么是數(shù)據(jù)挖掘數(shù)據(jù)挖掘的主要方法基于集合論的數(shù)據(jù)挖掘方法：關(guān)聯(lián)分析基于信息論的數(shù)據(jù)挖掘方法：決策樹Moretocome..數(shù)據(jù)挖掘的步驟三部曲數(shù)據(jù)準(zhǔn)備數(shù)據(jù)選擇：目標(biāo)數(shù)據(jù)數(shù)據(jù)預(yù)處理：

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

數(shù)據(jù)變換：連續(xù)數(shù)據(jù)離散化，數(shù)據(jù)轉(zhuǎn)化

數(shù)據(jù)歸約：特征選擇和抽取數(shù)據(jù)挖掘結(jié)果的解釋評(píng)估數(shù)據(jù)的預(yù)處理為什么要進(jìn)行預(yù)處理數(shù)據(jù)清理：60%的工作量數(shù)據(jù)集成數(shù)據(jù)變換數(shù)據(jù)歸約數(shù)據(jù)離散化為什么要預(yù)處理數(shù)據(jù)現(xiàn)實(shí)世界的數(shù)據(jù)是“骯臟的”–數(shù)據(jù)多了什么問題都會(huì)出現(xiàn)不完整的：有些感興趣的屬性缺少屬性值e.g.,occupation=“”含噪聲的：包含錯(cuò)誤的，或者孤立點(diǎn)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數(shù)據(jù)質(zhì)量的多維度量一個(gè)廣為認(rèn)可的多維度量觀點(diǎn)精確度完整度一致性可信度附加價(jià)值可訪問性根數(shù)據(jù)本身的含義相關(guān)的Intrinsic,contextual,representational,andaccessibility數(shù)據(jù)預(yù)處理的主要任務(wù)數(shù)據(jù)清理填寫空缺的值，平化噪聲數(shù)據(jù)，識(shí)別、刪除孤立點(diǎn)，消除不一致性數(shù)據(jù)集成集成多個(gè)數(shù)據(jù)庫、數(shù)據(jù)立方體或文件數(shù)據(jù)變換規(guī)范化和聚集數(shù)據(jù)歸約得到數(shù)據(jù)集的壓縮表示，它小得多，但可以得到相同或近似的結(jié)果數(shù)據(jù)離散化數(shù)據(jù)歸約的一部分，通過概念分層和數(shù)據(jù)的離散化來規(guī)約數(shù)據(jù)，對(duì)數(shù)字型數(shù)據(jù)特別重要FormsofDataPreprocessing

10數(shù)據(jù)的預(yù)處理為什么要進(jìn)行預(yù)處理數(shù)據(jù)清理：60%的工作量數(shù)據(jù)集成數(shù)據(jù)變換數(shù)據(jù)歸約數(shù)據(jù)離散化空缺值數(shù)據(jù)并不總是完整的E.g.數(shù)據(jù)庫表中，很多條記錄的對(duì)應(yīng)字段沒有相應(yīng)值，比如銷售表中的顧客收入引起空缺值的原因設(shè)備異常與其他已有的數(shù)據(jù)不一致而被刪除因?yàn)檎`解而沒有被輸入的數(shù)據(jù)對(duì)數(shù)據(jù)的改變沒有進(jìn)行日志記載如何處理空缺值忽略元組：當(dāng)類標(biāo)號(hào)缺少時(shí)通常會(huì)這么做人工填寫空缺值：工作量大，可行性低使用一個(gè)全局變量填充空缺值：如unknown,N/Aminingroutinesmaymistakenlythinkthefilledvalueformaninterestingconcept使用屬性的平均值填充空缺值使用與給定元組屬同一類的所有樣本的平均值使用最可能的值填充空缺值：使用像Bayesian公式或判定樹這樣的基于推斷的方法smarterstrategy,whichusesthemostinformationcontainedinthepresentdataHowtoHandleMissingData?AgeIncomeReligionGender2324,200MuslimM39?ChristianF4545,390?F??Fillmissingvaluesusingaggregatefunctions(e.g.,average)orprobabilisticestimatesonglobalvaluedistributionE.g.,puttheaverageincomehere,orputthemostprobableincomebasedonthefactthatthepersonis39yearsoldE.g.,putthemostfrequentreligionhere噪聲數(shù)據(jù)噪聲：一個(gè)測量變量中的隨機(jī)錯(cuò)誤或偏差引起不正確屬性值的原因數(shù)據(jù)收集工具的問題數(shù)據(jù)輸入錯(cuò)誤數(shù)據(jù)傳輸錯(cuò)誤技術(shù)限制命名規(guī)則的不一致其他需要數(shù)據(jù)清理的數(shù)據(jù)問題重復(fù)紀(jì)錄不完整的數(shù)據(jù)不一致的數(shù)據(jù)如何處理噪聲數(shù)據(jù)分箱（Binning）首先排序，并將他們分到等深的箱中然后可以按箱的平均值平滑，按箱中值平滑，按箱的邊界平滑等聚類檢測并且去除孤立點(diǎn)計(jì)算機(jī)和人工檢查結(jié)合計(jì)算機(jī)檢測可疑數(shù)據(jù)，然后對(duì)他們進(jìn)行人工判斷回歸通過讓數(shù)據(jù)適應(yīng)回歸函數(shù)來平滑數(shù)據(jù)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:數(shù)據(jù)平滑的分箱方法Price的排序后數(shù)據(jù)：4,8,15,21,21,24,25,28,34劃分為（等深的）箱箱14815箱2212124箱3252834平滑方法用箱的平均值平滑箱1999箱2222222箱3292929用箱邊界平滑箱14415箱2212124箱3252534劃分為（等深的）箱箱14815箱2212124箱3252834聚類消除噪聲分析查找孤立點(diǎn)回歸消除噪音通過構(gòu)造函數(shù)來符合數(shù)據(jù)變化的趨勢，這樣可以用一個(gè)變量預(yù)測另一個(gè)變量線性回歸非線性回歸xyy=x+1X1Y1Y1’數(shù)據(jù)的預(yù)處理為什么要進(jìn)行預(yù)處理數(shù)據(jù)清理：60%的工作量數(shù)據(jù)集成數(shù)據(jù)變換數(shù)據(jù)歸約數(shù)據(jù)離散化數(shù)據(jù)集成數(shù)據(jù)集成功能：將來自不同數(shù)據(jù)源的數(shù)據(jù)整合成一致的數(shù)據(jù)存儲(chǔ)。元數(shù)據(jù)、相關(guān)分析、數(shù)據(jù)沖突檢測和語義異種性的解析都有助于數(shù)據(jù)集成。問題和解決辦法：問題1：模式集成來自多個(gè)信息源的現(xiàn)實(shí)世界的實(shí)體如何“匹配”？--實(shí)體識(shí)別問題E.g.,數(shù)據(jù)分析者或計(jì)算機(jī)如何才能確信一個(gè)數(shù)據(jù)庫中的customer_id和另一個(gè)數(shù)據(jù)庫中的cust_number指的是同一個(gè)實(shí)體？E.g.familynamevs.surname解決方法：利用數(shù)據(jù)庫的元數(shù)據(jù)--一種關(guān)于數(shù)據(jù)的數(shù)據(jù)。這種元數(shù)據(jù)可以幫助避免模式集成中的錯(cuò)誤。問題2：冗余一個(gè)屬性若能由另一個(gè)表導(dǎo)出，它便是冗余的。例如年薪。屬性或維命名的不一致也可能導(dǎo)致數(shù)據(jù)集中的冗余。解決方法：可利用相關(guān)分析的方法檢測冗余。除了檢測屬性間的冗余外，“重復(fù)”也當(dāng)在元組級(jí)進(jìn)行檢測。所謂重復(fù)是指對(duì)于同一數(shù)據(jù)，存在兩個(gè)或多個(gè)相同的元組。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：數(shù)據(jù)值沖突的檢測和處理對(duì)于現(xiàn)實(shí)世界的同一實(shí)體，來自不同數(shù)據(jù)源的屬性值可能不同。這可能是因?yàn)楸硎尽⒈壤蚓幋a的不同。例如重量屬性可能在一個(gè)系統(tǒng)中以公制單位存放，而在另一個(gè)系統(tǒng)中以英制單位存放。數(shù)據(jù)這種語義上的異種性，是數(shù)據(jù)集成的巨大挑戰(zhàn)。數(shù)據(jù)的預(yù)處理為什么要進(jìn)行預(yù)處理數(shù)據(jù)清理：60%的工作量數(shù)據(jù)集成數(shù)據(jù)變換數(shù)據(jù)歸約數(shù)據(jù)離散化數(shù)據(jù)變換數(shù)據(jù)變換將數(shù)據(jù)轉(zhuǎn)換成適合挖掘的形式。平滑：去掉數(shù)據(jù)中的噪聲。這種技術(shù)包括分箱、聚類和回歸。聚集：對(duì)數(shù)據(jù)進(jìn)行匯總和聚集。例如可以聚集日銷售數(shù)據(jù)，計(jì)算年銷售額。通常這一步用來為多粒度數(shù)據(jù)分析構(gòu)造數(shù)據(jù)立方體。數(shù)據(jù)變換數(shù)據(jù)概化：使用概念分層，用高層次的概念替換低層次的“原始”數(shù)據(jù)。如分類的屬性street可以概化為較高層的概念，如city或country。規(guī)范化：將屬性數(shù)據(jù)按比例縮放，使之落入一個(gè)小的特定區(qū)間，如-1.0到1.0或0.0到1.0最小----最大規(guī)范化：對(duì)原始數(shù)據(jù)進(jìn)行線形變換。假定屬性A的最小和最大值分別為minA和maxA,計(jì)算Ex.Letincomerange$12,000to$98,000normalizedto[0.0,1.0].Then$73,000ismappedto數(shù)據(jù)變換

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

z-score規(guī)范化：屬性A的值基于A的平均值和標(biāo)準(zhǔn)差規(guī)范化，計(jì)算Ex.Letμ=54,000,σ=16,000.Then小數(shù)定標(biāo)規(guī)范化：通過移動(dòng)屬性A的小數(shù)點(diǎn)位置進(jìn)行規(guī)范化，計(jì)算數(shù)據(jù)變換屬性構(gòu)造：由給定的屬性構(gòu)造和添加新的屬性，以幫助提高精度和對(duì)高維數(shù)據(jù)結(jié)構(gòu)的理解。例如，我們可能根據(jù)屬性height和width添加屬性area。通過組合屬性，屬性構(gòu)造可以發(fā)現(xiàn)關(guān)于數(shù)據(jù)屬性間聯(lián)系的丟失信息，這對(duì)知識(shí)發(fā)現(xiàn)是有用的。數(shù)據(jù)的預(yù)處理為什么要進(jìn)行預(yù)處理數(shù)據(jù)清理：60%的工作量數(shù)據(jù)集成數(shù)據(jù)變換數(shù)據(jù)歸約數(shù)據(jù)離散化數(shù)據(jù)歸約數(shù)據(jù)倉庫中往往存有海量數(shù)據(jù)，在其上進(jìn)行數(shù)據(jù)分析與挖掘需要很長時(shí)間數(shù)據(jù)歸約數(shù)據(jù)歸約可以用來得到數(shù)據(jù)集的歸約表示，它小得多，卻可以產(chǎn)生相同的或幾乎相同的分析結(jié)果數(shù)據(jù)歸約策略數(shù)據(jù)立方體聚集：聚集操作用于數(shù)據(jù)立方體中的數(shù)據(jù)。維歸約：通過刪除不相關(guān)的屬性（或）維減少數(shù)據(jù)量。通常使用屬性子集選擇方法。數(shù)據(jù)壓縮數(shù)值歸約離散化和概念分層產(chǎn)生用于數(shù)據(jù)歸約的時(shí)間不應(yīng)當(dāng)超過或抵消歸約后的數(shù)據(jù)上挖掘節(jié)省的時(shí)間數(shù)據(jù)立方體聚集最底層的方體對(duì)應(yīng)于基本方體基本方體對(duì)應(yīng)感興趣的實(shí)體在數(shù)據(jù)立方體中存在著不同級(jí)別的匯總數(shù)據(jù)立方體可以看成方體的格每個(gè)較高層次的抽象將進(jìn)一步減少結(jié)果數(shù)量數(shù)據(jù)立方體提供了對(duì)于計(jì)算的匯總數(shù)據(jù)的快速訪問使用與給定任務(wù)相關(guān)的最小方體在可能的情況下，對(duì)于匯總數(shù)據(jù)的查詢應(yīng)當(dāng)使用數(shù)據(jù)立方體維歸約通過刪除不相干的屬性或維減少數(shù)據(jù)量屬性子集選擇目標(biāo)：找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布。優(yōu)點(diǎn)：減少了出現(xiàn)在發(fā)現(xiàn)模式上的屬性的數(shù)目，使得模式更易于理解。維歸約啟發(fā)式的方法屬性子集選擇方法包括以下技術(shù)：逐步向前選擇：由空屬性集開始，每次都選擇原屬性集中最好的屬性，將其添加到集合中。逐步向后刪除：由整個(gè)屬性集開始，在每一步，刪除掉尚在屬性集中的最壞屬性。向前選擇和向后刪除的結(jié)合：每一步選擇一個(gè)最好的屬性，并在剩余屬性中刪除一個(gè)最壞的屬性。判定樹歸納：用判定樹算法選擇“最好”的屬性，將數(shù)據(jù)劃分成類。逐步向前選擇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}向前選擇和向后刪除的結(jié)合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}數(shù)據(jù)壓縮有損壓縮vs.無損壓縮字符串壓縮有廣泛的理論基礎(chǔ)和精妙的算法通常是無損壓縮在解壓縮前對(duì)字符串的操作非常有限音頻/視頻壓縮通常是有損壓縮，壓縮精度可以遞進(jìn)選擇有時(shí)可以在不解壓整體數(shù)據(jù)的情況下，重構(gòu)某個(gè)片斷兩種有損數(shù)據(jù)壓縮的方法：小波變換和主要成分分析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數(shù)值歸約通過選擇替代的較小的數(shù)據(jù)表示形式來減少數(shù)據(jù)量有參方法：使用一個(gè)參數(shù)模型來估計(jì)數(shù)據(jù)，最后只要存儲(chǔ)參數(shù)即可線性回歸方法：無參方法：直方圖聚類選樣數(shù)據(jù)歸約：直方圖一種流行的數(shù)據(jù)歸約技術(shù)將某屬性的數(shù)據(jù)劃分成不相交的子集，或桶，桶中放置該值得出現(xiàn)頻率桶和屬性值得劃分規(guī)則等深：

equalbucketrange等寬：

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