楊　毅　盧誠波

(麗水學(xué)院工程與設(shè)計(jì)學(xué)院　浙江 麗水 323000)

?

一種基于極限學(xué)習(xí)機(jī)的缺失數(shù)據(jù)填充方法

楊毅盧誠波

(麗水學(xué)院工程與設(shè)計(jì)學(xué)院浙江 麗水 323000)

數(shù)據(jù)處理過程中經(jīng)常會遇到不完備數(shù)據(jù)需要填充的問題，尋求簡單有效的缺失數(shù)據(jù)填充方法非常重要。針對該情況，提出一種基于極限學(xué)習(xí)機(jī)ELM(Extreme Learning Machine)的缺失數(shù)據(jù)填充方法，通過極限學(xué)習(xí)機(jī)網(wǎng)絡(luò)建模，建立需要填充的缺失屬性與其他屬性的非線性映射模型。實(shí)驗(yàn)結(jié)果表明：該方法具有非常好的填充效果。

極限學(xué)習(xí)機(jī)缺失數(shù)據(jù)填充UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫

0　引　言

在信息處理過程中，經(jīng)常會遇到數(shù)據(jù)集不完整的情況，通常稱之為缺失數(shù)據(jù)。數(shù)據(jù)缺失產(chǎn)生原因很多，如人為疏忽被遺漏、信息屬性值不存在和客觀條件難以采集等，數(shù)據(jù)缺失普遍發(fā)生在各個研究領(lǐng)域。處理缺失數(shù)據(jù)最常用的方法是丟棄數(shù)據(jù)中不完整的點(diǎn)，只采用數(shù)據(jù)中完整的點(diǎn)，用減少樣本量換取信息的完備，但這樣會浪費(fèi)大量的采集資料，遺漏了隱藏在丟棄數(shù)據(jù)中的信息。特別是當(dāng)樣本容量較小時，丟棄數(shù)據(jù)會嚴(yán)重影響到數(shù)據(jù)的客觀性和多樣性。因此對缺失數(shù)據(jù)進(jìn)行填充是一項(xiàng)非常重要的工作。

對缺失數(shù)據(jù)進(jìn)行填充的傳統(tǒng)方法有零填充、均值填充、熱卡填充、回歸填充和多重填充等[1-3]。零填充指的是將缺失值用零替代，但只有當(dāng)缺失值近似為零時，零填充才能有較好的效果。均值填充指的是將缺失值用已知數(shù)據(jù)的平均值替換，這種方法也會產(chǎn)生有偏估計(jì)。熱卡填充指的是在數(shù)據(jù)集中找到一個與它最相似的值，將缺失值用這個近似值替代，該方法比較耗費(fèi)時間。K近鄰填充是熱卡填充的一種方法，它是找到數(shù)據(jù)集中與缺失數(shù)據(jù)的歐氏距離最小的K個點(diǎn)，用這K個點(diǎn)的平均值替換缺失值?；貧w填充指的是將缺失值用缺失數(shù)據(jù)的條件期望替代。多重填充是用一組近似值替換每個缺失值，再用標(biāo)準(zhǔn)的統(tǒng)計(jì)分析過程對多次替換后產(chǎn)生的若干數(shù)據(jù)進(jìn)行分析、比較，得到缺失值的估計(jì)值。

極限學(xué)習(xí)機(jī)ELM是一種單隱層前饋神經(jīng)網(wǎng)絡(luò)(SLFN)學(xué)習(xí)算法，網(wǎng)絡(luò)的輸入權(quán)為隨機(jī)給定，輸出權(quán)則通過最小二乘法計(jì)算得到。整個訓(xùn)練過程一次完成，不需要迭代過程。與已知的BP算法和支持向量機(jī)等算法相比，具有執(zhí)行過程簡單、運(yùn)行速度快且泛化性能好等特點(diǎn)。該算法已被廣泛地應(yīng)用到模式分類、回歸問題[7]、圖像識別[8,9]、高維數(shù)據(jù)的降維算法[10]等各個領(lǐng)域，均取得了非常好的效果。本文基于極限學(xué)習(xí)機(jī)提出一種新的缺失數(shù)據(jù)填充方法。

