高維相關性缺失數據的分塊填補算法研究*

楊 杰，楊 虎，王魯濱，金 鑫，郭 華，于亮亮

1.中央財經大學 信息學院，北京 100081

2.國網荊州供電公司 信通分公司，湖北 荊州 434000

3.國網遼寧省電力有限公司 信息通信分公司，沈陽 110000

高維相關性缺失數據的分塊填補算法研究*

楊 杰1+，楊 虎1，王魯濱1，金 鑫1，郭 華2，于亮亮3

1.中央財經大學 信息學院，北京 100081

2.國網荊州供電公司 信通分公司，湖北 荊州 434000

3.國網遼寧省電力有限公司 信息通信分公司，沈陽 110000

Abstract:This paper studies the method of filling the high dimensional correlation missing data,and proposes a new imputation algorithm based on data block.The key idea of the algorithm is to consider the correlation between variables when filling missing data,and only use the data correlated with the missing data to fill,thereby reducing imputation effects of the missing data caused by the irrelevant data,and improving the accuracy of data imputation.At the same time,the proposed imputation algorithm can be implemented in a parallel way,so that it performs efficiently to fill the high dimensional missing data.In order to divide the missing data with unknown information about blocks into several blocks,this paper proposes a block algorithm based onk-means clustering.Simulation research and application show that the proposed imputation algorithm is more effective and accurate to handle themissing for the correlation high dimensional data with considering variables'block relationship than others with not.

Key words:high dimensional correlation data;missing data;block imputation algorithm

研究了高維相關性缺失數據的填補方法，提出了分塊填補算法。該算法核心思想是：在填補數據的過程中會考慮變量之間的相互關系，僅利用與待填補數據有相關性的數據進行填補，從而降低不相關數據對缺失數據填補的影響，提高數據填補的準確度。同時，該算法能夠并行處理缺失數據，從而提高數據填補效率，對于高維缺失數據的填補有重要意義。為了對分塊情況未知的缺失數據進行分塊，提出了基于k-means聚類的分塊算法。大量的仿真實驗和基于真實數據集的實驗表明，對于相關性數據，分塊填補算法能夠有效地利用相關信息進行填補，從而提高數據填補準確度。

高維相關性數據；缺失數據；分塊填補算法

1 引言

隨著大數據相關理論和技術的發展，大數據在電力、醫療、金融、交通、電信等方面有了廣泛應用。由于大數據的數據量非常巨大，在采集和存儲過程中，不可避免地出現數據缺失的現象。缺失數據往往含有重要的信息和價值，對缺失數據處理不當，會對數據分析結果產生巨大影響，甚至會嚴重影響數據的客觀性和研究結論的正確性[1]。因此，如何對大數據中的缺失數據進行填補是一個重要的研究內容。

傳統的數據填補方法包括多重插補[2]、基于回歸的填補算法[3]、基于關聯規則的填補算法[4]、基于決策樹的填補算法[5]、基于K近鄰的填補算法[6]、基于貝葉斯的填補算法[7]、基于聚類的填補算法[8]。更進一步，可以結合兩種或兩種以上的算法對缺失數據進行填補，如基于關聯規則和K近鄰算法的填補算法[9]、基于關聯規則和聚類的填補算法[10]、基于聚類和最近鄰算法的填補算法[11]。

研究表明，傳統的數據填補算法對于小數據集填補的確有一定的準確性，但面對大數據集，往往填補效果不佳。針對這一問題，相關學者已經進行了一些缺失大數據填補方法的研究。陳肇強等人[12]運用互聯網中海量信息對缺失大數據進行填補，提出了基于上下文感知實體排序的缺失數據修復方法；金連等人[13]結合Map-Reduce的并行化特點，提出來了基于Map-Reduce的大數據缺失值填補算法，提高了大數據的填補效率；冷泳林等人[14]同時結合聚類算法和并行處理對缺失大數據進行填補；趙飛等人[15]針對高速流數據中的缺失值，提出了基于最小計數/頻率概要的缺失值填補方法。

傳統的針對一般缺失數據的填補方法和現有的針對缺失大數據的填補方法只考慮了觀測樣本之間的關系，而忽略了變量之間的關系，而變量之間的相關性往往會影響數據的填補效果。例如，身高與體重之間有相關關系，而與智力沒有直接關系，如果將智力這個變量的信息用于填補身高數據的缺失，則會對數據填補結果造成一定的影響。在高維大數據情形下，不相關變量會越來越多，對數據填補準確性的影響也會越來越大。

