LKNNI:一種局部K近鄰插補算法*

楊日東 李 琳 陳秋源 周 毅△

【提 要】 目的 針對K近鄰插補法在缺失率較大的數(shù)據(jù)集上的性能不佳，提出一種局部K近鄰插補法。方法 在6個完整的公開數(shù)據(jù)集上按照不同缺失率隨機刪除數(shù)據(jù)，根據(jù)填充數(shù)據(jù)和原始數(shù)據(jù)計算算法的填充性能，將局部K近鄰插補法與K近鄰插補法、多重插補法對比。結(jié)果 局部K近鄰插補法在缺失率較低的條件下，填充性能與多重插補法接近，且略勝于K近鄰插補法。在缺失率較高的條件下，局部K近鄰插補法的性能明顯優(yōu)于K近鄰插補法，且略勝于多重插補法。結(jié)論 相比K近鄰插補法，局部K近鄰插補法非常適合處理缺失率較大的數(shù)據(jù)集。

隨著信息時代的發(fā)展，各個領(lǐng)域積累了大量數(shù)據(jù)，如何有效地利用這些數(shù)據(jù)，已成為目前一大研究熱點。然而，實際中往往會出現(xiàn)數(shù)據(jù)缺失、噪聲、重復和不一致等情況，這很大程度地影響了數(shù)據(jù)挖掘算法的穩(wěn)定[1]。因此，對缺失數(shù)據(jù)集進行處理就顯得十分重要。數(shù)據(jù)重復和數(shù)據(jù)的不一致均可進行算法篩查，而造成數(shù)據(jù)缺失可能是由于數(shù)據(jù)無法獲取或者在操作過程中被遺漏，在不進行缺失值處理的情況下，某些機器學習算法甚至無法直接使用。因此，缺失值填充是數(shù)據(jù)挖掘和機器學習領(lǐng)域中一個實際且有挑戰(zhàn)性的問題[2]。

相關(guān)研究

K近鄰插補(Knearest neighbor imputation，KNNI)是Olga Troyanskaya[3]提出的一種基于數(shù)據(jù)局部相似性的填充算法。KNNI的基本思想是，對于含缺失值的樣本，其缺失的數(shù)據(jù)可參考與它最類似的K個樣本。具體地說，KNNI將數(shù)據(jù)集劃分為兩個集合，一個集合包含所有的完全樣本(即不含缺失值的樣本)，另外一個集合包含所有的不完全樣本(即存在缺失值的樣本)。對于每個不完全樣本，求其在完全樣本集中的K近鄰，對于缺失值是分類屬性的，則填充K近鄰樣本該屬性值的眾數(shù)；對于缺失值是數(shù)值屬性的，則填充K近鄰樣本該屬性值的平均數(shù)。由于不完全樣本的缺失值是根據(jù)“相鄰”樣本求得，因此KNNI算法不會增加過多的新樣本信息。

盡管 KNNI 是一種優(yōu)秀的填充算法，但是KNNI 的填充效果極大程度地受缺失率的影響。KNNI算法在數(shù)據(jù)集缺失率較大時，數(shù)據(jù)集中的完全樣本非常少，這意味著，對于不完全樣本而言，在完全樣本中算出的K近鄰樣本此時可能并非真正意義上的“近鄰”。這就會導致缺失樣本填充時參考的K近鄰實際上與樣本本身還有一定的差距，最終導致填充的數(shù)值誤差較大。另外，當缺失率大到一定程度時，數(shù)據(jù)集中并不一定含有完全數(shù)據(jù)，此時，將無法運用傳統(tǒng)的KNNI進行缺失值填充。

傳統(tǒng)插補算法屬于單值插補，填充值是唯一的，無法體現(xiàn)缺失數(shù)據(jù)的不確定性，一定程度改變了樣本分布。為了彌補單值插補的缺陷，綜合考慮缺失值的不確定性，Rubin[4]等人提出多重插補法(multiple imputation，MI)。多重插補方法產(chǎn)生多個候選插補值，形成了多個完整的數(shù)據(jù)集，這些可能的估計值反映了數(shù)據(jù)的不確定性，綜合分析得到估計量，進行統(tǒng)計推斷。構(gòu)造若干個可能估計值實際上是模擬一定條件下的估計值分布，借估計值分布來估計缺失變量的實際后驗分布[5]。文獻[6]對比了多重插補法與均值插補、EM算法和回歸插補等在不同缺失率下的填充性能，結(jié)果表明，在缺失率高的條件下多重插補法比其他方法的性能更佳。因此，本文將多重插補法與局部K近鄰插補法(localK-nearest neighbor imputation，LKNNI)進行對比。

