數(shù)據(jù)挖掘概念與技術(shù)第三章

數(shù)據(jù)挖掘概念與設(shè)計第三章數(shù)據(jù)預(yù)處理3.1數(shù)據(jù)預(yù)處理3.2數(shù)據(jù)清理3.3數(shù)據(jù)集成3.4數(shù)據(jù)規(guī)約3.5數(shù)據(jù)變換與數(shù)據(jù)離散化3.6小結(jié)第三章數(shù)據(jù)預(yù)處理3.3.1為什么要對數(shù)據(jù)預(yù)處理低質(zhì)量的數(shù)據(jù)將導(dǎo)致低質(zhì)量的挖掘結(jié)果準(zhǔn)確性完整性一致性時效性

可信性可解釋性3.1數(shù)據(jù)預(yù)處理

高質(zhì)量數(shù)據(jù)3.1.2數(shù)據(jù)處理的主要任務(wù)數(shù)據(jù)清理數(shù)據(jù)集成數(shù)據(jù)歸約數(shù)據(jù)變換3.1數(shù)據(jù)預(yù)處理

現(xiàn)實世界的的數(shù)據(jù)一般是不完整的，有噪聲的和不一致性的。數(shù)據(jù)清理試圖填充缺失值，光滑噪聲、識別離群點、糾正數(shù)據(jù)中的不一致。3.2.1缺失值1）忽略元組：缺少類標(biāo)號時通常這么做。但是忽略的元組其他屬性也不能用，即便是有用的。2）人工填寫：該方法很費事費時，數(shù)據(jù)集很大、缺失值很多時可能行不通。3）使用一個全局常量填充缺失值：將缺失值的屬性用同一個常量替換。（方法簡單但不可靠）4）使用屬性的中心度量（均值、中位數(shù)）填寫缺失值：對于正常的（對稱的）數(shù)據(jù)分布，可以使用均值；對于傾斜數(shù)據(jù)（非對稱）應(yīng)該使用中位數(shù)。5）使用與給定元組同一類的所有樣本的屬性均值或中位數(shù)：利用另外一個屬性分類數(shù)據(jù)，計算缺失值的屬性值該是多少（均值或中位數(shù)）。6）使用最可能的值填充：利用回歸、貝葉斯形式化方法的基于推理的工具或決策樹歸納確定。3.2數(shù)據(jù)清理3.2.2噪聲數(shù)據(jù)噪聲：被測量的變量的隨機誤差或方差。1）分箱：排序后的數(shù)據(jù)按等頻（每個箱幾個值）分箱，

然后：

用箱均值光滑：箱中每個值都被替換為箱中的均值。

用箱中位數(shù)光滑：箱中的每一個只都被替換為該箱的中位數(shù)。

用箱邊界光滑：給定箱中的最大和最小值同樣被視為箱邊界，

箱中每個值都被替換為最接近的邊界值。2）回歸：可以用一個函數(shù)擬合數(shù)據(jù)來光滑數(shù)據(jù)。3）離群點分析：通過如聚類來檢測利群點。3.2數(shù)據(jù)清理3.2.3數(shù)據(jù)清理作為一個過程數(shù)據(jù)清理的第一步是偏差檢測。導(dǎo)致偏差的因素很多，認(rèn)為輸入錯誤、有意錯誤、數(shù)據(jù)退化（過時數(shù)據(jù)）、編碼不一致、設(shè)備錯誤、系統(tǒng)錯誤。如何進(jìn)行偏差檢測？