一些研究已經注意到了這些問題，它們主要通過變量約簡的方法，剔除掉不相關的變量，來提高數據填補的效果。例如，陳志奎等人[16]通過變量約簡，將變量分成重要變量和非重要變量，分別采用不同的填補算法進行填補。劉春英[17]通過考慮變量之間的依賴關系而對變量進行區分，分別進行填補。

為了處理缺失高維大數據，本文創新性地提出了一種針對高維相關性缺失數據的分塊填補算法。本文算法首先通過變量之間的相關性，將原始數據集進行縱向分割，形成眾多的低維子數據集；然后利用數據填補算法，分別對每個分塊進行填補。本文算法最大的優點在于降低了不相關變量對填補結果的影響，從而能夠提高填補準確度；同時本文算法能夠以并行的方式對高維缺失大數據進行填補，不僅能提高缺失填補的精度，還能降低數據填補的計算時間。

本文組織結構如下：第2章給出了分塊填補算法及其相關定義，從理論上證明了分塊填補能夠提高準確性，并提出了基于k-means的數據分塊算法；第3章給出分塊填補算法的具體步驟；第4章通過模擬仿真說明本文填補算法處理高維缺失大數據的準確度和效率；第5章將分塊填補算法應用于基因測序數據，說明處理真實數據的能力；第6章總結全文。

2 相關理論

2.1 相關定義

定義1（缺失數據集）含缺失數據的數據集稱為缺失數據集。為了方便描述，本文利用粗糙集理論中信息系統的概念來進行描述。一個信息系統由一個四元組來表示：

其中，U={x(1),x(2),…,x(n)}表示對象集，n為對象的個數；A={a1,a2,…,ap}表示變量集，p表示變量的個數；V表示每個變量的值域；f是U×A到V的一個映射，即：

當信息系統S至少存在一組(i,j)使得，其中i=1,2,…,|U|,j=1,2,…,|A|,則稱該信息系統為不完備信息系統，即缺失數據集。

定義2（遺失數據集）遺失數據集是對缺失數據的描述，缺失數據集S的遺失數據集MI定義為：

其中，i=1,2,…,|U|,j=1,2,…,|A|。

定義3（變量相關性）變量相關性表示變量之間的相關程度或者依賴程度。本文用r(ai,aj)來表示變量ai和aj之間的相關性，其中ai,aj∈A,0≤r(ai,aj)≤ 1,r(ai,aj)越大，表示ai和aj相關性越高。r(ai,aj)=0,表示ai和aj完全無關；r(ai,aj)=1,表示ai和aj完全相關。

關于不同變量之間相關性的定義，在不同的領域都有不同的定義。由于相關性不是本文重點討論的內容，本文僅采用歸納的研究方法對相關性進行歸納描述，不做深入的討論和研究。在實際應用中，相關系數、關聯規則、依賴度等均可以用來表示變量之間的相關性。

（1）相關系數

相關系數可以刻畫兩個變量之間的變動關系，常用于數學、統計等領域。相關系數一般用ρ表示，值域為[-1,1]。ρ的絕對值越大，表示相關性越高，反之越低。

（2）關聯規則

關聯規則在數據挖掘領域中用來表示不同事務之間的相關性，其最大的特點就是能夠找出表面上不易發現，內在卻存在的相關性。例如一個人購物籃里面物品之間的相關性就可以用關聯規則來描述。

（3）依賴度

依賴度是粗糙集理論中的一個概念，用來表示一個變量對另外一個變量的依賴程度，依賴度越高，意味著其相關性也越高。

定義4（相關變量集）相關變量集RA是A的一個子集，設0≤?≤1為變量相關性閾值，則RA定義如下：

其中，ai,aj∈RA,i≠j。

定理1變量集A與相關變量集RA的關系為為變量集分塊個數。

證明 由定義4可知，RA是A的子集，且RAi?RAj=? ,i≠j。因此，對任意的i∈[1,K]，RAi是A的真子集，從而

定義5（分塊數據集）根據RA可以將S分成多個子數據集，每個子數據集稱為一個分塊數據集，分塊數據集RS定義為:

RS=(U,RA,V,f)

定理2數據集S與分塊數據集RS的關系為，K為數據集分塊個數。

定義6（分塊填補算法）數據填補算法可以統一定義為一種映射函數h:S→S′。其中S為缺失數據集，S′=(U′,A,V,f′)為經過填補后的完備數據集。

根據填補算法依賴的變量的不同，可以將填補算法分成3類：單變量依賴填補算法、全變量依賴填補算法和分塊填補算法。

設(i,j)∈MI(S)，為的填補值。

（1）單變量依賴填補算法是指對缺失值的填補只與當前的缺失變量有關，而與其他變量值無關，如均值填補、眾數填補等，定義如下：

