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

1.中央財(cái)經(jīng)大學(xué) 信息學(xué)院，北京 100081

2.國(guó)網(wǎng)荊州供電公司 信通分公司，湖北 荊州 434000

3.國(guó)網(wǎng)遼寧省電力有限公司 信息通信分公司，沈陽(yáng) 110000

高維相關(guān)性缺失數(shù)據(jù)的分塊填補(bǔ)算法研究*

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

1.中央財(cái)經(jīng)大學(xué) 信息學(xué)院，北京 100081

2.國(guó)網(wǎng)荊州供電公司 信通分公司，湖北 荊州 434000

3.國(guó)網(wǎng)遼寧省電力有限公司 信息通信分公司，沈陽(yáng) 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

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

高維相關(guān)性數(shù)據(jù)；缺失數(shù)據(jù)；分塊填補(bǔ)算法

1 引言

隨著大數(shù)據(jù)相關(guān)理論和技術(shù)的發(fā)展，大數(shù)據(jù)在電力、醫(yī)療、金融、交通、電信等方面有了廣泛應(yīng)用。由于大數(shù)據(jù)的數(shù)據(jù)量非常巨大，在采集和存儲(chǔ)過(guò)程中，不可避免地出現(xiàn)數(shù)據(jù)缺失的現(xiàn)象。缺失數(shù)據(jù)往往含有重要的信息和價(jià)值，對(duì)缺失數(shù)據(jù)處理不當(dāng)，會(huì)對(duì)數(shù)據(jù)分析結(jié)果產(chǎn)生巨大影響，甚至?xí)?yán)重影響數(shù)據(jù)的客觀性和研究結(jié)論的正確性[1]。因此，如何對(duì)大數(shù)據(jù)中的缺失數(shù)據(jù)進(jìn)行填補(bǔ)是一個(gè)重要的研究?jī)?nèi)容。

傳統(tǒng)的數(shù)據(jù)填補(bǔ)方法包括多重插補(bǔ)[2]、基于回歸的填補(bǔ)算法[3]、基于關(guān)聯(lián)規(guī)則的填補(bǔ)算法[4]、基于決策樹(shù)的填補(bǔ)算法[5]、基于K近鄰的填補(bǔ)算法[6]、基于貝葉斯的填補(bǔ)算法[7]、基于聚類(lèi)的填補(bǔ)算法[8]。更進(jìn)一步，可以結(jié)合兩種或兩種以上的算法對(duì)缺失數(shù)據(jù)進(jìn)行填補(bǔ)，如基于關(guān)聯(lián)規(guī)則和K近鄰算法的填補(bǔ)算法[9]、基于關(guān)聯(lián)規(guī)則和聚類(lèi)的填補(bǔ)算法[10]、基于聚類(lèi)和最近鄰算法的填補(bǔ)算法[11]。

研究表明，傳統(tǒng)的數(shù)據(jù)填補(bǔ)算法對(duì)于小數(shù)據(jù)集填補(bǔ)的確有一定的準(zhǔn)確性，但面對(duì)大數(shù)據(jù)集，往往填補(bǔ)效果不佳。針對(duì)這一問(wèn)題，相關(guān)學(xué)者已經(jīng)進(jìn)行了一些缺失大數(shù)據(jù)填補(bǔ)方法的研究。陳肇強(qiáng)等人[12]運(yùn)用互聯(lián)網(wǎng)中海量信息對(duì)缺失大數(shù)據(jù)進(jìn)行填補(bǔ)，提出了基于上下文感知實(shí)體排序的缺失數(shù)據(jù)修復(fù)方法；金連等人[13]結(jié)合Map-Reduce的并行化特點(diǎn)，提出來(lái)了基于Map-Reduce的大數(shù)據(jù)缺失值填補(bǔ)算法，提高了大數(shù)據(jù)的填補(bǔ)效率；冷泳林等人[14]同時(shí)結(jié)合聚類(lèi)算法和并行處理對(duì)缺失大數(shù)據(jù)進(jìn)行填補(bǔ)；趙飛等人[15]針對(duì)高速流數(shù)據(jù)中的缺失值，提出了基于最小計(jì)數(shù)/頻率概要的缺失值填補(bǔ)方法。

