基于局部線(xiàn)性重構(gòu)的近鄰填充算法

溫海標(biāo)

（廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，南寧 530023）

基于局部線(xiàn)性重構(gòu)的近鄰填充算法

溫海標(biāo)

（廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，南寧 530023）

K近鄰填充算法（KNNI）對(duì)缺失數(shù)據(jù)填充時(shí)，使用K個(gè)近鄰的訓(xùn)練樣本屬性值的平均值作為KNNI算法的填充值，該值偏離真實(shí)值較大，一種有效的方法是K近鄰樣本屬性值的加權(quán)平均值作為填充值。如何確定K近鄰樣本的權(quán)值，是KNNI算法研究熱點(diǎn)。為此，提出引入局部線(xiàn)性重構(gòu)方法用于近鄰填充，該方法是用K近鄰樣本重構(gòu)測(cè)試樣本得出權(quán)值。實(shí)驗(yàn)結(jié)果表明提出的算法比KNNI算法填充效果更好，填充值更接近真實(shí)值。

缺失值填充；重構(gòu)技術(shù)；K近鄰；LLR

0 引言

在機(jī)器學(xué)習(xí)的實(shí)際應(yīng)用中，樣本的一些數(shù)據(jù)經(jīng)常因?yàn)槟承┰驅(qū)е聵颖緮?shù)據(jù)不完整，例如數(shù)據(jù)暫時(shí)無(wú)法得到、被遺漏等原因?qū)е聰?shù)據(jù)缺失[1]。樣本數(shù)據(jù)的缺失會(huì)影響機(jī)器從樣本數(shù)據(jù)學(xué)習(xí)得來(lái)的模型性能或規(guī)則的正確性。因此在機(jī)器學(xué)習(xí)領(lǐng)域，缺失數(shù)據(jù)填充是基礎(chǔ)而又重要的研究問(wèn)題。

目前，已有多種方法處理缺失值，例如最近鄰、決策樹(shù)、貝葉斯網(wǎng)絡(luò)、支持向量機(jī)、粗糙集和模糊集、神經(jīng)網(wǎng)絡(luò)等方法[2]。其中K近鄰填充算法[3]時(shí)間復(fù)雜度低，填充效率和準(zhǔn)確率高等優(yōu)點(diǎn)受到了廣泛研究。其基本原理是通過(guò)相似度量函數(shù)計(jì)算出缺失樣本的K個(gè)近鄰?fù)暾麡颖?，?jì)算求得K個(gè)樣本的均值作為填充值。KNNI（K-Nearest Neighbor Imputation）存在一個(gè)明顯的缺陷，如圖1，當(dāng)K=3時(shí)，A、B、C樣本作為缺失樣本的近鄰，A、B、C樣本的均值作為缺失樣本的填充值，該值偏離真實(shí)值的偏差是較大的，因?yàn)镃樣本離缺失樣本較遠(yuǎn)，其中對(duì)填充值有較大影響。一個(gè)有效的方法是對(duì)A、B、C樣本設(shè)置權(quán)值，離缺失樣本越近，權(quán)值越大，即A最大，C最小，A、B、C樣本加權(quán)平均值作為缺失樣本的填充值。這種方法就是降低離缺失樣本較遠(yuǎn)的整樣本的值對(duì)填充值的影響。本文用局部線(xiàn)性重構(gòu)的方法用于KNNI算法，找出合適的K近鄰樣本權(quán)值，進(jìn)一步降低填充值的偏差。

圖1 缺失樣本近鄰點(diǎn)選擇

1 LLR-KNNI算法

1.1 重構(gòu)技術(shù)理論

一個(gè)向量被一組線(xiàn)性無(wú)關(guān)的向量線(xiàn)性組合近似表示，稱(chēng)為重構(gòu)[4]。已知一組線(xiàn)性無(wú)關(guān)向量x1，x2，x3，…，xk，xk∈Rd，和被這組線(xiàn)性近似表示的向量y，y∈Rd，其中d表示向量的元素個(gè)數(shù)，根據(jù)重構(gòu)理論，得出如下函數(shù)：

式（1）中，wi為重構(gòu)系數(shù)，值越大，說(shuō)明xi向量的元素值和y向量元素值接近。W為重構(gòu)系數(shù)向量。式（2）中的e為重構(gòu)誤差，e的值越小，說(shuō)明這組線(xiàn)性無(wú)關(guān)向量的近似表示的向量與y接近。目前重構(gòu)技術(shù)的應(yīng)用得到廣泛應(yīng)用，如人臉識(shí)別、圖像去噪、屬性降維等[5]，其中屬性降維中的局部線(xiàn)性嵌入算法較為經(jīng)典。局部線(xiàn)性嵌入（Locally Linear Embedding，LLE）算法[6]假設(shè)在一個(gè)高維樣本空間中某個(gè)流行局部小領(lǐng)域看成局部線(xiàn)性，即在這個(gè)小領(lǐng)域里的某點(diǎn)可以用重構(gòu)技術(shù)被它周?chē)狞c(diǎn)線(xiàn)性重構(gòu)表示。高維樣本空間中，局部小領(lǐng)域的點(diǎn)是近鄰關(guān)系，降維后這些點(diǎn)仍然是近鄰關(guān)系，是一種基于流行的降維算法。LLE算法因計(jì)算復(fù)雜度低，需配置參數(shù)少，魯棒性好等優(yōu)點(diǎn)得到了廣泛應(yīng)用。

