缺失數(shù)據(jù)的混合式重建方法

于本成，丁世飛

（1. 中國礦業(yè)大學 計算機科學與技術學院，江蘇 徐州 221116; 2. 徐州工業(yè)職業(yè)技術學院 信息與電氣工程學院，江蘇 徐州 221004）

鑒于缺失數(shù)據(jù)重建的重要性，研究人員已經(jīng)就缺失數(shù)據(jù)重建問題提出了多種解決方法。粒子群優(yōu)化 (particle swarm optimization，PSO)在1995年由Kennedy和Eberhart提出[1-2]。PSO通過群體內個體之間的信息共享來對問題的解進行協(xié)同搜索[3]，即初始化一群隨機粒子，并通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤局部最優(yōu)值和全局最優(yōu)值來更新自己的速度與位置[4]。文獻[5]通過調整慣性權重的取值，提出了自適應混沌粒子群優(yōu)化算法，該算法避免了粒子早熟收斂情況。文獻[6]中Krishna和Ravi提出了一種基于粒子群優(yōu)化和矩陣協(xié)方差結構的數(shù)據(jù)重建方法，他們使用PSO重建缺失值。

進化聚類算法(evolving clustering method，ECM)是一步到位的快速聚類算法，在ECM中，由用戶定義的閾值參數(shù)會影響群集合數(shù)量的估計，值太大或太小都不利于找出群集合數(shù)量[7-8]。Ravi等[9-10]提出了4種用于重建的混合方法。在線重建中使用了具有廣義回歸神經(jīng)網(wǎng)絡的ECM(ECM+GRNN)，在離線重建中使用了K-means+GRNN和K-medoids+GRNN以及具有多層感知機的K-medoids(K-medoids+MLP)。他們雖然提出了基于ECM的數(shù)據(jù)重建，但值選擇涉及了試錯法，結果都不同程度地受到值的影響。

極限學習機(extreme learning machine，ELM)是由Huang等[11-12]提出的，它是一種新穎的前饋神經(jīng)網(wǎng)絡，不需要權重更新。目前ELM的理論與算法研究主要集中在隨機生成參數(shù)的優(yōu)化、最優(yōu)外權的求解、最優(yōu)隱藏層節(jié)點個數(shù)的選取、ELM核函數(shù)、在線極限學習機算法等方面[13]。文獻[14]發(fā)現(xiàn)自聯(lián)想的極限學習機(auto associative extreme learning machine，AAELM)在同一個數(shù)據(jù)集合中的不同運行產(chǎn)生了不同的結果。有時，連接輸入層和隱藏層的隨機加權會使結果出現(xiàn)很大的波動。在文獻[15]中Ravi和Krishna為重建提出了多種在線和離線方法，即粒子群優(yōu)化訓練后的自動關聯(lián)神經(jīng)網(wǎng)絡(PSOAANN)、粒子群優(yōu)化訓練后的自動關聯(lián)子波神經(jīng)網(wǎng)絡(PSOAAWNN)、徑向基函數(shù)自動關聯(lián)神經(jīng)網(wǎng)絡(RBFAANN)、廣義回歸自動關聯(lián)神經(jīng)網(wǎng)絡(GRAANN)，這些算法仍有待于進一步改進。

1 基礎理論

1.1 PSO算法

1)隨機初始化群體，設定粒子的位置和速度；

2)根據(jù)適應度函數(shù)計算粒子的適應度值，選取具有最優(yōu)適應度值的粒子位置作為，每個粒子當前位置為；

3)根據(jù)式(1)、式(2)更新粒子的速度和位置；

6)檢查是否滿足終止條件，如果滿足則終止迭代，否則返回2)。

1.2 ECM算法

2)如果輸入數(shù)據(jù)流的所有樣本都已處理完畢，則算法結束。否則，取當前樣本，計算與已經(jīng)創(chuàng)建的所有個集群中心之間的距離，

1.3 ELM算法

