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

2023-12-11 07:11:20朱先遠嚴遠亭張燕平

計算機工程與應用 2023年23期

朱先遠，嚴遠亭，張燕平

1.安徽商貿職業技術學院信息與人工智能學院，安徽蕪湖 241002

2.安徽大學計算機科學與技術學院，合肥 230601

數據分類是機器學習、數據挖掘和模式識別等領域的重要任務[1-2]，但由于數據收集、網絡傳輸等，人們拿到的待分類數據往往都有一定程度的不完整性，這類數據稱為不完整數據集，如：微陣列數據[3-4]、移動電話數據[5]、可視化數據[6]、工業數據[7]、軟件項目數據[8]等。對不完整數據集分類首先需要對其進行預處理再分類。不完整數據集預處理常用方法有刪除法和填充法兩類方法。刪除法即直接刪除含有缺失值的數據樣本，數據集中只保留信息完整的數據樣本。在數據樣本獲取代價較高情形下，刪除含有缺失值的數據樣本會造成數字資源浪費和有用信息的丟失。填充法是利用一些經典填充算法對不完整數據集中的缺失值進行估計填充。在不完整數據分類前利用填充算法將不完整數據填充為完整數據可以提高分類精確度[9]。不完整數據的填充算法研究，對不完整數據分類具有重要現實意義。

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

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

結合對不完整數據分類問題的上述考慮，本文提出一種基于鄰域信息修正不完整數據多填充集成分類方法。該方法一方面通過嵌入基于鄰域信息的修正填充策略，實現了利用近鄰數據樣本鄰域信息對缺失值的填充，另一方面也利用多填充的數據多樣性，通過集成學習融合了不同經典填充方法的優勢。

1 相關工作

1.1 不完整數據集及相關預填充方法

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

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

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

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

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

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

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

其中，I為第k維屬性值非空的數據樣本集合，I*為集合I中進行排序后集合。

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

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

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

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

其中均值填充、中值填充都屬于基于統計學指標的填充策略；ISVD 為矩陣分解填充策略的代表；K近鄰填充屬于使用機器學習算法進行填充策略；相似度加權平均填充是利用樣本間的相似性來推斷缺失值，在基因表達數據集上測試結果十分優異的填充算法代表。

1.2 修正填充相關方法

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

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

1.3 集成學習方法

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

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

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

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

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

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

2.1 不完整數據集成分類總體框架

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

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

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

2.2 不完整數據修正填充

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

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

球樹的主要優點在于它能夠快速地定位到距離查詢點最近的一些數據點，對于高維數據具有較好的性能，因為它能夠避免在高維空間中出現“維度災難”問題。

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

其中，|B|表示超球體內的樣本點數，yi表示樣本點Xi的類別，yB表示超球體球心類別，I是一個指示函數，當yi=yB時取值為1，否則為0。

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

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

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

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

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

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

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

2.3 多填充集成分類

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

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

3 實驗

3.1 評價指標

本文選取NRMSE 評價指標對不完整數據集的填充效果進行評價，選取Accuracy對不完整數據的分類精確度進行評價。NRMSE和Accuracy的定義如下：

（1）NRMSE

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

（2）Accuracy

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

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

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

3.2 基準數據集下算法性能分析

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

表1 基準數據集Table 1 Benchmark dataset

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

3.2.1 算法填充效果實驗

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

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

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

3.2.2 不完整數據分類精確度實驗結果與分析

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

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

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

3.3 真實不完整數據集下對比實驗及結果分析

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

表2 真實數據集信息描述Table 2 Real dataset information

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

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

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

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

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

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

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

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

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

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

3.4 時間復雜度分析

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

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

集成分類階段的任務為根據各個基分類器的輸出結果進行投票，確定數據樣本類別。時間復雜度主要由基分類器的時間復雜度，記作Ovote。

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

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

4 結語

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

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