基于屬性相關(guān)性的KNN近鄰填補(bǔ)算法改進(jìn)

謝霖銓， 趙楠， 徐浩， 畢永朋

（江西理工大學(xué)理學(xué)院，江西 贛州 341000）

0 引 言

高速發(fā)展的經(jīng)濟(jì)社會產(chǎn)生了海量的信息，因某些數(shù)據(jù)暫時(shí)無法獲取或在獲取過程中的粗心導(dǎo)致一些數(shù)據(jù)遺漏的情況經(jīng)常發(fā)生，且基本是無可避免的.然而，這些缺失數(shù)據(jù)項(xiàng)很有可能攜帶該數(shù)據(jù)對象的重要信息，若直接利用這些帶有缺失的數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘或數(shù)據(jù)分析，其得出的結(jié)果對決策會存在一定的影響，即包含缺值的數(shù)據(jù)會使挖掘過程陷人混亂，導(dǎo)致不可靠的輸出[1].所以，在數(shù)據(jù)處理分析之前，對缺失數(shù)據(jù)的預(yù)處理成為一項(xiàng)很重要的準(zhǔn)備工作[2].對缺失數(shù)據(jù)的預(yù)處理通常是刪除、尋找替代值或是不處理.刪除數(shù)據(jù)簡單易行，但是有很大的局限性，還會附帶刪除數(shù)據(jù)中隱藏的很多原始信息.尋找替代值即數(shù)據(jù)的插補(bǔ)，是最常用的方法，插補(bǔ)的基本原理是利用一些現(xiàn)成的規(guī)則或是合理的方法推測插補(bǔ)值或者替代值[3].

近年來，數(shù)據(jù)填補(bǔ)不再簡單的以數(shù)據(jù)的數(shù)值大小作為計(jì)算準(zhǔn)則，粗糙集合理論[4]、關(guān)聯(lián)規(guī)則[5]等更多的改進(jìn)算法相繼被提出來[6].近鄰均值填補(bǔ)是單一填補(bǔ)的一種方法，操作簡單，其受噪聲影響比較大[7]，文獻(xiàn)[8]則介紹了一種基于噪聲處理的近鄰填補(bǔ)算法.主成份分析 （Principal Computer Analysis，PCA）是Karl parson[9]于1901年提出的一種多元統(tǒng)計(jì)分析方法是經(jīng)典的特征降維算法，根據(jù)原始數(shù)據(jù)集的協(xié)方差矩陣和特征值特征向量計(jì)算新的向量基最，終將原始數(shù)據(jù)投影到新的向量基中，并使這些新變量盡可能多地反映原變量的信息量.統(tǒng)計(jì)學(xué)領(lǐng)域?qū)θ笔?shù)據(jù)填補(bǔ)方法也有廣泛的研究，如回歸法[10]、熱卡填補(bǔ)（Hot Deck Imputation）[11]、最大期望法（Expectation Maximization）[12]、隨機(jī)回歸填補(bǔ)法等，這些方法對處理缺失數(shù)據(jù)，建立完備的數(shù)據(jù)集起到很重要的作用.用于數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)的各種算法對缺失數(shù)據(jù)填補(bǔ)都有借鑒，如基于神經(jīng)網(wǎng)絡(luò)的缺失填補(bǔ)算法[13]、基于K最近鄰法（K-Nearest Neighbor,KNN）[14]、基于貝葉斯網(wǎng)絡(luò)的填補(bǔ)算法[15]、基于聚類的填補(bǔ)算法、基于關(guān)聯(lián)規(guī)則[16]的填補(bǔ)算法.通過實(shí)驗(yàn)證明，即使一些比較簡單的、填充效果一般的算法，都明顯的提高了算法的執(zhí)行和效果.

文中主要研究的是KNN最近鄰算法在數(shù)據(jù)填補(bǔ)方面的運(yùn)用.KNN最近鄰填補(bǔ)算法是數(shù)據(jù)填補(bǔ)的一種常用方法，以其簡單易明的算法原理和方便的操作過程深受廣大學(xué)者的青睞，也被廣泛的應(yīng)用在很多實(shí)際問題中，比如人口統(tǒng)計(jì)或者水文數(shù)據(jù)的分析.KNN算法最早是由Cover和Heart[17]在1968年提出了最原始的計(jì)算模型.根據(jù)K近鄰算法存在的缺點(diǎn)，一些對于它的改進(jìn)也響應(yīng)而出，文獻(xiàn)[18]介紹了一種針對噪聲處理的KNN算法，文獻(xiàn)[19]則是結(jié)合了哈希表對KNN填補(bǔ)算法進(jìn)行改進(jìn)，文獻(xiàn)[20]利用粒子群優(yōu)化方法的隨機(jī)搜索能力指導(dǎo)KNN算法近鄰搜索，文獻(xiàn)[21]將支持向量機(jī)算法和KNN算法相結(jié)合來提高算法的精度.本實(shí)驗(yàn)則考慮了屬性的相關(guān)性，應(yīng)用主成分分析過程的相關(guān)系數(shù)矩陣，對傳統(tǒng)KNN進(jìn)行優(yōu)化.

