鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法

朱先遠(yuǎn)，嚴(yán)遠(yuǎn)亭，張燕平

1.安徽商貿(mào)職業(yè)技術(shù)學(xué)院 信息與人工智能學(xué)院，安徽 蕪湖 241002

2.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥 230601

數(shù)據(jù)分類是機器學(xué)習(xí)、數(shù)據(jù)挖掘和模式識別等領(lǐng)域的重要任務(wù)[1-2]，但由于數(shù)據(jù)收集、網(wǎng)絡(luò)傳輸?shù)龋藗兡玫降拇诸悢?shù)據(jù)往往都有一定程度的不完整性，這類數(shù)據(jù)稱為不完整數(shù)據(jù)集，如：微陣列數(shù)據(jù)[3-4]、移動電話數(shù)據(jù)[5]、可視化數(shù)據(jù)[6]、工業(yè)數(shù)據(jù)[7]、軟件項目數(shù)據(jù)[8]等。對不完整數(shù)據(jù)集分類首先需要對其進(jìn)行預(yù)處理再分類。不完整數(shù)據(jù)集預(yù)處理常用方法有刪除法和填充法兩類方法。刪除法即直接刪除含有缺失值的數(shù)據(jù)樣本，數(shù)據(jù)集中只保留信息完整的數(shù)據(jù)樣本。在數(shù)據(jù)樣本獲取代價較高情形下，刪除含有缺失值的數(shù)據(jù)樣本會造成數(shù)字資源浪費和有用信息的丟失。填充法是利用一些經(jīng)典填充算法對不完整數(shù)據(jù)集中的缺失值進(jìn)行估計填充。在不完整數(shù)據(jù)分類前利用填充算法將不完整數(shù)據(jù)填充為完整數(shù)據(jù)可以提高分類精確度[9]。不完整數(shù)據(jù)的填充算法研究，對不完整數(shù)據(jù)分類具有重要現(xiàn)實意義。

目前，針對不完整數(shù)據(jù)集的缺失值填充已積累了不少研究成果[10-14]，這些成果在缺失值填充上多是基于統(tǒng)計學(xué)指標(biāo)和機器學(xué)習(xí)算法。如均值填充（mean imputation，MEI）[15]，其用數(shù)據(jù)樣本中非空屬性值的均值對缺失值進(jìn)行填充，其一般適合缺失值極少情況或者需要快速填充的場景，類似地還有矩陣分解填充（imputation iterative SVD，ISVD）[16]、SoftImput[17]等，利用矩陣分解技術(shù)，對數(shù)據(jù)進(jìn)行降維，然后在降維后的數(shù)據(jù)矩陣?yán)媒y(tǒng)計學(xué)指標(biāo)來估計缺失值。在機器學(xué)習(xí)填充算法中，數(shù)據(jù)樣本空間中完整數(shù)據(jù)樣本作為訓(xùn)練和測試的輸入，待填充的空缺值被看作是模型的目標(biāo)輸出，常見的算法有K最近鄰填充（Knearest neighbor imputation，KNNI）[18]、聚類填充（CKNNI）[19]、決策樹填充等。K近鄰填充利用離缺失樣本最近的K個鄰居樣本產(chǎn)生一個估計值進(jìn)行填充，在數(shù)據(jù)填充問題上不需要復(fù)雜模型，但其在不平衡數(shù)據(jù)問題上表現(xiàn)效果不佳。聚類填充是將所有樣本聚類到若干個簇中，利用簇內(nèi)相似度較高的完整樣本對缺失值進(jìn)行填充。其一定程度上考慮了樣本空間分布，但其初始聚類中心數(shù)依賴于樣本數(shù)據(jù)，不同樣本數(shù)據(jù)進(jìn)行調(diào)參過程復(fù)雜多變，難以控制。

這些經(jīng)典數(shù)據(jù)填充算法目前已被廣泛應(yīng)用于解決不完整數(shù)據(jù)的填充問題。但這些研究方法在不完整數(shù)據(jù)分類的缺失值填充處理上，往往都是選擇一種填充方法進(jìn)行填充，很少考慮融合多種填充方法。此外，相鄰的數(shù)據(jù)樣本屬性值具有相關(guān)性，如何快速有效地找到缺失樣本的近鄰數(shù)據(jù)樣本，用這些近鄰數(shù)據(jù)樣本鄰域信息對缺失值進(jìn)行填充仍需做進(jìn)一步研究。

結(jié)合對不完整數(shù)據(jù)分類問題的上述考慮，本文提出一種基于鄰域信息修正不完整數(shù)據(jù)多填充集成分類方法。該方法一方面通過嵌入基于鄰域信息的修正填充策略，實現(xiàn)了利用近鄰數(shù)據(jù)樣本鄰域信息對缺失值的填充，另一方面也利用多填充的數(shù)據(jù)多樣性，通過集成學(xué)習(xí)融合了不同經(jīng)典填充方法的優(yōu)勢。