1　基于極限學(xué)習(xí)機(jī)的缺失數(shù)據(jù)填充方法

2004年，黃廣斌等提出極限學(xué)習(xí)機(jī)算法[4-6]，該算法只需要設(shè)置單隱層前饋神經(jīng)網(wǎng)絡(luò)的隱層節(jié)點(diǎn)個數(shù)，在算法執(zhí)行過程中不需要調(diào)整網(wǎng)絡(luò)的輸入權(quán)和隱元的偏置，并產(chǎn)生唯一的最優(yōu)解。

給定樣本容量為N的樣本(xi,yi)，其中i≤N，xi∈Rn且yi∈Rm，xi是輸入的樣本值，yi是輸出的期望值。隱層節(jié)點(diǎn)數(shù)為L的單隱層前饋神經(jīng)網(wǎng)絡(luò)可表示如下：

(1)

其中βi=(βi1,βi2,…,βim)T是輸出外權(quán)，f(x)是激活函數(shù)，ωi和xj的內(nèi)積，oj是輸出的真實(shí)值，如圖1所示。式(1)可表達(dá)成矩陣的形式如下：

Hβ=O

(2)

其中 O=(o1,o2,…,oN)T。

(3)

圖1　輸入權(quán)和隱層偏置隨機(jī)給定的單隱層前饋神經(jīng)網(wǎng)絡(luò)

令O=y，其中y=(y1,y2,…,yN)T，則式(2)可表達(dá)成：

Hβ=y

(4)

極限學(xué)習(xí)機(jī)算法的基本思想是：隨機(jī)選取ωi和bi，然后利用β=H?y計(jì)算輸出外權(quán)，其中H?表示H的廣義逆。利用正交投影法求H的廣義逆可得：

H?=(HTH)-1HT

為了權(quán)衡經(jīng)驗(yàn)風(fēng)險和結(jié)構(gòu)風(fēng)險，進(jìn)一步提高網(wǎng)絡(luò)的泛化性能，文獻(xiàn)[11-14]研究了正則極限學(xué)習(xí)機(jī),其數(shù)學(xué)模型為：

(5)

式中，誤差‖ε‖2代表經(jīng)驗(yàn)風(fēng)險，‖β‖2代表結(jié)構(gòu)風(fēng)險，它來自于統(tǒng)計(jì)學(xué)中邊緣距離最大化原理；而γ是兩種風(fēng)險的比例參數(shù)，用來權(quán)衡這兩種風(fēng)險。

求解上述模型，可得:

(6)

本文設(shè)計(jì)的基于極限學(xué)習(xí)機(jī)進(jìn)行缺失數(shù)據(jù)填充的主要思想是：利用樣本集中完備的樣本進(jìn)行極限學(xué)習(xí)機(jī)網(wǎng)絡(luò)建模，建立需要填充的缺失屬性與其他屬性的非線性映射模型。例如，若需填充樣本的缺失屬性為第1個屬性，則將第2個屬性至第n個屬性的值構(gòu)造成輸入向量，將第1個屬性的值作為輸出向量，利用數(shù)據(jù)集中的完備樣本訓(xùn)練網(wǎng)絡(luò)的外權(quán)矩陣β。最后，將缺失樣本的數(shù)據(jù)代入網(wǎng)絡(luò)，獲得屬性1的估計(jì)值。

該算法的具體步驟如下：

第1步根據(jù)完備樣本的數(shù)目確定合適的隱層節(jié)點(diǎn)個數(shù)；