1 KNN填補(bǔ)算法和PCA算法

1.1 KNN填補(bǔ)算法

首先計(jì)算目標(biāo)數(shù)據(jù)集（包括含有數(shù)據(jù)缺失的數(shù)據(jù)記錄項(xiàng)，m是數(shù)據(jù)記錄數(shù)量，n是數(shù)據(jù)維數(shù)）和數(shù)據(jù)集中所有的完全值數(shù)據(jù)記錄的歐式距離，在所有的完全值數(shù)據(jù)記錄中選擇出與目標(biāo)數(shù)據(jù)歐式距離最小的k個(gè)數(shù)據(jù)記錄作為目標(biāo)數(shù)據(jù)的最近鄰，k最近鄰數(shù)據(jù)記錄相應(yīng)位置的加權(quán)平均值即可作為數(shù)據(jù)記錄缺失數(shù)據(jù)的評估值.

1）數(shù)據(jù)初始化，構(gòu)建完整數(shù)據(jù)集矩陣：（x1,x2,…,xj,…,xm）T，其中[X]r是數(shù)據(jù)的第 r個(gè)屬性，r≤n，m為樣本數(shù)量；

2）計(jì)算目標(biāo)值與數(shù)據(jù)矩陣中其他數(shù)據(jù)記錄的歐式距離，給定一個(gè)缺失實(shí)例xir：

3）選出距離最小的k個(gè)距離對應(yīng)的數(shù)據(jù)記錄作為目標(biāo)數(shù)據(jù)的k近鄰數(shù)據(jù)；

4）計(jì)算目標(biāo)數(shù)據(jù)的k個(gè)最近鄰目標(biāo)的權(quán)值：

5）算出缺失值的替代值：

其中，xkr表示最近鄰相應(yīng)屬性的數(shù)值.

1.2 PCA算法

主成分分析 （Principal Component Analysis，PCA）是一類處理高維數(shù)據(jù)的算法，實(shí)質(zhì)將高維的數(shù)據(jù)投影到低維空間上，最小化屬性間相關(guān)性.計(jì)算過程中的協(xié)方差矩陣，是來反映各個(gè)緯度之間的相互關(guān)系[22].如果兩個(gè)變量的變化趨勢一致，也就是說如果其中一個(gè)大于自身的期望值，另外一個(gè)也大于自身的期望值，那么兩個(gè)變量之間的協(xié)方差就是正值.如果兩個(gè)變量的變化趨勢相反，即其中一個(gè)大于自身的期望值，另外一個(gè)卻小于自身的期望值，那么兩個(gè)變量之間的協(xié)方差就是負(fù)值.如果是統(tǒng)計(jì)獨(dú)立的，那么二者之間的協(xié)方差就是0[23].

協(xié)方差作為描述和相關(guān)程度的量，在同一物理量綱之下有一定的作用，但同樣的兩個(gè)量采用不同的量綱使它們的協(xié)方差在數(shù)值上表現(xiàn)出很大的差異，因此，在應(yīng)用協(xié)方差度量相鄰數(shù)據(jù)相關(guān)關(guān)系時(shí)，首先要保證數(shù)據(jù)在同一物理量綱下，所以在實(shí)驗(yàn)時(shí)先對數(shù)據(jù)矩陣做標(biāo)準(zhǔn)化處理.

2 改進(jìn)的KNN填補(bǔ)算法過程

2.1 構(gòu)造數(shù)據(jù)的相關(guān)性系數(shù)矩陣

第一步：初始化數(shù)據(jù)矩陣，構(gòu)建完整的數(shù)據(jù)矩陣Xm*n，m表示數(shù)據(jù)有m條數(shù)據(jù)記錄，n表示數(shù)據(jù)記錄的維數(shù).將所有缺失數(shù)據(jù)標(biāo)記，以待下一步處理.

第二步：數(shù)據(jù)標(biāo)準(zhǔn)化，目的是使數(shù)據(jù)的平均值為0，標(biāo)準(zhǔn)差為1，這樣可以使得不同量綱的數(shù)據(jù)放在同一矩陣.數(shù)據(jù)標(biāo)準(zhǔn)化的數(shù)學(xué)公式是：

