第2章 數(shù)據(jù)預處理

Chapter2:DataPreprocessingWhypreprocessthedata?(數(shù)據(jù)預處理的必要性）Descriptivedatasummarization（描述性數(shù)據(jù)匯總）Datacleaning（數(shù)據(jù)清洗）Dataintegrationandtransformation（數(shù)據(jù)集成和轉(zhuǎn)換）Datareduction（數(shù)據(jù)規(guī)約）Discretizationandconcepthierarchygeneration（數(shù)值離散化和概念分層）Summary（小結(jié)）第二章數(shù)據(jù)預處理

2.1預處理的必要性

目前，數(shù)據(jù)挖掘的研究工作大都集中在算法的探討而忽視對數(shù)據(jù)處理的研究。事實上，數(shù)據(jù)預處理對數(shù)據(jù)挖掘十分重要，一些成熟的算法對其處理的數(shù)據(jù)集合都有一定的要求：比如數(shù)據(jù)的完整性好，冗余性小，屬性的相關(guān)性小等。數(shù)據(jù)預處理是數(shù)據(jù)挖掘的重要一環(huán)，而且必不可少。要使挖掘算法挖掘出有效的知識，必須為其提供干凈，準確，簡潔的數(shù)據(jù)。然而，實際應用系統(tǒng)中收集的數(shù)據(jù)通常是“臟”數(shù)據(jù)

1、雜亂性

如性別：

A數(shù)據(jù)庫male=1,female=2B數(shù)據(jù)庫

male=‘男’，female=‘女’

C數(shù)據(jù)庫

male=‘M’,female=‘F’2、重復性

同一客觀事物在數(shù)據(jù)庫中存在兩個以上相同的物理描述假設(shè)某周刊有100000個訂戶，郵件列表中0.1%的記錄是重復的，主要是一個名字有不同的寫法

JonDoe和JohnDoe

因此，每周需要印刷和郵寄100份額外的刊物，假設(shè)每周的郵寄和印刷費用是兩圓，公司每年將浪費10000元以上3、不完整性

由于實際系統(tǒng)設(shè)計時存在的缺陷以及使用過程中的一些人為因素，數(shù)據(jù)記錄可能會出現(xiàn)數(shù)據(jù)值的丟失或不確定，原因可能有：（1）有些屬性的內(nèi)容有時沒有（家庭收入，參與銷售事物數(shù)據(jù)中的顧客信息）（2）有些數(shù)據(jù)當時被認為是不必要的（3）由于誤解或檢測設(shè)備失靈導致相關(guān)數(shù)據(jù)沒有記錄下來（4）與其它記錄內(nèi)容不一致而被刪除（5）忽略了歷史數(shù)據(jù)或?qū)?shù)據(jù)的修改4、噪聲數(shù)據(jù)

數(shù)據(jù)中存在著錯誤或異常（偏離期望值），血壓和身高為0就是明顯的錯誤，當數(shù)據(jù)缺失且用默認值來填充缺失項時，很容易發(fā)生這類錯誤。（1）數(shù)據(jù)采集設(shè)備有問題（2）數(shù)據(jù)錄入過程中發(fā)生了人為或計算機錯誤（3）傳輸過程中發(fā)生錯誤4.2數(shù)據(jù)預處理的功能

數(shù)據(jù)清理（清洗）

------可以去掉數(shù)據(jù)中的噪聲，糾正不一致

數(shù)據(jù)集成

-----將多個數(shù)據(jù)源合并成一致的數(shù)據(jù)存儲，構(gòu)成一個完整的數(shù)據(jù)集，如數(shù)據(jù)倉庫或數(shù)據(jù)立方體

數(shù)據(jù)變換（轉(zhuǎn)換）---將一種格式的數(shù)據(jù)轉(zhuǎn)換為另一格式的數(shù)據(jù)(如規(guī)范化)

數(shù)據(jù)歸約（消減）----可以通過聚集、刪除冗余特性或聚類等方法來壓縮數(shù)據(jù)

這里需要指出的是：上述的各種數(shù)據(jù)預處理方法，并不是相互獨立的，而是相互關(guān)聯(lián)的，如消除數(shù)據(jù)冗余既可以看成是一種形式的數(shù)據(jù)清洗，也可以看成是一種數(shù)據(jù)消減。Chapter2:DataPreprocessing2.1Whypreprocessthedata?2.2Descriptivedatasummarization2.3Datacleaning2.4Dataintegrationandtransformation2.5Datareduction2.6DiscretizationandconcepthierarchygenerationSummaryMiningDataDescriptive