傳統(tǒng)的針對(duì)一般缺失數(shù)據(jù)的填補(bǔ)方法和現(xiàn)有的針對(duì)缺失大數(shù)據(jù)的填補(bǔ)方法只考慮了觀測(cè)樣本之間的關(guān)系，而忽略了變量之間的關(guān)系，而變量之間的相關(guān)性往往會(huì)影響數(shù)據(jù)的填補(bǔ)效果。例如，身高與體重之間有相關(guān)關(guān)系，而與智力沒(méi)有直接關(guān)系，如果將智力這個(gè)變量的信息用于填補(bǔ)身高數(shù)據(jù)的缺失，則會(huì)對(duì)數(shù)據(jù)填補(bǔ)結(jié)果造成一定的影響。在高維大數(shù)據(jù)情形下，不相關(guān)變量會(huì)越來(lái)越多，對(duì)數(shù)據(jù)填補(bǔ)準(zhǔn)確性的影響也會(huì)越來(lái)越大。

一些研究已經(jīng)注意到了這些問(wèn)題，它們主要通過(guò)變量約簡(jiǎn)的方法，剔除掉不相關(guān)的變量，來(lái)提高數(shù)據(jù)填補(bǔ)的效果。例如，陳志奎等人[16]通過(guò)變量約簡(jiǎn)，將變量分成重要變量和非重要變量，分別采用不同的填補(bǔ)算法進(jìn)行填補(bǔ)。劉春英[17]通過(guò)考慮變量之間的依賴(lài)關(guān)系而對(duì)變量進(jìn)行區(qū)分，分別進(jìn)行填補(bǔ)。

為了處理缺失高維大數(shù)據(jù)，本文創(chuàng)新性地提出了一種針對(duì)高維相關(guān)性缺失數(shù)據(jù)的分塊填補(bǔ)算法。本文算法首先通過(guò)變量之間的相關(guān)性，將原始數(shù)據(jù)集進(jìn)行縱向分割，形成眾多的低維子數(shù)據(jù)集；然后利用數(shù)據(jù)填補(bǔ)算法，分別對(duì)每個(gè)分塊進(jìn)行填補(bǔ)。本文算法最大的優(yōu)點(diǎn)在于降低了不相關(guān)變量對(duì)填補(bǔ)結(jié)果的影響，從而能夠提高填補(bǔ)準(zhǔn)確度；同時(shí)本文算法能夠以并行的方式對(duì)高維缺失大數(shù)據(jù)進(jìn)行填補(bǔ)，不僅能提高缺失填補(bǔ)的精度，還能降低數(shù)據(jù)填補(bǔ)的計(jì)算時(shí)間。

本文組織結(jié)構(gòu)如下：第2章給出了分塊填補(bǔ)算法及其相關(guān)定義，從理論上證明了分塊填補(bǔ)能夠提高準(zhǔn)確性，并提出了基于k-means的數(shù)據(jù)分塊算法；第3章給出分塊填補(bǔ)算法的具體步驟；第4章通過(guò)模擬仿真說(shuō)明本文填補(bǔ)算法處理高維缺失大數(shù)據(jù)的準(zhǔn)確度和效率；第5章將分塊填補(bǔ)算法應(yīng)用于基因測(cè)序數(shù)據(jù)，說(shuō)明處理真實(shí)數(shù)據(jù)的能力；第6章總結(jié)全文。

2 相關(guān)理論

2.1 相關(guān)定義

定義1（缺失數(shù)據(jù)集）含缺失數(shù)據(jù)的數(shù)據(jù)集稱(chēng)為缺失數(shù)據(jù)集。為了方便描述，本文利用粗糙集理論中信息系統(tǒng)的概念來(lái)進(jìn)行描述。一個(gè)信息系統(tǒng)由一個(gè)四元組來(lái)表示：

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

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

