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

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

陳小杰（重慶師范大學數(shù)學科學學院，重慶401131）0引言在如今數(shù)據(jù)充斥生活的時代,數(shù)據(jù)的缺失問題引起了越來越多的學者的關注與研究。一個完整的數(shù)據(jù)集才能更好地揭露事物的真實性,含有缺失值的數(shù)據(jù)集被稱作不完全數(shù)據(jù)集?，F(xiàn)如今已經有許多方法被運用于不完全數(shù)據(jù)集的填補中,這些方法主要被分成兩大類:機器學習填補方法與統(tǒng)計學填補方法［1］。相對于統(tǒ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個樣本中缺失值所在的屬性列對應的數(shù)據(jù),即可得到與缺失數(shù)據(jù)鄰近的k個數(shù)值,最后根據(jù)這k個數(shù)值去填補所缺失的數(shù)據(jù)。但是,在填補過程中由于每一個數(shù)據(jù)到目標填補數(shù)據(jù)的距離不一樣,所以k個數(shù)據(jù)的貢獻是不一致的。本文就是在k-近鄰填補算法的基礎上,與主成分分析相結合,提出了基于熵權法的優(yōu)化權重的填補算法,使得最后的填補效果更佳。1相關概念1.1KNN填補算法早在1968年,Cover和Heart提出了原始的計算模型——KNN算法［5］。在缺失數(shù)據(jù)填補應用中,它的原理簡單易懂,通俗來講就是“近朱者赤,近墨者黑”,即將缺失值作為目標值,找到與它距離最近的k個“鄰居”,最后根據(jù)這k個數(shù)值的均值來填補缺失值,算法步驟如下［6］:①輸入m×n維數(shù)據(jù)集并進行數(shù)據(jù)初始化,構造數(shù)據(jù)矩陣:②計算出目標值(設為xir）所對應的樣本實例與其他樣本實例間的距離(傳統(tǒng)KNN算法采用歐式距離）:在數(shù)據(jù)集X中找到與xir最鄰近的k個數(shù)據(jù)點,即xir的k近鄰數(shù)據(jù)；③算出缺失值的替代值:其中ωkr為k個最近鄰數(shù)據(jù)的權值,取值為距離的倒數(shù)。1.2PCA算法的應用主成分分析(PrincipalComponentAnalysis）的主要目的是將關系“密切”的變量維數(shù)盡量減少。通過計算,找到與原變量密切相關且相互正交的新變量,最后新變量組成的數(shù)據(jù)維度仍然為n維。但是在前k(k＜n）個變量中,其方差值都是較大的,后面的(n-k）個變量所得的方差幾乎為0,可直接忽略,從而達到將數(shù)據(jù)降維的效果［7］。PCA算法是應用最廣泛的降維算法,在數(shù)據(jù)缺失的處理中也受到學者的青睞。協(xié)方差是PCA算法中很重要的量,協(xié)方差為正時,代表兩個變量之間是正相關關系；協(xié)方差為負時,代表兩變量之間是負相關關系；協(xié)方差為0時,代表兩個變量相互獨立。例如,三維數(shù)據(jù)(X,Y,Z）的協(xié)方差矩陣表示為:樣本量X和樣本量Y的協(xié)方差為:2優(yōu)化權重后的填補算法過程現(xiàn)在有許多學者將KNN算法與PCA算法進行結合,使得最后的填補效果較傳統(tǒng)的KNN填補算法更加有效。但是在結合的同時往往忽略了k個近鄰到目標數(shù)據(jù)的距離大小不一,所以僅僅用它們的均值或者用距離的倒數(shù)作為權值,這樣的效果往往不理想。接下來就是將這種填補算法進行優(yōu)化,為了更加清楚地展示算法的過程,下面用一個簡單的例子來說明,幫助理解后面詳細的算法步驟。表1給出的數(shù)據(jù)集中,一共5個樣本3個屬性,缺失值用？來表示。表1不完全數(shù)據(jù)集2.1KNN填補算法預備工作(1）對原始數(shù)據(jù)矩陣標準化。原始數(shù)據(jù)集中包括m條數(shù)據(jù)記錄,每一個數(shù)據(jù)記錄的維度為n維,數(shù)據(jù)標準化可以消除量綱的影響。而且,在數(shù)據(jù)大小不均衡的時候,也避免了大數(shù)據(jù)與小數(shù)據(jù)在計算過程中的權重影響,簡化了后面的運算。(2）確定距離的計算公式。明考夫斯基距離(即明氏距離）可以用來計算兩樣本變量之間的距離,它可分為曼哈頓距離、歐氏距離和切比雪夫距離。李航［8］表明將三階明考夫斯基距離運用在KNN算法距離中,效果更好,其公式為:(3）k值的確定。k值的選取在算法中起著重要的作用。k值較小不能完全體現(xiàn)出目標值的特征,導致結果誤差較大；k值較大會使大量的數(shù)據(jù)樣本分成一類,從而對目標數(shù)據(jù)起較小作用的值也被納入其中,使得最終的結果不理想甚至出現(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距離最近的兩個樣本具體結果如表3所示。表3最近鄰樣本所對應的目標填補數(shù)據(jù)的兩個近鄰值如表4中的數(shù)據(jù)。表4具體最近鄰數(shù)據(jù)值2.2優(yōu)化權重的KNN填補算法在運用傳統(tǒng)KNN算法填補缺失值時,直接利用均值去填補,或者距離的倒數(shù)來作為權值去填補,這樣的結果會形成較大的誤差。直接用距離的倒數(shù)作為權重,會導致距離很近的兩個樣本量在直接取倒數(shù)后使得權重系數(shù)相差較大,最后的填補值效果不佳。例如,上述例子中離目標值距離分別為0.83,1.39,兩兩之間距離僅僅相差0.56(＜1）,代表兩樣本距離貼近,所占權重值相差不大,但是直接取倒數(shù)算出權重值,分別為1.20和0.72,第一個數(shù)值比重接近第二個數(shù)值的兩倍,加權平均后算出此時的填補值為32.45,效果不是很理想。并且AITTOKALLIOT［9］也提到,直接取倒數(shù)法會產生較大誤差,所以權重的算法需要得到改進。本文中的權重是在林晨欣［10］提出的熵權法的基礎上進行改進的,并將其運用到KNN算法中,改進后的權重計算公式如下:其中n為樣本容量,xij為k個近鄰樣本中的元素(不包含缺失列）,wi即為最終的k個近鄰數(shù)的權重系數(shù)。該方法的優(yōu)點在于不會受到距離較近的兩個數(shù)據(jù)因直接取倒而權重系數(shù)相差較大的影響。在例子中,可以計算得到兩個樣本的權重值分別為0.52、0.48,這樣既保證了k個數(shù)據(jù)值貢獻程度的不一,也避免了因為權重系數(shù)的過度波動而產生的誤差。此時,填補值x0＝34.15。2.3結合PCA算法原理得到最終填補值上述分析中,根據(jù)距離公式得到了樣本間的相關性,卻忽略了特征之間也會相互影響。所以,接下來結合PCA算法原理,計算特征的影響值,具體操作過程如下:(1）按照公式(3）對原始數(shù)據(jù)求出協(xié)方差矩陣［9］,對于一個n維的數(shù)據(jù)來說可以得到一個n*n維矩陣,記為C:(2）對于k個樣本變量的特征所對應的值可能不一致,算出每一個值的偏差:用每一個值減去本特征數(shù)值的均值。結果記為ak:m0為屬性列中去掉缺失值后剩下的數(shù)據(jù)總數(shù),xij為屬性列中去掉缺失值后的所對應的剩余數(shù)據(jù)。(3）在k個近鄰值中,用上一步算出的偏差值與算出的協(xié)方差矩陣C中對應位置的協(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ù)來源為了證明本文提出的新方法的有效性,將最后的結果與未設置缺失的原始數(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ù)的填補效果不具有巧合性,采用在每個類別中構造缺失的方法:在Setosa類別中構造第9行Sepal.Width屬性缺失；在Versicolor類別中構造第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個樣本量,可得到對應樣本中目標列的數(shù)值,即作為缺失數(shù)據(jù)距離最近的k個“鄰居”。在3種類別中得到的k個近鄰數(shù)據(jù)見表6。表63種類別下k個數(shù)據(jù)在得到數(shù)據(jù)的7個最近鄰數(shù)據(jù)后,根據(jù)公式(5）、(6）可以計算出賦予這k個數(shù)據(jù)基于熵權法改進的權重系數(shù),加上最終的權重系數(shù)如表7所示。表7基于熵權法改進后的權重系數(shù)通過畫圖,可以得到改進權重系數(shù)前、后的關系。從圖1中的權重大致趨勢圖可以清楚地了解到,改進后的權重系數(shù)較傳統(tǒng)的權重系數(shù)要穩(wěn)定許多,與距離較近的幾個數(shù)據(jù)所對應的權重系數(shù)也應相差不大的事實相符合,這表明改進后的權重系數(shù)缺失比傳統(tǒng)的要優(yōu)化許多。圖1優(yōu)化權重前后的權重系數(shù)趨勢對比3.4實驗結果在優(yōu)化KNN填補算法后,得到具體的填補值,但是在這個時候填補值效果不佳,與真實值還是有較大誤差。這是因為忽略了屬性之間的影響,所以最后根據(jù)公式(7）、(8）可以算出3個樣本分別對應的k(k＝7）個數(shù)值具體的影響因子:0.0780,0.0216,0.0341,最終填補結果如表8所示。表8對比不同方法對缺失值填補情況表8可以看出,在缺失填補效果上,優(yōu)化后的算法對于缺失值的填補效果更好,更貼近真實值,且最后的均方根誤差相對傳統(tǒng)的KNN算法和一般權重KNN算法要小許多,證實了本文優(yōu)化算法的有效性與可行性。4結語KNN填補算法被廣泛地應用在缺