1 相關(guān)工作

1.1 不完整數(shù)據(jù)集及相關(guān)預(yù)填充方法

預(yù)填充和修正填充主要都是以不完整數(shù)據(jù)集的缺失值為對象，為了方便描述，這里先給出一個不完整數(shù)據(jù)集和缺失值集合的定義。

定義1（不完整數(shù)據(jù)集）D={X1,X2,…,Xn} 表示一個不完整數(shù)據(jù)集，其中，n表示數(shù)據(jù)樣本的數(shù)量，Xi表示一個數(shù)據(jù)樣本，每個數(shù)據(jù)樣本由m個屬性組成，為不完整數(shù)據(jù)集D的第i個數(shù)據(jù)樣本的第j維屬性值，表示數(shù)據(jù)集中第i個樣本的第j維屬性值為空，即缺失值。

定義2（缺失值集合）給定一個不完整數(shù)據(jù)集D={X1,X2,…,Xn}，所有缺失值的集合IND為：

對不完整數(shù)據(jù)進(jìn)行預(yù)填充，就是利用一些經(jīng)典填充算法對不完整數(shù)據(jù)集D的缺失值集合IND中所有元素進(jìn)行填充。下面給出幾種常用預(yù)填充算法的定義。

定義3（均值填充（MEI））[15]一種簡單的基于統(tǒng)計學(xué)的單一填充方法，適用于快速完成數(shù)據(jù)填充需求，對缺失值的計算如公式（2）所示：

其中，I為第k維屬性值非空的數(shù)據(jù)樣本集合，|I|為第k維屬性值非空的數(shù)據(jù)樣本的個數(shù)。

定義4（中值填充（median imputation，MDI））[15]一種缺失值處理方法，它使用樣本數(shù)據(jù)中的中位數(shù)來填補缺失值。對缺失值的計算如公式（3）所示：

其中，I為第k維屬性值非空的數(shù)據(jù)樣本集合，I*為集合I中進(jìn)行排序后集合。

定義5（矩陣分解填充（ISVD））[16]一種基于矩陣分解的缺失值填充方法，它采用奇異值分解（SVD）來分解矩陣，并使用迭代過程逐步重建缺失值。

定義6（K近鄰填充（KNNI））[17]一種基于KNN 算法的一種缺失值填充方法，對缺失值的計算如公式（4）所示：

其中，Ni表示的是第j維屬性不缺失且距離第i個樣本最近的k個樣本集合；|Ni|表示的是Ni集合中的樣本個數(shù)。

定義7（相似度加權(quán)平均填充（similarity weighted averaging impute，SWAI））[20]一種基于相似性的插補方法，它的基本思想是利用與含缺失值樣本相似的完整樣本對缺失值進(jìn)行填充。在這種方法中，對于每個缺失的數(shù)據(jù)樣本，先尋找與該樣本相似的其他數(shù)據(jù)樣本（通常是歐幾里德距離或余弦相似度等度量方法），然后對這些相似數(shù)據(jù)樣本的已知值進(jìn)行加權(quán)平均以獲得缺失值的估計值。

其中均值填充、中值填充都屬于基于統(tǒng)計學(xué)指標(biāo)的填充策略；ISVD 為矩陣分解填充策略的代表；K近鄰填充屬于使用機器學(xué)習(xí)算法進(jìn)行填充策略；相似度加權(quán)平均填充是利用樣本間的相似性來推斷缺失值，在基因表達(dá)數(shù)據(jù)集上測試結(jié)果十分優(yōu)異的填充算法代表。

1.2 修正填充相關(guān)方法

修正填充是對不完整數(shù)據(jù)進(jìn)行預(yù)填充后，進(jìn)一步對填充值進(jìn)行修改和優(yōu)化的過程。在相關(guān)研究中，Liu等[21]提出了一種基于兩階段深度自動編碼器的缺失數(shù)據(jù)插補方法。該方法可以分為兩個階段：第一階段利用已知數(shù)據(jù)訓(xùn)練一個深度自動編碼器，以學(xué)習(xí)數(shù)據(jù)的潛在表示。然后使用該自動編碼器來重構(gòu)缺失數(shù)據(jù)，并計算真實數(shù)據(jù)和重構(gòu)數(shù)據(jù)之間的重構(gòu)誤差。在第二階段，使用另一個自動編碼器來進(jìn)一步優(yōu)化缺失數(shù)據(jù)的重構(gòu)，以減小重構(gòu)誤差。嚴(yán)遠(yuǎn)亭等[22]提出了一種構(gòu)造性覆蓋下不完整數(shù)據(jù)修正填充方法。首先利用現(xiàn)有填充方法對樣本進(jìn)行預(yù)填充；然后再通過引入一種空間鄰域信息挖掘方法來找到與待填樣本具有更高相似度的若干個空間鄰域；最后利用待填樣本的空間鄰域內(nèi)的有效信息對現(xiàn)有填充方法產(chǎn)生的填充結(jié)果進(jìn)行修正。Choudhury等[23-24]基于神經(jīng)網(wǎng)絡(luò)給出分類任務(wù)中的缺失數(shù)據(jù)填充方法。該方法使用已知數(shù)據(jù)進(jìn)行訓(xùn)練構(gòu)建一個神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。然后，通過在神經(jīng)網(wǎng)絡(luò)中進(jìn)行信息傳播和融合的方式，將已知數(shù)據(jù)的信息傳遞給缺失數(shù)據(jù)樣本，以預(yù)測和修正填充缺失值。該方法可以利用全局信息和數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，提高修正填充的準(zhǔn)確性。