定義2（遺失數(shù)據(jù)集）遺失數(shù)據(jù)集是對(duì)缺失數(shù)據(jù)的描述，缺失數(shù)據(jù)集S的遺失數(shù)據(jù)集MI定義為：

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

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

關(guān)于不同變量之間相關(guān)性的定義，在不同的領(lǐng)域都有不同的定義。由于相關(guān)性不是本文重點(diǎn)討論的內(nèi)容，本文僅采用歸納的研究方法對(duì)相關(guān)性進(jìn)行歸納描述，不做深入的討論和研究。在實(shí)際應(yīng)用中，相關(guān)系數(shù)、關(guān)聯(lián)規(guī)則、依賴(lài)度等均可以用來(lái)表示變量之間的相關(guān)性。

（1）相關(guān)系數(shù)

相關(guān)系數(shù)可以刻畫(huà)兩個(gè)變量之間的變動(dòng)關(guān)系，常用于數(shù)學(xué)、統(tǒng)計(jì)等領(lǐng)域。相關(guān)系數(shù)一般用ρ表示，值域?yàn)閇-1,1]。ρ的絕對(duì)值越大，表示相關(guān)性越高，反之越低。

（2）關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則在數(shù)據(jù)挖掘領(lǐng)域中用來(lái)表示不同事務(wù)之間的相關(guān)性，其最大的特點(diǎn)就是能夠找出表面上不易發(fā)現(xiàn)，內(nèi)在卻存在的相關(guān)性。例如一個(gè)人購(gòu)物籃里面物品之間的相關(guān)性就可以用關(guān)聯(lián)規(guī)則來(lái)描述。

（3）依賴(lài)度

依賴(lài)度是粗糙集理論中的一個(gè)概念，用來(lái)表示一個(gè)變量對(duì)另外一個(gè)變量的依賴(lài)程度，依賴(lài)度越高，意味著其相關(guān)性也越高。

定義4（相關(guān)變量集）相關(guān)變量集RA是A的一個(gè)子集，設(shè)0≤?≤1為變量相關(guān)性閾值，則RA定義如下：

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

定理1變量集A與相關(guān)變量集RA的關(guān)系為為變量集分塊個(gè)數(shù)。

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

定義5（分塊數(shù)據(jù)集）根據(jù)RA可以將S分成多個(gè)子數(shù)據(jù)集，每個(gè)子數(shù)據(jù)集稱(chēng)為一個(gè)分塊數(shù)據(jù)集，分塊數(shù)據(jù)集RS定義為:

RS=(U,RA,V,f)

定理2數(shù)據(jù)集S與分塊數(shù)據(jù)集RS的關(guān)系為，K為數(shù)據(jù)集分塊個(gè)數(shù)。

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

根據(jù)填補(bǔ)算法依賴(lài)的變量的不同，可以將填補(bǔ)算法分成3類(lèi)：?jiǎn)巫兞恳蕾?lài)填補(bǔ)算法、全變量依賴(lài)填補(bǔ)算法和分塊填補(bǔ)算法。

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

（1）單變量依賴(lài)填補(bǔ)算法是指對(duì)缺失值的填補(bǔ)只與當(dāng)前的缺失變量有關(guān)，而與其他變量值無(wú)關(guān)，如均值填補(bǔ)、眾數(shù)填補(bǔ)等，定義如下：

（2）全變量依賴(lài)填補(bǔ)算法是指對(duì)缺失值的填補(bǔ)與所有的變量都有關(guān)，如KNN填補(bǔ)算法、回歸填補(bǔ)算法等，其定義如下：

（3）分塊填補(bǔ)算法是指對(duì)缺失值的填補(bǔ)只與部分變量相關(guān)，定義如下：

其中，RAj為變量aj所在的相關(guān)變量集。

2.2 分塊填補(bǔ)的性質(zhì)

假設(shè)存在一個(gè)高維數(shù)據(jù)集A∈Rn×p，n?p，假定A滿(mǎn)足以下的假設(shè)。

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

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

（3）線(xiàn)性關(guān)系。各變量之間有近似的線(xiàn)性相關(guān)關(guān)系，即有：

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