第2步利用完備樣本，將缺失屬性值作為輸出值，其他屬性的值作為輸入值，通過極限學(xué)習(xí)機(jī)建立缺失樣本中的缺失屬性與其他屬性的非線性映射模型，計(jì)算式(6)中的β；

第3步利用缺失樣本的剩余屬性值計(jì)算H, 最后利用式(4)計(jì)算缺失屬性值。

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

實(shí)驗(yàn)將本文的填充方法與零填充、均值填充、K近鄰填充方法在廣義平均絕對誤差和聚類純度兩個指標(biāo)上進(jìn)行比較。

廣義平均絕對誤差(GMAD)可表達(dá)如下：

(7)

聚類純度(Purity)[15]表示如下：

其中S={s1,s2,…,sk}表示數(shù)據(jù)集真實(shí)的聚類，s1表示落入s1中的樣本數(shù)據(jù)，C={c1,c2,…,ck}表示人為給予的分類，c1表示落入c1中的樣本數(shù)據(jù)，N為樣本數(shù)據(jù)的數(shù)量。顯然，聚類純度越大意味著填充后的數(shù)據(jù)有效性越高。

本文所用的數(shù)據(jù)集來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫的鳶尾屬植物數(shù)據(jù)集、乳腺癌數(shù)據(jù)集、種子數(shù)據(jù)集、精液活力數(shù)據(jù)集和僧侶問題數(shù)據(jù)集。

(1) 鳶尾屬植物數(shù)據(jù)集由Fisher于1936年提供，數(shù)據(jù)集包含3個類別的鳶尾屬植物，每個類別有50個數(shù)據(jù)。其中，第一類與第二、三兩類是線性可分的，而第二類與第三類是非線性可分的。

(2) 種子數(shù)據(jù)集由波蘭科學(xué)院的農(nóng)業(yè)研究所提供，該數(shù)據(jù)集包含3類小麥內(nèi)核幾何結(jié)構(gòu)的測量值。實(shí)驗(yàn)者用X射線技術(shù)掃描種子內(nèi)核，把成像圖記錄在13×18厘米的X射線柯達(dá)板上，并獲取相關(guān)數(shù)據(jù)。

(3) 乳腺癌數(shù)據(jù)集是由Ljublijana大學(xué)醫(yī)學(xué)中心腫瘤研究所的Matjaz Zwitter和Milan Soklic提供。數(shù)據(jù)集包含2類：良性腫瘤和惡性腫瘤，每類分別為201個數(shù)據(jù)和85個數(shù)據(jù)。

(4) 精液活力數(shù)據(jù)集是根據(jù)WHO 2010標(biāo)準(zhǔn)對100個志愿者的精液分析得到的數(shù)據(jù)，精液樣本被分為正常與不正常兩類。該數(shù)據(jù)集由Alicante大學(xué)計(jì)算機(jī)系的David Gil和生物系的Jose Luis Girela提供。

(5) 僧侶問題數(shù)據(jù)集由Carnegie Mellon 大學(xué)計(jì)算機(jī)學(xué)院的Sebastian Thrun提供給UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫，通常被用于測試歸納算法。

實(shí)驗(yàn)中采用5-折交叉驗(yàn)證[16]，數(shù)據(jù)集平均分成5份，其中4份作為訓(xùn)練數(shù)據(jù)集，另外1份作為測試數(shù)據(jù)集，輪流讓其中的1份作為測試樣本，其余4份作為訓(xùn)練樣本，實(shí)驗(yàn)結(jié)果取平均值。

實(shí)驗(yàn)中依次將測試樣本中的前若干個屬性作為缺失屬性；然后由完備樣本(即訓(xùn)練樣本)，利用極限學(xué)習(xí)機(jī)算法建立缺失屬性與其他屬性之間的非線性映射關(guān)系；最后利用這個映射關(guān)系對測試樣本進(jìn)行填充。通過比較填充數(shù)據(jù)與真實(shí)數(shù)據(jù)的廣義平均絕對誤差和聚類純度兩個指標(biāo)來評價填充數(shù)據(jù)的效果。