（2）全變量依賴填補算法是指對缺失值的填補與所有的變量都有關，如KNN填補算法、回歸填補算法等，其定義如下：

（3）分塊填補算法是指對缺失值的填補只與部分變量相關，定義如下：

其中，RAj為變量aj所在的相關變量集。

2.2 分塊填補的性質

假設存在一個高維數據集A∈Rn×p，n?p，假定A滿足以下的假設。

（1）可分性。A可以按列分成K個分塊，即：

（2）獨立性。各塊之間相互獨立，即有：

（3）線性關系。各變量之間有近似的線性相關關系，即有：

其中，ui為白噪聲，i∈[1,p]；A*=Aai,表示不包含第i個變量。

（4）數據隨機缺失。

同時，本文用均方根誤差（root mean square error，RMSE）來評價數據填補的準確程度，RMSE定義如下：

其中，N為缺失數據的個數；為缺失數據xi的填補估計值；ei2表示殘差的平方。RMSE越小，表示填補準確度越高，反之越低。

根據上述假設，可得到定理3。

定理3在滿足4個假設條件的前提下，分塊填補的精度高于不分塊填補的準確性。

證明（1）由假設（3），各變量之間存在近似的線性相關關系，因此可以采用最小二乘的方法來對缺失數據的填補值進行估計，用表示ai的最小二乘估計值。對ai的估計有兩種情況：一種是利用全部的信息進行估計，即不分塊填補；另一種是僅利用最相關信息進行估計，即分塊填補。

情形1ai的不分塊估計值：

由假設（1）可知，A是按列可分的，因此式（2）可以變換為：

則ai不分塊估計的殘差平方和為：

情形2ai的分塊估計值為：

則ai的分塊估計的殘差平方和為：

用aim表示變量ai上由缺失數據組成的向量，由假設（4）可知，由于缺失方式為隨機缺失，aim也滿足假設（2）的獨立性條件。因此，變量ai上缺失數據在不分塊估計和分塊估計上的殘差平方和（分別用和表示）也滿足:

（3）根據RMSE的定義，不分塊填補和分塊填補兩種方式下的填補精度（用RMSEnb和RMSEb來表示）分別為：

結合式（7）可得，RMSEnb≥RMSEb,即分塊填補的精度高于不分塊填補的精度。

2.3 分塊方法

根據對數據集的理解情況，可以分為分塊已知和分塊未知兩種情況進行討論。

2.3.1 分塊已知的情況

對于一個分塊信息已知的情況，直接根據已知分塊信息進行分塊即可。分塊已知的情況一般出現在變量較少，且對變量的含義有明確認識的情況。

2.3.2 分塊未知的情況

實際中，大多數數據集都是未知分塊的。特別是對于高維數據或者對變量含義不了解的數據，難以識別其中的分塊信息。針對分塊未知的情況，本文基于k-means算法，通過改進數據缺失情況下的距離度量方式，從而實現了對缺失數據進行分塊，本文稱之為KMB算法（k-means block algorithm）。

（1）k-means算法

k-means是一種經典的聚類算法。給定數據集A∈Rn×p。k-means算法步驟如下所示。

算法1k-means算法

輸入：數據集A，聚類個數K。

輸出：每個對象a(i)所在的聚類。

步驟1隨機選取K個聚類中心為u1,u2,…,uK∈Rp。

步驟2迭代直至收斂。

對A中的每一個對象a(i)，計算其所屬的聚類：

對于每一個類j，更新類的中心：

（2）基于k-means的分塊算法

結合k-means算法的思想，本文提出了對變量進行分塊的KMB算法。在描述算法之前，需要解決以下幾個問題。

第一，聚類算法可以分為Q型聚類和R型聚類。Q型聚類是指對數據對象進行聚類，k-means算法就是一種Q型聚類算法。R型聚類是指對變量進行聚類。為了能夠使用k-means算法對變量進行聚類，首先需要對數據集進行轉置得到AT∈Rp×n，然后對A′進行聚類。

第二，k-means算法對高維數據的處理效果不佳，存在一定的局限性。本文中，當樣本量n較小時，轉置后的AT是一個低維的數據集，則使用k-means算法進行聚類不存在局限性問題。當n比較大時，轉置后的AT仍然是一個高維的數據集，此時使用k-means算法進行聚類存在一定的局限性。為了解決這一問題，本文采用Witten等人[18]提出的稀疏性k-means算法（sparsek-means clustering）進行變量選擇。其核心思想是約束目標函數中變量的權重，使得權重較小的變量不參與聚類，而保留權重較大的變量，從而實現變量選擇，其目標函數定義如下所示：

