基于距離最大化和缺失數據聚類的填充算法

趙星，王遜，黃樹成

（江蘇科技大學計算機科學與工程學院，江蘇鎮(zhèn)江212003）

數據挖掘中的數據往往都不可避免的存在著缺失數據、冗余數據、不確定數據和不一致數據等多種問題[1]。在各個領域中，缺失數據這一問題都是不容忽視的。尤其是目前的數據收集工作，已漸漸從人工搜集轉變?yōu)闄C器搜集。并且，由于數據量的急速膨脹，導致各種數據質量問題屢見不鮮，在這中間數據缺失尤為常見。導致數據中存在大量“空值”的因素有許多，例如數據收集條件的制約、度量方法錯誤、人工錄入時出現遺漏和違反數據約束等[2]。在某些領域中的數據庫中缺失值比例高達50%～60%以上[3，11-12]。這些不完整的數據不僅意味著信息空白，更重要的是它會影響后續(xù)數據挖掘抽取模式的正確性和導出規(guī)則的準確性[4]。因此，如何處理缺失數據已成為數據清洗及數據預處理領域研究的主要問題之一。

當前，存在的用于缺失值處理的方法共分為兩類[13，15]。第一種方法為直接刪除不完整數據，將含有缺失值的屬性或記錄從數據集中全部刪除。這種方法的實現方式比較簡單，并且容易實現。但這種方法可能會刪除潛在的有用數據，使得挖掘結果產生偏差[14]。第二種方法為基于填充技術的方法。該方法是采取填充算法對不完整數據進行填充，大多是運用完整數據分析方法，分析完整數據來對不完整數據進行填充，從而用最接近的值來替代缺失值[5]。這種方法可以提高可用數據的數量。因此，采用填充算法來處理數據缺失問題，不管從量上還是質上，對缺失數據的處理效果都要好于第一種。目前國內外已提出了很多有關缺失數據填充的算法，在當前是一個研究熱點。主要可以分為統計方法、分類方法、關聯規(guī)則分類方法等[6]。雖然這些方法在不同的應用環(huán)境下都有各自的優(yōu)點，但仍然存在一些不足[7]。

文中研究了聚類方法在缺失值填充中的使用，基于K-means聚類的缺失值填充算法根據與目標最相似的實例屬性值來估計缺失值，處理后的結果具有較高的準確性。但這種算法方法依然存在一些不足，因此，文中在原有算法基礎上，設計了一種改進的算法：基于距離最大化和缺失數據聚類的填充算法。新算法根據相距最遠的數據不在同一類中的原則，改進后的算法使用數據間的最大距離確定聚類中心，可以自動確定k值，使得聚類結果達到最優(yōu)，更高效的進行數據填充；其次，對聚類的距離函數進行改進，采用部分距離度量方式，改進后的算法可以對含有缺失值的記錄進行聚類，做到同時進行聚類和標記缺失數據所屬類，從而簡化原填充算法步驟。最后，在填充過程中，增加對離散型數據的填充處理。

1 改進的基于K-means聚類的缺失數據填充算法

1.1 基于K-means聚類的缺失值填充算法

基于K-means聚類的缺失值填充方法需要對數據進行預處理：提前除去原始數據集中缺失過多數據，這些數據包括含有較多缺失值的記錄或者屬性。通常情況下，如果缺失的屬性值比重達到50%及以上就選擇去除該條記錄[8]。由于同類事物間有許多屬性是相似的。因此，在對完整數據進行聚類后，可以根據聚類結果計算出缺失值并加以填充。

基于K-means算法的缺失值填充算法的主要步驟如圖1所示，具體描述如下：

圖1 基于聚類算法的缺失值填充算法流程圖

輸入：含有m個對象的數據集D，聚類個數k

輸出：經過缺失值填充處理的數據集D′

步驟：

Step1.根據記錄中是否含有缺失值將原始數據集D劃分為兩個數據子集，分別為完整數據子集C和缺失數據子集M。

Step2.在完整的數據子集C上進行K-means聚類，最終將數據集C分成k個類。

Step3.標記M中的記錄所屬類。計算缺失數據子集M中的每條記錄與C上k個類重心之間的相似度，然后選出相似度最大的一個類，把記錄賦給該類。

Step4.填充M中的缺失值。根據上一步標記的所屬類，將M中的每條記錄的缺失值用標記類相應的屬性均值來填充。

經過填充后，得到經過缺失值填充處理的數據集D′，D′包含完整數據子集C和經填充后的子集M′。