使用的仿真軟件為Matlab R2013a，聚類算法采用Matlab 模式識別工具箱中的kmeans函數(shù)。該實(shí)驗(yàn)環(huán)境為：Windows XP操作系統(tǒng)，AMD Athlon(tm)II X2 250 Processor 3.01 GHz，2 GB內(nèi)存。

表1給出了四種填充方法在5個數(shù)據(jù)集上的廣義平均絕對誤差比較和實(shí)驗(yàn)數(shù)據(jù)的細(xì)節(jié)。由表1可見，對于鳶尾屬植物數(shù)據(jù)集和種子數(shù)據(jù)集，在四種填充算法中，極限學(xué)習(xí)機(jī)填充方法得到的廣義的平均絕對誤差最小；對于乳腺癌數(shù)據(jù)集、精液活力數(shù)據(jù)集和僧侶問題數(shù)據(jù)集，極限學(xué)習(xí)機(jī)填充方法在多數(shù)情況下得到的廣義的平均絕對誤差最小，這意味著利用極限學(xué)習(xí)機(jī)填充方法得到的填充數(shù)據(jù)更接近真實(shí)值。

表1　四種填充方法在5個數(shù)據(jù)集上的廣義平均絕對誤差比較和實(shí)驗(yàn)數(shù)據(jù)的細(xì)節(jié)

圖2-圖6給出了四種填充方法在5個UCI數(shù)據(jù)集上的聚類純度比較。可以看出，對于鳶尾屬植物數(shù)據(jù)集、種子數(shù)據(jù)集和乳腺癌數(shù)據(jù)集，在四種填充算法中，極限學(xué)習(xí)機(jī)填充方法得到的聚類純度最高；對于精液活力數(shù)據(jù)集，四種方法取得的聚類純度幾乎相同；對于僧侶問題數(shù)據(jù)集，極限學(xué)習(xí)機(jī)填充方法在多數(shù)情況下得到的聚類純度最高，這意味著利用極限學(xué)習(xí)機(jī)填充方法得到的填充數(shù)據(jù)更具有使用價值。綜上所述，本文提出的極限學(xué)習(xí)機(jī)填充方法在多數(shù)情況下能取得比其他三種經(jīng)典的填充方法更好的填充效果。

圖2　四種填充方法在鳶尾屬植物數(shù)據(jù)集數(shù)據(jù)集上的聚類純度比較

圖3　四種填充方法在種子數(shù)據(jù)集上的聚類純度比較

圖4　四種填充方法在乳腺癌數(shù)據(jù)集上的聚類純度比較

圖5　四種填充方法在精液活力數(shù)據(jù)集上的聚類純度比較

圖6　四種填充方法在僧侶問題數(shù)據(jù)集上的聚類純度比較

3　結(jié)　語

本文提出了一種基于極限學(xué)習(xí)機(jī)的缺失數(shù)據(jù)填充方法，利用極限學(xué)習(xí)機(jī)建立缺失屬性與其他屬性之間的非線性映射關(guān)系，并利用這種映射關(guān)系進(jìn)行缺失屬性填充。 零填充和均值填充執(zhí)行過程簡單、速度較快，但執(zhí)行過程中沒有進(jìn)行充分的學(xué)習(xí)，填充效果較差。K近鄰填充比零填充和均值填充的填充效果要好，但當(dāng)樣本容量較大時，由于要計(jì)算缺失樣本中每個樣本點(diǎn)與完備樣本中每個樣本點(diǎn)的歐氏距離，運(yùn)算量很大，嚴(yán)重影響其運(yùn)算速度。實(shí)驗(yàn)表明，新的填充方法是有效的。

[1] 龐新生.缺失數(shù)據(jù)處理方法的比較[J].統(tǒng)計(jì)與決策,2010(24):152-155.

