LKNNI:一種局部K近鄰插補(bǔ)算法*

楊日東 李 琳 陳秋源 周 毅△

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

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

相關(guān)研究

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

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

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

局部K近鄰插補(bǔ)法

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

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

LKNNI算法：

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

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

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

對(duì)于T中的每個(gè)樣本Ti，求Ti的所有缺失屬性。

對(duì)于Ti的每個(gè)缺失屬性j：

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

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

②樣本Ti當(dāng)前的缺失屬性j在slice_data中也不缺失

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

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

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

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

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

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

實(shí) 驗(yàn)

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

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

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

2.實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

3.實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

總 結(jié)

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

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