基于PCA的近鄰均值填補(bǔ)優(yōu)化算法

謝霖銓 畢永朋 廖龍龍

摘 要：均值填補(bǔ)是常用的數(shù)據(jù)填補(bǔ)方式，但往往忽略了相鄰變量之間的相互關(guān)系，又對(duì)噪聲數(shù)據(jù)極為敏感。將主成份分析算法應(yīng)用到均值填補(bǔ)算法中，提取相鄰各屬性的特征重要度，并采用屬性重要度作為權(quán)重，以均值填補(bǔ)的計(jì)算方式算出缺失數(shù)據(jù)相鄰矩陣的加權(quán)平均值，將其作為相鄰屬性對(duì)于均值填補(bǔ)的影響偏移值，加入到均值填補(bǔ)的均值計(jì)算中。通過(guò)對(duì)UCI數(shù)據(jù)集的仿真實(shí)驗(yàn)可知，基于PCA改進(jìn)的算法填補(bǔ)的準(zhǔn)確性明顯優(yōu)于均值填補(bǔ)算法。

關(guān)鍵詞：近鄰均值填補(bǔ)；主成分分析；特征重要度；偏移值

DOI：10.11907/rjdk.172938

中圖分類號(hào)： TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）006-0067-03

Abstract：Mean filling algorithm is a commonly-adopted way to fill missing data. However the correlation between these variables is ignored and also extremely sensitive to noise data. In this paper， the principal component analysis（PCA） algorithm is applied to mean filling algorithm， and the characteristics of adjacent properties are proposed. The weighted mean value of the adjoining matrix of the missing data is calculated by using the attribute importance as the weight. As an adjacent property， the offset value of the mean value is added to the mean calculation of the mean filling. According to results of the UCI dataset simulation experiment， the accuracyof the improved complement algorithm based on PCA is clearly higher than that of the mean filling algorithm.

Key Words：nearest neighbor imputation； PCA； attribute significance； deviant

0 引言

缺失數(shù)據(jù)指在數(shù)據(jù)采集時(shí)由于某種原因，應(yīng)該得到而實(shí)際沒(méi)有得到的數(shù)據(jù)，導(dǎo)致現(xiàn)有數(shù)據(jù)集中某個(gè)或某些數(shù)據(jù)不完全。

數(shù)據(jù)處理需要建立在完備數(shù)據(jù)上，但在現(xiàn)實(shí)數(shù)據(jù)整理收集過(guò)程中，收集的數(shù)據(jù)很難避免缺失問(wèn)題。這些缺失的數(shù)據(jù)給后續(xù)數(shù)據(jù)分析帶來(lái)巨大影響，特別是分析過(guò)程和所得結(jié)果的準(zhǔn)確性。所以，在數(shù)據(jù)處理分析之前，對(duì)缺失數(shù)據(jù)的預(yù)處理成為一項(xiàng)很重要的準(zhǔn)備工作[1]。常用的缺失數(shù)據(jù)處理方法有刪除缺失數(shù)據(jù)或?qū)θ笔?shù)據(jù)進(jìn)行填補(bǔ)。為不影響其它有效數(shù)據(jù)，一般會(huì)采用數(shù)據(jù)填補(bǔ)。數(shù)據(jù)填補(bǔ)方法是利用其它輔助信息，經(jīng)過(guò)計(jì)算，得到一個(gè)新的數(shù)值，插入缺失位置來(lái)代替缺失值。根據(jù)所構(gòu)造數(shù)值的個(gè)數(shù)，可分為單一填補(bǔ)和多重填補(bǔ)[2]。

近年來(lái)，數(shù)據(jù)填補(bǔ)不再簡(jiǎn)單地以數(shù)據(jù)的數(shù)值大小作為計(jì)算準(zhǔn)則，基于粗糙集合理論[3]、相似關(guān)系、關(guān)聯(lián)規(guī)則[4]等理論，更多的改進(jìn)算法相繼被提出來(lái)[5]。

最近鄰均值填補(bǔ)是一種單一填補(bǔ)的方法，操作簡(jiǎn)單，深受廣大研究者青睞[6]，但受噪聲影響比較大。文獻(xiàn)[7]介紹了一種基于噪聲處理的近鄰填補(bǔ)算法。

主成份分析（principal component analysis，PCA）是Karl Parson[8]于1901年提出的一種經(jīng)典特征降維算法和多元統(tǒng)計(jì)分析方法。根據(jù)原始數(shù)據(jù)集的協(xié)方差矩陣和特征值特征向量，計(jì)算新的向量基，最終將原始數(shù)據(jù)投影到新的向量基中，并使這些新變量盡可能多地反映原變量的信息量。文獻(xiàn)[9]采用PCA的思想對(duì)水質(zhì)數(shù)據(jù)之間蘊(yùn)含相似性進(jìn)行剖析，并找出其影響水質(zhì)狀況的各個(gè)指標(biāo)的相似程度大小。文獻(xiàn)[10]則使用PCA算法處理屬性相關(guān)的問(wèn)題，借鑒PCA算法的壓縮原理，通過(guò)算出協(xié)方差矩陣的特征值特征向量，找到主要元素，并計(jì)算各屬性權(quán)重，加入到其它算法中，以此排除無(wú)關(guān)屬性的干擾。