使用任何關(guān)于數(shù)據(jù)性質(zhì)的知識：元數(shù)據(jù)（主要是描述數(shù)據(jù)屬性（property）的信息）、數(shù)據(jù)的基本統(tǒng)計描述（均值、中位數(shù)、眾數(shù)、方差、標(biāo)準(zhǔn)差等）、唯一性規(guī)則、連續(xù)性規(guī)則、空值規(guī)則。3.2數(shù)據(jù)清理數(shù)據(jù)挖掘經(jīng)常需要數(shù)據(jù)集成——合并來自多個數(shù)據(jù)存儲的數(shù)據(jù)。3.3.1實體識別問題模式集成和對象匹配可能需要技巧，例如如何讓計算機識別customer_id和另外一個數(shù)據(jù)庫的cust_number是同一屬性？——利用元數(shù)據(jù)，每個屬性的元數(shù)據(jù)包括名字、含義、數(shù)據(jù)類型和屬性的值的允許范圍，以及處理空值的規(guī)則。這些元數(shù)據(jù)可以用來幫助避免模式集成的錯誤，還有助于變化數(shù)據(jù)3.3數(shù)據(jù)集成3.3.2冗余和相關(guān)分析

一個屬性如果能由另一個或另一組屬性“導(dǎo)出”，則這個屬性可能是冗余的；屬性或維命名的不一致也可能導(dǎo)致結(jié)果數(shù)據(jù)集的冗余。1.標(biāo)稱數(shù)據(jù)的卡方相關(guān)檢驗2.數(shù)值數(shù)據(jù)的相關(guān)系數(shù)3.數(shù)值數(shù)據(jù)的協(xié)方差3.3數(shù)據(jù)集成1.標(biāo)稱數(shù)據(jù)的卡方相關(guān)檢驗假設(shè)A有c個不同的值，a1,a2,….ac.

B有r個不同的值，b1,b2,…br.

則包含屬性A和屬性B的元組可以使用一個列聯(lián)表來表示，其中A屬性的c個不同值構(gòu)成表的列，B屬性的r個不同值構(gòu)成表的行。令(Ai,Bj)表示屬性A取ai而屬性B取bj的聯(lián)合事件，即（A=ai,B=bj).3.3數(shù)據(jù)集成

在表中每一個可能的(Ai,Bj)聯(lián)合事件都有一個單元。卡方值的公式是：其中，oij表示觀察到的（Ai,Bj)聯(lián)合事件的頻率（實際次數(shù)）。而eij表示(Ai,Bj)事件的期望頻率，計算公式是：其中，n是數(shù)據(jù)元組的個數(shù)。卡方統(tǒng)計檢驗假定屬性A和屬性B是互相獨立的，即這兩個屬性之間沒有關(guān)聯(lián)?；陲@著性水平，自由度是(r-1)*(c-1)。如果假設(shè)被拒絕，則A和B統(tǒng)計相關(guān)。3.13.2假設(shè)調(diào)查了1500個人，按性別分成男和女。每個人投票是否喜歡閱讀小說。這樣，就有了兩個屬性：gender和preferred_reading.觀察到的每個可能的聯(lián)合事件的次數(shù)在表3.1中。圓括號中的表示事件的期望次數(shù)，按照公式3.2計算出來的。可以注意到，每一行中，期望次數(shù)的總和必須和這一行的觀察次數(shù)的總和相等；每一列中，期望次數(shù)的和等于這一列的觀察次數(shù)的和。利用公式3.1，計算卡方值為：對于2*2的表，自由度為(2-1)*(2-1)=1.在自由度為1時，卡方值為10.828則可以在0.001的顯著性水平上拒絕值原假設(shè)。因為計算出的值大于這個值，所以能以更小的顯著性水平拒絕原假設(shè)，即性別和是否喜歡讀小說之間存在強相關(guān)關(guān)系。2數(shù)值數(shù)據(jù)的相關(guān)系數(shù)3.3數(shù)據(jù)集成

3.3

相關(guān)系數(shù)rAB的值在-1到+1之間。如果rAB>0，則稱A和B正相關(guān)。表示A的值隨著B的值的增大而增大。值越大，相關(guān)性越強。因此，一個很大的值意味著A（或B)需要被作為冗余刪除。

如果rAB=0,則A和B相互獨立，它們之間沒有任何關(guān)系。如果值<0,則A和B負(fù)相關(guān)，表示一個屬性的值隨著另一個值的降低而增大。散點圖可以用來可視化屬性之間的關(guān)聯(lián)關(guān)系。