CharacteristicsMotivationTobetterunderstandthedata:centraltendency,variationandspreadDatadispersioncharacteristics

median,max,min,quantiles,outliers,variance,etc.NumericaldimensionscorrespondtosortedintervalsDatadispersion:analyzedwithmultiplegranularitiesofprecisionBoxplotorquantileanalysisonsortedintervalsDispersionanalysisoncomputedmeasuresFoldingmeasuresintonumericaldimensionsBoxplotorquantileanalysisonthetransformedcubeMeasuringtheCentralTendency

（度量數(shù)據(jù)的中心趨勢）Mean(algebraicmeasure)(samplevs.population):Weightedarithmeticmean:Trimmedmean:choppingextremevaluesMedian:Aholisticmeasure(中值，整體度量）Middlevalueifoddnumberofvalues,oraverageofthemiddletwovaluesotherwiseEstimatedbyinterpolation(forgroupeddata):Mode（眾數(shù)）ValuethatoccursmostfrequentlyinthedataUnimodal,bimodal,trimodalEmpiricalformula:P2

Symmetricvs.SkewedData

對稱的和傾斜的數(shù)據(jù)Median,meanandmodeofsymmetric,positivelyandnegativelyskeweddataMeasuringtheDispersionofData

度量數(shù)據(jù)的離散程度Quartiles,outliersandboxplots（四分位數(shù)、離散點和盒圖）Quartiles:Q1(25thpercentile),Q3(75thpercentile)Inter-quartilerange:IQR=Q3–

Q1Fivenumbersummary:min,Q1,M,

Q3,maxBoxplot:endsoftheboxarethequartiles,medianismarked,whiskers,andplotoutlierindividuallyOutlier:usually,avaluehigher/lowerthan1.5xIQRVarianceandstandarddeviation(sample:

s,population:σ)（方差和標準差）Variance:(algebraic,scalablecomputation)Standarddeviations(orσ)isthesquarerootofvariances2(or

σ2)PropertiesofNormalDistributionCurve

正態(tài)分布特性Thenormal(distribution)curveFromμ–σtoμ+σ:containsabout68%ofthemeasurements(μ:mean,σ:standarddeviation)

Fromμ–2σtoμ+2σ:containsabout95%ofitFromμ–3σtoμ+3σ:containsabout99.7%ofit

BoxplotAnalysisFive-numbersummaryofadistribution:Minimum,Q1,M,Q3,MaximumBoxplotDataisrepresentedwithaboxTheendsoftheboxareatthefirstandthirdquartiles,i.e.,theheightoftheboxisIRQThemedianismarkedbyalinewithintheboxWhiskers:twolinesoutsidetheboxextendtoMinimumandMaximumVisualizationofDataDispersion:BoxplotAnalysisHistogramAnalysisGraphdisplaysofbasicstatisticalclassdescriptionsFrequencyhistogramsAunivariategraphicalmethodConsistsofasetofrectanglesthatreflectthecountsorfrequenciesoftheclassespresentinthegivendataP36QuantilePlot（分位數(shù)圖）Displaysallofthedata(allowingtheusertoassessboththeoverallbehaviorandunusualoccurrences)Plotsquantile

informationForadataxi

datasortedinincreasingorder,fi

indicatesthatapproximately100fi%ofthedataarebeloworequaltothevaluexiP37Quantile-Quantile(Q-Q)PlotGraphsthequantilesofoneunivariatedistributionagainstthecorrespondingquantilesofanotherAllowstheusertoviewwhetherthereisashiftingoingfromonedistributiontoanotherP38Scatterplot（散點圖）Providesafirstlookatbivariatedatatoseeclustersofpoints,outliers,etcEachpairofvaluesistreatedasapairofcoordinatesandplottedaspointsintheplaneLoessCurve（Loess曲線）AddsasmoothcurvetoascatterplotinordertoprovidebetterperceptionofthepatternofdependenceLoesscurveisfittedbysettingtwoparameters:asmoothingparameter,andthedegreeofthepolynomialsthatarefittedbytheregressionPositivelyandNegativelyCorrelatedData

正相關(guān)和負相關(guān)NotCorrelatedDataGraphicDisplaysofBasicStatisticalDescriptionsHistogram:(shownbefore)Boxplot:(coveredbefore)Quantileplot:eachvaluexi

ispairedwithfi

indicatingthatapproximately100fi

%ofdataare

xi

Quantile-quantile(q-q)plot:graphsthequantilesofoneunivariantdistributionagainstthecorrespondingquantilesofanotherScatterplot:eachpairofvaluesisapairofcoordinatesandplottedaspointsintheplaneLoess(localregression)curve:addasmoothcurvetoascatterplottoprovidebetterperceptionofthepatternofdependence2.3數(shù)據(jù)清理（清洗）數(shù)據(jù)清理完成:

填充空缺的值識別孤立點消除噪聲糾正數(shù)據(jù)中的不一致

數(shù)據(jù)清理可以分為有監(jiān)督和無監(jiān)督兩類

有監(jiān)督過程是在領(lǐng)域?qū)＜抑笇拢治鍪占臄?shù)據(jù)，去除明顯錯誤的噪聲數(shù)據(jù)和重復記錄，填補缺省數(shù)據(jù)；

