一種優(yōu)化權(quán)重的k-近鄰填補(bǔ)缺失值的算法研究

陳小杰

（重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401131）

0 引言

在如今數(shù)據(jù)充斥生活的時(shí)代,數(shù)據(jù)的缺失問(wèn)題引起了越來(lái)越多的學(xué)者的關(guān)注與研究。 一個(gè)完整的數(shù)據(jù)集才能更好地揭露事物的真實(shí)性,含有缺失值的數(shù)據(jù)集被稱作不完全數(shù)據(jù)集。 現(xiàn)如今已經(jīng)有許多方法被運(yùn)用于不完全數(shù)據(jù)集的填補(bǔ)中,這些方法主要被分成兩大類:機(jī)器學(xué)習(xí)填補(bǔ)方法與統(tǒng)計(jì)學(xué)填補(bǔ)方法［1］。 相對(duì)于統(tǒng)計(jì)學(xué)填補(bǔ)方法,例如均值填補(bǔ)法、多重填補(bǔ)法、期望值最大化方法,機(jī)器學(xué)填補(bǔ)算法因其能獲得更多的有價(jià)值信息而受到各個(gè)領(lǐng)域的廣泛運(yùn)用,其中包括決策樹、隨機(jī)森林、支持向量機(jī)和k-近鄰( KNN）填補(bǔ)算法［2］。 在這些算法中, KNN 操作簡(jiǎn)單、算法快速且有較成熟的理論支撐,在缺失數(shù)據(jù)填補(bǔ)中被廣泛運(yùn)用［3-4］。

k-近鄰填補(bǔ)算法的基本思想是將整個(gè)數(shù)據(jù)集分成兩個(gè)部分:完全數(shù)據(jù)集與不完全數(shù)據(jù)集。 完全數(shù)據(jù)集代表不含缺失值的數(shù)據(jù)集,不完全數(shù)據(jù)集代表含有缺失值的數(shù)據(jù)集。 在完全數(shù)據(jù)集中找到與目標(biāo)填補(bǔ)值所在樣本的k個(gè)最近鄰樣本,找到k個(gè)樣本中缺失值所在的屬性列對(duì)應(yīng)的數(shù)據(jù),即可得到與缺失數(shù)據(jù)鄰近的k個(gè)數(shù)值,最后根據(jù)這k個(gè)數(shù)值去填補(bǔ)所缺失的數(shù)據(jù)。但是,在填補(bǔ)過(guò)程中由于每一個(gè)數(shù)據(jù)到目標(biāo)填補(bǔ)數(shù)據(jù)的距離不一樣,所以k個(gè)數(shù)據(jù)的貢獻(xiàn)是不一致的。 本文就是在k-近鄰填補(bǔ)算法的基礎(chǔ)上,與主成分分析相結(jié)合,提出了基于熵權(quán)法的優(yōu)化權(quán)重的填補(bǔ)算法,使得最后的填補(bǔ)效果更佳。

1 相關(guān)概念

1.1 KNN 填補(bǔ)算法

早在1968 年,Cover 和Heart 提出了原始的計(jì)算模型—— KNN 算法［5］。 在缺失數(shù)據(jù)填補(bǔ)應(yīng)用中,它的原理簡(jiǎn)單易懂,通俗來(lái)講就是“近朱者赤,近墨者黑”,即將缺失值作為目標(biāo)值,找到與它距離最近的k個(gè)“鄰居”,最后根據(jù)這k個(gè)數(shù)值的均值來(lái)填補(bǔ)缺失值,算法步驟如下［6］:

①輸入m × n維數(shù)據(jù)集并進(jìn)行數(shù)據(jù)初始化,構(gòu)造數(shù)據(jù)矩陣:

②計(jì)算出目標(biāo)值(設(shè)為xir）所對(duì)應(yīng)的樣本實(shí)例與其他樣本實(shí)例間的距離(傳統(tǒng)KNN 算法采用歐式距離）:

在數(shù)據(jù)集X中找到與xir最鄰近的k個(gè)數(shù)據(jù)點(diǎn),即xir的k近鄰數(shù)據(jù)；

③算出缺失值的替代值:

其中ωkr為k個(gè)最近鄰數(shù)據(jù)的權(quán)值,取值為距離的倒數(shù)。

1.2 PCA 算法的應(yīng)用

主成分分析(Principal Component Analysis）的主要目的是將關(guān)系“密切”的變量維數(shù)盡量減少。 通過(guò)計(jì)算,找到與原變量密切相關(guān)且相互正交的新變量,最后新變量組成的數(shù)據(jù)維度仍然為n維。 但是在前k(k ＜n） 個(gè)變量中,其方差值都是較大的,后面的 (n - k） 個(gè)變量所得的方差幾乎為0,可直接忽略,從而達(dá)到將數(shù)據(jù)降維的效果［7］。 PCA 算法是應(yīng)用最廣泛的降維算法,在數(shù)據(jù)缺失的處理中也受到學(xué)者的青睞。

協(xié)方差是PCA 算法中很重要的量,協(xié)方差為正時(shí),代表兩個(gè)變量之間是正相關(guān)關(guān)系；協(xié)方差為負(fù)時(shí),代表兩變量之間是負(fù)相關(guān)關(guān)系；協(xié)方差為0 時(shí),代表兩個(gè)變量相互獨(dú)立。 例如,三維數(shù)據(jù)(X,Y,Z） 的協(xié)方差矩陣表示為:

樣本量X和樣本量Y的協(xié)方差為:

2 優(yōu)化權(quán)重后的填補(bǔ)算法過(guò)程

現(xiàn)在有許多學(xué)者將KNN 算法與PCA 算法進(jìn)行結(jié)合,使得最后的填補(bǔ)效果較傳統(tǒng)的KNN 填補(bǔ)算法更加有效。 但是在結(jié)合的同時(shí)往往忽略了k個(gè)近鄰到目標(biāo)數(shù)據(jù)的距離大小不一,所以僅僅用它們的均值或者用距離的倒數(shù)作為權(quán)值,這樣的效果往往不理想。 接下來(lái)就是將這種填補(bǔ)算法進(jìn)行優(yōu)化,為了更加清楚地展示算法的過(guò)程,下面用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明,幫助理解后面詳細(xì)的算法步驟。 表1 給出的數(shù)據(jù)集中,一共5個(gè)樣本3 個(gè)屬性,缺失值用？ 來(lái)表示。

表1 不完全數(shù)據(jù)集

2.1 KNN 填補(bǔ)算法預(yù)備工作

(1）對(duì)原始數(shù)據(jù)矩陣標(biāo)準(zhǔn)化。 原始數(shù)據(jù)集中包括m條數(shù)據(jù)記錄,每一個(gè)數(shù)據(jù)記錄的維度為n維,數(shù)據(jù)標(biāo)準(zhǔn)化可以消除量綱的影響。 而且,在數(shù)據(jù)大小不均衡的時(shí)候,也避免了大數(shù)據(jù)與小數(shù)據(jù)在計(jì)算過(guò)程中的權(quán)重影響,簡(jiǎn)化了后面的運(yùn)算。

(2）確定距離的計(jì)算公式。 明考夫斯基距離(即明氏距離）可以用來(lái)計(jì)算兩樣本變量之間的距離,它可分為曼哈頓距離、歐氏距離和切比雪夫距離。 李航［8］表明將三階明考夫斯基距離運(yùn)用在KNN 算法距離中,效果更好,其公式為:

(3）k值的確定。k值的選取在算法中起著重要的作用。k值較小不能完全體現(xiàn)出目標(biāo)值的特征,導(dǎo)致結(jié)果誤差較大；k值較大會(huì)使大量的數(shù)據(jù)樣本分成一類,從而對(duì)目標(biāo)數(shù)據(jù)起較小作用的值也被納入其中,使得最終的結(jié)果不理想甚至出現(xiàn)錯(cuò)誤。 在一般情況下,k值的選取遵循(n為樣本的容量）的原則。

在這個(gè)例子中,根據(jù)數(shù)據(jù)集首先得到表2 所示的完整數(shù)據(jù)集。

表2 不含缺失值的完全數(shù)據(jù)集

取k ＝2,按照上述過(guò)程可以計(jì)算出樣本間的距離,樣本3 與樣本1、樣本2、樣本4、樣本5 距離分別為:2.24,2.36,0.83,1.39。 找到與樣本3 距離最近的兩個(gè)樣本具體結(jié)果如表3 所示。

表3 最近鄰樣本

所對(duì)應(yīng)的目標(biāo)填補(bǔ)數(shù)據(jù)的兩個(gè)近鄰值如表4 中的數(shù)據(jù)。

表4 具體最近鄰數(shù)據(jù)值

2.2 優(yōu)化權(quán)重的KNN 填補(bǔ)算法

在運(yùn)用傳統(tǒng)KNN 算法填補(bǔ)缺失值時(shí),直接利用均值去填補(bǔ),或者距離的倒數(shù)來(lái)作為權(quán)值去填補(bǔ),這樣的結(jié)果會(huì)形成較大的誤差。 直接用距離的倒數(shù)作為權(quán)重,會(huì)導(dǎo)致距離很近的兩個(gè)樣本量在直接取倒數(shù)后使得權(quán)重系數(shù)相差較大,最后的填補(bǔ)值效果不佳。 例如,上述例子中離目標(biāo)值距離分別為0.83,1.39,兩兩之間距離僅僅相差0.56(＜1） ,代表兩樣本距離貼近,所占權(quán)重值相差不大,但是直接取倒數(shù)算出權(quán)重值,分別為1.20 和0.72,第一個(gè)數(shù)值比重接近第二個(gè)數(shù)值的兩倍,加權(quán)平均后算出此時(shí)的填補(bǔ)值為32.45,效果不是很理想。 并且 AITTOKALLIOT［9］也提到,直接取倒數(shù)法會(huì)產(chǎn)生較大誤差,所以權(quán)重的算法需要得到改進(jìn)。 本文中的權(quán)重是在林晨欣［10］提出的熵權(quán)法的基礎(chǔ)上進(jìn)行改進(jìn)的,并將其運(yùn)用到KNN 算法中,改進(jìn)后的權(quán)重計(jì)算公式如下:

其中n為樣本容量,xij為k個(gè)近鄰樣本中的元素(不包含缺失列）,wi即為最終的k個(gè)近鄰數(shù)的權(quán)重系數(shù)。 該方法的優(yōu)點(diǎn)在于不會(huì)受到距離較近的兩個(gè)數(shù)據(jù)因直接取倒而權(quán)重系數(shù)相差較大的影響。

在例子中,可以計(jì)算得到兩個(gè)樣本的權(quán)重值分別為0.52、0.48,這樣既保證了k個(gè)數(shù)據(jù)值貢獻(xiàn)程度的不一,也避免了因?yàn)闄?quán)重系數(shù)的過(guò)度波動(dòng)而產(chǎn)生的誤差。此時(shí),填補(bǔ)值x0＝34.15。

2.3 結(jié)合PCA 算法原理得到最終填補(bǔ)值

上述分析中,根據(jù)距離公式得到了樣本間的相關(guān)性,卻忽略了特征之間也會(huì)相互影響。 所以,接下來(lái)結(jié)合PCA 算法原理,計(jì)算特征的影響值,具體操作過(guò)程如下:

(1）按照公式(3） 對(duì)原始數(shù)據(jù)求出協(xié)方差矩陣［9］,對(duì)于一個(gè)n維的數(shù)據(jù)來(lái)說(shuō)可以得到一個(gè)n*n維矩陣,記為C:

(2）對(duì)于k個(gè)樣本變量的特征所對(duì)應(yīng)的值可能不一致,算出每一個(gè)值的偏差:用每一個(gè)值減去本特征數(shù)值的均值。 結(jié)果記為ak:

m0為屬性列中去掉缺失值后剩下的數(shù)據(jù)總數(shù),xij為屬性列中去掉缺失值后的所對(duì)應(yīng)的剩余數(shù)據(jù)。

(3）在k個(gè)近鄰值中,用上一步算出的偏差值與算出的協(xié)方差矩陣C中對(duì)應(yīng)位置的協(xié)方差值相乘,然后取均值。 因?yàn)樗硎玖藰颖咀兞恐刑卣魉诰S度的影響,所以將這個(gè)值稱為維度影響因子,記為x′:

(4）得到最終填補(bǔ)值:

在上述例子中,兩個(gè)近鄰數(shù)據(jù)所算出的偏差值:a1＝-3.75,a2＝-8.75；影響因子值:x′ ＝-1.03。 所以最后的填補(bǔ)值就為:x ＝x0+x′＝34.15+(-1.03）＝33.12。

3 實(shí)證分析

3.1 數(shù)據(jù)來(lái)源

為了證明本文提出的新方法的有效性,將最后的結(jié)果與未設(shè)置缺失的原始數(shù)據(jù)進(jìn)行對(duì)比分析。 實(shí)驗(yàn)數(shù)據(jù)來(lái)源于UCI 數(shù)據(jù)庫(kù)中的iris (鳶尾花）數(shù)據(jù)集,數(shù)據(jù)集總共包含3 個(gè)類別,每一個(gè)類別包含50 個(gè)數(shù)據(jù)記錄,并且每組數(shù)據(jù)記錄包含4 個(gè)識(shí)別鳶尾花的屬性,具體數(shù)據(jù)如表5 所示。

表5 鳶尾花原始數(shù)據(jù)集

3.2 檢驗(yàn)方法

從原始數(shù)據(jù)表格可以看出所要操作的數(shù)據(jù)均為數(shù)值型數(shù)據(jù),而均方根誤差( RMSE）是衡量真實(shí)值與填補(bǔ)值之間差距的有效指標(biāo),所以現(xiàn)將此作為評(píng)價(jià)缺失數(shù)據(jù)填補(bǔ)效果的指標(biāo),其值越小代表填補(bǔ)數(shù)據(jù)效果越好。 其計(jì)算公式為:

3.3 實(shí)驗(yàn)過(guò)程

在上述三個(gè)類別的數(shù)據(jù)集中,為了使缺失數(shù)據(jù)的填補(bǔ)效果不具有巧合性,采用在每個(gè)類別中構(gòu)造缺失的方法:在Setosa 類別中構(gòu)造第9 行Sepal.Width 屬性缺失；在Versicolor 類別中構(gòu)造第30 行Sepal.Width 屬性丟失；Virginica 類別中使第11 行Sepal.Width 缺失。再分別用本文方法進(jìn)行驗(yàn)證。 在數(shù)據(jù)集中,一個(gè)類別數(shù)據(jù)記錄為50 條,記為樣本容量n ＝50,根據(jù)k值選取原則,取k ＝7。 遵照上述KNN 填補(bǔ)算法,將缺失數(shù)據(jù)所在屬性列作為目標(biāo)列,取不含有缺失數(shù)據(jù)完整樣本集(不包含目標(biāo)列）,按照公式(4） 中的三階明氏距離算出與缺失值所在樣本的最近鄰的k個(gè)樣本量,可得到對(duì)應(yīng)樣本中目標(biāo)列的數(shù)值,即作為缺失數(shù)據(jù)距離最近的k個(gè)“鄰居”。 在3 種類別中得到的k個(gè)近鄰數(shù)據(jù)見表6。

表6 3 種類別下k 個(gè)數(shù)據(jù)

在得到數(shù)據(jù)的7 個(gè)最近鄰數(shù)據(jù)后,根據(jù)公式(5）、(6） 可以計(jì)算出賦予這k個(gè)數(shù)據(jù)基于熵權(quán)法改進(jìn)的權(quán)重系數(shù),加上最終的權(quán)重系數(shù)如表7 所示。

表7 基于熵權(quán)法改進(jìn)后的權(quán)重系數(shù)

通過(guò)畫圖,可以得到改進(jìn)權(quán)重系數(shù)前、后的關(guān)系。從圖1 中的權(quán)重大致趨勢(shì)圖可以清楚地了解到,改進(jìn)后的權(quán)重系數(shù)較傳統(tǒng)的權(quán)重系數(shù)要穩(wěn)定許多,與距離較近的幾個(gè)數(shù)據(jù)所對(duì)應(yīng)的權(quán)重系數(shù)也應(yīng)相差不大的事實(shí)相符合,這表明改進(jìn)后的權(quán)重系數(shù)缺失比傳統(tǒng)的要優(yōu)化許多。

圖1 優(yōu)化權(quán)重前后的權(quán)重系數(shù)趨勢(shì)對(duì)比

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

在優(yōu)化KNN 填補(bǔ)算法后,得到具體的填補(bǔ)值,但是在這個(gè)時(shí)候填補(bǔ)值效果不佳,與真實(shí)值還是有較大誤差。 這是因?yàn)楹雎粤藢傩灾g的影響,所以最后根據(jù)公式(7）、(8）可以算出3 個(gè)樣本分別對(duì)應(yīng)的k(k ＝7） 個(gè)數(shù)值具體的影響因子:0.078 0,0.021 6,0.034 1,最終填補(bǔ)結(jié)果如表8 所示。

表8 對(duì)比不同方法對(duì)缺失值填補(bǔ)情況

表8 可以看出,在缺失填補(bǔ)效果上,優(yōu)化后的算法對(duì)于缺失值的填補(bǔ)效果更好,更貼近真實(shí)值,且最后的均方根誤差相對(duì)傳統(tǒng)的KNN 算法和一般權(quán)重KNN 算法要小許多,證實(shí)了本文優(yōu)化算法的有效性與可行性。

4 結(jié)語(yǔ)

KNN 填補(bǔ)算法被廣泛地應(yīng)用在缺失數(shù)據(jù)的填補(bǔ)中。 熵權(quán)法作為賦予權(quán)重的十分有效的方法［9］,是在信息論的基礎(chǔ)上提出來(lái)的。 本文主要在KNN 算法的基礎(chǔ)上,提出了基于熵權(quán)法的優(yōu)化權(quán)重系數(shù),并且考慮到屬性之間的相關(guān)性,在優(yōu)化權(quán)重后的基礎(chǔ)上,與PCA原理取得的屬性相關(guān)影響因子相結(jié)合,得到最后的填補(bǔ)值。 這樣的優(yōu)點(diǎn)在于不僅考慮了目標(biāo)數(shù)據(jù)最近鄰數(shù)據(jù)的影響程度不一,將每一個(gè)“鄰居”賦予更加穩(wěn)定的權(quán)重系數(shù),還考慮了屬性相關(guān)的影響,使得最后的填補(bǔ)效果更加準(zhǔn)確,更加逼近真實(shí)值。