注意：關(guān)聯(lián)并不表示因果。即如果A和B相關(guān)，但并不意味著A導(dǎo)致B或者B導(dǎo)致A。

例如，在分析一個人口統(tǒng)計數(shù)據(jù)庫時，我們發(fā)現(xiàn)表示醫(yī)院數(shù)目的屬性和盜車數(shù)目相關(guān)。但這并不表示一個屬性導(dǎo)致了另外一個。兩個屬性實際上都是因為人口數(shù)這第三個屬性導(dǎo)致的。3.數(shù)值數(shù)據(jù)的協(xié)方差3.3數(shù)據(jù)集成

在概率理論和統(tǒng)計學(xué)中，相關(guān)性和協(xié)方差是評價兩個屬性是否一起發(fā)生變化的兩種相似的測量?？紤]兩個數(shù)值型屬性A和B,n個觀察{(a1,b1),…(an,bn)}.屬性A和屬性B的均值，即期望值為：和則屬性A和B的協(xié)方差為：如果利用公式3.3來計算相關(guān)系數(shù)rA,B,則：其中分母是屬性A和B的標(biāo)準(zhǔn)差?？梢钥吹?，

考慮下表，這是一個觀察到的5次AllElectronics和Hightech公式的股票價格。如果股票是被同一個公司的趨勢影響，那么它們的價格是否一起漲落呢？計算均值：則協(xié)方差為：協(xié)方差值為正，因此，我們可以說兩個公司的股票是一起漲的。3.3.3元祖重復(fù)3.3數(shù)據(jù)集成

除了檢測屬性間的冗余，元組級別的冗余也需要被檢測。不規(guī)范表的使用（一般是為了避免連接提高性能）是另一種數(shù)據(jù)冗余的來源。在不同的復(fù)制之間常常產(chǎn)生不一致性。因為不精確的數(shù)據(jù)輸入或者更新了一部分而非全部的數(shù)據(jù)。

例如，一個購買訂單數(shù)據(jù)庫包含購買者的姓名和地址屬性，而非這個信息的主鍵信息。不一致性就可能產(chǎn)生，比如在購買訂單數(shù)據(jù)庫中同樣的購買者姓名卻是不同的地址。3.3.4數(shù)據(jù)值沖突的檢測與處理3.3數(shù)據(jù)集成

數(shù)據(jù)集成還包含數(shù)據(jù)值沖突的檢測和解析。例如，對于同一個真實世界實體，不同來源的屬性值可能不同?？赡苁且驗楸磉_(dá)、刻度或者編碼的不同。

比如，體重屬性在一個系統(tǒng)中可能以公制單位存放而在另一個中以英制單位存放。

學(xué)校之間交換信息的時候，每個學(xué)校有自己的課程設(shè)置和等級模式。一個大學(xué)可能采用一個季度系統(tǒng)，一個數(shù)據(jù)庫系統(tǒng)中3門課程，等級從A+到F。另一個可能采用學(xué)期值，數(shù)據(jù)庫中提供2門課程，等級從1到10.很難制定兩所大學(xué)精確的課程——等級轉(zhuǎn)換規(guī)則，交換信息很困難。3.4.1數(shù)據(jù)規(guī)約策略的概述3.4.2小波變換3.4.3主成分分析3.4.4屬性子集選擇3.4.5回歸和對數(shù)線性模型：參數(shù)化數(shù)據(jù)規(guī)約3.4.6直方圖3.4.7聚類3.4.8抽樣3.4.9數(shù)據(jù)立方體聚集3.4數(shù)據(jù)規(guī)約3.4.1數(shù)據(jù)規(guī)約策略的概述數(shù)據(jù)規(guī)約策略包括維歸約，數(shù)量規(guī)約，數(shù)據(jù)壓縮1）維歸約：減少所考慮的隨機變量或?qū)傩缘膫€數(shù)。方法有小波變換和主成分分析，它們把原數(shù)據(jù)變換或投影到較小的空間。屬性子集選擇是一種維歸約方法，其中不相關(guān)、弱相關(guān)或冗余的屬性或維被檢測和刪除。