第三步：對標(biāo)準(zhǔn)化后的數(shù)據(jù)矩陣求協(xié)方差，協(xié)方差是一種用來度量兩個(gè)隨機(jī)變量關(guān)系的統(tǒng)計(jì)量，公式為：

對于一個(gè)n維的數(shù)據(jù)矩陣，由于數(shù)據(jù)兩兩之間的便可以得出一個(gè)協(xié)方差.那么這個(gè)n維的數(shù)據(jù)便可以得到一個(gè)n*n的協(xié)方差矩陣.

若xi表示矩陣的第i個(gè)屬性，可以表示為：

2.2 計(jì)算KNN算法的估計(jì)值

這一部分算法主要是KNN填補(bǔ)算法的過程.

第一步：計(jì)算完備數(shù)據(jù)集的歐式距離.首先因?yàn)槿笔?shù)據(jù)基本是隨機(jī)的，所以可能在任何一維或者某條數(shù)據(jù)記錄里出現(xiàn)，因此在計(jì)算距離時(shí)，僅僅將沒有缺失的數(shù)據(jù)考慮進(jìn)來.不過這里只是在計(jì)算兩兩之間的距離時(shí)，忽略那些有缺失的維數(shù).

第二步：由于整個(gè)算法過程都與距離的有關(guān)系，距離的大小決定著后續(xù)選取的K個(gè)近鄰的質(zhì)量和選取準(zhǔn)確度.在前兩步的基礎(chǔ)上計(jì)算矩陣X的歐式距離矩陣，用Xi表示第i條數(shù)據(jù)記錄.

矩陣的每一行就代表X中的其余行從第一行開始和本行的歐式距離.

第三步：從原始數(shù)據(jù)的第一行第一列開始遍歷尋找缺失值xij，那么它所在的行數(shù)就是i，第i行所對應(yīng)的距離矩陣即是dis的第i行.然后確定要使用的近鄰的個(gè)數(shù)K，選取dis對應(yīng)行的最小的K個(gè)數(shù)值構(gòu)成向量：

針對每一個(gè)距離數(shù)值確定它對應(yīng)的數(shù)據(jù)項(xiàng)得行數(shù)，再找到缺失值在這行數(shù)據(jù)中對應(yīng)的同一屬性的數(shù)值.距離和這個(gè)數(shù)值的乘積便是一個(gè)鄰居的加權(quán)值，最終的K個(gè)鄰居加權(quán)值的和除以距離的和的加權(quán)均值就是最后KNN算法所求得的替代值x0.

xpj是最近鄰相應(yīng)位置的數(shù)值.p是距離矩陣的列數(shù)對應(yīng)原數(shù)據(jù)矩陣的行數(shù).

2.3 計(jì)算維度相關(guān)值得到最終填補(bǔ)值

利用第一步所得的協(xié)方差矩陣和K個(gè)近鄰數(shù)據(jù)組成的近鄰矩陣，通過計(jì)算得到一個(gè)和維度相關(guān)的量，將這個(gè)量稱為維度相關(guān)量.

第一步：考慮到每一個(gè)屬性對應(yīng)數(shù)值的大小不一樣，所以用每一個(gè)數(shù)值減去本屬性下的統(tǒng)計(jì)值的均值作為計(jì)算的標(biāo)準(zhǔn)，這個(gè)值被稱為偏差，它表示一個(gè)數(shù)值偏離中心的程度.

m0是這個(gè)屬性中未缺失的個(gè)數(shù)，xij就是對應(yīng)的統(tǒng)計(jì)值.

第二步：求出用第一步所求的差值和相應(yīng)協(xié)方差矩陣對應(yīng)值，就是這個(gè)屬性對于缺失數(shù)據(jù)所在維度的影響大小.對K個(gè)近鄰中所有不是缺失數(shù)據(jù)的觀測數(shù)值做同樣操作，最后所得的數(shù)值相加后取均值，得到其余完備數(shù)據(jù)的屬性和這個(gè)缺失值所對應(yīng)屬性的維度相關(guān)數(shù)值.

r是數(shù)據(jù)項(xiàng)中這一行中未缺失的數(shù)據(jù)個(gè)數(shù)，也是現(xiàn)實(shí)條件下能統(tǒng)計(jì)到的對缺失值產(chǎn)生影響的維度數(shù)目，Coeff是ar對應(yīng)的協(xié)方差數(shù)值.