局部K近鄰插補法

考慮到KNNI在缺失率較大時難以找到真正的“近鄰”樣本，本文提出了一種局部K近鄰插補法。算法的初衷是通過切片，使得填充不完全樣本時的參考樣本(即用于求K近鄰的樣本集)更多，從而提高填充準確度。所謂切片，是指數(shù)據(jù)集在特定屬性集合上的投影。例如：對于屬性集{年齡,婚姻,學歷,家庭條件}、數(shù)據(jù)集T={(“青年”,“未婚”,“本科”,“良好”),(“中年”,“已婚”,“碩士”,“一般”)}，則T在婚姻和學歷屬性上的投影為T′={(“未婚”,“本科”),(“已婚”,“碩士”)}。

對不完全樣本Ti的第j個缺失屬性進行缺失值填充時，數(shù)據(jù)T中的樣本只需滿足其本身在Ti中未缺失的屬性也不缺失(因為計算K近鄰時需要)并且在Ti當前的缺失屬性j也不缺失(因為計算填充值時需要)，即可將此樣本加入求Ti的K近鄰的樣本集合當中，無論此樣本是否是完全樣本。這樣一來，填充所參考的樣本集由不完全樣本Ti決定，并非必須參考完全樣本，相比傳統(tǒng)KNNI靈活。算法的具體步驟如下：

LKNNI算法：

輸入：含缺失數(shù)據(jù)的數(shù)據(jù)集T，K近鄰的參數(shù)K

輸出：已填充數(shù)據(jù)集

根據(jù)數(shù)據(jù)集T中樣本的缺失值個數(shù)，對樣本進行倒序排序

對于T中的每個樣本Ti，求Ti的所有缺失屬性。

對于Ti的每個缺失屬性j：

(1)切片：遍歷T，求出T中滿足以下所有條件的樣本slice_data：

①樣本Ti中未缺失的屬性在slice_data中也不缺失

②樣本Ti當前的缺失屬性j在slice_data中也不缺失

(2)求樣本Ti在slice_data中的K近鄰TiK

(3)若當前樣本的缺失屬性j是分類屬性，將TiK在屬性j的取值的眾數(shù)填充到Ti的缺失屬性中

(4)若當前樣本的缺失屬性j是數(shù)值屬性，將TiK在屬性j的取值的平均數(shù)填充到Ti的缺失屬性中

輸出數(shù)據(jù)集T

在上述LKNNI算法中，步驟1的目的是為了降低參考樣本集為空的風險，即利用“貪心算法”的思想，對T中樣本按照缺失值個數(shù)進行倒序排序，認為樣本的缺失值個數(shù)越多，其切片得到的數(shù)據(jù)集也越大，空集的可能更小。

LKNNI算法與KNNI算法最大的區(qū)別在于：KNNI算法填充不完全樣本是根據(jù)完全樣本中的K近鄰，而LKNNI算法是根據(jù)樣本當前正在處理的缺失屬性和未缺失屬性，在整個數(shù)據(jù)集T中進行一次投影，然后在投影得到的數(shù)據(jù)集中求得當前樣本的K近鄰，最后進行相應(yīng)的填充。與KNNI算法相比，LKNNI算法使得不完全樣本可在一個更大的樣本集中求得K近鄰，這意味著K近鄰算法可學習的樣本數(shù)更大，找到的近鄰“更像”當前處理的不完全樣本。

實 驗

1． 數(shù)據(jù)集

如表1所示，本次實驗采用4個來自UCI上的公開數(shù)據(jù)集。

表1 數(shù)據(jù)集統(tǒng)計描述

2.實驗設(shè)計