（4）數(shù)據(jù)隨機(jī)缺失。

同時(shí)，本文用均方根誤差（root mean square error，RMSE）來(lái)評(píng)價(jià)數(shù)據(jù)填補(bǔ)的準(zhǔn)確程度，RMSE定義如下：

其中，N為缺失數(shù)據(jù)的個(gè)數(shù)；為缺失數(shù)據(jù)xi的填補(bǔ)估計(jì)值；ei2表示殘差的平方。RMSE越小，表示填補(bǔ)準(zhǔn)確度越高，反之越低。

根據(jù)上述假設(shè)，可得到定理3。

定理3在滿(mǎn)足4個(gè)假設(shè)條件的前提下，分塊填補(bǔ)的精度高于不分塊填補(bǔ)的準(zhǔn)確性。

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

情形1ai的不分塊估計(jì)值：

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

則ai不分塊估計(jì)的殘差平方和為：

情形2ai的分塊估計(jì)值為：

則ai的分塊估計(jì)的殘差平方和為：

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

（3）根據(jù)RMSE的定義，不分塊填補(bǔ)和分塊填補(bǔ)兩種方式下的填補(bǔ)精度（用RMSEnb和RMSEb來(lái)表示）分別為：

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

2.3 分塊方法

根據(jù)對(duì)數(shù)據(jù)集的理解情況，可以分為分塊已知和分塊未知兩種情況進(jìn)行討論。

2.3.1 分塊已知的情況

對(duì)于一個(gè)分塊信息已知的情況，直接根據(jù)已知分塊信息進(jìn)行分塊即可。分塊已知的情況一般出現(xiàn)在變量較少，且對(duì)變量的含義有明確認(rèn)識(shí)的情況。

2.3.2 分塊未知的情況

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

（1）k-means算法

k-means是一種經(jīng)典的聚類(lèi)算法。給定數(shù)據(jù)集A∈Rn×p。k-means算法步驟如下所示。

算法1k-means算法

輸入：數(shù)據(jù)集A，聚類(lèi)個(gè)數(shù)K。

輸出：每個(gè)對(duì)象a(i)所在的聚類(lèi)。

步驟1隨機(jī)選取K個(gè)聚類(lèi)中心為u1,u2,…,uK∈Rp。

步驟2迭代直至收斂。

對(duì)A中的每一個(gè)對(duì)象a(i)，計(jì)算其所屬的聚類(lèi)：

對(duì)于每一個(gè)類(lèi)j，更新類(lèi)的中心：

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

結(jié)合k-means算法的思想，本文提出了對(duì)變量進(jìn)行分塊的KMB算法。在描述算法之前，需要解決以下幾個(gè)問(wèn)題。

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

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

其中，w為變量的權(quán)重向量；wv表示第v個(gè)變量的權(quán)重系數(shù)；s為調(diào)整參數(shù)。

這樣，通過(guò)變量選擇解決了數(shù)據(jù)量很大時(shí)kmeans算法的局限性問(wèn)題。

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

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

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

算法2KMB算法

輸入：數(shù)據(jù)集A，聚類(lèi)個(gè)數(shù)K。

輸出：分塊數(shù)據(jù)集。

步驟1對(duì)A進(jìn)行轉(zhuǎn)置，得到AT。

步驟2隨機(jī)選取K個(gè)聚類(lèi)中心點(diǎn)為u1,u2,…,uK∈Rn。

步驟3迭代直至收斂。

對(duì)AT中的每一個(gè)對(duì)象a(i),計(jì)算其所屬的聚類(lèi)：

對(duì)于每一個(gè)類(lèi)j，按照本文定義的方法更新聚類(lèi)的中心：

步驟4轉(zhuǎn)置聚類(lèi)完成的數(shù)據(jù)集，得到A1。

步驟5根據(jù)聚類(lèi)結(jié)果分割數(shù)據(jù)集A1,得到多個(gè)分塊數(shù)據(jù)集。

3 分塊填補(bǔ)算法