其中，w為變量的權重向量；wv表示第v個變量的權重系數；s為調整參數。

這樣，通過變量選擇解決了數據量很大時kmeans算法的局限性問題。

第三，經典k-means算法一般采用歐式距離來計算距離，在數據缺失的條件下，難以計算歐式距離。本文采用Hathaway等人[19]提出的計算缺失數據的距離的方法。包含缺失對象a(i)和a(j)之間的距離定義為：

第四，經典k-means算法一般采用算數平均的方法來更新聚類的中心，但在數據缺失的情況下，此方法不再可行。同樣借鑒Hathaway等人的思想，本文提出了在缺失情況下更新聚類中心的方法。設第j個聚類中有s個對象{a(1),a(2),…,a(s)}，且包含缺失，則類中心uj在第i個變量上的取值定義為：

解決了以上問題，下面給出具體的KMB算法步驟，如下所示。

算法2KMB算法

輸入：數據集A，聚類個數K。

輸出：分塊數據集。

步驟1對A進行轉置，得到AT。

步驟2隨機選取K個聚類中心點為u1,u2,…,uK∈Rn。

步驟3迭代直至收斂。

對AT中的每一個對象a(i),計算其所屬的聚類：

對于每一個類j，按照本文定義的方法更新聚類的中心：

步驟4轉置聚類完成的數據集，得到A1。

步驟5根據聚類結果分割數據集A1,得到多個分塊數據集。

3 分塊填補算法

分塊填補算法是根據數據集的特征，通過對數據集進行分塊而形成的一種缺失數據填補算法。其最大的特征是適用的填補算法范圍廣，凡是依賴于其他變量的數據填補算法均適用于分塊填補的方案，統稱此類算法為宿主算法。分塊填補算法步驟見算法3。

算法3分塊填補算法

輸入：缺失數據集S=(U,A,V,f)。

輸出：完備數據集S′=(U′,A,V,f′)。

步驟1確定分塊。如果分塊已知，則直接進行分塊；否則應用KMB算法（算法2）進行分塊，得到分塊信息。

步驟2根據分塊信息，對缺失數據集S進行分割，得到K個子缺失數據集RSi=(U,Ai,V,f),i=1,2,…,K。

步驟3對于每一個子缺失數據集，使用宿主填補算法進行填補，得到完備的子數據集Si=(U′,Ai,V,f′),i=1,2,…,K。

步驟4合并完備的子數據集Si，得到完備數據集S′=(U′,A,V,f′)。

由算法3可知，分塊填補算法具有以下特點：

（1）缺失數據集是可分的，即可以分成多個塊內相關性高，塊間相關性低的數據分塊。一方面，如果缺失數據集的所有變量之間都具有很高的相關性，那么對數據集進行分割，反而會破壞這種強的相關性，不利于數據填補。另一方面，如果數據集的變量之間均存在較弱的相關性，劃分之后，變量之間的相關性仍然很低，也不利于數據填補。

（2）適用的宿主填補算法廣，即大部分傳統的填補算法均可作為本文提出的分塊填補算法的宿主算法，適用范圍廣。具體來講，除均值填補和眾數填補等少數不依賴變量的填補算法外，都適合分塊填補算法。

（3）并行填補，提高填補效率。通過對原始數據集進行分塊，對每個分塊可以采用并行的方式進行填補，總的填補計算時間降為max(t1,t2,…,tK)，其中K為分塊個數，tK表示第K個分塊的填補時間。當數據集的維度和數據量很大時，分塊填補能夠明顯降低填補計算時間。

4 仿真實驗

4.1 實驗環境

（1）實驗數據生成

為了評價分塊填補算法對存在分塊的高維相關性缺失數據在分塊已知和分塊未知兩種情況下的填補效果，本文仿真生成了樣本量固定為n=100,變量個數分別為p=100,p=200和p=400的3個仿真數據集，來檢驗對于不同變量個數的數據集，分塊填補算法的效果。每個數據集的生成方式如下：首先確定數據集的分塊數為K塊；然后對于每個分塊Ki，它有pi個變量，數據由多元正態分布N(ui,Σi)產生，其中ui是pi維期望向量，Σi是pi×pi的協方差矩陣。為了保證不同塊之間有一定的差異，使不同分塊的期望向量之間存在一定的差異；最后將各個分塊合并形成仿真數據集，并重復100次。

（2）實驗平臺

本實驗采用Matlab 2011B作為實驗平臺，操作系統是Windows8.1專業版，Intel?Pentium?CPU P6200 2.13 GHz，2 GB 內存，320 GB硬盤。

4.2 實驗設置

（1）實驗方法