第三步：將第二部分中所求的估計(jì)值和維度相關(guān)量相加，得到我們最終改進(jìn)算法后的缺失值的估計(jì)值.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 檢驗(yàn)方法

比較實(shí)驗(yàn)前后填數(shù)據(jù)果和原始數(shù)據(jù)的差別，所以采用均方根誤差RMSE（Root Mean SquareError）評價(jià)缺失數(shù)據(jù)填補(bǔ)效果.

另外，為了詳細(xì)比較兩個(gè)算法最后填補(bǔ)的RMSE，所以我們增加一個(gè)評價(jià)量decrmse表示兩種填補(bǔ)結(jié)果的差：

PKRMSE表示改進(jìn)算法的均方根誤差，KRMSE表示原KNN算法的均方根誤差.因?yàn)镽MSE在做評價(jià)標(biāo)準(zhǔn)時(shí)，數(shù)值越小，就代表估計(jì)值就越接近原始數(shù)值.所以當(dāng)decrmse小于零時(shí)證明改進(jìn)后的算法均方根誤差更小，也就說明它的填補(bǔ)效果更好.文中將改進(jìn)的算法稱為PKNN算法.

實(shí)驗(yàn)的平臺是Windows10專業(yè)版，Intel（R）Core（TM） i5-3210M CPU 2.5 GHz，4 GB 內(nèi)存，500 GB 硬盤.開發(fā)工具采用matlab R2015a.選用UCI數(shù)據(jù)庫上的 wine，slump，isolet，SPECTF.UCI數(shù)據(jù)庫是一個(gè)專門用于測試機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘算法的公共數(shù)據(jù)庫，庫中的數(shù)據(jù)都有確定的分類，因此可以用均方根誤差直觀地表示缺失數(shù)據(jù)填補(bǔ)的效果，缺失比例取5%到60%，本次實(shí)驗(yàn)取K值分別為4、8、24，所以每組實(shí)驗(yàn)分三個(gè)部分，為避免實(shí)驗(yàn)偶然性，每次實(shí)驗(yàn)10次取均值.數(shù)據(jù)集信息如表1所示.

3.2 K為定值不同的數(shù)據(jù)集結(jié)果

對于上述數(shù)據(jù)集均取K值為24，觀察改進(jìn)的算法的填補(bǔ)效果，對比傳統(tǒng)的K近鄰填補(bǔ)算法，比較結(jié)果如圖1至圖3所示.

表1 實(shí)驗(yàn)數(shù)據(jù)集信息

圖1 ISOLET在K=24時(shí)填補(bǔ)效果

圖2 SPECTF在K=24時(shí)填補(bǔ)效果

圖3 HAYES在K=24時(shí)填補(bǔ)效果

對這3種數(shù)據(jù)仿真時(shí)，由實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)后的算法對缺失數(shù)據(jù)項(xiàng)的填補(bǔ)效果要比傳統(tǒng)KNN填補(bǔ)算法填補(bǔ)效果更好，并且在數(shù)據(jù)缺失比例比較低時(shí)優(yōu)化效果更明顯，隨著缺失比例上升，數(shù)據(jù)集中完備數(shù)據(jù)減少，可用信息量降低，改進(jìn)算法結(jié)果逐漸接近傳統(tǒng)填補(bǔ)算法.在另外兩組數(shù)據(jù)組中，均方根誤差數(shù)值較大，兩條曲線很接近，但是從兩者數(shù)值差值可以比較出仍然是改進(jìn)過的算法擁有更好一些的效果，如圖4所示.

3.3 不同K值對結(jié)果的影響

實(shí)驗(yàn)中，我們對K近鄰的數(shù)量選取還做了不同實(shí)驗(yàn)，分別去了K值為 4、8、24，觀測不同 K值下的結(jié)果，及改進(jìn)的算法和K值的關(guān)系，其實(shí)驗(yàn)結(jié)果如圖5所示.-3

圖4 SLUMP和WINE在K=24時(shí)填補(bǔ)效果

圖5 不同數(shù)據(jù)集在不同K值的填補(bǔ)

由幾組實(shí)驗(yàn)的結(jié)果可以看出，對于不同的K值，K近鄰選擇數(shù)量愈多，改進(jìn)后的算法的填補(bǔ)效果明顯也更好.三種K值時(shí)都有相同的趨勢，隨著缺失比例上升，逐漸趨于相同，且趨于0.證明缺失比例到一定程度后，K近鄰的數(shù)量對填補(bǔ)的結(jié)果影響越來越小，并且可用信息量減少后，改進(jìn)算法優(yōu)化效果也不在明顯.

3.4 與其它算法的比較