從上述描述看出，該算法的輸入值有兩個，分別為含有m個對象的數據集D和聚類個數k。需要使用者提前輸入聚類個數，這是它的缺點所在。并且在填充數據時使用均值，對于離散性數據，正確率會大大降低。

1.2 改進算法的策略

文中從以下幾個方面對K-means聚類的缺失值填充算法進行改進。

1）通過最大距離確定k值。原算法要求用戶提前輸入聚類的個數（k值），這其實也是K-means算法自身的缺點。如果通過經驗來評估出k值，有可能會導致最終形成的聚類的結果與實際的類別數目差別甚遠。數據量越龐大，k值就越難以估算，并且在聚類的過程中極易陷入局部最優(yōu)解的局面[10]。若想選擇合適的k值，常常需要使用其他方法進行k值的估算。所以本文將基于聚類的缺失值填充算法加以改進，提出了基于距離最大化的k值自動生成算法，在一定程度解決了K-means算法中k值的確定問題。

改進算法思想：針對原算法的第二步加以改進，省略k值的輸入，使k值自動生成。首先選擇盡可能離得遠的數據對象作為初始的聚類中心進行劃分，然后分別按照歐式距離尋找各類中離聚類中心點最遠的數據對象，再在其中選擇距離最大的那個數據對象為新增的聚類中心點，進行重新劃分，如此反復，直到滿足一定的條件算法結束。聚類完成后，聚類的個數也就自動產生了。

在該算中相似度的計算均采用的是歐式距離度量方式，改進算法步驟與流程如下：

Step1.設定一個含有n個數據對象的集合D，。首先選擇距離最大兩個數據對象xp，xq作為初始的聚類中心，即xp，xq之間的距離滿足，則把xp作為第一個類的聚類中心，記為S1，即S1=xp；把xq作為第二個類的聚類中心，記為S2，即S2=xq。

Step2.將集合Sn中其余的n-2個數據對象，按照歐式距離計算，并以S1，S2為聚類中心劃分類，若，則將xi劃分到類S1中，否則將xi劃分到類S2中，這樣就將集合D以S1，S2為聚類中心劃分成了兩大類，分別記作D21，D22。Step3.計算類D21中的所有數據對象到S1的距離，并取最大距離記為d21，即計算類D22中的所有數據對象到S2的距離，同樣取最大距離，得

Step4.取d2=max{d21,d22} ，若d2＞hd1（h為輸入參數，一般由經驗獲得），對應的那個數據對象為第3個聚類中心點，記為S3，把D以S1，S2，S3為聚類中心劃分成了3大類，分別記作D31，D32，D33。

Step5.計算類D31中的所有數據對象到S1的距離，得，計算類D32中的所有數據對象到S2的距離，得計算類D33中的所有數據對象到S3的距離，得

其中參數h的取值范圍為0.5≤h≤1，可以看出h的取值與最終形成的聚類中心的個數成反比。因為h越小越容易滿足Step6中的檢驗條件，即聚類中心之間的距離比較小，也就越容易找到新的聚類中心。根據實際經驗，h一般取為0.5。

改進后的算法必須在去除孤立點之后才能使用，因為對未處理的數據進行聚類，恰恰容易選擇兩個孤立點作為初始的聚類中心，產生錯誤的聚類結果。但由于此算法應用于數據挖掘前，數據預處理的數據清洗中，數據清洗還需要對數據集光滑噪聲并去除離群點，糾正數據的不一致性[9]。所以在此情況下，去除了“噪聲”和孤立點數據的影響后，應用此方法，去除了不足之處。并且改進后的聚類算法避免了用戶輸入的參數對聚類結果的影響，在一定程度上也避免了聚類陷入局部最優(yōu)解的局面。

2）將聚類和標記操作合并，省略計算缺失數據所屬類這一步驟。在K-means聚類的缺失數據填充算法中，第三步為計算每個缺失記錄所屬類，該步驟需再次搜索數據集，計算缺失記錄與類重心的相似度，增加了整個算法的處理時間，針對這一缺點，加以改進，直接對整個數據集進行聚類，在聚類同時對缺失記錄做標記。