式中H表示隱藏層的矩陣。H矩陣第i行代表輸入層中第i個實例在隱藏層所有神經(jīng)元上的輸出，H矩陣的第j列代表所有訓練樣本在第j個隱藏層神經(jīng)元上的輸出，即

在已知權值和偏置的情況下，上面問題的求解就轉化為求解線性系統(tǒng)的最小范數(shù)最小二乘解：

2 提出的混合式重建方法

2.1 PSOECM方法

PSOECM方法步驟：

5) 重復 1)～4)直至收斂。

計算平均絕對百分比誤差(mean absolute percentage error，MAPE)值：

2.2 MAAELM方法

MAAELM方法采用PSOECM與AAELM混合重建缺失數(shù)據(jù)。MAAELM結構如圖1所示。

圖1 MAAELM結構Fig. 1 Architecture of the MAAELM

MAAELM方法步驟：

1)將數(shù)據(jù)歸一化至[0,1]范圍內。

2)將數(shù)據(jù)集合分為完整記錄集合和不完整記錄集合。

3)在1)中執(zhí)行基于PSOECM的重建，確定群集中心。

5)執(zhí)行PSOECM方法的3)。

6)計算得到各個群集中心之間的歸一化歐幾里德距離。

為了估算出隱藏層和輸出層之間的權重，在6)得到的距離中應用激活函數(shù)并進行非線性轉換，再應用Moore-Penrose廣義逆矩陣得出。

最后，根據(jù)文獻[12]使用Moore-Penrose廣義逆矩陣求解估算出隱藏層和輸出層之間的權重，其中為權向量，為目標向量。利用式(12)計算平均絕對百分誤差(MAPE)值。

3 選取實驗數(shù)據(jù)集與激活函數(shù)

實驗選取UCI機器學習數(shù)據(jù)庫中的6個標準數(shù)據(jù)集來進行驗證，實驗數(shù)據(jù)集如表1所示。同時，在選取的實驗數(shù)據(jù)集上使用9個激活函數(shù)來研究它們對文章所提方法的影響。實驗選取激活函數(shù)如表2所示。所選數(shù)據(jù)集中除Auto-mpg中的馬力屬性值存在缺失，其他5個數(shù)據(jù)集均不存在屬性缺失值，所以通過隨機刪除原始數(shù)據(jù)集的一些值來進行實驗，并創(chuàng)建了除目標變量以外的所有變量中的缺失值。每一個數(shù)據(jù)集被分成10個相等的小集合，其中9個小集合經(jīng)過聚類處理，剩下的1個留下為缺失值備用。

為了在每一個小集合中創(chuàng)建缺失值，隨機刪除了近10%的值(單元)，并確保從每個記錄中刪除至少一個單元。因此，在10倍交叉驗證中，有不同缺失記錄的10個小集合。

對于完整記錄集合中的各個小集合，將它們從全部記錄中分理并用于聚類。在完整記錄集合中應用ECM算法，并通過最近群集中心屬性的對應值重建出不完整記錄集合中的屬性缺失值。

使用PSO優(yōu)化算法和文獻[6]提及的兩個適應度函數(shù)為PSOECM選出最佳值，并將相同的值提供給MAAELM。對于所有數(shù)據(jù)集合，對比了本文所提方法與文獻[6, 9-10, 15, 17]所提多種混合方法的MAPE平均值。

表1 實驗數(shù)據(jù)集Table 1 Data sets for the experiment

表2 激活函數(shù)表Table 2 Activation functions

4 實驗結果和分析

不同激活函數(shù)作用于MAAELM所得的MAPE值以及PSOECM、MAAELM與其他算法比較的結果如圖2和圖3所示。

圖2 不同激活函數(shù)對MAAELM的影響Fig. 2 Influence of different activation functions on the MAAELM

圖3 不同算法的MAPE值Fig. 3 MAPE value of different algorithms