采用隨機缺失的方法，根據設定的缺失率，隨機地置空仿真數據集，得到包含缺失的數據集。分別使用宿主填補算法KNN（K近鄰）填補算法和REGRESS（線性回歸）填補算法對缺失數據進行分塊填補，并與不分塊的填補算法進行對比，比較它們的填補準確度和填補計算時間。每種算法均用于分析100個模擬生成的數據，并計算平均填補準確度和平均填補計算時間。

（2）評價指標

根據數據類型的不同，對填補準確度的衡量方法也不同。對于數值型數據，使用均方根誤差（RMSE）來衡量填補準確度，其定義見式（1）。

對于離散性數據，采用填補準確率（Precise）來衡量，即填補正確的數據記錄數占整個缺失數據的比例。Precise越大，填補精度越高。其定義為：

（3）實驗設計

根據實驗目的不同，本文總共設計了兩個實驗。

實驗1假定分塊已知，即按照仿真數據產生時設定的分塊對各數據集進行分塊，然后使用K近鄰（KNN）填補算法和回歸（REGRESS）填補算法分別進行填補，將結果與不分塊的情況進行比較，以驗證在數據存在分塊的情況下，本文提出的分塊填補算法是否優于不分塊填補算法。

實驗2假定分塊未知，即實驗前只知道數據存在分塊，但并不知道具體的分塊情況。首先使用本文提出的分塊算法KMB（算法2）對數據進行分塊，然后用KNN填補算法和REGRESS填補算法分別進行填補；最后比較和驗證在數據存在分塊但分塊未知的情況下，本文提出的分塊填補算法是否優于不分塊填補算法，并對KMB算法進行評價。

4.3 實驗結果

（1）實驗1結果分析

按10%、20%、30%、40%和50%缺失比例隨機缺失3個變量個數不同的數據集，然后在分塊和不分塊的情形下，分別采用KNN填補算法和REGRESS填補算法進行填補。各算法填補的均方根誤差和平均填補時間分別由表1和表2給出。

表1表明，已知分塊的情況下，在相同的缺失率水平下，同一宿主算法的分塊填補算法的均方根誤差均大于其不分塊填補算法，即分塊填補算法的填補準確度高于不分塊填補算法，這在3個變量個數不同的數據集中均成立；對于任意的填補算法，填補的準確度均隨缺失率的上升而下降。以上結果表明，在數據存在分塊的情況下，本文提出的分塊填補算法能夠提高填補準確度。

表2是各算法對不同數據集在不同缺失率情況下進行填補的平均時間比較。可以得到，對于相同的數據集，各算法的平均填補時間均隨缺失率的上升而上升；對于相同數據集和相同缺失率，同一宿主算法分塊填補的平均填補時間小于不分塊填補；同一算法在相同缺失率水平下，平均填補時間隨變量個數的增加而增加。以上表明，本文提出的分塊填補算法能夠有效降低數據填補時間。

Table 1 RMSE of different imputation algorithms in different simulation datasets表1 不同模擬數據集上各個填補算法的均方根誤差

Table 2 Average imputation time of different imputation algorithms in different simulation datasets表2 不同模擬數據集上各個填補算法的平均填補時間

（2）實驗2結果分析

實驗2采用仿真生成的(n=100,p=100)和(n=100,p=1 000)兩個數據集進行實驗，分別代表變量個數較小和變量個數較大的兩種情況。與實驗1不同的是，實驗前假定并不知道具體分塊情況，而是通過KMB算法（算法2）來自動進行分塊，然后使用KNN填補算法和REGRESS填補算法進行填補。由于并不知道具體的分塊數，因而無法確定KMB算法中的K值。本文通過設定一個較大的K值(MAXK),然后從K=1到K=MAXK循環調用KMB算法進行分塊，同時對每個分塊使用KNN填補算法和REGRESS填補算法進行填補，然后觀察比較在K的不同取值下，填補結果的RMSE與K的關系。

情形1變量較少的情況

在仿真數據集(n=100,p=100)下，設定MAXK=25，相關結果如圖1所示。

Fig.1 Results of case 1(n=100,p=100)圖1 情形1(n=100,p=100)的實驗結果

圖1（a）描述了在不同缺失率下，KNN填補算法的RMSE與K的關系。由圖1（a）可以看出，隨著K的增加，RMSE先減小，后增加，整個圖形呈“U”型，在K=5左右達到最小值。從圖1（a）中可以得到以下結論：

（1）在分塊數K相同時，RMSE隨缺失率的增加而增加，意味著在分塊未知的情況下，填補準確度仍隨著缺失率的上升而下降。

