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

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

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

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

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

然后：

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

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

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

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

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

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

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

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

在表中每一個可能的(Ai,Bj)聯(lián)合事件都有一個單元。卡方值的公式是：其中，oij表示觀察到的（Ai,Bj)聯(lián)合事件的頻率（實際次數(shù)）。而eij表示(Ai,Bj)事件的期望頻率，計算公式是：其中，n是數(shù)據元組的個數(shù)?？ǚ浇y(tǒng)計檢驗假定屬性A和屬性B是互相獨立的，即這兩個屬性之間沒有關聯(lián)?；陲@著性水平，自由度是(r-1)*(c-1)。如果假設被拒絕，則A和B統(tǒng)計相關。3.13.2假設調查了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的顯著性水平上拒絕值原假設。因為計算出的值大于這個值，所以能以更小的顯著性水平拒絕原假設，即性別和是否喜歡讀小說之間存在強相關關系。2數(shù)值數(shù)據的相關系數(shù)3.3數(shù)據集成

3.3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（6）聚類

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

（7）抽樣

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

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

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

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

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

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

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

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

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

Z-分數(shù)標準化

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

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

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

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

四中標稱數(shù)據概念分層產生的方法：

1）由用戶或專家在模式級顯示地說明屬性的部分序。（標稱屬性或維的概念分層涉及一組屬性，由用戶或專家說明屬性的偏序或全序，然后很容易定義概念分層。）

2）通過顯式數(shù)據分組說明分層結構的一部分。對于小部分數(shù)據，顯式說明分組。

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

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

即使目前存在大量的數(shù)據預處理技術，這仍然是一個研究的活躍領域，因為大量的不一致和臟數(shù)據的存在以及問題的復雜度的原因。3.6小結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