無監(jiān)督過程是用樣本數(shù)據(jù)訓練算法，使其獲得一定的經(jīng)驗，并在以后的處理過程中自動采用這些經(jīng)驗完成數(shù)據(jù)清洗工作。一、遺漏數(shù)據(jù)的處理

(1)忽略該元組若一條記錄中有屬性值被遺漏了，則將該記錄排除在數(shù)據(jù)挖掘之外；尤其當類標號缺少時通常這樣做（假定挖掘任務涉及分類或描述)。當每個屬性缺少值的百分比變化很大時，它的性能非常差。

(2)人工填寫空缺值當數(shù)據(jù)集很大、缺少很多值時，該方法可能行不通。(3)使用一個全局常量填充空缺值(4)使用屬性的平均值填充空缺值將空缺的屬性值用同一個常數(shù)(如“Unknown”或)替換。如果空缺值都用“Unknown”替換，當空缺值較多時。挖掘程序可能誤以為它們形成了一個有趣的概念，因為它們都具有相同的值——“Unknown”。因此，盡管該方法簡單，我們并不推薦它。例如，假定AllElectronics顧客的平均收入為$28000，則使用該值替換income中的空缺值(5)利用同類別均值填補遺漏數(shù)據(jù)例如，如果將顧客按creditrisk分類，則用具有相同信用度的顧客的平均收入替換income中的缺值(6)使用最可能的值填充空缺值可以利用回歸、貝葉斯計算公式或判定樹歸納確定，推斷出該條記錄特定屬性最大可能的取值。例如，利用數(shù)據(jù)集中其他顧客的屬性，可以構(gòu)造一棵判定樹，來預測income的空缺值。二、噪聲數(shù)據(jù)噪聲(noise)是一個測量變量中的隨機錯誤或偏差。給定一個數(shù)值屬性，例如price，我們怎樣才能平滑數(shù)據(jù)，去掉噪聲?

(1)分箱(binning)

分箱方法通過考察“鄰居”(即周圍的值)來平滑存儲數(shù)據(jù)的值。存儲的值被分布到一些“桶”或箱中。由于分箱方法參考相鄰的值，因此它進行局部平滑。下圖展示示了一些分箱技術(shù)。

在該例中，price數(shù)據(jù)首先被劃分并存人等深的箱中(深度3)。對于按箱平均值平滑，箱中每一個值被箱中的平均值替換。例如，箱1中的值4，8和15的平均值是9；這樣，該箱中的每一個值被替換為9。類似地，可以使用按箱中值平滑。此時，箱中的每一個值被箱中的中值替換。對于按箱邊界平滑，箱中的最大和最小值被視為箱邊界。箱中的每一個值被最近的邊界值替換。

(2)聚類(clustering)

通過聚類分析可以檢測孤立點，聚類將類似的值組織成群或“聚類”。直觀地看，落在聚類集合之外的值被視為孤立點(3)計算機和人工檢查結(jié)合

可以通過計算機和人工檢查結(jié)合的辦法來識別孤立點。

(4)回歸(regression)

可以利用擬合函數(shù)(如回歸函數(shù))來平滑數(shù)據(jù)。