除了上述方法，還有其他修正填充方法，每種方法都有其獨特的特點和適用場景，選擇合適的方法需要考慮數(shù)據(jù)集的特征、缺失值的模式以及應(yīng)用需求等因素。

1.3 集成學(xué)習(xí)方法

集成學(xué)習(xí)（ensemble learning）[25]就是組合多個弱監(jiān)督模型以期得到一個更好、更全面的強監(jiān)督模型，研究始于1990年，是由Hansen和Salamon[26]提出的神經(jīng)網(wǎng)絡(luò)集成的方法。集成學(xué)習(xí)潛在的思想是即便某一個弱分類器得到了錯誤的預(yù)測，其他弱分類器也可以將錯誤糾正回來。按照用于集成學(xué)習(xí)算法中的基分類器是否相同可以將集成學(xué)習(xí)劃分為同質(zhì)集成和異質(zhì)集成。同質(zhì)集成是指構(gòu)成集成的所有基分類器都是同一種分類器，而異質(zhì)集成是指使用不同的分類器構(gòu)成集成學(xué)習(xí)。當(dāng)前已有的集成學(xué)習(xí)方法中，同質(zhì)集成學(xué)習(xí)最為常見。同質(zhì)集成學(xué)習(xí)又可以根據(jù)各個體學(xué)習(xí)器間是否存在依賴關(guān)系分為兩類：存在強依賴關(guān)系的個體學(xué)習(xí)器和不存在強依賴關(guān)系的個體學(xué)習(xí)器。前者的典型代表算法為Boosting算法[27]；后者的典型代表算法有Bagging算法[28]。

Boosting 算法是將弱學(xué)習(xí)器提升為強學(xué)習(xí)器的算法。主要的工作機制：首先利用初始訓(xùn)練集訓(xùn)練出一個弱學(xué)習(xí)器T1；再根據(jù)T1 的表現(xiàn)對訓(xùn)練樣本分布進(jìn)行調(diào)整，依據(jù)學(xué)習(xí)誤差率來對訓(xùn)練樣本的權(quán)重進(jìn)行更新，讓先前被T1判斷錯誤的樣本在后續(xù)學(xué)習(xí)中得到更多的關(guān)注。

Bagging 算法是另一種典型的集成學(xué)習(xí)策略，是從訓(xùn)練集進(jìn)行子抽樣組成每個基模型所需要的子訓(xùn)練集，來訓(xùn)練個體學(xué)習(xí)器（弱學(xué)習(xí)器），其主要工作機制：從原始樣本集中抽取訓(xùn)練集；每次使用一個訓(xùn)練集得到一個模型，k個訓(xùn)練集共得到k個模型；對分類問題：將上步得到的k個模型采用投票的方式得到分類結(jié)果，對回歸問題，計算上述模型的均值作為最后的結(jié)果。

集成方法是將幾種機器學(xué)習(xí)技術(shù)組合成一個預(yù)測模型的元算法，以達(dá)到減小方差（Bagging）、偏差（Boosting）或改進(jìn)預(yù)測（Stacking）的效果。集成學(xué)習(xí)的結(jié)合策略根據(jù)處理問題的差異，可以采用平均法、投票法[29]和學(xué)習(xí)法等。其中投票法是集成學(xué)習(xí)中最基礎(chǔ)的方法之一，其又分為硬投票和軟投票。硬投票是指取預(yù)測結(jié)果中票數(shù)最高的類別作為集成結(jié)果。軟投票則是將基分類器的預(yù)測概率加權(quán)平均作為最終的預(yù)測結(jié)果。雖然軟投票方法的效果會更好一些，但在實際運用中需要耗費更多的計算資源和時間，因此硬投票方法使用更為廣泛。鑒于以上考慮，本文采用了硬投票策略對幾個分類器預(yù)測的結(jié)果進(jìn)行投票。

2 鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法

本章將從不完整數(shù)據(jù)集成分類總體框架、不完整數(shù)據(jù)修正填充和多填充集成分類三方面，對本文提出的基于鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法做具體介紹。

2.1 不完整數(shù)據(jù)集成分類總體框架

本文提出鄰域信息修正的不完整數(shù)據(jù)多填充集成分類框架如圖1所示。其主要包括預(yù)填充、修正填充和集成分類等模塊組成。