由于均值填補(bǔ)算法也常受無(wú)關(guān)屬性干擾和噪聲數(shù)據(jù)的影響，使找到的替代值偏大或偏小。基于以上研究，將PCA算法融入到最近鄰均值填補(bǔ)算法中，以新的向量基下的數(shù)據(jù)集屬性方差貢獻(xiàn)率為權(quán)值，計(jì)算鄰近數(shù)據(jù)整體的影響值，提高填補(bǔ)效果，可有效克服噪聲和無(wú)關(guān)屬性對(duì)填補(bǔ)結(jié)果的影響。

1 最近鄰填補(bǔ)

最近鄰填補(bǔ)是在圖像處理中常用的數(shù)據(jù)填補(bǔ)算法。原理是選擇未知像素一定范圍內(nèi)的K個(gè)近鄰像素?cái)?shù)據(jù)作為目標(biāo)數(shù)據(jù)的最近鄰，把K個(gè)最近鄰像素?cái)?shù)據(jù)的平均值作為目標(biāo)數(shù)據(jù)缺失像素的替代值。

最近鄰填補(bǔ)算法流程：

（1）整理數(shù)據(jù)集（包含有缺失項(xiàng)的數(shù)據(jù)記錄）。

（2）查找數(shù)據(jù)集中有缺失的數(shù)據(jù)項(xiàng)，找到缺失數(shù)據(jù)的近鄰數(shù)據(jù)x-1，x-2，…，x-k。

（3）計(jì)算K個(gè)最近鄰數(shù)據(jù)的和。

（4）將均值M=S/k作為缺失值的替代值，填補(bǔ)到缺失位置。

（5）重復(fù)（2）～（4），直到數(shù)據(jù)集中不再含有缺失數(shù)據(jù)為止。

2 PCA算法

PCA算法是一種無(wú)監(jiān)督降維學(xué)習(xí)方法，通過(guò)抽取樣本的主要影響因素，簡(jiǎn)化復(fù)雜的問(wèn)題。

PCA的基本原理是：

（1）將原始數(shù)據(jù)集按列組成m行n列矩陣X。

（2）將X的每一行進(jìn)行零均值化，即減去這一行的均值：

（3）求出協(xié)方差矩陣C：

m代表樣本個(gè)數(shù)

（5）計(jì)算特征貢獻(xiàn)率：

（6）將特征向量按對(duì)應(yīng)特征值大小從上到下按行排列成矩陣，組成矩陣P。

（7）Y=PX即為降維到k維后的數(shù)據(jù)。

3 PCA改進(jìn)的均值填補(bǔ)算法

基于PCA的最近鄰填補(bǔ)算法，是依靠原始樣本數(shù)據(jù)，得到缺失值的替代值，在填補(bǔ)效果上有良好的表現(xiàn)。它的主要思想是根據(jù)缺失值的近鄰值，通過(guò)PCA算法計(jì)算出一個(gè)基于屬性特征值的影響值，作為一個(gè)額外的特征偏移值加在均值算法最后的計(jì)算中。該算法主要分為3個(gè)階段。

3.1 第一階段算法

（1）首先數(shù)據(jù)初始化，構(gòu)建完整的數(shù)據(jù)矩陣X，并將所有缺失數(shù)據(jù)標(biāo)記為-1以待下一步處理。

3.2 第二階段算法

PCA算法會(huì)把貢獻(xiàn)率特別低的無(wú)關(guān)屬性以及噪聲剔除，而且不會(huì)影響數(shù)據(jù)的整體特性，減少噪音和冗余，降低過(guò)度擬合的可能性。通過(guò)PCA算法對(duì)近鄰矩陣L分析，將數(shù)據(jù)映射到新的維度下，生成新的5*5數(shù)據(jù)集N。

（1）進(jìn)行標(biāo)準(zhǔn)化矩陣L主成份分析，得到各特征值λ-1和主特征貢獻(xiàn)率e-i，及由特征向量d-i構(gòu)成的轉(zhuǎn)換矩陣P。

（2）映射到新數(shù)據(jù)集：

（3）求出其它屬性值對(duì)缺失值屬性的影響偏移值，既每個(gè)屬性特征重要度和屬性值乘積的加權(quán)和的均值。

n-ij是矩陣N中的元素，k是特征值個(gè)數(shù)，25是所選取的缺失值近鄰數(shù)據(jù)個(gè)數(shù)24加上缺失值本身，即矩陣N的數(shù)據(jù)個(gè)數(shù)。

3.3 第三階段算法

利用均值填補(bǔ)算法計(jì)算最近鄰數(shù)據(jù)的數(shù)值和，在計(jì)算替代值M算法的基礎(chǔ)上加上特征影響偏移量m，得到新的填補(bǔ)值M′。