如線性回歸涉及找出適合兩個變量的“最佳”直線，使得一個變量能夠預測另一個。多線性回歸是線性回歸的擴展，它涉及多于兩個變量，數(shù)據(jù)要適合一個多維面。使用回歸，找出適合數(shù)據(jù)的數(shù)學方程式，能夠幫助消除噪聲。Regressionxyy=x+1X1Y1Y1’

許多數(shù)據(jù)平滑的方法也是涉及離散化的數(shù)據(jù)歸約方法。例如，上面介紹的分箱技術(shù)減少了每個屬性的不同值的數(shù)量。概念分層是一種數(shù)據(jù)離散化形式，也可以用于數(shù)據(jù)平滑。例如，price的概念分層可以把price的值映射到inexpensive，moderately_priced和expensive，從而減少了挖掘過程所處理的值的數(shù)量。

2.4

數(shù)據(jù)集成和變換一、數(shù)據(jù)集成

它需要統(tǒng)一原始數(shù)據(jù)中的所有矛盾之處，如字段的:

同名異義、異名同義、單位不統(tǒng)一字長不一致，從而把原始數(shù)據(jù)在最低層上加以轉(zhuǎn)換，提煉和集成。

1、模式集成數(shù)據(jù)分析者或計算機如何才能確信一個數(shù)據(jù)庫中的customer_id和另一個數(shù)據(jù)庫中的cust_number指的是同一實體？通常，數(shù)據(jù)庫和數(shù)據(jù)倉庫有元數(shù)據(jù)——關(guān)于數(shù)據(jù)的數(shù)據(jù)。這種元數(shù)據(jù)可以幫助避免模式集成中的錯誤。2、冗余問題一個屬性是冗余的，如果它能由另一個表“導出”，如年薪屬性；命名的不一致也可能導致數(shù)據(jù)集中的冗余有些冗余可以被相關(guān)分析檢測到。例如，給定兩個屬性，根據(jù)可用的數(shù)據(jù)，這種分析可以度量一個屬性能在多大程度上蘊含另一個。屬性A和B之間的相關(guān)性可用下式度量：其中，n是元組個數(shù)，分別是A和B的平均值，分別是A和B的標準差。

如果(2.1)式的值大于0，則A和B是正相關(guān)的，意味A的值隨B的值增加而增加。該值越大，一個屬性蘊涵另一個的可能性越大。因此，一個很大的值表明A(或B)可以作為冗余而被去掉。如果結(jié)果等于0，則A和B是獨立的，它們之間不相關(guān)。如果結(jié)果值小于0，則A和B是負相關(guān)的，一個值隨另一個減少而增加。

(2．1)式可以用來檢測上面的的customer_id和cust_number的相關(guān)性。3、數(shù)據(jù)值沖突的檢測與處理

表示不同導致數(shù)據(jù)沖突語義不同導致數(shù)據(jù)沖突

對于現(xiàn)實世界的同一實體，來自不同數(shù)據(jù)源的屬性值可能不同。這可能是因為表示、比例或編碼不同。例如，重量屬性可能在一個系統(tǒng)中以公制單位存放，而在另一個系統(tǒng)中以英制單位存放。不同旅館的價格不僅可能涉及不同的貨幣，而且可能涉及不同的服務(如免費早餐)和稅。數(shù)據(jù)這種語義上的異種性，是數(shù)據(jù)集成的巨大挑戰(zhàn)。仔細將多個數(shù)據(jù)源中的數(shù)據(jù)集成起來，能夠減少或避免結(jié)果數(shù)據(jù)集中數(shù)據(jù)的冗余和不一致性。這有助于提高其后挖掘的精度和速度。另外，在數(shù)據(jù)集成中還應考慮數(shù)據(jù)類型的選擇問題，如在值域范圍內(nèi)應盡量用tinyint代替int,可大大減少字節(jié)數(shù)，對于大規(guī)模數(shù)據(jù)集來說將會大大減少系統(tǒng)開銷。二、數(shù)據(jù)變換-----數(shù)據(jù)變換將數(shù)據(jù)轉(zhuǎn)換成適合于挖掘的形式。主要是找到數(shù)據(jù)的特征表示，對數(shù)據(jù)進行規(guī)格化處理。用維變換或轉(zhuǎn)換方式減少有效變量的數(shù)目或找到數(shù)據(jù)的不變式

（1）平滑(smoothing)

去掉數(shù)據(jù)中的噪聲。這種技術(shù)包括分箱（Bin)、聚類和回歸。