圖1 鄰域信息修正的多填充集成分類框架Fig.1 Multiple imputation-revision ensemble classification framework with neighborhood information

對于一份原始不完整數(shù)據(jù)集D劃分為訓(xùn)練集Dtrain、測試集Dtest。對于訓(xùn)練集Dtrain，首先根據(jù)1.1節(jié)中介紹的五種經(jīng)典缺失值填充算法（MEI、KNNI、MICE、SWAI和ISVD）進(jìn)行預(yù)填充。對于同一個Dtrain每使用一種填充方法進(jìn)行預(yù)填充都可以得到一個完整數(shù)據(jù)集，若使用n種預(yù)填充方法將可以得到一組完整數(shù)據(jù)集{Dpre1,Dpre2,…,Dpren}。在預(yù)填充后、數(shù)據(jù)分類前的階段本框架嵌入了修正填充模塊，利用該模塊對{Dpre1,Dpre2,…,Dpren}中的填充值做進(jìn)一步修正，修正填充后可以得到一組完整數(shù)據(jù)集{Dcmp1,Dcmp2,…,Dcmpn}。最后，該框架引入集成學(xué)習(xí)方法，將多填充得到的完整數(shù)據(jù)集集合{Dcmp1,Dcmp2,…,Dcmpn}分別作為輸入，分別訓(xùn)練基分類器，最終通過集成投票策略給出最終分類。在測試階段，對于一個測試樣本，首先判斷其是否包含缺失值，如不包含缺失值，則直接輸入集成分類器確定類別，如包含缺失值則先進(jìn)行預(yù)填充，然后利用已訓(xùn)練的分類器進(jìn)行集成分類，投票確定其類別。

2.2 不完整數(shù)據(jù)修正填充

本文提出的修正填充主要思想是以與缺失值高相關(guān)性的近鄰樣本信息為依據(jù)，對缺失值進(jìn)行再估算。要解決的關(guān)鍵問題是在預(yù)填充得到的完整數(shù)據(jù)集Dpre中找出與待填充樣本高相關(guān)性的近鄰數(shù)據(jù)樣本集合。K近鄰算法填充是依據(jù)距離大小搜索最近的K個鄰居，但對于不平衡數(shù)據(jù)集搜索時，K近鄰算法決策結(jié)果容易被其周圍的多數(shù)類近鄰樣本所誤導(dǎo)。為了避免在搜索不平衡數(shù)據(jù)集出現(xiàn)同樣問題，本文在搜索與待填充樣本高相關(guān)性的近鄰數(shù)據(jù)樣本時，除了考慮樣本空間距離因素外，還融合了候選樣本集中的類別純度因素。此外，為了方便在高維空間中快速搜索到近鄰樣本，在修正填充過程中還引入球樹[30]。為了方便描述，這里先給出球樹、純度和鄰域半徑的定義。

定義8（球樹（BallTree））一種二叉樹，其每個節(jié)點表示一個d維的超球面，或稱為球，球樹的每個內(nèi)部節(jié)點將數(shù)據(jù)點集合劃分為兩個不相交的集合，這兩個集合與不同的球相關(guān)聯(lián)。當(dāng)球本身可能相交時，每個點根據(jù)它到球心的距離被分配到其中一個球中。樹中每個葉節(jié)點定義了一個球并枚舉該球內(nèi)的所有數(shù)據(jù)點。

球樹的主要優(yōu)點在于它能夠快速地定位到距離查詢點最近的一些數(shù)據(jù)點，對于高維數(shù)據(jù)具有較好的性能，因為它能夠避免在高維空間中出現(xiàn)“維度災(zāi)難”問題。

定義9（純度（purity））對于由若干數(shù)據(jù)樣本點構(gòu)成的超球體，純度是指球心同類別的樣本點在超球體內(nèi)的占比，即待填充樣本點的候選集中與待填充樣本點同類別的點在候選集中的占比，純度計算公式如公式（5）所示：

其中，|B|表示超球體內(nèi)的樣本點數(shù)，yi表示樣本點Xi的類別，yB表示超球體球心類別，I是一個指示函數(shù)，當(dāng)yi=yB時取值為1，否則為0。

定義10（鄰域半徑（R））對于由若干數(shù)據(jù)樣本點構(gòu)成的超球體，鄰域半徑是指超球體的半徑，即一個數(shù)據(jù)樣本與其相鄰樣本共同構(gòu)造的鄰域空間的半徑。對于一個完整數(shù)據(jù)集Dpre={X1,X2,…,Xn}，鄰域半徑初始值R0的計算如公式（6）所示：

其中，n表示的數(shù)據(jù)集Dpre樣本數(shù)，d(Xi,Xj)表示Xi,Xj兩個樣本間的歐氏距離。