分塊填補(bǔ)算法是根據(jù)數(shù)據(jù)集的特征，通過(guò)對(duì)數(shù)據(jù)集進(jìn)行分塊而形成的一種缺失數(shù)據(jù)填補(bǔ)算法。其最大的特征是適用的填補(bǔ)算法范圍廣，凡是依賴(lài)于其他變量的數(shù)據(jù)填補(bǔ)算法均適用于分塊填補(bǔ)的方案，統(tǒng)稱(chēng)此類(lèi)算法為宿主算法。分塊填補(bǔ)算法步驟見(jiàn)算法3。

算法3分塊填補(bǔ)算法

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

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

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

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

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

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

由算法3可知，分塊填補(bǔ)算法具有以下特點(diǎn)：

（1）缺失數(shù)據(jù)集是可分的，即可以分成多個(gè)塊內(nèi)相關(guān)性高，塊間相關(guān)性低的數(shù)據(jù)分塊。一方面，如果缺失數(shù)據(jù)集的所有變量之間都具有很高的相關(guān)性，那么對(duì)數(shù)據(jù)集進(jìn)行分割，反而會(huì)破壞這種強(qiáng)的相關(guān)性，不利于數(shù)據(jù)填補(bǔ)。另一方面，如果數(shù)據(jù)集的變量之間均存在較弱的相關(guān)性，劃分之后，變量之間的相關(guān)性仍然很低，也不利于數(shù)據(jù)填補(bǔ)。

（2）適用的宿主填補(bǔ)算法廣，即大部分傳統(tǒng)的填補(bǔ)算法均可作為本文提出的分塊填補(bǔ)算法的宿主算法，適用范圍廣。具體來(lái)講，除均值填補(bǔ)和眾數(shù)填補(bǔ)等少數(shù)不依賴(lài)變量的填補(bǔ)算法外，都適合分塊填補(bǔ)算法。

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

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

（1）實(shí)驗(yàn)數(shù)據(jù)生成

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

（2）實(shí)驗(yàn)平臺(tái)

本實(shí)驗(yàn)采用Matlab 2011B作為實(shí)驗(yàn)平臺(tái)，操作系統(tǒng)是Windows8.1專(zhuān)業(yè)版，Intel?Pentium?CPU P6200 2.13 GHz，2 GB 內(nèi)存，320 GB硬盤(pán)。

4.2 實(shí)驗(yàn)設(shè)置

（1）實(shí)驗(yàn)方法

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

（2）評(píng)價(jià)指標(biāo)

根據(jù)數(shù)據(jù)類(lèi)型的不同，對(duì)填補(bǔ)準(zhǔn)確度的衡量方法也不同。對(duì)于數(shù)值型數(shù)據(jù)，使用均方根誤差（RMSE）來(lái)衡量填補(bǔ)準(zhǔn)確度，其定義見(jiàn)式（1）。

對(duì)于離散性數(shù)據(jù)，采用填補(bǔ)準(zhǔn)確率（Precise）來(lái)衡量，即填補(bǔ)正確的數(shù)據(jù)記錄數(shù)占整個(gè)缺失數(shù)據(jù)的比例。Precise越大，填補(bǔ)精度越高。其定義為：

（3）實(shí)驗(yàn)設(shè)計(jì)

根據(jù)實(shí)驗(yàn)?zāi)康牟煌?，本文總共設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)。

實(shí)驗(yàn)1假定分塊已知，即按照仿真數(shù)據(jù)產(chǎn)生時(shí)設(shè)定的分塊對(duì)各數(shù)據(jù)集進(jìn)行分塊，然后使用K近鄰（KNN）填補(bǔ)算法和回歸（REGRESS）填補(bǔ)算法分別進(jìn)行填補(bǔ)，將結(jié)果與不分塊的情況進(jìn)行比較，以驗(yàn)證在數(shù)據(jù)存在分塊的情況下，本文提出的分塊填補(bǔ)算法是否優(yōu)于不分塊填補(bǔ)算法。