2）數(shù)量歸約：用替代的、較小的數(shù)據(jù)表示形式替換原數(shù)據(jù)。

3）數(shù)據(jù)壓縮：使用變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。如果原數(shù)據(jù)能夠從壓縮后的數(shù)據(jù)重構(gòu)，而不損失信息，該數(shù)據(jù)歸約為無損的，近似重構(gòu)原數(shù)據(jù)稱為有損的。3.4數(shù)據(jù)規(guī)約（1）離散小波變換（DWT）：一種線性信號處理技術(shù)，用于數(shù)據(jù)向量X時，將它變成不同的數(shù)值小波系數(shù)向量X’。（2）主成分分析：（PCA）又稱K-L方法，搜索k個最能代表數(shù)據(jù)的n維正交向量，其中k<=n。（3）屬性子集選擇：通過刪除不相關(guān)或冗余的屬性（維）減少數(shù)據(jù)量。目標(biāo)是找出最小屬性集，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性得到的原分布。另外，在縮小后的屬性集上挖掘能夠減少出現(xiàn)在發(fā)現(xiàn)模式上的屬性數(shù)目，使得模式更易于理解。

3.4數(shù)據(jù)規(guī)約（4）回歸和對數(shù)線性模型：參數(shù)化數(shù)據(jù)歸約

回歸和對數(shù)線性模型可以用來近似給定的數(shù)據(jù)。

對數(shù)線性模型：近似離散的多維概率分布。給定n維元組的集合，我們把每個元組看做n維空間的點，對于離散屬性集，可使用對數(shù)線性模型，基于維組合的一個較小子集，估計多維空間中每個點的概率。（5）直方圖

直方圖使用分箱來近似數(shù)據(jù)分布，是一種流行的數(shù)據(jù)歸約形式。

（6）聚類

聚類技術(shù)把數(shù)據(jù)元組看做對象，將對象劃分為群或簇，使得在一個簇中的對象相互“相似”，而與其他簇中的對象“相異”。通常，相似性基于距離函數(shù)。

（7）抽樣

抽樣可以作為一種數(shù)據(jù)歸約的技術(shù)使用，因為它允許用數(shù)據(jù)小得多的隨機樣本表示數(shù)據(jù)集。

例如：簇抽樣，分層抽樣（8）數(shù)據(jù)立方體聚集

對數(shù)據(jù)倉庫的多維數(shù)據(jù)結(jié)構(gòu)建模3.5.1數(shù)據(jù)變換策略概述：

1）光滑：去掉數(shù)據(jù)中的噪聲。技術(shù)包括分箱、回歸、聚類。

2）屬性構(gòu)造（特征構(gòu)造）：由給定的屬性構(gòu)造新的屬性并添加到屬性集中，以幫助數(shù)據(jù)挖掘。

3）聚集：對數(shù)據(jù)進(jìn)行匯總或聚集。

4）規(guī)范化：把屬性數(shù)據(jù)按比例縮放，使之落入一個特定的區(qū)間。

5）離散化：數(shù)值屬性（eg。年齡）的原始值用區(qū)間標(biāo)簽（eg.0-10,11-20）或概念標(biāo)簽（youth，adult，senior）替換。

