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

陳小杰

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

0 引言

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

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

1 相關(guān)概念

1.1 KNN 填補算法

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

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

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

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

③算出缺失值的替代值:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 最近鄰樣本

所對應(yīng)的目標填補數(shù)據(jù)的兩個近鄰值如表4 中的數(shù)據(jù)。

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

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

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

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

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

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

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

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

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

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

(3）在k個近鄰值中,用上一步算出的偏差值與算出的協(xié)方差矩陣C中對應(yīng)位置的協(xié)方差值相乘,然后取均值。 因為它表示了樣本變量中特征所在維度的影響,所以將這個值稱為維度影響因子,記為x′:

(4）得到最終填補值:

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

3 實證分析

3.1 數(shù)據(jù)來源

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

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

3.2 檢驗方法

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

3.3 實驗過程

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

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

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

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

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

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

3.4 實驗結(jié)果

在優(yōu)化KNN 填補算法后,得到具體的填補值,但是在這個時候填補值效果不佳,與真實值還是有較大誤差。 這是因為忽略了屬性之間的影響,所以最后根據(jù)公式(7）、(8）可以算出3 個樣本分別對應(yīng)的k(k ＝7） 個數(shù)值具體的影響因子:0.078 0,0.021 6,0.034 1,最終填補結(jié)果如表8 所示。

表8 對比不同方法對缺失值填補情況

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

4 結(jié)語

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