為了測試實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，和對算法改進(jìn)的可行性，本次實(shí)驗(yàn)加入了列均值填補(bǔ)算法，來比較填補(bǔ)算法的效果.表2是在5個(gè)數(shù)據(jù)集上進(jìn)行填補(bǔ)實(shí)驗(yàn)的均方根誤差.其中：KNN表示傳統(tǒng)的K近鄰填補(bǔ)算法，P-KNN表示結(jié)合了屬性相關(guān)值的K近鄰填補(bǔ)算法，其后的數(shù)字表示K近鄰選擇的個(gè)數(shù)，比如，KNN_8表示近鄰個(gè)數(shù)為8的經(jīng)典KNN填補(bǔ)算法.col-means表示列均值填補(bǔ)算法.取缺失數(shù)據(jù)為10%時(shí)的實(shí)驗(yàn)數(shù)據(jù).

表2 三種算法均方根誤差

從表2中數(shù)據(jù)可以看到，在5個(gè)數(shù)據(jù)集上，缺失比例保持在10%時(shí)，傳統(tǒng)KNN算法和基于屬性相關(guān)的KNN算法，在取近鄰個(gè)數(shù)相同情況下，它們的誤差基本上是保持相同的.而列均值填補(bǔ)算法在五種數(shù)據(jù)集上的誤差都高于KNN和改進(jìn)的KNN算法.這種情況的原因可能是：①缺失比例較低，數(shù)據(jù)完備性高，同一列數(shù)值更多，列均值計(jì)算的數(shù)值大，相關(guān)性較低的一些數(shù)值也被計(jì)算其中.②列均值對于異常點(diǎn)比較敏感，而KNN算法在選擇K近鄰時(shí)，近似性低的數(shù)據(jù)項(xiàng)不會被選擇，因而排出了一些噪聲數(shù)據(jù)的影響.

在不同缺失比例，五種數(shù)據(jù)集上我們也做了相同的實(shí)驗(yàn)，在K為24時(shí)，實(shí)驗(yàn)的結(jié)果是比較直接的，圖6表示SPECTF、SLUMP和HAYES三種算法的效果圖.

圖6 SPECTF、SLUMP和HAYES三種算法比較

在SPECTF和HAYES數(shù)據(jù)的實(shí)驗(yàn)中，三種算法的結(jié)果折線圖可以直觀的展現(xiàn)出來，在SLUMP數(shù)據(jù)進(jìn)行實(shí)驗(yàn)時(shí)，兩種KNN算法仍然是基本上保持持平的，但是折線圖不能很好的體現(xiàn)出來，這種情況的原因和同意維度下數(shù)據(jù)值的大小離散程度較大有關(guān)系，近鄰算法的近鄰數(shù)值相差不會太大，但是在列均值計(jì)算時(shí)，這些離散的數(shù)值會一同計(jì)算，從而影響了均值和緊鄰計(jì)算均值相差較大.另外兩組的實(shí)驗(yàn)數(shù)據(jù)結(jié)果如表3和表4所示.

類似的，從表3和表4中可以看出，依然是KNN的算法準(zhǔn)確度要高于列均值算法.相較于經(jīng)典KNN，經(jīng)過屬性相關(guān)度改進(jìn)后的算法保持了一定的優(yōu)化效果，不過，隨著缺失比例的上升，準(zhǔn)確度也有下降的趨勢.但是列均值卻沒有這種情況，由于采用的是隨機(jī)缺失的機(jī)制，對于整體而言，部分隨機(jī)的數(shù)據(jù)，對于均值的影響就比較小.

表3 wine均方根誤差（K=24）

表4 isolet均方根誤差（K=24）

4 結(jié) 論

通過PCA算法，使用相關(guān)系數(shù)來改進(jìn)傳統(tǒng)KNN填補(bǔ)算法，經(jīng)過實(shí)驗(yàn)表明了它還是可取的.利用屬性相關(guān)性計(jì)算屬性相關(guān)量，盡可能的使用數(shù)據(jù)集中完備數(shù)據(jù)的信息來優(yōu)化傳統(tǒng)基于歐式距離的KNN近鄰填補(bǔ)算法，獲得了更好的結(jié)果，填補(bǔ)值更接近原始值，這樣得到的數(shù)值也更貼近于實(shí)際獲得的數(shù)據(jù)值.對于之后的數(shù)據(jù)挖掘和分析可以提供更好的數(shù)據(jù)組，最終結(jié)果也會更加準(zhǔn)確可信.對于實(shí)驗(yàn)和改進(jìn)算法中存在的不足，在后期的工作中我們會進(jìn)一步改進(jìn)和優(yōu)化.