本文提出的基于鄰域信息修正填充方法是首先利用球樹作為樣本點間距離的存儲結(jié)構(gòu)，將所有數(shù)據(jù)樣本點劃分到一組嵌套的超球體內(nèi)，通過純度purity和鄰域半徑R，找出與缺失樣本相鄰的數(shù)據(jù)樣本，從而利用與缺失樣本相鄰的數(shù)據(jù)樣本信息對缺失值進(jìn)行修正填充。具體基于鄰域信息修正填充方法如下：

（1）利用公式（6）計算鄰域半徑初始值R0。

其中，min{d(Xi,Xj)}為與待填充樣本的所有同類別的樣本歐式距離的最小值，經(jīng)過迭代計算鄰域半徑R不斷接近min{d(Xi,Xj)}。

（3）對缺失值進(jìn)行修正填充。對于一個含缺失值的數(shù)據(jù)樣本Xi，假定經(jīng)過步驟2 后得到候選集為Candidate，則的計算如公式（8）所示：

其中，SETsc為候選集Candidate中與待填充樣本同類別的所有樣本組成的集合，|SETsc|表示集合SETsc中樣本數(shù)量，當(dāng)|SETsc|≠0 時，缺失值用候選集中所有與待填充樣本同類別的樣本第j維屬性值的均值對其進(jìn)行修正填充。在少數(shù)情形下|SETsc|=0，即候選集內(nèi)沒有與待填充樣本同類別的數(shù)據(jù)樣本，對于這類特殊情形不做修正填充，保留預(yù)填充值。

（4）重復(fù)步驟（2）、（3），直到完成所有缺失值的修正填充。

2.3 多填充集成分類

同一個不完整數(shù)據(jù)集經(jīng)過不同的預(yù)填充和修正后，得到了一組互不相同的完整數(shù)據(jù)集{Dcmp1,Dcmp2,…,Dcmpn}。為了融合不同填充算法的優(yōu)勢，本文引入基于bagging 的集成學(xué)習(xí)策略，將{Dcmp1,Dcmp2,…,Dcmpn}中每一個Dcmpi均作為一個基分類器的輸入，以此訓(xùn)練n個基分類器，最終通過集成學(xué)習(xí)的投票策略給出最終分類。多填充集成分類（multiple imputation ensemble classification，MIEC）算法偽代碼如算法1所示。

算法1多填充集成分類算法

3 實驗

3.1 評價指標(biāo)

本文選取NRMSE 評價指標(biāo)對不完整數(shù)據(jù)集的填充效果進(jìn)行評價，選取Accuracy對不完整數(shù)據(jù)的分類精確度進(jìn)行評價。NRMSE和Accuracy的定義如下：

（1）NRMSE

其中，xo和xg分別為數(shù)據(jù)集中缺失值對應(yīng)的原始值和被填充后的估計值。NRMSE值可以衡量出對缺失值的填充效果，值越小則代表填充的數(shù)據(jù)越接近原始值。

（2）Accuracy

其中，TP表示預(yù)測為正樣本實際也為正樣本的數(shù)量，TN表示預(yù)測為負(fù)樣本實際也為負(fù)樣本的數(shù)量，P和N分別表示正樣本數(shù)量和負(fù)樣本數(shù)量。Accuracy表示預(yù)測類別正確的樣本數(shù)量占所有樣本數(shù)量的比例，值越大則代表分類越好。

為了方便對比不同算法對不完整數(shù)據(jù)集的分類精確度，本文引入了精確度提高率（ImproveRate）概念，用來表示本文提出算法相對于其他分類算法的精度改善程度。

其中，Accuracy為本文提出算法的分類精確度，Accuracylevel為其他對比算法的分類精確度。ImproveRate若為正值，則表示本文分類算法分類精確度有提高，若為負(fù)值則表示本文分類算法分類精確度不如對比方法。

3.2 基準(zhǔn)數(shù)據(jù)集下算法性能分析

對于真實不完整數(shù)據(jù)集，由于缺失值所對應(yīng)的原始數(shù)據(jù)丟失，難以評估出填充算法的填充值與數(shù)據(jù)集原始值的擬合程度。為了方便評估缺失值填充實驗的填充效果，實驗時采用對完整數(shù)據(jù)集隨機刪除屬性值來模擬不完整數(shù)據(jù)集，最后通過對比填充算法給出的填充值與原始值的歸一化均方根誤差來評估算法填充效果。實驗時從UCI 選取10 個完整數(shù)據(jù)集作為基準(zhǔn)數(shù)據(jù)集，如表1所示。

表1 基準(zhǔn)數(shù)據(jù)集Table 1 Benchmark dataset

這10個數(shù)據(jù)集涉及不同領(lǐng)域，數(shù)據(jù)集規(guī)模、數(shù)據(jù)特征數(shù)各不相同，樣本數(shù)量規(guī)模從178 至13 611 個，樣本屬性數(shù)量從3 至32，樣本類別數(shù)量從2 分類至13 分類，其中ecoli、haberman、vertebral 為不平衡數(shù)據(jù)集。實驗時按照1%、5%、10%、20%這4 種不同缺失率對數(shù)據(jù)集的樣本屬性值進(jìn)行隨機刪除，模擬生成不同缺失率的不完整數(shù)據(jù)集。