（2）聚集對數(shù)據(jù)進行匯總和聚集例如，可以聚集日銷售數(shù)據(jù)，計算月和年銷售額。這一步用來為多粒度數(shù)據(jù)分析構(gòu)造數(shù)據(jù)立方體。

(3)數(shù)據(jù)概化使用概念分層，用高層次概念替換低層次“原始”數(shù)據(jù)。例如，分類的屬性，如street，可以概化為較高層的概念，如city或country。類似地，數(shù)值屬性，如age映射到較高層概念，如young，middle-age和senior。

(4)規(guī)范化(規(guī)格化）

將屬性數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間，如-1．0到1．0或0.0到1.0。如學生成績GINT（G/10）規(guī)格化的目的是將一個屬性取值范圍影射到一個特定范圍之內(nèi)，以消除數(shù)值性屬性因大小不一而造成挖掘結(jié)果的偏差在正式進行數(shù)據(jù)挖掘之前，尤其是使用基于對象距離的挖掘算法時，必須進行數(shù)據(jù)的規(guī)格化。如對于一個顧客信息數(shù)據(jù)庫中年齡屬性或工資屬性，由于工資屬性的取值比年齡屬性的取值要大得多，若不進行規(guī)格化處理，基于工資屬性的距離計算值將遠遠超過基于年齡屬性的計算值，這就意味著工資屬性的作用在整個數(shù)據(jù)對象的距離計算中被錯誤放大了①最小-最大規(guī)范化對原始數(shù)據(jù)進行線性變換。假定minA，和maxA分別為屬性A的最小和最大值。最小—最大規(guī)范化通過計算

將屬性A的一個值v影射到v’[new_minA,new-maxA](3.2)EX1

假定屬性income的最小與最大值分別為$12000和$98000。我們想映射income到區(qū)間[0，1]。根據(jù)最小-最大規(guī)范化，income值$73000將變換為②Z-score規(guī)范化（或零-均值規(guī)范化）該方法是根據(jù)屬性A的平均值和標準差規(guī)范化。A的值v被規(guī)范化為v’，由下式計算：(3.3)EX2假定屬性income的平均值和標準差分別為$54000和$16000。使用z-score規(guī)范化，值$73600被轉(zhuǎn)化為③小數(shù)定標規(guī)范化(十基數(shù)變換）通過移動屬性A的小數(shù)點位置進行規(guī)范化。小數(shù)點的移動位數(shù)依賴于A的最大絕對值。

A的值v被規(guī)范化為，由下式計算其中，j是使max(|v’|<1)成立最小整數(shù)。

EX3假定A的值由-986到917。

A的最大絕對值為986。為使用小數(shù)定標規(guī)范化，我們用1000（即j=3）除每一值。這樣，-986被規(guī)范化為-0.986。注意，規(guī)范化將原來的數(shù)據(jù)改變很多，特別是上述的后兩種方法。有必要保留規(guī)范化參數(shù)（如平均值和標準差，如果使用z-score規(guī)范化），以便將來的數(shù)據(jù)可以用一致的方式規(guī)范化。

（5）屬性構(gòu)造(或特征構(gòu)造)

可以利用已知的屬性構(gòu)造新的屬性并添加到屬性集中，以幫助挖掘過程。（由長，寬求面積）2.5數(shù)據(jù)規(guī)約（消減）

數(shù)據(jù)立方合計維數(shù)削減數(shù)據(jù)壓縮數(shù)據(jù)塊消減離散化與概念層次生成

1、數(shù)據(jù)立方體合計主要用于構(gòu)造數(shù)據(jù)立方---建立數(shù)據(jù)倉庫如對某公司三年銷售合計處理，可用一個三維數(shù)據(jù)立方體（時間，商品，部門）表示，它從三個角度描述相應時空的銷售額。每個屬性都可對應一個概念層次樹，以幫助進行多抽象層次的數(shù)據(jù)分析。2、維歸約

----主要用于檢測并刪除不相關(guān)、弱相關(guān)或冗余的屬性維。用于數(shù)據(jù)分析的數(shù)據(jù)可能包含數(shù)以百計的屬性，其中大部分屬性與挖掘任務不相關(guān)，是冗余的。例如，如果分析任務是按顧客聽到廣告后，是否愿意在A11E1ectronics買流行的新款CD將顧客分類，與屬性age，music_tasfe不同，諸如顧客的電話號碼等屬性多半是不相關(guān)的。

屬性子集選擇的目標是找出最小屬性子集，使得數(shù)據(jù)類的概率分布盡可能地接近原分布。

“如何找出原屬性的一個‘好的’子集?”d個屬性有2d個可能的子集。窮舉搜索找出屬性的最佳子集可能是不現(xiàn)實的，特別是當d和數(shù)據(jù)類的數(shù)目增加時。

因此，對于屬性子集選擇，通常使用壓縮搜索空間的啟發(fā)式算法。它們的策略是做局部最優(yōu)選擇，期望由此導致全局最優(yōu)解。

(1)逐步向前選擇(逐步添加方法）：該過程由空屬性集開始，選擇原屬性集中最好的屬性，并將它添加到該集合中。在其后的每一次迭代，將原屬性集剩下的屬性中的最好的屬性添加到該集合中。如遺傳算法遺傳算法是一種基于生物進化論和分子遺傳學的全局隨機搜索算法。

(2)逐步向后刪除(逐步消減方法）：該過程由整個屬性集開始。在每一步，刪除掉在屬性集中的最壞屬性。直到無法選擇出最壞屬性或滿足一定的閾值為止。

如粗集理論不需要先驗知識；

算法簡單，易于操作，可有效地去除冗余屬性，對于每個屬性值域出現(xiàn)的冗余現(xiàn)象，也可用粗集理論刪除，從而使條件屬性的個數(shù)和取值得到化減。其基本思路是：利用定義的數(shù)據(jù)集合U上的等價關(guān)系對U進行劃分，對于數(shù)據(jù)表來說，這種等價關(guān)系可以是某個屬性，或者是幾個屬性的集合。因此，按照不同屬性的組合就把數(shù)據(jù)表劃分成不同的基本類，在這些基本類的基礎(chǔ)上進一步求得最小約簡集。(3)向前選擇和向后刪除的結(jié)合：向前選擇和向后刪除方法可以結(jié)合在一起，每一步選擇一個最好的屬性，并在剩余屬性中刪除一個最壞的屬性。

(4)判定樹歸納

判定樹算法，如ID3和C4．5最初是用于分類的,也可用于構(gòu)造屬性子集利用決策樹的歸納方法對初始數(shù)據(jù)進行分類歸納學習，獲得一個初始決策樹，所有沒出現(xiàn)在這個樹上的屬性均認為是無關(guān)屬性，刪除無關(guān)屬性之后，就可獲得一個較優(yōu)的屬性子集。3、數(shù)據(jù)壓縮數(shù)據(jù)壓縮使用數(shù)據(jù)編碼或數(shù)據(jù)轉(zhuǎn)換機制壓縮數(shù)據(jù)集。若根據(jù)壓縮后的數(shù)據(jù)集可以恢復原來的數(shù)據(jù)集-----無損（loseless)若根據(jù)壓縮后的數(shù)據(jù)集不能恢復原來的數(shù)據(jù)集-----有損(lossy)常用的有小波變換和主要素分析

離散小波變換是一種線形信號處理技術(shù)，可將一個向量D轉(zhuǎn)換為D’（為小波相關(guān)系數(shù)）為提高數(shù)據(jù)運算處理的效率，可以保留用戶指定閾值的小波系數(shù)，而將其他小波系數(shù)置0。小波變換可以保留數(shù)據(jù)的主要特征情況下除去數(shù)據(jù)中的噪聲。應用小波變換進行數(shù)據(jù)轉(zhuǎn)換時，通常采用通用層次算法：(1)L為所輸入數(shù)據(jù)向量的長度，它必須是2的冪(2)每次轉(zhuǎn)換使用兩個函數(shù)，第一個負責初步平滑，第二個完成帶權(quán)差值計算以獲得數(shù)據(jù)的主要特征。(3)將數(shù)據(jù)向量一分為二，應用(2)中的兩個函數(shù)分別處理低頻、高頻數(shù)據(jù)(4)對所輸入的向量循環(huán)使用(3)中的處理步驟，直到所有劃分的子數(shù)據(jù)向量的長度均為2為止(5)取出(3),(4)步驟處理結(jié)果便獲得被轉(zhuǎn)換數(shù)據(jù)向量的小波相關(guān)系數(shù)。4、數(shù)據(jù)塊消減------利用更簡單的數(shù)據(jù)表達形式

參數(shù)與非參數(shù)兩種方法參數(shù)方法是通過模型計算獲得原來的數(shù)據(jù)，只要存儲模型的參數(shù)即可非參數(shù)方法是指存儲利用直方圖、聚類或采樣而獲得的消減后的數(shù)據(jù)直方圖（等寬，等高）采樣（隨機，聚類，分類）5離散化和概念分層生成

離散化技術(shù)通過將屬性域劃分為區(qū)間來減少給定連續(xù)屬性值的個數(shù)。區(qū)間的標號可以替代實際的數(shù)據(jù)值。概念層次樹可以通過利用較高層次概念替換較低層次概念而減少原來的數(shù)據(jù)。

對于用戶或領(lǐng)域?qū)＜?，人工地定義概念分層可能是一項令人乏味、耗時的任務。幸而，許多分層蘊涵在數(shù)據(jù)庫模式中，并且可以在模式定義級定義。概念分層常常自動地產(chǎn)生，或根據(jù)數(shù)據(jù)分布的統(tǒng)計分析動態(tài)地加以提煉。

數(shù)值數(shù)據(jù)的離散化和概念分層生成數(shù)值屬性的概念分層可以根據(jù)數(shù)據(jù)分布分析自動地構(gòu)造。分箱

通過將數(shù)據(jù)分布到箱中，并用箱中的平均值或中值替換箱中的每個值，可以將屬性值離散化。就像用箱的平均值平滑或用箱的中值平滑一樣。這些技術(shù)可以遞歸地作用于結(jié)果劃分，產(chǎn)生概念分層。

直方圖分析直方圖也可以用于離散化.下面給出了一個直方圖，顯示某給定數(shù)據(jù)集price屬性的數(shù)據(jù)分布。例如，頻率最高的價格大約在$300—$325?？梢允褂脛澐忠?guī)則定義值的范圍。例如，在等寬直方圖中，將值劃分成相等的部分或區(qū)間(如($0…S100)，($100…$200)，…，($900…S1000)。在等深直方圖中，值被劃分使得每一部分包括相同個數(shù)的樣本。聚類算法可以用來將數(shù)據(jù)劃分成簇或群。每一個簇形成概念分層的一個節(jié)點，而所有的節(jié)點在同一概念層。每一個簇可以進一步分成若干子簇，形成較低的概念層。簇也可以聚集在一起，以形成分層結(jié)構(gòu)中較高的概念層。

基于熵的離散化

熵(entropy)，可以用來遞歸地劃分數(shù)值屬性A的值，產(chǎn)生分層的離散化,形成屬性的數(shù)值概念分層。給定一個數(shù)據(jù)元組的集合S，基于熵對A離散化的方法如下：1)A的每個值可以認為是一個潛在的區(qū)間邊界或閾值T。例如，A的值v可以將樣本劃分成分別滿足條件A<T和A>T的兩個子集,這樣就創(chuàng)建了一個二元離散化。2)給定S，所選擇的閾值是這樣的值，它使其后劃分得到的信息增益最大。信息增益(informationgain)是

其中，S1，S2分別對應于S中滿足條件A<T和A>T的樣本。對它的熵函數(shù)Ent根據(jù)集合中樣本的類分布來計算。例如，給定m個類，它的熵是3)確定閾值的過程遞歸地用于所得到的每一個劃分，直到滿足某個終止條件，如

基于熵的離散化可以壓縮數(shù)據(jù)量。與迄今為止提到的其他方法不同，基于熵的離散化使用類信息，有助于提高分類的準確性。這里介紹的信息增益和熵也用于判定樹歸納。

分類數(shù)據(jù)的概念分層生成分類數(shù)據(jù)(categoricaldata)是離散數(shù)據(jù)。一個分類屬性具有有限個(但可能很多)不同值，值之間無序。如地理位置、工作分類和商品類型。

由用戶或?qū)＜以谀Ｊ郊夛@式地說明屬性的部分序：通常，分類屬性或維的概念分層涉及一組屬性。用戶或?qū)＜以谀Ｊ郊壨ㄟ^說明屬性的部分序或全序，可以很容易地定義概念分層。例如，關(guān)系數(shù)據(jù)庫或數(shù)據(jù)倉庫的維location可能包含如下一組屬性：street，city，province_or_state，和country。可以在模式級說明一個全序，如