1.2 LLR-KNNI

局部線(xiàn)性重構(gòu)（Local Linear Reconstruction，LLR）是基于重構(gòu)理論和LLE算法得出并應(yīng)用于KNNI算法中，局部指的是重構(gòu)缺失樣本的完整樣本來(lái)自缺失樣本的某個(gè)領(lǐng)域，LLR-KNNI算法分為預(yù)處理和決策過(guò)程，預(yù)處理中，首先把數(shù)據(jù)樣本分為訓(xùn)練樣本和測(cè)試樣本，具有完整數(shù)據(jù)的作為訓(xùn)練樣本，含缺失數(shù)據(jù)的樣本作為測(cè)試樣本。樣本屬性可分為一般屬性和決策屬性，缺失樣本的缺失屬性值可以是一般屬性，也可以是決策屬性，LLR-KNNI算法把缺失屬性視為決策屬性，即當(dāng)缺失屬性值是一般屬性的值時(shí)，該屬性作為決策屬性，其他為一般屬性。其次將整個(gè)數(shù)據(jù)樣本除決策屬性之外的其他屬性值規(guī)范化到[0，1]區(qū)間。決策過(guò)程中，每個(gè)缺失樣本通過(guò)相似度量函數(shù)計(jì)算出k領(lǐng)域的k個(gè)近鄰樣本，通過(guò)重構(gòu)方法找出k個(gè)近鄰樣本的重構(gòu)系數(shù)，這個(gè)系數(shù)稱(chēng)為權(quán)值，權(quán)值越大，說(shuō)明，該權(quán)值對(duì)應(yīng)的近鄰樣本與缺失樣本越相似。最后加權(quán)求和得出填充值。算法描述如下：

訓(xùn)練樣本X∈Rn×d，測(cè)試樣本Y∈Rm×d，m，n為樣本數(shù)，d為屬性個(gè)數(shù)。

步驟1數(shù)據(jù)樣本將非決策屬性規(guī)范化為[0，1]區(qū)間，規(guī)范化方法采用最小最大規(guī)范化法，如下式：

式（3）中，max和min分別表示樣本屬性A的最大值和最小值。

步驟2通過(guò)相似度量函數(shù)計(jì)算測(cè)試樣本的K個(gè)近鄰樣本，相似度量函數(shù)采用歐氏距離函數(shù)：

測(cè)試樣本與每個(gè)訓(xùn)練樣本根據(jù)式（4）計(jì)算距離，計(jì)算結(jié)果從小到大排序，取前K個(gè)距離對(duì)應(yīng)的樣本作為測(cè)試樣本的K近鄰樣本。

步驟3測(cè)試樣本的K近鄰樣本根據(jù)下式重構(gòu)測(cè)試樣本

式（5）中，Ni∈Rk×d是近鄰樣本矩陣，存儲(chǔ)的是測(cè)試樣本的K個(gè)近鄰樣本，wi∈R1×k為近鄰樣本權(quán)值向量，W∈Rm×k為近鄰樣本權(quán)值矩陣。

步驟4通過(guò)求解式（5）的目標(biāo)函數(shù)，得出測(cè)試樣本K個(gè)近鄰樣本的權(quán)值，假設(shè)樣本第j個(gè)屬性為決策屬性，根據(jù)下式計(jì)算試樣本的填充值：

其中Ni（:，j）表示抽取矩陣Ni的第j個(gè)列向量。算法的偽代碼如下：

算法1 LLR-KNNI算法

輸入：訓(xùn)練樣本X，測(cè)試樣本Y，近鄰個(gè)數(shù)K

輸出：測(cè)試樣本決策屬性值

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

實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)采用均方根誤差（Root Mean Square Error，RMSE），計(jì)算公式如下：

其中m為測(cè)試樣本的缺失值個(gè)數(shù)，yi*和yi分別為填充值和真實(shí)值。RMSE表明填充值和真實(shí)值之間的關(guān)系，RMSE值越小，說(shuō)明填充值與真實(shí)值差值越小，即填充值越接近真實(shí)值。

實(shí)驗(yàn)過(guò)程中，LLR-KNNI算法和KNNI算法分別對(duì)缺失樣本填充，分別計(jì)算RMSE值，作為比較LLRKNNI算法和KNNI算法的填充性能。

實(shí)驗(yàn)部分的數(shù)據(jù)集選取UCI[7]機(jī)器學(xué)習(xí)知識(shí)庫(kù)中的部分?jǐn)?shù)據(jù)集（表1）進(jìn)行實(shí)驗(yàn)，所選的數(shù)據(jù)集全部是無(wú)缺失值的完整數(shù)據(jù)集，以測(cè)試LLR-KNNI算法的填充性能。