3.2.1 算法填充效果實驗

為驗證本文提出的不完整數(shù)據(jù)多填充集成分類方法中嵌入的修正填充算法效果，實驗時將1%、5%、10%、20%這4 種缺失率的不完整數(shù)據(jù)集作為輸入，在嵌入修正填充前后分別計算NRMSE 值做對比實驗。實驗時首先采用1.1 節(jié)介紹的MEI 填充、MDI 填充、KNNI 填充、SWAI填充和ISVD填充5種經(jīng)典填充方法對輸入數(shù)據(jù)集進(jìn)行預(yù)填充，并根據(jù)公式（9）計算NRMSE值，然后再利用本文2.2 節(jié)給出的修正填充方法進(jìn)行修正填充，并根據(jù)公式（9）計算修正填充后的NRMSE 值。圖2 為不同缺失率下的10種數(shù)據(jù)集上嵌入修正填充前后的填充效果對比圖。其中，每個顏色柱的高度值為該填充算法的NRMSE值，MEI表示均值填充，R-MEI填充表示先均值填充再基于鄰域信息修正填充，MDI 表示中值填充，R-MDI 填充表示先中值填充再基于鄰域信息修正填充，KNNI 表示K近鄰填充，R-KNNI 表示先K近鄰填充再基于鄰域信息修正填充，ISVD 表示矩陣分解填充，R-ISVD 表示先矩陣分解填充再修正填充，SWAI 表示相似度加權(quán)平均填充，R-SWAI 表示先相似度加權(quán)平均填充再修正填充。為了避免了單次實驗得到的NRMSE 數(shù)據(jù)不穩(wěn)定性，實驗得到的NRMSE 值均為循環(huán)100次實驗獲取數(shù)據(jù)的均值。

圖2 填充效果對比圖Fig.2 Comparison diagram of imputation effects

從同一缺失率、某種數(shù)據(jù)集上各種填充算法嵌入修正填充前后的填充效果對比來看：R-KNNI 與KNNI 相比、R-MEI 與MEI 相比及MDI 與R-MDI 相比，在多數(shù)不完整數(shù)據(jù)集上嵌入修正填充后所表現(xiàn)出來的NRMSE值都較小，填充過效果較好，剩余少數(shù)數(shù)據(jù)集填充效果接近；R-SWAI 與SWAI 相比、ISVD 與R-ISVD 相比，在多數(shù)數(shù)據(jù)集上進(jìn)行修正填充后的NRMSE 值略小或近似相等，即填充效果有小幅提升或接近。從圖2（a）、（b）、（c）、（d）圖整體看，在ecoli、haberman、vertebral、wine 數(shù)據(jù)集上相比于其他數(shù)據(jù)集的算法填充NRMSE值都較大，究其原因，像wine 數(shù)據(jù)集的樣本量只有178個，用于填充可依據(jù)的數(shù)據(jù)樣本信息較少，所以填充的NRMSE 值都較大，填充效果欠佳。像ecoli、haberman、vertebral數(shù)據(jù)集為不平衡數(shù)據(jù)集，不平衡數(shù)據(jù)集中缺失值如果為少數(shù)類時，填充容易受到多數(shù)類影響，所以一般來說填充算法在不平衡數(shù)據(jù)集上填充效果都較一般，但就嵌入修正填充后的R-MEI、R-MDI、R-KNNI、R-SWAI、R-SVD 的幾種算法修正效果，相比于MDI、KNNI、SWAI、SVD來說，在多數(shù)不平衡數(shù)據(jù)集上填充效果都有提高。總體來說，嵌入修正填充相比于單獨采用MEI、MDI、KNNI、SWAI和ISVD算法填充，在大多數(shù)的不完整數(shù)據(jù)上的填充效果都有提高。

3.2.2 不完整數(shù)據(jù)分類精確度實驗結(jié)果與分析

為驗證本文提出的鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法在解決不完整數(shù)據(jù)集分類問題上的效果，本小節(jié)在表1給出的10種基準(zhǔn)數(shù)據(jù)集上做了精確度提高率對比實驗。實驗時首先采用MEI填充、MDI填充、KNNI填充、SWAI填充和ISVD填充5種算法填充得到五份完整數(shù)據(jù)集對某種分類器（本實驗數(shù)據(jù)采用KNN 作為分類器得到，采用其他分類器可以得到類似實驗結(jié)果）進(jìn)行訓(xùn)練，得出分類精確度；然后將預(yù)填充的5份數(shù)據(jù)集再進(jìn)一步修正填充得到對應(yīng)完整數(shù)據(jù)集，并利用最終得到的5份完整數(shù)據(jù)集對5個基分類器進(jìn)行訓(xùn)練，得出分類精確度；最后根據(jù)公式（11）計算出本文提出的多填充集成分類方法相對于其他分類方法的精確度提高率。圖3 為在10 種不同缺失率的不完整數(shù)據(jù)下算法分類精度提升率對比圖，其中，MEI、KNNI、SWAI、MED和ISVD這5種顏色柱，分別表示使用本文提出鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法相比于采用一種算法單填充后的分類精度提高率，如果顏色柱位于x軸上方表示本文提出的分類算法提高了分類準(zhǔn)確率，反之則表示算法的分類效果不理想。