（2）關于“U”型形狀的解釋。當K=1時，為不分塊填補，填補結果有較大的均方根誤差，因為缺失數據中含有較多的不相關信息參與了缺失值的填補；隨著K的逐漸增加，同一分塊中的不相關變量被分割出去，相關變量的比例上升，即同一分塊的相關性相對上升，從而使得填補的準確性上升；當K增加到一定程度之后，同一分塊的變量之間已經具有較多的相關變量，同時具有較低的不相關變量；當K進一步增加，同一分塊的變量個數必然下降，致使部分相關性高的變量被分割出去，即分塊內本身存在的強相關性此時也被破壞，從而導致了填補準確度下降；當K很大時，分塊填補的準確度甚至會超過不分塊填補的準確度，因為此時產生了大量相關性弱的分塊。

（3）分塊未知的情況下，以及在K較小的情況下，KMB算法能夠找到合適的分塊來提高填補準確度，說明KMB算法能夠很好地對分塊未知的數據進行分塊。

圖1（b）描述了在不同缺失率下，KNN算法平均填補時間隨K的變動情況。可以看出，隨K的增加，各缺失率下，平均填補時間呈下降趨勢，當K增加到一定程度時，平均填補時間保持平穩。這是因為此時每個分塊都很小，不再是影響填補時間的主要因素。同時，對于相同的K，平均填補時間隨著缺失率的上升而上升。

圖1（c）和（d）分別是REGRESS填補算法在數據集1上填補的均方根誤差和平均填補時間隨分塊數K的變動情況。與KNN算法相比，有類似的結論，這里不再贅述。

情形2變量較多的情況

在仿真數據集(n=100,p=1 000)下，設定MAXK=100,相關結果如圖2所示。

從圖2（a）中可以看出，基于KNN的分塊填補算法在變量個數較多的情況下RMSE與K仍具有明 顯的“U”型特征，填補的均方根誤差隨缺失率上升而上升。

從圖2（b）中可以看出，填補時間隨K的增加而減少，隨缺失率的上升而上升。說明KNN填補算法對不同的樣本量具有良好的穩定性。

Fig.2 Results of case 2(n=100,p=1 000)圖2 情形2(n=100,p=1 000)的實驗結果

從圖2（c）中可以看出，在變量很多的情況下，REGRESS算法的均方根誤差與分塊數的“U”型特征不是十分明顯，均方根誤差先隨著分塊數的增加逐步下降，然后逐步保持在較低的水平，當K=40左右才有微弱的上升趨勢。主要是因為K值還不夠大，總的變量個數又很多，所以各個分塊還有足夠的相關變量用于缺失數據的填補。

從圖2（d）中可以看出，平均填補時間隨K的增加仍然有逐步減少，然后保持在較低水平的規律。

綜上，仿真實驗的結果表明了對于相關性數據，在已知分塊的情況下，分塊填補的準確度高于不分塊填補，同時可以降低填補時間；在分塊未知的情況下，也可以通過KMB算法（算法2）找到分塊，從而提高數據填補的準確度。仿真實驗還揭示了分塊填補的準確度隨分塊個數的增加，先增加后降低的規律；當分塊數足夠大時，會因為不正確的分塊導致分塊填補的準確度低于不分塊填補的情況出現。

5 真實數據分析

為了評價分塊填補算法在電力、醫療等真實數據上的填補效果，本文將分塊填補算法應用到白血病的基因表達數據集leukemia上。該數據集來源于麻省理工學院和哈佛大學的生物醫學和基因組研究中心Broad Institute，含有461個變量，1 394個樣本。因為數據分塊未知，先用KMB算法（算法2）進行分塊，然后采用KNN填補算法進行填補，實驗結果如圖3和圖4所示。

Fig.3 Relationship betweenRMSEandK圖3 均方根誤差與分塊數K的關系

Fig.4 Relationship between average imputation time andK圖4 平均填補時間與分塊數K的關系

從圖3中可以看出，采用不分塊的方式進行填補(K=1)有較高的均方根誤差，隨著分塊數的增加，均方根誤差逐步減小，在K=10左右達到最低，然后波動上升，整個圖形呈“U”型。同時，在分塊數K相同時，RMSE隨著缺失率的提高而上升，即填補準確度隨缺失率上升而下降。綜上可知，使用分塊填補算法在真實數據集中也能夠提高填補準確度。

由圖4可知，相同缺失率下，平均填補時間隨著分塊數的增加而減少；相同分塊數下，平均填補時間隨缺失率上升而下降。

綜上可知，真實數據中的結果與仿真實驗得到的結論一致，進一步說明了分塊填補算法能夠提高填補準確度和降低填補時間。

6 結束語