實(shí)驗(yàn)2假定分塊未知，即實(shí)驗(yàn)前只知道數(shù)據(jù)存在分塊，但并不知道具體的分塊情況。首先使用本文提出的分塊算法KMB（算法2）對(duì)數(shù)據(jù)進(jìn)行分塊，然后用KNN填補(bǔ)算法和REGRESS填補(bǔ)算法分別進(jìn)行填補(bǔ)；最后比較和驗(yàn)證在數(shù)據(jù)存在分塊但分塊未知的情況下，本文提出的分塊填補(bǔ)算法是否優(yōu)于不分塊填補(bǔ)算法，并對(duì)KMB算法進(jìn)行評(píng)價(jià)。

4.3 實(shí)驗(yàn)結(jié)果

（1）實(shí)驗(yàn)1結(jié)果分析

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

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

表2是各算法對(duì)不同數(shù)據(jù)集在不同缺失率情況下進(jìn)行填補(bǔ)的平均時(shí)間比較?？梢缘玫?，對(duì)于相同的數(shù)據(jù)集，各算法的平均填補(bǔ)時(shí)間均隨缺失率的上升而上升；對(duì)于相同數(shù)據(jù)集和相同缺失率，同一宿主算法分塊填補(bǔ)的平均填補(bǔ)時(shí)間小于不分塊填補(bǔ)；同一算法在相同缺失率水平下，平均填補(bǔ)時(shí)間隨變量個(gè)數(shù)的增加而增加。以上表明，本文提出的分塊填補(bǔ)算法能夠有效降低數(shù)據(jù)填補(bǔ)時(shí)間。

Table 1 RMSE of different imputation algorithms in different simulation datasets表1 不同模擬數(shù)據(jù)集上各個(gè)填補(bǔ)算法的均方根誤差

Table 2 Average imputation time of different imputation algorithms in different simulation datasets表2 不同模擬數(shù)據(jù)集上各個(gè)填補(bǔ)算法的平均填補(bǔ)時(shí)間

（2）實(shí)驗(yàn)2結(jié)果分析

實(shí)驗(yàn)2采用仿真生成的(n=100,p=100)和(n=100,p=1 000)兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別代表變量個(gè)數(shù)較小和變量個(gè)數(shù)較大的兩種情況。與實(shí)驗(yàn)1不同的是，實(shí)驗(yàn)前假定并不知道具體分塊情況，而是通過(guò)KMB算法（算法2）來(lái)自動(dòng)進(jìn)行分塊，然后使用KNN填補(bǔ)算法和REGRESS填補(bǔ)算法進(jìn)行填補(bǔ)。由于并不知道具體的分塊數(shù)，因而無(wú)法確定KMB算法中的K值。本文通過(guò)設(shè)定一個(gè)較大的K值(MAXK),然后從K=1到K=MAXK循環(huán)調(diào)用KMB算法進(jìn)行分塊，同時(shí)對(duì)每個(gè)分塊使用KNN填補(bǔ)算法和REGRESS填補(bǔ)算法進(jìn)行填補(bǔ)，然后觀察比較在K的不同取值下，填補(bǔ)結(jié)果的RMSE與K的關(guān)系。

情形1變量較少的情況

在仿真數(shù)據(jù)集(n=100,p=100)下，設(shè)定MAXK=25，相關(guān)結(jié)果如圖1所示。

Fig.1 Results of case 1(n=100,p=100)圖1 情形1(n=100,p=100)的實(shí)驗(yàn)結(jié)果

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

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

（2）關(guān)于“U”型形狀的解釋。當(dāng)K=1時(shí)，為不分塊填補(bǔ)，填補(bǔ)結(jié)果有較大的均方根誤差，因?yàn)槿笔?shù)據(jù)中含有較多的不相關(guān)信息參與了缺失值的填補(bǔ)；隨著K的逐漸增加，同一分塊中的不相關(guān)變量被分割出去，相關(guān)變量的比例上升，即同一分塊的相關(guān)性相對(duì)上升，從而使得填補(bǔ)的準(zhǔn)確性上升；當(dāng)K增加到一定程度之后，同一分塊的變量之間已經(jīng)具有較多的相關(guān)變量，同時(shí)具有較低的不相關(guān)變量；當(dāng)K進(jìn)一步增加，同一分塊的變量個(gè)數(shù)必然下降，致使部分相關(guān)性高的變量被分割出去，即分塊內(nèi)本身存在的強(qiáng)相關(guān)性此時(shí)也被破壞，從而導(dǎo)致了填補(bǔ)準(zhǔn)確度下降；當(dāng)K很大時(shí)，分塊填補(bǔ)的準(zhǔn)確度甚至?xí)^(guò)不分塊填補(bǔ)的準(zhǔn)確度，因?yàn)榇藭r(shí)產(chǎn)生了大量相關(guān)性弱的分塊。