圖3 分類精度提升率對比圖Fig.3 Comparison diagram of classification accuracy improvement rates

從最終實驗結(jié)果看，本文提出的鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法的精確度，在4種缺失率的10 種不完整數(shù)據(jù)集上，只有兩個顏色柱位于x軸下方，其余198個顏色柱都位于x軸上方。也就是說本文提出的鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法，基本上都比僅采用某種算法單填充后分類的分類精確度要高。尤其是在raisin、wine數(shù)據(jù)集上，算法的分類精度提升率最明顯。結(jié)合3.2.1小節(jié)填充效果實驗結(jié)果看，wine數(shù)據(jù)集在進(jìn)行3.2.1小節(jié)填充效果實驗時，各種填充算法填充效果都不理想。然而，在本節(jié)分類精度提升率實驗中，采用本文提出的分類算法后，其分類精確度有了明顯的提高。這表明，本文提出的融合不同填充算法的多填充集成分類算法是有效的，提高了不完整數(shù)據(jù)集分類精度。

3.3 真實不完整數(shù)據(jù)集下對比實驗及結(jié)果分析

在這一節(jié)中，為驗證本文分類算法對解決真實不完整數(shù)據(jù)分類問題的有效性，從UCI 中下載了10 個真實不完整數(shù)據(jù)集進(jìn)行實驗，數(shù)據(jù)集的詳細(xì)信息如表2 所示。這10 個數(shù)據(jù)集規(guī)模、數(shù)據(jù)特征數(shù)各不相同，樣本數(shù)量規(guī)模從32 至2 536 個，樣本屬性數(shù)量從6 至279，樣本類別數(shù)量從2分類至16分類，缺失率從2.2%至98.1%，這10 個數(shù)據(jù)集除了horse-colic、lung-cancer 和primarytumor均為不平衡數(shù)據(jù)集。

表2 真實數(shù)據(jù)集信息描述Table 2 Real dataset information

實驗過程中先分別用MEI、MDI、KNNI、SWAI 和ISVD 填充算法進(jìn)行預(yù)填充，得到5 份完整數(shù)據(jù)集。然后這5 份完整數(shù)據(jù)集作為輸入，并分別在KNN、RandomForestClassifier（RF）、SVM、DecisionTreeClassifier（DT）和LogisticRegression（LR）這5 種分類器中進(jìn)行分類實驗，根據(jù)公式（10）計算分類精確度；然后再利用本文2.3 節(jié)算法1（MIEC）進(jìn)行多填充集成分類實驗，根據(jù)公式（10）計算分類精確度。實驗中采用10倍交叉驗證方式將數(shù)據(jù)集分為訓(xùn)練集和測試集。表3至表7記錄了這10種真實不完整數(shù)據(jù)集在5種分類器中分類精確度，每張表的最后一行給出了各種數(shù)據(jù)集下分類精確度的均值。

表3 KNN分類器上實驗結(jié)果Table 3 Experimental results on KNN單位：%

表4 RF分類器上實驗結(jié)果Table 4 Experimental results on RF 單位：%

表5 SVM分類器上實驗結(jié)果Table 5 Experimental results on SVM 單位：%

表6 DT分類器上實驗結(jié)果Table 6 Experimental results on DT 單位：%

表7 LR分類器上實驗結(jié)果Table 7 Experimental results on LR 單位：%

從實驗結(jié)果看，在10 種不完整數(shù)據(jù)集上，采用5 種填充方法進(jìn)行預(yù)填充，再根據(jù)鄰域信息進(jìn)行修正填充，得到5組完整數(shù)據(jù)集，最后采用本文提出的多填充集成分類算法（MIEC）進(jìn)行分類實驗，其分類精確度明顯高于其他對比算法。其中采用RF、DT作為分類器時，本文提出的MIEC算法平均分類精度值高達(dá)90%以上。采用KNN、SVM和LR作為分類器時，本文提出的MIEC算法在各種數(shù)據(jù)集上的平均分類精度值為79.51%、75.03%和85.03%，均優(yōu)于其他對比算法的平均分類精度。綜合來說，本文提出的鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法對不完整數(shù)據(jù)的分類精確度都有大大提升。

為進(jìn)一步驗證本文提出的修正填充方法在真實不完整數(shù)據(jù)集上的有效性，對經(jīng)預(yù)填充后得到的5組完整數(shù)據(jù)集進(jìn)行了對比實驗。其中，在進(jìn)行修正填充前和修正填充后分別將5組完整數(shù)據(jù)集作為集成分類的輸入，并計算兩種情形下集成分類算法的精確度。表8 為未嵌入和嵌入修正填充的集成分類算法精度對比實驗結(jié)果表。實驗中依次采用KNN、RF、SVM、DT 和LR 這5種分類器作為集成學(xué)習(xí)的基分類器。