根據(jù)圖2所展示的不同激活函數(shù)作用于MAAELM所得的MAPE值可以發(fā)現(xiàn)：Sigmoid在所有激活函數(shù)中的表現(xiàn)最佳，Hardlim激活函數(shù)表現(xiàn)最差，而其他激活函數(shù)對于MAAELM的MAPE值影響基本相同。Hardlim激活函數(shù)表現(xiàn)最差是因為它將一個輸入空間只分割為0和1兩個類別。

圖3中將本文所提算法與Krishna M和Ravi V[6]的PSO_COV算法，Nishanth和Ravi[9]的K-means+GRNN、K-medoids+MLP、K-medoids+GRNN、ECM+GRNN等算法，Gautam和Ravi[10]的ECM Imputation算法，Ravi和 Krishna[15]的PSOAANN、PSOAAWNN、RBFAANN、GRAANN等算法，Ankaiah和 Ravi[17]的K-Means+MLP算法的結果進行對比，對比結果顯示了最佳值在所提方法中可以更有效地進行基于ECM的重建，以及在大部分數(shù)據(jù)集合上局部學習和整體學習混合使用優(yōu)于文獻[6, 9-10, 15, 17]所提方法。

在Auto-mpg 數(shù)據(jù)集合方面，只有K-medoids+GRNN、ECM+GRNN和GRAANN這3種混合法的結果與PSOECM方法接近，分別落后1.31%、1.65%和0.19%。PSOECM 通過選擇最佳值，在Auto-mpg數(shù)據(jù)集合中的表現(xiàn)優(yōu)于ECM重建。將PSOECM得出的相同值帶入MAAELM時，誤差又降低了0.96%。

在Boston Housing數(shù)據(jù)集合方面，除了GRAANN方法與PSOECM方法相差0.88%之外，其他方法的MAPE值至少比PSOECM高3%。PSOECM 通過選擇最佳值，在Boston Housing數(shù)據(jù)集合中的表現(xiàn)同樣優(yōu)于ECM重建。在MAAELM中應用PSOECM得出的最佳值之后，MAPE值便可以進一步降低0.32%。

在Forest fires數(shù)據(jù)集合方面，可以觀察到與Boston Housing數(shù)據(jù)集合相似的性能。除了GRAANN落后PSOECM的結果0.13%之外，其他方法的MAPE值比PSOECM至少高4%。PSOECM 通過選擇最佳值，MAPE同樣有所下降。在MAAELM中應用PSOECM得出最佳值之后，誤差又降低了0.68%。

除了在Spectf 數(shù)據(jù)集合中，PSOECM略遜于GRAANN 之外，在 Iris、Spectf 和 Wine recognition數(shù)據(jù)集合中，PSOECM與MAAELM同樣表現(xiàn)出了類似在 Auto-mpg、Boston Housing、Forest fires數(shù)據(jù)集合中的優(yōu)勢。

經(jīng)上述實驗結果的分析得出：1)PSOECM 通過選擇最佳值，在各個數(shù)據(jù)集合中的表現(xiàn)優(yōu)于ECM重建；2)將PSOECM得出的相同值代入MAAELM時，所得MAPE值均有所降低。

5 結束語

本文提出了2種新穎的缺失數(shù)據(jù)的混合式重建方法，并使用6個數(shù)據(jù)集驗證了所提方法的有效性。發(fā)現(xiàn)由PSO為ECM選出的最佳值在PSOECM和MAAELM的優(yōu)異性能方面起到了重要作用，解決了值的選取困難和值對ECM重建結果的影響問題，同時去除了AAELM的隨機性。下一步研究將增大實驗數(shù)據(jù)集，驗證本文所提方法在原始數(shù)據(jù)缺失不同百分比時的結果，以及使用更多的激活函數(shù)來進一步驗證所提方法的有效性，并對所提方法與現(xiàn)有方法進行威爾克森符號秩檢驗，驗證所提方法的顯著性。