6）由標(biāo)稱數(shù)據(jù)產(chǎn)生概念分層：將某個屬性（eg.street）泛化到較高的概念層（city）。3.5數(shù)據(jù)變換與數(shù)據(jù)離散化3.5.2通過規(guī)范化變換數(shù)據(jù)1.最小-最大規(guī)范化：對原始數(shù)據(jù)進(jìn)行線性變換。令minA和maxA表示屬性A的最小值和最大值，最小—最大值標(biāo)準(zhǔn)化將值vi映射為vi’(范圍是[new_minA,new_maxA]:最小—最大值標(biāo)準(zhǔn)化保留了原有數(shù)據(jù)值的關(guān)系。如果后來的輸入的標(biāo)準(zhǔn)化的數(shù)據(jù)落在了原有數(shù)據(jù)區(qū)間的外面，將會發(fā)生過界的錯誤。3.5數(shù)據(jù)變換與數(shù)據(jù)離散化假定收入屬性的最小值和最大值分別是$12,000和$98,000.將收入屬性映射到范圍[0.0,1.0]上。則一個值為$73,600的收入標(biāo)準(zhǔn)化為：3.5.2通過規(guī)范化變換數(shù)據(jù)2.

Z-分?jǐn)?shù)標(biāo)準(zhǔn)化

3.5數(shù)據(jù)變換與數(shù)據(jù)離散化假定income屬性的均值和標(biāo)準(zhǔn)差是$54,000和$16,000。使用z-分?jǐn)?shù)標(biāo)準(zhǔn)化，則$73,600被轉(zhuǎn)換為：3.5.3通過分箱離散化

分箱并不使用類信息，因此是一種非監(jiān)督的離散化技術(shù)，對用戶制定的箱個數(shù)很敏感，也容易受離群點的影響。3.5.4通過直方圖分析離散化

直方圖分析也是一種非監(jiān)督離散化技術(shù)，因為它不使用類信息。3.5.5通過聚類、決策樹和相關(guān)分析離散化

聚類將數(shù)學(xué)的值劃分成簇或；離散化的決策樹方法是監(jiān)督的，它們使用了類標(biāo)號（分類）。3.5數(shù)據(jù)變換與數(shù)據(jù)離散化3.5.6標(biāo)稱數(shù)據(jù)的概念分層產(chǎn)生標(biāo)稱屬性具有有窮多個不同值，值之間無序。如地理位置，商品類型。

四中標(biāo)稱數(shù)據(jù)概念分層產(chǎn)生的方法：

1）由用戶或?qū)＜以谀Ｊ郊夛@示地說明屬性的部分序。（標(biāo)稱屬性或維的概念分層涉及一組屬性，由用戶或?qū)＜艺f明屬性的偏序或全序，然后很容易定義概念分層。）

2）通過顯式數(shù)據(jù)分組說明分層結(jié)構(gòu)的一部分。對于小部分?jǐn)?shù)據(jù)，顯式說明分組。

3）說明屬性集但不說明它們的偏序：用戶可以說明一個屬性集形成概念分層，但并不顯式說明它們的偏序，系統(tǒng)可以試圖自動產(chǎn)生屬性的序，構(gòu)造有意義的概念分層。

4）只說明部分屬性集3.5數(shù)據(jù)變換與數(shù)據(jù)離散化數(shù)據(jù)質(zhì)量包括精確性、完整性、一致性、時效性、可信性和可解釋性。質(zhì)量的評估基于對數(shù)據(jù)的預(yù)期使用。

即使目前存在大量的數(shù)據(jù)預(yù)處理技術(shù)，這仍然是一個研究的活躍領(lǐng)域，因為大量的不一致和臟數(shù)據(jù)的存在以及問題的復(fù)雜度的原因。3.6小結(jié)D.P.BallouandG.K.Tayi.Enhancingdataqualityindatawarehouseenvironments.Comm.ofACM,42:73-78,1999A.Bruce,D.Donoho,andH.-Y.Gao.Waveletanalysis.IEEESpectrum,Oct1996T.DasuandT.Johnson.ExploratoryDataMiningandDataCleaning.JohnWiley,2003J.DevoreandR.Peck.Statistics:TheExplorationandAnalysisofData.DuxburyPress,1997.H.Galhardas,D.Florescu,D.Shasha,E.Simon,andC.-A.Saita.Declarativedatacleaning:Language,model,andalgorithms.VLDB'01M.HuaandJ.Pei.Cleaningdisguisedmissingdata:Aheuristicapproach.KDD'0