表8 算法精度對比實驗結(jié)果Table 8 Experimental results for algorithm accuracy comparison 單位：%

實驗結(jié)果表明，當(dāng)采用KNN、RF、SVM、DT和LR這5個分類器作為集成分類的基分類器時，有修正填充的集成分類精準(zhǔn)度平均值均高于沒有修正的情況。在KNN、RF 和DT 作為基分類器的情況下，集成分類方法使用改進(jìn)填充方法的精準(zhǔn)度明顯高于沒有修正的情況。同時，在SVM 和LR 分類器上，這種改進(jìn)填充方法對10 種不完整數(shù)據(jù)集的集成分類有著更高的精確度，其中有7種數(shù)據(jù)集達(dá)到更高的分類精度。

3.4 時間復(fù)雜度分析

本文給出的多填充集成分類算法主要由預(yù)填充、修正填充和集成分類三個階段組成，算法的時間復(fù)雜度由這三個階段的時間復(fù)雜度組成。

預(yù)填充階段的時間復(fù)雜度由選擇的預(yù)填充算法時間復(fù)雜度決定，該階段時間復(fù)雜度記為Oimpution；修正填充階段包括構(gòu)建球樹、迭代縮小鄰域半徑尋找候選集和利用候選集計算修正值三個過程。構(gòu)建球樹包括計算歐幾里德的距離和球樹構(gòu)建兩個環(huán)節(jié)，時間復(fù)雜度為O(n×n×m)+O(n×lbn)，其中，n為數(shù)據(jù)樣本數(shù)，m為數(shù)據(jù)樣本的屬性數(shù)；尋找候選集的時間復(fù)雜度主要取決于遍歷所有缺失值和迭代縮小半徑兩個過程。遍歷缺失值集合的時間復(fù)雜度為O(p)，這里p是缺失值個數(shù)。迭代縮小半徑的迭代數(shù)最壞情況下是O(lbn)，其中n為數(shù)據(jù)樣本數(shù)。利用候選集計算修正值的時間復(fù)雜度、一些條件判斷和球樹查詢等操作的時間復(fù)雜度近似為O(1)，可忽略不計。因此修正填充階段的時間復(fù)雜度為O(n×n×m)+O(n×lb n)+O(p)，記作Orevision。

集成分類階段的任務(wù)為根據(jù)各個基分類器的輸出結(jié)果進(jìn)行投票，確定數(shù)據(jù)樣本類別。時間復(fù)雜度主要由基分類器的時間復(fù)雜度，記作Ovote。

綜合所述，本文提出的多填充集成分類算法時間復(fù)雜度OMIEC可以表示為公式（12）：

其中，i表示預(yù)填充所選用的經(jīng)典填充算法個數(shù)，j表示所選用的基分類器個數(shù)。一般來說，這里的i和j都不會太大，相比于采用一種算法單填充后再利用一種分類器，時間復(fù)雜度并沒有大幅度提高，且可以通過設(shè)計多節(jié)點并行執(zhí)行算法來提高算法效率，因此，從時間復(fù)雜度來說，本文融合多種填充算法的優(yōu)勢，進(jìn)行多填充集成分類方法具有一定可行性。

4 結(jié)語

針對不完整數(shù)據(jù)分類問題，本文提出了一種基于鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法。該方法嵌入了修正填充步驟，利用純度和鄰域半徑篩選出待修正填充的近鄰數(shù)據(jù)樣本，然后根據(jù)近鄰數(shù)據(jù)樣本對缺失值進(jìn)行修正填充。基準(zhǔn)數(shù)據(jù)集實驗結(jié)果表明，該方法對缺失值的填充效果表現(xiàn)更優(yōu)。此外，該方法通過引入多填充集成分類方法，融合了不同經(jīng)典填充算法的優(yōu)勢。基準(zhǔn)數(shù)據(jù)集分類精度提高率實驗以及10個真實不完整數(shù)據(jù)集驗證實驗結(jié)果表明，本文提出的不完整數(shù)據(jù)集分類方法是有效的，并且相比于一般分類方法，分類精度得到了大幅提升。

盡管本文提出的基于鄰域信息修正的不完整數(shù)據(jù)多填充集成分類方法能夠較好地提升缺失值填充效果并提高分類精度，但仍需要進(jìn)一步研究。例如，考慮結(jié)合不完整數(shù)據(jù)產(chǎn)生的實際應(yīng)用場景，從數(shù)據(jù)對象相似度度量、聚類算法等角度考慮缺失值填充效果問題。此外，在高維不完整數(shù)據(jù)的多填充集成分類速度方面，還可以考慮如何設(shè)計分布式算法以加快分類速度。