本文針對高維相關性數據提出了基于變量分塊的分塊填補算法，有助于解決現實中電力、醫療等行業的大數據缺失填補問題。在分塊已知的情況下，仿真實驗表明分塊填補能夠提高數據填補的準確度和降低數據填補的計算時間。在分塊未知的情況下，本文首先利用改進的k-means算法進行分塊，然后再分別對各分塊進行填補。仿真實驗和真實數據分析結果表明，分塊未知情況下分塊填補同樣可以提高填補準確度和降低數據填補的計算時間。同時實驗表明，填補準確度隨分塊數的增加有先增加再減少的規律，即不同的分塊數對填補準確度的提高程度不同。如何確定最優的分塊數使得能夠最大程度地提高分塊填補算法的填補準確度是進一步研究的方向。

[1]Nakagawa S,Freckleton R P.Missing inaction:the dangers of ignoring missing data[J].Trends in Ecology and Evolution,2008,23(11):592-596.

[2]Rubin D B.Multiple imputation in sample surveys—a phenomenological Byesian approach to nonresponse[M]//Survey Research Methodology Section.Washington:American StatisticalAssociation,1978:20-34.

[3]Bello A L.Imputation techniques in regression analysis:looking closely at their implementation[J].Computational Statistics and DataAnalysis,1995,20(1):45-57.

[4]Shen J J,Chang C C,Li Y C.Combined association rules for dealing with missing values[J].Journal of Information Science,2007,33(4):468-480.

[5]Vateekul P,Sarinnapakorn K.Tree-based approach to missing data imputation[C]//Proceedings of the 2009 International Conference on Data Mining Workshops,Miami,USA,Dec 6,2009.Washington:IEEE Computer Society,2009:70-75.

[6]Zhang Sunli,Yang Huizhong.Missing data completion based on an improvedK-neighbor algorithm[J].Computers and Applied Chemistry,2015,32(12):1499-1502.

[7]Zou Wei,Wang Huijin.EM algorithm to implement missing values based on naive Bayesian[J].Microcomputer&Its Applications,2011,30(16):75-77.

[8]Wu Sen,Feng Xiaodong,Shan Zhiguang.Missing data imputation approach based on incomplete data clustering[J].Chinese Journal of Computers,2012,35(8):1726-1738.

[9]Wang Fengmei,Hu Lixia.A missing data imputation method based on neighbor rules[J].Computer Engineering,2012,38(21):53-55.

[10]Fang Kuangnan,Xie Bangchang.Research on dealing with missing data based on clustering and association rule[J].Statistical Research,2011,28(2):87-92.

[11]Zhang Chi,Feng Hongcai,Jin Kai,et al.Nearest neighbor filling algorithm for missing data based on cluster analysis[J].ComputerApplications and Software,2014,31(5):282-284.

[12]Chen Zhaoqiang,Li Jiajun,Jiang Chuan,et al.A contextaware entity ranking method for Web-based data imputation[J].Chinese Journal of Computers,2015,38(9):1755-1766.

[13]Jin Lian,Wang Hongzhi,Huang Shenbing,et al.Missing value imputation in big data based on Map-Reduce[J].Journal of Computer Research and Development,2013,50(S1):312-321.

[14]Leng Yonglin,Chen Zhikui,Zhang Qingchen,et al.Distributed clustering and filling algorithm of incomplete big data[J].Computer Engineering,2015,41(5):19-25.

[15]Zhao Fei,Liu Qizhi,Zhang Yan,et al.Fill absent values in massive domain data stream[J].Journal of Nanjing University:Natural Sciences,2011,47(1):32-39.

[16]Chen Zhikui,Yang Yingda,Zhang Qingchen,et al.Novel algorithm for filling incomplete data of Internet of things based on attribute reduction[J].Computer Engineering and Design,2013,34(2):418-422.

[17]Liu Chunying.A sequential filling algorithm for missing values based on attribute dependency[J].Computer Applications and Software,2013,30(9):215-218.

[18]Witten D M,Tibshirani R.A framework for feature selection in clustering[J].Journal of theAmerican StatisticalAssociation,2012,105(490):713-726.

[19]Hathaway R J,Bezdek J C.Fuzzy C-means clustering of incomplete data[J].IEEE Transactions on Systems,Man and Cybernetics:Part B Cybernetics,2001,31(5):735-744.

附中文參考文獻：

[6]張孫力,楊惠中.基于改進的K近鄰缺失數據補全[J].計算機應用與化學,2015,32(12):1499-1502.

[7]鄒微,王會進.基于樸素貝葉斯的EM缺失數據填充算法[J].微型機與應用,2011,30(16):75-77.

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