(1)模擬缺失：為了衡量填充值與實際數(shù)值之間的相似度，我們按照文獻[9]中的做法，采用完整數(shù)據(jù)集，然后采用隨機刪除的方法模擬多變量隨機缺失，經(jīng)過缺失值填充后再對比填充值與原始屬性值。

(2)歸一化：為了保證求解K近鄰時不受數(shù)值屬性的量綱影響，本實驗在預處理時，均對所有的數(shù)值屬性進行歸一化處理。具體計算方式如下：

其中xi表示未歸一化之前的值，xmin表示該屬性的最小值，xmax表示該屬性的最大值。

(3)度量指標：為了準確評價填充算法在不同數(shù)據(jù)集上的性能，本實驗在計算度量指標時，均對所有的數(shù)值屬性進行歸一化處理。在衡量算法性能時，數(shù)值屬性的填充效果用均方誤差表示；分類屬性則采用正確率表示[8-9]。計算方式如下：

其中，L是缺失個數(shù)，xi是原始數(shù)據(jù)，xI是填充的數(shù)據(jù)。

3.實驗結(jié)果

考慮到KNNI在缺失率大時無法運行的局限性，我們根據(jù)不同數(shù)據(jù)集上KNNI所能夠運行的最大缺失率來設(shè)計缺失率的取值區(qū)間。并且為了保證實驗結(jié)果可信度，降低模擬缺失帶來的誤差，本實驗對相同填充算法和相同缺失率的樣本進行30次實驗，用度量指標的平均值作為實驗結(jié)果。如圖1～4所示。

從圖1～4可以看出，三種算法的填充性能均隨缺失率的增大而變差，且KNNI對缺失率最為敏感，MI次之，而LKNNI最不敏感?？梢缘贸鼋Y(jié)論：由于LKNNI在缺失率較大時，通過投影得到的數(shù)據(jù)集遠大于完全樣本集，因此找到的K近鄰樣本更接近于待插補的不完全樣本，從而填充性能更佳，適合處理缺失率大的數(shù)據(jù)集。

圖1 不同算法、缺失率在ILPD數(shù)據(jù)集上的填充性能比較

圖2 不同算法、缺失率在Breast Cancer Coimbra數(shù)據(jù)集上的填充性能比較

圖3 不同算法、缺失率在WDBC數(shù)據(jù)集上的填充性能比較

圖4 題不同算法、缺失率在Parkinsons數(shù)據(jù)集上的填充性能比較

另外，不同的數(shù)據(jù)集，基于K近鄰思想的插補方法與多重插補法的性能比較結(jié)果不同。例如：WDBC數(shù)據(jù)集本身易于分類，適合多重插補等模型，而ILPD數(shù)據(jù)集本身可能更適合K近鄰模型，因此不能簡單地認為哪種算法的性能絕對優(yōu)于其他算法。但是，在缺失率較大時，LKNNI的填充效果通常優(yōu)于KNNI。

總 結(jié)

本文提出一種基于K近鄰插補法改進的算法——局部K近鄰插補法，是在KNNI的基礎(chǔ)上，引入切片思想，擴大不完全樣本尋找K近鄰的集合容量，從而易于找到與不完全樣本更類似的樣本。通過4個UCI數(shù)據(jù)集，在不同缺失率下進行對比實驗。結(jié)果表明，LKNNI在缺失率小的條件下性能與MI接近且略優(yōu)于KNNI；LKNNI在缺失率大時明顯優(yōu)于KNNI，且略勝于MI。

LKNNI在填充不完全樣本時，每填充一個缺失值均在全局數(shù)據(jù)上進行投影，以求得該不完全樣本的可參考樣本。而傳統(tǒng)KNNI則一次性求出參考樣本(即完全樣本)，因此LKNNI相比傳統(tǒng)KNNI速度更慢。我們發(fā)現(xiàn)，在同一不完全樣本中，當前缺失值的參考樣本必定是前一個缺失值的參考樣本的子集。因此，在未來研究中，在一個不完全樣本的填充過程中，將不再以全局數(shù)據(jù)進行投影，而是在前一個缺失值的參考樣本集進行投影，以此減小數(shù)據(jù)規(guī)模，進而提高LKNNI的整體運行速度。