表1 實(shí)驗(yàn)采用的UCI數(shù)據(jù)集

本文算法采用MATLAB軟件編程實(shí)現(xiàn)，MATLAB軟件版本為2014a。系統(tǒng)平臺(tái)為AMD AthlonⅡX2 B24 3.0 GHz，4GB內(nèi)存，操作系統(tǒng)：Windows 7旗艦版。LLR-KNNI算法和KNNI算法近鄰個(gè)數(shù)K設(shè)置為5，實(shí)驗(yàn)的驗(yàn)證方法采用10折交叉驗(yàn)證法，對(duì)數(shù)據(jù)集拆分10份，第一次實(shí)驗(yàn)時(shí)，第1份設(shè)為測(cè)試集，其余為訓(xùn)練集，第二次實(shí)驗(yàn)將第2份設(shè)為測(cè)試集，其余為訓(xùn)練集，此操作重復(fù)十次。對(duì)表1中的每個(gè)數(shù)據(jù)集采用10折交叉驗(yàn)證法實(shí)驗(yàn)十次，并取十次實(shí)驗(yàn)得出的RMSE的均值加上標(biāo)準(zhǔn)差得出如表2。

從表2可以看出，在每個(gè)數(shù)據(jù)集上，LLR-KNNI算法的RMSE的值比KNNI的小，說(shuō)明LLR-KNNI算法的填充值更接近真實(shí)值，即LLR-KNNI算法的填充性能優(yōu)于傳統(tǒng)KNNI算法。從每個(gè)數(shù)據(jù)集中的標(biāo)準(zhǔn)差的值可以看出，LLR-KNNI算法的標(biāo)準(zhǔn)差值比KNNI的小，說(shuō)明LLR-KNNI算法比KNNI算法有更好的穩(wěn)定性。從圖2更直觀(guān)看出LLR-KNNI的優(yōu)越性，也說(shuō)明LLRKNNI算法比KNNI具有更好的填充性能。

表2 LLR-KNNI算法和KNNI算法在各數(shù)據(jù)集上RMSE的比較（均值標(biāo)準(zhǔn)差）

圖2 算法在各數(shù)據(jù)集十次實(shí)驗(yàn)RMSE對(duì)比圖

3 結(jié)語(yǔ)

本文的LLR-KNNI算法，使用線(xiàn)性重構(gòu)的方法得出樣本近鄰點(diǎn)的權(quán)值，近鄰樣本權(quán)值的大小說(shuō)明與缺失樣本的相似程度，離缺失樣本越遠(yuǎn)，近鄰樣本權(quán)值越小，一定程度降低KNNI算法中較遠(yuǎn)的近鄰點(diǎn)對(duì)算法的填充性能影響。通過(guò)對(duì)比LLR-KNNI算法和KNNI算法的均方根誤差的實(shí)驗(yàn)分析表明，LLR-KNNI算法的填充性能優(yōu)于KNNI算法。

[1]Little，Roderick J A，Rubin，et al.Statistical Analysis with Missing Data[J].American Journal of Sociology，1988，26（Volume 94，Num-ber 1）:1322-39.

[2]Zhang S，Jin Z，Zhu X.Missing Data Imputation by Utilizing Information Within Incomplete Instances[J].Journal of Systems&Software，2011，84（3）:452-459.

[3]Cover T，Hart P.Nearest Neighbor Pattern Classification[J].IEEE Transactions on Information Theory，1967，13（1）:21-27.

[4]Kang P，Cho S.Locally Linear Reconstruction for Instance-Based Learning[J].Pattern Recognition,2008,41（11）:3507-3518.

[5]Zhang L,Chen C,Bu J,et al.Active Learning Based on Locally Linear Reconstruction[J].IEEE Transactions on Pattern Analysis& Machine Intelligence,2011,33（10）:2026-38.

[6]Roweis S T,Saul L K.Nonlinear Dimensionality Reduction by Locally Linear Embedding[J].Science,2000,290（5500）:2323-6.

[7]UCI Repository of Machine Learning Datasets[DB/OL].http://archive.ics.uci.edu/-m.

Nearest Neighbor Filling Algorithm Based on Local Linear Reconstruction

WEN Hai-biao

（School of Computer and Information Engineering,Guangxi Teachers Education University，Nanning 530023）

Knearest neighbor filling algorithm for filling missing data,the average value of training sample attributes uses Kneighbor values as the filling value of KNNI algorithm,the value is far from the real values,an effective method is to sample attribute weighted Knearest neighbor average as filling value.How to determine the weights of Knearest neighbor samples is a hot research topic of KNNI algorithm.For this reason,proposes a method of local linear reconstruction for nearest neighbor filling.The method uses the Knearest neighbor sample to reconstruct the test sample.The experimental results show that the proposed algorithm is better than the KNNI algorithm,and the filling value is close to the real value.

溫海標(biāo)（1989-），男，廣東河源人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)

2017-03-24

2017-05-15

1007-1423（2017）15-0003-04

10.3969/j.issn.1007-1423.2017.15.001

Missing Values Filling;Reconstruction Technique;KNearest Neighbor;LLR