謝霖銓 畢永朋 廖龍龍

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

關鍵詞：近鄰均值填補；主成分分析；特征重要度；偏移值

DOI：10.11907/rjdk.172938

中圖分類號： TP312

文獻標識碼：A 文章編號：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ù)據(jù)，導致現(xiàn)有數(shù)據(jù)集中某個或某些數(shù)據(jù)不完全。

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

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

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

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

由于均值填補算法也常受無關屬性干擾和噪聲數(shù)據(jù)的影響，使找到的替代值偏大或偏小?；谝陨涎芯浚瑢CA算法融入到最近鄰均值填補算法中，以新的向量基下的數(shù)據(jù)集屬性方差貢獻率為權值，計算鄰近數(shù)據(jù)整體的影響值，提高填補效果，可有效克服噪聲和無關屬性對填補結果的影響。

1 最近鄰填補

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

最近鄰填補算法流程：

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

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

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

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

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

2 PCA算法

PCA算法是一種無監(jiān)督降維學習方法，通過抽取樣本的主要影響因素，簡化復雜的問題。

PCA的基本原理是：

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

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

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

m代表樣本個數(shù)

（5）計算特征貢獻率：

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

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

3 PCA改進的均值填補算法

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

3.1 第一階段算法

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

3.2 第二階段算法

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

（1）進行標準化矩陣L主成份分析，得到各特征值λ-1和主特征貢獻率e-i，及由特征向量d-i構成的轉換矩陣P。

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

（3）求出其它屬性值對缺失值屬性的影響偏移值，既每個屬性特征重要度和屬性值乘積的加權和的均值。

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

3.3 第三階段算法

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

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

4 實驗結果與分析

4.1 檢驗方法

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

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

4.2 實驗結果

為了測試實驗結果的準確性，本實驗設置不同的缺失比例，缺失率分別為5%、10%、15%、20%、25%、30%、35%、40%、45%、50%、55%。為使結果準確，取多次實驗的均值。通過Matlab仿真實驗得到對比結果。

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

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

5 結語

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

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

參考文獻：

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

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

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

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

[5] 毛玫靜，鄂旭，譚艷，等.基于屬性相關度的缺失數(shù)據(jù)填補算法研究[J].計算機工程與應用，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ù)填補算法[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] 董建華，王國胤，姚文.基于PCA的水質數(shù)據(jù)相似度分析模型[J].環(huán)境工程，2016（s1）：841-844.

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

（責任編輯：江 艷）