（3）分塊未知的情況下，以及在K較小的情況下，KMB算法能夠找到合適的分塊來(lái)提高填補(bǔ)準(zhǔn)確度，說(shuō)明KMB算法能夠很好地對(duì)分塊未知的數(shù)據(jù)進(jìn)行分塊。

圖1（b）描述了在不同缺失率下，KNN算法平均填補(bǔ)時(shí)間隨K的變動(dòng)情況?？梢钥闯觯SK的增加，各缺失率下，平均填補(bǔ)時(shí)間呈下降趨勢(shì)，當(dāng)K增加到一定程度時(shí)，平均填補(bǔ)時(shí)間保持平穩(wěn)。這是因?yàn)榇藭r(shí)每個(gè)分塊都很小，不再是影響填補(bǔ)時(shí)間的主要因素。同時(shí)，對(duì)于相同的K，平均填補(bǔ)時(shí)間隨著缺失率的上升而上升。

圖1（c）和（d）分別是REGRESS填補(bǔ)算法在數(shù)據(jù)集1上填補(bǔ)的均方根誤差和平均填補(bǔ)時(shí)間隨分塊數(shù)K的變動(dòng)情況。與KNN算法相比，有類(lèi)似的結(jié)論，這里不再贅述。

情形2變量較多的情況

在仿真數(shù)據(jù)集(n=100,p=1 000)下，設(shè)定MAXK=100,相關(guān)結(jié)果如圖2所示。

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

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

Fig.2 Results of case 2(n=100,p=1 000)圖2 情形2(n=100,p=1 000)的實(shí)驗(yàn)結(jié)果

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

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

綜上，仿真實(shí)驗(yàn)的結(jié)果表明了對(duì)于相關(guān)性數(shù)據(jù)，在已知分塊的情況下，分塊填補(bǔ)的準(zhǔn)確度高于不分塊填補(bǔ)，同時(shí)可以降低填補(bǔ)時(shí)間；在分塊未知的情況下，也可以通過(guò)KMB算法（算法2）找到分塊，從而提高數(shù)據(jù)填補(bǔ)的準(zhǔn)確度。仿真實(shí)驗(yàn)還揭示了分塊填補(bǔ)的準(zhǔn)確度隨分塊個(gè)數(shù)的增加，先增加后降低的規(guī)律；當(dāng)分塊數(shù)足夠大時(shí)，會(huì)因?yàn)椴徽_的分塊導(dǎo)致分塊填補(bǔ)的準(zhǔn)確度低于不分塊填補(bǔ)的情況出現(xiàn)。

5 真實(shí)數(shù)據(jù)分析

為了評(píng)價(jià)分塊填補(bǔ)算法在電力、醫(yī)療等真實(shí)數(shù)據(jù)上的填補(bǔ)效果，本文將分塊填補(bǔ)算法應(yīng)用到白血病的基因表達(dá)數(shù)據(jù)集leukemia上。該數(shù)據(jù)集來(lái)源于麻省理工學(xué)院和哈佛大學(xué)的生物醫(yī)學(xué)和基因組研究中心Broad Institute，含有461個(gè)變量，1 394個(gè)樣本。因?yàn)閿?shù)據(jù)分塊未知，先用KMB算法（算法2）進(jìn)行分塊，然后采用KNN填補(bǔ)算法進(jìn)行填補(bǔ)，實(shí)驗(yàn)結(jié)果如圖3和圖4所示。