文中提出了將聚類（Step2）和標記操作（Step3）合并的方法。若要合并2、3步，需要含有缺失值的記錄同時參與聚類，但K-means聚類算法不能計算含有缺失值記錄之間的距離。并且，在第3步中，計算每個缺失記錄所屬類，需要計算缺失記錄與每個類重心的相似度，最大相似度對應的類標記為缺失記錄所屬類。其中相似度的計算，則利用歐氏距離計算各個屬性之間的相異度，變換之后，得到記錄間的相似度。可以看出，第二步聚類中的距離函數和第三步計算缺失記錄所屬類中的相似度函數均基于歐氏距離。因此若要對含有缺失記錄的數據集進行聚類，則需要對K-means算法的距離函數加以改進，來適用于計算含缺失值數據集中對象之間的距離。改進后的算法，屬性值之間的距離依然采用歐氏距離，當遇到含有缺失值的記錄時，使用該記錄的剩余屬性值來計算與其他記錄之間的距離。通過添加指示變量ε來區(qū)分缺失屬性值，然后再將該距離乘以擴展系數來計算二者的整體距離。

設整個數據集合為D，數據集D中存在缺失記錄，D中每個記錄均有m個屬性用xi表示記錄X的第i個屬性值。數據集D中存在記錄X和Y，若記錄X和Y第i個屬性值上存在缺失值，即X和Y其中一個第i個屬性值缺失，或X和Y第i個屬性值均缺失，則X和Y的第i個屬性的指示變量εi為0，否則為1，εi計算公式如式（1）：

歐式距離度量方法如式（2），在此基礎上加入指示變量和擴展系數，改進后的距離函數如式（3）。

3）使用重值對離散型數據填充。在最后一步填充過程中，原算法采用標記類的屬性均值來填充缺失值。若該屬性值為離散性數據，使用均值填充，會大大的降低填充的準確性。所以針對此處不足，加以改進：如果缺失數據為數值型數據，則依然使用標記類的平均值作為缺失數據的值；如果缺失數據是離散型數據，則改使用標記類中出現次數最多的屬性值作為缺失數據值。計算方法如下：其中Ai為缺失值所在屬性的屬性值，n為該類記錄總數。

1.3 改進算法的步驟

改進的基于K-means算法的缺失值清洗算法的具體描述如下：

輸入：含有m個對象的數據集D

輸出：已經過缺失值填充處理的數據集D′

方法：

Step1．不做劃分，對整個數據集D使用改進的K-means聚類算法進行聚類，會得到k個類，將聚類結果標記為D1,D2,…,Dk。

Step 2．依次檢查中D1,D2,…,Dk是否存在缺失記錄，若Di中包含缺失數據記錄，則將Di拆分成兩個子集，分別為完整數據子集Ci和缺失數據子集Mi，即數據子集Ci中的所有記錄均為完整記錄，不包含缺失值，而數據集Mi中的記錄均含有一個及以上的屬性存在缺失值。并且數據集Ci和Mi存在以下關系：Di=Ci?Mi，Ci?Mi=?。

Step 3．根據數據子集Mi所在類，使用式（7），對記錄的缺失數據進行填充，若缺失數據為數值型數據，則使用標記類的平均值作為缺失數據的值；若缺失數據是離散型數據，則使用標記類中出現次數最多的數值作為缺失數據值。填充后數據集記為

2 實驗結果

本實驗的數據集采用來自UCI的STUDENT ALCOHOL CONSUMPTION Data Set數據集，該數據集具有13個屬性，1 044條數據。由于STUDENT ALCOHOL CONSUMPTION數據集并不存在缺失數據，為完整數據集，其中每條記錄都已經含有類標簽，為了實驗，將人為地制造不同比例的缺失值到數據集中，也就是選取某一屬性并且將一部分實例的該屬性值設為unkown，這里要指出的是，屬性的選取非常關鍵，需要選擇對實例其他屬性有關聯的屬性。

文中采用正確率衡量算法的填充精度。實驗最終，將經過算法填充的數據集與原始數據集進行比較，通過計算正確率來體現填充算法的匹配程度。正確率計算方法如下：

其中m是正確填充的屬性值個數，n為原始數據集中缺失的屬性值個數，P為填充算法的正確率。當P值為0時，表示所有填充的缺失值都錯誤；相反，當P值為1時，所有填充的缺失值都正確。

實驗結果及分析：

圖2 基于K-means聚類的缺失值填充算法不同k值下的精確度曲線

圖3 本文算法不同h值下的精確度曲線

從圖2可以看出，對于原聚類填充算法，并非值越大缺失值填充效果就越好，而且k的取值沒有規(guī)律可循，當與數據集的分類吻合時，其實k驗結果較好。從圖3可以看出，可以看出h的取值與正確率基本成反。因為h越小表示，即聚類中心之間的距離比較小，數據的相似度也就越高，填充效果也就更好。