[9]王鳳梅,胡麗霞.一種基于近鄰規則的缺失數據填補方法[J].計算機工程,2012,38(21):53-55.

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

[11]張赤,豐洪才,金凱,等.基于聚類分析的缺失數據最近鄰填補算法[J].計算機應用與軟件,2014,31(5):282-284.

[12]陳肇強,李佳俊,蔣川,等.基于上下文感知實體排序的缺失數據修復方法[J].計算機學報,2015,38(9):1755-1766.

[13]金連,王宏志,黃沈冰,等.基于Map-Reduce的大數據缺失值填充算法[J].計算機研究與發展,2013,50(S1):312-321.

[14]冷泳林,陳志奎,張清辰,等.不完整大數據的分布式聚類填充算法[J].計算機工程,2015,41(5):19-25.

[15]趙飛,劉奇志,張剡,等.一種大域數據流中缺失值的填充方法[J].南京大學學報:自然科學,2011,47(1):32-39.

[16]陳志奎,楊英達,張清辰,等.基于變量約簡的物聯網不完全數據填充算法[J].計算機工程與設計,2013,34(2):418-422.

[17]劉春英.基于變量依賴度的缺失值順序填充算法[J].計算機應用與軟件,2013,30(9):215-218.

Research on Block Imputation Algorithm for High Dimensional Correlation Missing Data*

YANG Jie1+,YANG Hu1,WANG Lubin1,JIN Xin1,GUO Hua2,YU Liangliang3
1.School of Information,Central University of Finance and Economics,Beijing 100081,China
2.Jingzhou Power Supply Company ICT Branch of State Grid Corporation,Jingzhou,Hubei 434000,China
3.Liaoning Power Supply Company ICT Branch of State Grid Corporation,Shenyang 110000,China

A

TP311

+Corresponding author:E-mail:yangjiecufe@163.com

YANG Jie,YANG Hu,WANG Lubin,et al.Research on block imputation algorithm for high dimensional correlation missing data.Journal of Frontiers of Computer Science and Technology,2017,11(10)：1557-1569.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2017/11(10)-1557-13

10.3778/j.issn.1673-9418.1609010

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

*The Young Teachers Development Foundation of Central University of Finance and Economics under Grant No.QJJ1510(中央財經大學青年教師發展基金);the Technology Project of State Grid Corporation of China under Grant No.SGTYHT/14-JS-188(國家電網科技部項目).

Received 2016-09,Accepted 2016-11.

CNKI網絡優先出版:2016-11-07,http://www.cnki.net/kcms/detail/11.5602.TP.20161107.1703.002.html

YANG Jie was born in 1992.He is an M.S.candidate at Central University of Finance and Economics.His research interest is data analysis.

楊杰（1992—），男，四川廣元人，中央財經大學碩士研究生，主要研究領域為數據分析。

YANG Hu was born in 1983.He received the Ph.D.degree in statistics from Renmin University of China in 2014.Now he is a lecturer at Central University of Finance and Economics,and the member of CCF.His research interests include E-business,data analysis and computational statistics,etc.

楊虎（1983—），男，貴州貴陽人，2014年于中國人民大學統計學專業獲得博士學位，現為中央財經大學信息學院講師，CCF會員，主要研究領域為電子商務，數據分析與統計計算等。主持中央財經大學青年發展基金等項目。

WANG Lubin was born in 1960.He is a professor at Central University of Finance and Economics.His research interests include information management and financial informatization,etc.

王魯濱（1960—），男，黑龍江哈爾濱人，中央財經大學繼續教育學院院長、教授，主要研究領域為信息管理，金融信息化等。主持國家自然科學基金等項目。

JIN Xin was born in 1974.He received the Ph.D.degree in control theory and engineering from Donghua University in 2004.Now he is a professor at Central University of Finance and Economics,and the member of CCF.His research interests include big data analysis and business intelligence,etc.

金鑫（1974—），男，內蒙古烏海人，2004年于東華大學控制工程專業獲得博士學位，現為中央財經大學信息學院教授，CCF會員，主要研究領域為大數據分析，商務智能等。

GUO Hua was born in 1972.He is an engineer at Jingzhou Power Supply Company ICT Branch of State Grid Corporation.His research interest is information system and management.

郭華（1972—），男，湖北荊州人，荊州供電公司信通分公司工程師，主要研究領域為信息系統運維及安全管理。

YU Liangliang was born in 1986.He is an engineer at Liaoning Power Supply Company ICT Branch of State Grid Corporation.His research interest is power system communication.

于亮亮（1986—），男，內蒙赤峰人，華北電力大學通信與信息系統專業碩士，國網遼寧省電力有限公司信息通信分公司工程師，主要研究領域為電力系統通信。