Fig.3 Relationship betweenRMSEandK圖3 均方根誤差與分塊數(shù)K的關(guān)系

Fig.4 Relationship between average imputation time andK圖4 平均填補(bǔ)時(shí)間與分塊數(shù)K的關(guān)系

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

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

綜上可知，真實(shí)數(shù)據(jù)中的結(jié)果與仿真實(shí)驗(yàn)得到的結(jié)論一致，進(jìn)一步說(shuō)明了分塊填補(bǔ)算法能夠提高填補(bǔ)準(zhǔn)確度和降低填補(bǔ)時(shí)間。

6 結(jié)束語(yǔ)

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

[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.

附中文參考文獻(xiàn)：

[6]張孫力,楊惠中.基于改進(jìn)的K近鄰缺失數(shù)據(jù)補(bǔ)全[J].計(jì)算機(jī)應(yīng)用與化學(xué),2015,32(12):1499-1502.

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

[8]武森,馮小東,單志廣.基于不完備數(shù)據(jù)聚類(lèi)的缺失數(shù)據(jù)填補(bǔ)方法[J].計(jì)算機(jī)學(xué)報(bào)，2012,35(8):1726-1738.

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

[10]方匡南,謝邦昌.基于聚類(lèi)關(guān)聯(lián)規(guī)則的缺失數(shù)據(jù)處理研究[J].統(tǒng)計(jì)研究,2011,28(2):87-92.

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

[12]陳肇強(qiáng),李佳俊,蔣川,等.基于上下文感知實(shí)體排序的缺失數(shù)據(jù)修復(fù)方法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(9):1755-1766.

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

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

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

[16]陳志奎,楊英達(dá),張清辰,等.基于變量約簡(jiǎn)的物聯(lián)網(wǎng)不完全數(shù)據(jù)填充算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2013,34(2):418-422.

[17]劉春英.基于變量依賴(lài)度的缺失值順序填充算法[J].計(jì)算機(jī)應(yīng)用與軟件,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(中央財(cái)經(jīng)大學(xué)青年教師發(fā)展基金);the Technology Project of State Grid Corporation of China under Grant No.SGTYHT/14-JS-188(國(guó)家電網(wǎng)科技部項(xiàng)目).

Received 2016-09,Accepted 2016-11.

CNKI網(wǎng)絡(luò)優(yōu)先出版: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—），男，四川廣元人，中央財(cái)經(jīng)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)分析。

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—），男，貴州貴陽(yáng)人，2014年于中國(guó)人民大學(xué)統(tǒng)計(jì)學(xué)專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為中央財(cái)經(jīng)大學(xué)信息學(xué)院講師，CCF會(huì)員，主要研究領(lǐng)域?yàn)殡娮由虅?wù)，數(shù)據(jù)分析與統(tǒng)計(jì)計(jì)算等。主持中央財(cái)經(jīng)大學(xué)青年發(fā)展基金等項(xiàng)目。

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—），男，黑龍江哈爾濱人，中央財(cái)經(jīng)大學(xué)繼續(xù)教育學(xué)院院長(zhǎng)、教授，主要研究領(lǐng)域?yàn)樾畔⒐芾恚鹑谛畔⒒?。主持?guó)家自然科學(xué)基金等項(xiàng)目。

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—），男，內(nèi)蒙古烏海人，2004年于東華大學(xué)控制工程專(zhuān)業(yè)獲得博士學(xué)位，現(xiàn)為中央財(cái)經(jīng)大學(xué)信息學(xué)院教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)榇髷?shù)據(jù)分析，商務(wù)智能等。

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—），男，湖北荊州人，荊州供電公司信通分公司工程師，主要研究領(lǐng)域?yàn)樾畔⑾到y(tǒng)運(yùn)維及安全管理。

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—），男，內(nèi)蒙赤峰人，華北電力大學(xué)通信與信息系統(tǒng)專(zhuān)業(yè)碩士，國(guó)網(wǎng)遼寧省電力有限公司信息通信分公司工程師，主要研究領(lǐng)域?yàn)殡娏ο到y(tǒng)通信。