一種基于極限學習機的缺失數據填充方法

楊　毅　盧誠波

(麗水學院工程與設計學院　浙江 麗水 323000)

?

一種基于極限學習機的缺失數據填充方法

楊毅盧誠波

(麗水學院工程與設計學院浙江 麗水 323000)

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

極限學習機缺失數據填充UCI機器學習數據庫

0　引　言

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

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

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

1　基于極限學習機的缺失數據填充方法

2004年，黃廣斌等提出極限學習機算法[4-6]，該算法只需要設置單隱層前饋神經網絡的隱層節點個數，在算法執行過程中不需要調整網絡的輸入權和隱元的偏置，并產生唯一的最優解。

給定樣本容量為N的樣本(xi,yi)，其中i≤N，xi∈Rn且yi∈Rm，xi是輸入的樣本值，yi是輸出的期望值。隱層節點數為L的單隱層前饋神經網絡可表示如下：

(1)

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

Hβ=O

(2)

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

(3)

圖1　輸入權和隱層偏置隨機給定的單隱層前饋神經網絡

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

Hβ=y

(4)

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

H?=(HTH)-1HT

為了權衡經驗風險和結構風險，進一步提高網絡的泛化性能，文獻[11-14]研究了正則極限學習機,其數學模型為：

(5)

式中，誤差‖ε‖2代表經驗風險，‖β‖2代表結構風險，它來自于統計學中邊緣距離最大化原理；而γ是兩種風險的比例參數，用來權衡這兩種風險。

求解上述模型，可得:

(6)

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

該算法的具體步驟如下：

第1步根據完備樣本的數目確定合適的隱層節點個數；

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

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

2　仿真實驗

實驗將本文的填充方法與零填充、均值填充、K近鄰填充方法在廣義平均絕對誤差和聚類純度兩個指標上進行比較。

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

(7)

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

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

本文所用的數據集來自UCI機器學習數據庫的鳶尾屬植物數據集、乳腺癌數據集、種子數據集、精液活力數據集和僧侶問題數據集。

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

(2) 種子數據集由波蘭科學院的農業研究所提供，該數據集包含3類小麥內核幾何結構的測量值。實驗者用X射線技術掃描種子內核，把成像圖記錄在13×18厘米的X射線柯達板上，并獲取相關數據。

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

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

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

實驗中采用5-折交叉驗證[16]，數據集平均分成5份，其中4份作為訓練數據集，另外1份作為測試數據集，輪流讓其中的1份作為測試樣本，其余4份作為訓練樣本，實驗結果取平均值。

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

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

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

表1　四種填充方法在5個數據集上的廣義平均絕對誤差比較和實驗數據的細節

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

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

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

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

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

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

3　結　語

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

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

[2] 金勇進.缺失數據的插補調整[J].數理統計與管理,2001，20(5):47-53.

[3] 何凱濤,陳明,張治國，等.用人工神經網絡進行空間不完備數據的插補[J].地質通報,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].計算機學報,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。國家自然科學基金項目(11171137)；浙江省自然科學基金項目(LY13A010008)。楊毅，講師，主研領域：人工神經網絡與機器學習。盧誠波，副教授。

TP181TP183

A

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