[2] 金勇進(jìn).缺失數(shù)據(jù)的插補(bǔ)調(diào)整[J].數(shù)理統(tǒng)計(jì)與管理,2001，20(5):47-53.

[3] 何凱濤,陳明,張治國，等.用人工神經(jīng)網(wǎng)絡(luò)進(jìn)行空間不完備數(shù)據(jù)的插補(bǔ)[J].地質(zhì)通報(bào),2005，24(5):476-479.

[4] Huang G B,Zhu Q Y,Siew C K.Extreme learning machine:theory and applications[J].Neurocomputing,2006,70(1-3):489-501.

[5] Huang G B,Chen L.Convex incremental extreme learning machine[J].Neurocomputing,2007,70(16-18):3056-3062.

[6] Ding S F,Zhao H,Zhang Y N,et al.Extreme learning machine:algorithm, theory and applications[J].Artificial Intelligence Review,2015,44(1):103-115.

[7] Huang G B,Zhou H M,Ding X J,et al.Extreme learning machine for regression and multiclass classification[J].Systems, Man & Cybernetics, Part B: Cybernetics, IEEE Transactions on,2012,42(2):513-529.

[8] Zhang L,Zhang Y,Li P.A novel Bio-inspired image recognition Network with Extreme Learning Machine[C]//Proceedings of ELM-2014:Algorithms and Theories,2015,1:131-139.

[9] Dwiyasa F,Lim M H.Extreme learning machine for active RFID location classification[C]//Proceedings of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems,2015,2:657-670.

[10] Feng L,Wang J,Liu S L,et al.Multi-label dimensionality reduction and classification with Extreme learning machines[J].Journal of Systems Engineering & Electronics,2014,25(3):502-513.

[11] Deng W Y,Zheng Q H,Chen L.Regularized extreme learning machine[C]//IEEE Symposium on Computational Intelligence and Data Mining,2009:389-395.

[12] 鄧萬宇,鄭慶華,陳琳，等.神經(jīng)網(wǎng)絡(luò)極速學(xué)習(xí)方法研究[J].計(jì)算機(jī)學(xué)報(bào),2010,33(2):279-287.

[13] Martínez-Martínez J M,Escandell-Montero P,Soria-Olivas E, et al.Regularized extreme learning machine for regression problems[J].Neurocomputing,2011,74(17):3716-3721.

[14] Yu Q，Miche Y,Eirola E,et al.Regularized extreme learning machine for regression with missing data[J].Neurocomputing,2013,102:45-51.

[15] He Q,Jin X,Du C Y,et al.Clustering in extreme learning machine feature Space[J].Neurocomputing,2013,128:88-95.

[16] Zhao Y P,Wang K K.Fast cross validation for regularized extreme learning machine[J].Journal of Systems Engineering & Electronics,2014,25(5):895-900.

A METHOD FOR MISSING DATA IMPUTATION BASED ON EXTREME LEARNING MACHINE

Yang YiLu Chengbo

(FacultyofEngineeringandDesign,LishuiUniversity,Lishui323000,Zhejiang,China)

In data processing process the problems of having to impute incomplete data are often encountered, so it is important to look for a simple and effective missing data imputation method. In view of this, the paper presents an extreme learning machine-based method for missing data imputation. Based on extreme learning machine modelling it builds a nonlinear mapping model of missing attributes with the need of imputation as well as other attributes. Experimental result shows that the new algorithm has excellent performance in imputation.

Extreme learning machineMissing data imputationUCI machine learning database

2015-04-27。國家自然科學(xué)基金項(xiàng)目(11171137)；浙江省自然科學(xué)基金項(xiàng)目(LY13A010008)。楊毅，講師，主研領(lǐng)域：人工神經(jīng)網(wǎng)絡(luò)與機(jī)器學(xué)習(xí)。盧誠波，副教授。

TP181TP183

A

10.3969/j.issn.1000-386x.2016.10.054