在算法過(guò)程中，為避免某些屬性對(duì)待填補(bǔ)值的影響過(guò)大導(dǎo)致偏移值不受控制，在矩陣L中設(shè)置了一個(gè)缺失替代值的取值域，規(guī)定上限不超過(guò)最大值的平方與最小值的商，下限不低于最小值的平方與最大值的商。若超出這個(gè)范圍，則用均值代替M填補(bǔ)，填補(bǔ)值域上限：

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

4.1 檢驗(yàn)方法

為驗(yàn)證算法的運(yùn)算效果，實(shí)驗(yàn)將本算法結(jié)果和原近鄰填補(bǔ)算法結(jié)果相對(duì)比。選用UCI數(shù)據(jù)庫(kù)的SPECTF，WINE，GLASS，ARRHYMIA數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集。使用均方根誤差RMSE（root mean square error）評(píng)價(jià)缺失數(shù)據(jù)填補(bǔ)的效果.

其中，n為填補(bǔ)個(gè)數(shù)，g-i是原數(shù)值，是填充估值。最終的RMSE數(shù)值越小，代表算法填補(bǔ)準(zhǔn)確率越高，效果越好。

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

為了測(cè)試實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，本實(shí)驗(yàn)設(shè)置不同的缺失比例，缺失率分別為5%、10%、15%、20%、25%、30%、35%、40%、45%、50%、55%。為使結(jié)果準(zhǔn)確，取多次實(shí)驗(yàn)的均值。通過(guò)Matlab仿真實(shí)驗(yàn)得到對(duì)比結(jié)果。

三角形折線表示原始均值算法填補(bǔ)實(shí)驗(yàn)效果，正方形折線代表改進(jìn)算法實(shí)驗(yàn)效果，圖1、圖2、圖3分別是3種不同類型數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果。

由實(shí)驗(yàn)結(jié)果可知，基于PCA改進(jìn)后的填補(bǔ)算法在準(zhǔn)確度上有明顯提升，總體上優(yōu)于之前算法。在WINE和GLASS數(shù)據(jù)集仿真中，優(yōu)化后的算法結(jié)果明顯更平穩(wěn)，缺失比例從5%上升到55%的過(guò)程中，衡量填補(bǔ)效果的均方根更趨于平緩。

5 結(jié)語(yǔ)

基于PCA算法的最鄰近算法與原始均值算法相比，通過(guò)對(duì)均值計(jì)算的加權(quán)，并設(shè)置上限值和下限值，更好地解決了噪聲或冗余數(shù)據(jù)數(shù)據(jù)對(duì)結(jié)果造成影響的問(wèn)題。

不過(guò)，該算法也有不足之處，在對(duì)類似于數(shù)據(jù)集SPECTF這種噪聲數(shù)據(jù)較少、數(shù)據(jù)集數(shù)值比較平均的缺失數(shù)據(jù)填補(bǔ)時(shí)，增大了工作量和時(shí)間復(fù)雜度，填補(bǔ)效果也并沒(méi)有有效提高，在以后的工作中將會(huì)繼續(xù)對(duì)算法研究改進(jìn)以達(dá)到更好的效果。

參考文獻(xiàn)：

[1] ALLISON P D.缺失數(shù)據(jù)[M].林毓玲，譯.上海：格致出版社，2012.

[2] 龐新生.缺失數(shù)據(jù)插補(bǔ)處理方法的比較研究[J].統(tǒng)計(jì)與決策，2012（24）：18-22.

[3] 武森，馮小東，單志廣.基于不完備數(shù)據(jù)聚類的缺失數(shù)據(jù)填補(bǔ)方法[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（8）：1726-1738.

[4] 于力超，金勇進(jìn)，王俊.缺失數(shù)據(jù)插補(bǔ)方法探討——基于最近鄰插補(bǔ)法和關(guān)聯(lián)規(guī)則法[J].統(tǒng)計(jì)與信息論壇，2015，172（1）：35-40.

[5] 毛玫靜，鄂旭，譚艷，等.基于屬性相關(guān)度的缺失數(shù)據(jù)填補(bǔ)算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（6）：74-79.

[6] PAN R， YANG T， CAO J， et al. Missing data imputation by K nearest neighbours based on grey relational structure and mutual information[J]. Applied Intelligence，2015，43（3）：614-632.

[7] 郝勝軒，宋宏，周曉鋒.基于近鄰噪聲處理的K-NN缺失數(shù)據(jù)填補(bǔ)算法[J].計(jì)算機(jī)仿真，2014，31（7）：264-268.

[8] BERNSTEIN H J， ANDREWS L C. Accelerating k-nearest-neighbor searches[J]. Journal of Applied Crystallography，2016，49（5）：1471-1477.

[9] 董建華，王國(guó)胤，姚文.基于PCA的水質(zhì)數(shù)據(jù)相似度分析模型[J].環(huán)境工程，2016（s1）：841-844.

[10] 黃秀霞，孫力.基于屬性依賴度計(jì)算和PCA的C4.5算法[J].傳感器與微系統(tǒng)，2017，36（1）：131-134.

（責(zé)任編輯：江 艷）