圖4 不同算法不同缺失比例下的精確度曲線

從圖4可以看出，缺失值較少的情況下，填充的精確度普遍較高，當缺失值比例40%以上的時候，精確度降低。

表1 不同填充算法最優(yōu)正確率對比表

通過此表可以看出，使用基于K-means的缺失值填充算法和經過改進的基于K-means的缺失值填充算法對缺失值進行有效填充的準確度較均值填充算法有所提高，特別是經過改進的K-means的缺失值填充算法，在沒有損失正確率的前提下，成功的解決K-means算法對用戶k值輸入的依賴，另外也避免了初始值選取的非常近而增加算法迭代循環(huán)次數影響算法效率的問題。而且可根據實際情況，調節(jié)準確度。可見，改進后的算法對缺失值填充還是十分有效的。

3 結論

文中提出了一種基于距離最大化和缺失數據聚類的填充算法。首先，對K-means聚類算法加以改進，利用數據間的最大距離確定聚類中心；其次對聚類的距離函數進行改進，使之能夠對缺失數據進行聚類，在聚類的同時完成標記缺失數據所屬類，簡化了原填充算法步驟；最后，在填充過程中，對于離散型數據，改用標記類中出現頻率最高的值填充缺失值。改進后的算法不需要提前輸入聚類個數，避免了用戶輸入的參數對聚類結果的影響，在一定程度上也避免了聚類陷入局部最優(yōu)解的局面。并且通過化簡原算法步驟和增加離散型數據的處理，使得填充過程更簡潔高效。實驗結果表明本文提出的算法在填充正確率上高于原有的經典算法，而且該算法具有更高的運行效率。

[1]Oud J H L，Voelkle M C.Do missing values exist?Incomplete data handling in cross- national longitudinal studies by means of continuous time modeling[J].Quality&；Quantity，2014，48（6）:3271-3288.

[2]方匡南，謝邦昌.基于聚類關聯規(guī)則的缺失數據處理研究[J].統計研究，2011（2）:87-92.

[3]Julie M D，Kannan B.Attribute reduction and missing value imputing with ANN:prediction of learning disabilities[J].NeuralComputing and Applications，2012，21（7）:1757-1763.

[4]Yozgatligil C，Aslan S，Iyigun C，et al.Comparison of missing value imputation methods in time series:the case of Turkish meteorological data[J].Theoretical and Applied Climatology，2013，112（1）:143-167.

[5]Juhola M，Laurikkala J.Missing values:how many can they be to preserve classification reliability[J].Artificial Intelligence Review，2013，40（3）:231-245.

[6]帥平，李曉松，周曉華，等.缺失數據統計處理方法的研究進展[J].中國衛(wèi)生統計，2013（1）:135-139，142.

[7]金連.不完全數據中缺失值填充關鍵技術研究[D].哈爾濱：哈爾濱工業(yè)大學，2013.

[8]Li Z，Sharaf M A，Sitbon L，et al.A web-based approach to data imputation[J].World Wide Web，2014，17（5）:873-897.

[9]黃樑昌.kNN填充算法的分析和改進研究[D].桂林：廣西師范大學，2010.

[10]Gokhale M，Frigo J，Mccabe K，et al.Experience withaHybridProcessor:K-MeansClustering[J].The Journal of Supercomputing，2003，26（2）:131-148.

[11]Chang G，Zhang Y，Yao D.Missing Data Imputation for Traffic Flow Based on Improved Local Least Squares[J].Tsinghua Science and Technology，2012（3）:304-309.

[12]武森，馮小東，單志廣.基于不完備數據聚類的缺失數據填補方法[J].計算機學報，2012（8）:1726-1738.

[13]沐守寬，周偉.缺失數據處理的期望-極大化算法與馬爾可夫蒙特卡洛方法[J].心理科學進展，2011（7）:1083-1090.

[14]沈琳，陳千紅，譚紅專.缺失數據的識別與處理[J].中南大學學報，2013（12）:1289-1294.

[15]楊軍，趙宇，丁文興.抽樣調查中缺失數據的插補方法[J].數理統計與管理，2008（5）:821-832.

[16]Zou G H，LI Ying-fu，Zhu R，et al.Imputation of Mean ofRatios for Missing Data and Its Application to PPSWR Sampling[J]. Acta Mathematica Sinica（English Series），2010（5）:863-874.