基于屬性相關(guān)性與特征選擇的K-近鄰缺失值順序填充算法

摘要：由于K-局部近鄰插補(bǔ)算法無(wú)法直接計(jì)算相關(guān)性，因此在插補(bǔ)時(shí)難以進(jìn)行特征選擇，提出一種基于屬性相關(guān)性的對(duì)于多維數(shù)據(jù)缺失按順序并進(jìn)行特征選擇的填充方法，在解決相關(guān)性計(jì)算的問(wèn)題同時(shí)提出了采用相關(guān)性進(jìn)行填充順序選擇。算法首先提取完整數(shù)據(jù)集或者投影計(jì)算距離相關(guān)性，并按照一定的方式按相關(guān)性從大到小進(jìn)行填充，保證在填充時(shí)不會(huì)因?yàn)樘卣鬟x擇出現(xiàn)參照數(shù)據(jù)集為空的情況，在填充時(shí)選擇大于相關(guān)性臨界點(diǎn)的特征在投影的基礎(chǔ)上進(jìn)行近鄰填充。實(shí)驗(yàn)分別在不同缺失率下計(jì)算該方法與其它算法的均方誤差結(jié)果，結(jié)果表明，該算法在填充效果上明顯優(yōu)于其它算法。

關(guān)鍵詞：距離相關(guān)性;特征選擇;順序插補(bǔ)

引言

數(shù)據(jù)缺失在現(xiàn)實(shí)中是一種非常常見(jiàn)的現(xiàn)象，它產(chǎn)生的原因可能是信息難以獲取或者是數(shù)據(jù)傳輸中發(fā)生錯(cuò)誤產(chǎn)生遺漏。數(shù)據(jù)缺失會(huì)導(dǎo)致模型難以建立，使決策分析無(wú)法達(dá)到好的效果。數(shù)據(jù)挖掘中預(yù)處理占最大比重，而預(yù)處理中最關(guān)鍵的就是對(duì)缺失數(shù)據(jù)的處理。

常用的處理方法有加權(quán)法、刪除法和插補(bǔ)法。加權(quán)法通過(guò)某些方法把權(quán)數(shù)從缺失單位上轉(zhuǎn)移到非缺失單位上，刪除法則是直接刪除存在缺失單位的樣本，直接得到一個(gè)完整的數(shù)據(jù)集。刪除法雖然簡(jiǎn)單，但當(dāng)缺失率比較高的時(shí)候可能會(huì)刪除較多的樣本，產(chǎn)生較多誤差，因此國(guó)內(nèi)外學(xué)者更希望采用其他方法來(lái)填補(bǔ)不完整數(shù)據(jù)，以保證數(shù)據(jù)的質(zhì)量，即插補(bǔ)法，插補(bǔ)法是用一個(gè)或者多個(gè)估計(jì)值來(lái)代替缺失值的方法，前后分為單值插補(bǔ)和多重插補(bǔ)，常用的單值插補(bǔ)有均值填充、回歸填充、冷卡填充和熱卡填充等。

K-近鄰填充（K-nearest neighbor imputation， KNNI）是一種比較典型的冷卡填充，它是Olga Troyanskaya提出的基于局部相似性的插補(bǔ)算法，它將完整數(shù)據(jù)集提取出來(lái)，缺失值的近鄰樣本將從完整數(shù)據(jù)集中提取，分類值采用眾數(shù)填充，連續(xù)值采用平均數(shù)填充，這種方法的填充效果極大程度上收到了缺失率的影響，當(dāng)缺失率極大時(shí)，完整數(shù)據(jù)集的樣本數(shù)量將會(huì)非常少，這意味著這種情況下得到的近鄰樣本實(shí)際上相似性并不高，這可能導(dǎo)致產(chǎn)生較大的誤差，在這個(gè)基礎(chǔ)上，楊日東、李琳等提出了基于局部K近鄰的填充算法，它并不直接提取完整數(shù)據(jù)集，而是在填充缺失值時(shí)，將當(dāng)前樣本的完整屬性投影出來(lái)，并根據(jù)屬性投影結(jié)果從數(shù)據(jù)集中提取完整數(shù)據(jù)集，這在缺失率較大的情況下極大地改善了K近鄰插補(bǔ)的缺陷，但以上都并未考慮過(guò)屬性相關(guān)性以及填充順序?qū)μ畛錅?zhǔn)確率的影響。劉春英提出了一種基于屬性依賴度的順序填充方法，利用填充樹(shù)按依賴度從大到小進(jìn)行填充。謝霖銓、趙楠等和張曉琴、王敏都采用了主成分分析法進(jìn)行二次插補(bǔ)。現(xiàn)有的將相關(guān)性應(yīng)用到算法中的方法很多，但對(duì)于填充順序進(jìn)行處理的方法卻相對(duì)較少，本文將通過(guò)距離相關(guān)性研究填充順序與特征選擇在提升K-近鄰填充準(zhǔn)確率的能力。

1相關(guān)概念與原理

距離相關(guān)性（Distance Correlation）

皮爾遜相關(guān)系數(shù)常被用于度量?jī)蓚€(gè)變量之間的線性相關(guān)程度，兩個(gè)變量必須服從正態(tài)分布的假設(shè)，對(duì)于非線性關(guān)系無(wú)法進(jìn)行測(cè)量，即pearson相關(guān)系數(shù)為0時(shí)，兩個(gè)變量不一定是獨(dú)立的，自然界中的變量仍有大部分是非線性關(guān)系，而距離相關(guān)系數(shù)能很好地克服這個(gè)缺點(diǎn)，距離相關(guān)系數(shù)為0時(shí)，我們可以說(shuō)這兩個(gè)變量一定是獨(dú)立的。王黎明、吳香華等對(duì)比了皮爾遜相關(guān)系數(shù)、秩相關(guān)系數(shù)、距離相關(guān)性的利弊，最終采用距離相關(guān)系數(shù)來(lái)衡量預(yù)報(bào)因子和PM2.5之間的相關(guān)性。

研究變量 和 的獨(dú)立性，記為 。當(dāng) 時(shí)， 和 相互獨(dú)立; 越大，代表 和 的相關(guān)性越強(qiáng)。設(shè) 是總體 的隨機(jī)樣本， Székely等 （2008） 定義兩隨機(jī)變量的 和 的DC樣本估計(jì)值為

1.2K-局部投影

傳統(tǒng)K-近鄰填充在缺失率較大的時(shí)候可能導(dǎo)致完整數(shù)據(jù)集的樣本數(shù)量過(guò)小或者為空，填充時(shí)難以找到真正的近鄰，K-局部近鄰插補(bǔ)針對(duì)這個(gè)缺點(diǎn)做了改進(jìn)，使能夠參考的完整數(shù)據(jù)集更多。

K-局部近鄰插補(bǔ)中，投影是其中最關(guān)鍵的部分。若樣本 在屬性 上的值是缺失值，對(duì)于 在數(shù)據(jù)集T上投影的完整數(shù)據(jù)子集為TC，其中 ，任意 對(duì)應(yīng)的TC都是不同的。例如表1來(lái)說(shuō)，如果需要對(duì)數(shù)據(jù)aB進(jìn)行填充，那么缺失屬性集 ，完整數(shù)據(jù)子集 ，近鄰樣本則在TC中取舍。而對(duì)于傳統(tǒng)K-近鄰填充，完整數(shù)據(jù)集 。

1.3基于屬性相關(guān)性與特征選擇的K-近鄰缺失值順序填充算法

在K-局部近鄰插補(bǔ)中，插補(bǔ)從樣本中缺失值最多、屬性中缺失最少的數(shù)據(jù)開(kāi)始，這說(shuō)明算法的插補(bǔ)順序完全是由數(shù)據(jù)的缺失分布確定的，并且在計(jì)算樣本相似度時(shí)，也未曾考慮屬性之間的依賴程度，這可能導(dǎo)致相關(guān)性不高的屬性介入相似度計(jì)算，使計(jì)算出的近鄰是相似度不高的偽近鄰。如果要在該算法基礎(chǔ)上將相關(guān)性計(jì)算與它結(jié)合，有缺失值的數(shù)據(jù)集會(huì)無(wú)法進(jìn)行相關(guān)性的計(jì)算，若在對(duì)每個(gè)缺失值做相似度計(jì)算前計(jì)算屬性的相關(guān)性再進(jìn)行屬性篩選，這將極大地增加算法的運(yùn)行時(shí)間與復(fù)雜度。因此本文將K-近鄰插補(bǔ)和K-局部近鄰插補(bǔ)兩種算法結(jié)合后進(jìn)行改進(jìn)，使屬性相關(guān)性能夠同時(shí)對(duì)填充順序和特征選擇作出干預(yù)，同時(shí)最小化相關(guān)性計(jì)算、順序填充和特征選擇的運(yùn)算時(shí)間代價(jià)。

1.3.1 屬性相關(guān)性計(jì)算

K-近鄰插補(bǔ)的優(yōu)點(diǎn)在于它直接篩選出沒(méi)有缺失值的完整數(shù)據(jù)子集，所有插補(bǔ)計(jì)算都在這個(gè)完整數(shù)據(jù)子集上進(jìn)行，因此它十分簡(jiǎn)便，計(jì)算速度也很快。由于不存在缺失值，距離相關(guān)性也可以在完整數(shù)據(jù)子集上很方便地計(jì)算出來(lái)。但K-近鄰插補(bǔ)的缺點(diǎn)在于，當(dāng)缺失率較大時(shí)，無(wú)法找到完整數(shù)據(jù)子集或者子集容量太小無(wú)法進(jìn)行計(jì)算，此時(shí)將屬性兩兩篩選完整子集進(jìn)行相關(guān)性計(jì)算，最終計(jì)算出屬性相關(guān)性矩陣C。

在數(shù)據(jù)集 中，屬性集 的數(shù)量為 ， 表示標(biāo)簽列的數(shù)量，樣本數(shù)量為 ，樣本中存在缺失值的屬性集為 ，該數(shù)據(jù)集相關(guān)性矩陣為 。 變量 的距離相關(guān)性， ，因此 為軸對(duì)稱矩陣，其中 。當(dāng)缺失率較小、通過(guò)刪除法得到的完整數(shù)據(jù)子集 的樣本數(shù)量i'占數(shù)據(jù)集T樣本數(shù)量i的比例≥一個(gè)給定的 假設(shè)值時(shí)，直接使用完整數(shù)據(jù)子集通過(guò)式（1）計(jì)算相關(guān)性矩陣 ;當(dāng)缺失率較大，可能導(dǎo)致比率 時(shí)，通過(guò)對(duì)數(shù)據(jù)集 的屬性列 作刪除法，將得到的子集 通過(guò)式（1）計(jì)算相關(guān)性矩陣 。

1.3.2 特征選擇

在進(jìn)行插補(bǔ)時(shí)，如果采用全部的屬性集做近鄰插補(bǔ)，某些屬性與待填充數(shù)據(jù)的屬性相關(guān)性較小或者是相互獨(dú)立的情況下，無(wú)論是計(jì)算相似度還是近鄰填充都會(huì)扭曲近鄰分布，降低插補(bǔ)的準(zhǔn)確率，因此需要根據(jù)相關(guān)性剔除參照屬性中相關(guān)性過(guò)低的屬性。參照屬性指的是對(duì)于待插補(bǔ)值選出的用于計(jì)算近鄰的完整數(shù)據(jù)集的屬性，參照集是該完整數(shù)據(jù)集。對(duì)于待插補(bǔ)值 ，首先通過(guò)投影得到參照數(shù)據(jù)集D，其中屬性集為 ，設(shè)定相關(guān)性臨界點(diǎn)Cr，當(dāng) 中的屬性在相關(guān)性矩陣 中的屬性 列中的對(duì)應(yīng)值小于 時(shí)將剔除該屬性列。

當(dāng) 時(shí)，算法不做特征處理，相當(dāng)于有排序的K-局部近鄰插補(bǔ); 時(shí)，表示只有強(qiáng)相關(guān)的屬性才能進(jìn)行近鄰計(jì)算，此時(shí)將無(wú)法進(jìn)行填補(bǔ)運(yùn)算。經(jīng)過(guò)大量實(shí)驗(yàn)， 的取值在0.6左右表現(xiàn)為最好。

1.3.3 順序選擇

由于本文針對(duì)的是屬性中的缺失值插補(bǔ)，而標(biāo)簽中的數(shù)據(jù)是完整的，因此當(dāng)標(biāo)簽列作為參照屬性時(shí)，不會(huì)減少參照集的樣本數(shù)量，因此當(dāng)按照與標(biāo)簽的相關(guān)性從大到小的順序進(jìn)行插補(bǔ)能得到較多的參照樣本數(shù)量，在極限情況下與當(dāng)前屬性的相關(guān)性只有標(biāo)簽列達(dá)到臨界點(diǎn)要求時(shí)，不會(huì)出現(xiàn)參照集太小或者為空的情況。

選擇第二個(gè)填充列時(shí)，選擇 中使值最大的 作為當(dāng)前填充列 ，以此類推，直到填充完畢。

1.3.4 極端情況

當(dāng)數(shù)據(jù)集的缺失率較大時(shí)，存在一種情況，即選擇的填充列 與其它屬性列的相關(guān)性并不大，甚至小于 ，該列在特征選擇上會(huì)刪除所有的參照集的屬性，導(dǎo)致無(wú)法進(jìn)行插補(bǔ)。對(duì)于這種情況，本文作如下設(shè)計(jì)：對(duì)于當(dāng)前設(shè)定的相關(guān)性臨界點(diǎn) ，如果在填充時(shí)由于 比較高導(dǎo)致參照集為空，那么將 減去一定的值，直到使參照集非空，然后在下一個(gè)缺失值填補(bǔ)時(shí)返回原設(shè)定的 值。

1.4算法的實(shí)現(xiàn)

基于屬性相關(guān)性與特征選擇的K-近鄰缺失值順序填充算法流程如圖1所示。

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

2.1 實(shí)驗(yàn)方法

為了驗(yàn)證算法在真實(shí)情況下的有效性，進(jìn)行了仿真實(shí)驗(yàn)。從公開(kāi)數(shù)據(jù)集UCI上提取Breast、Slump、Real Estate、Yacht4個(gè)完整數(shù)據(jù)集，隨機(jī)在屬性中分別生成5%、10%、15%、20%、25%、30%的缺失值，分別采用本文提出的方法和K-近鄰插補(bǔ)法、K-局部近鄰插補(bǔ)方法在4個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。

由于數(shù)據(jù)量綱的不同，將所有數(shù)據(jù)集進(jìn)行歸一化，實(shí)驗(yàn)中采用的是Min-Max標(biāo)準(zhǔn)化（Min-Max Normalization），將原始數(shù)據(jù)通過(guò)線性變換轉(zhuǎn)映射到[0，1]之間，公式如下：

從結(jié)果來(lái)看，改進(jìn)后的算法明顯優(yōu)于K-局部近鄰算法，并且具有一定的穩(wěn)定性，并且在大部分的情況下隨著缺失率的增加MSE的增長(zhǎng)速率明顯小于LKNN。兩種算法在Yacht上的MSE的差要比其他三個(gè)數(shù)據(jù)集上小一些，這是由于不同數(shù)據(jù)集中的屬性與屬性、屬性與標(biāo)簽之間的相關(guān)性都是不同的，可以看出Yacht數(shù)據(jù)集的相關(guān)性比較強(qiáng)，導(dǎo)致即使做了特征選擇，剔除的屬性也沒(méi)有其他三個(gè)數(shù)據(jù)集多，使算法和K-局部近鄰方法更相當(dāng)一些。

3結(jié)語(yǔ)

為解決特征選擇無(wú)法直接在KNN局布近鄰插補(bǔ)法上使用的問(wèn)題，本文采用K近鄰插補(bǔ)算法中提取完整數(shù)據(jù)集的方法計(jì)算距離相關(guān)性，并采用距離相關(guān)性同時(shí)對(duì)插補(bǔ)順序和特征選擇進(jìn)行了融合改進(jìn)，通過(guò)觀察仿真實(shí)驗(yàn)結(jié)果，可知基于屬性相關(guān)性與特征選擇的K-近鄰缺失值順序填充算法在填充準(zhǔn)確率上明顯優(yōu)于K-局部近鄰插補(bǔ)算法。

但算法也有不足之處，在屬性值較多的情況下，頻繁進(jìn)行特征選擇將大量提高算法的時(shí)間復(fù)雜度，在未來(lái)的研究中將會(huì)對(duì)這一不足之處進(jìn)行優(yōu)化。

參考文獻(xiàn)

[1]LUKASZ A K， PETR M. A survey of knowledge discovery and data mining process models[J]. Knowledge Engineering Review， 2006， 21（1）：1-24.

[2]鄧建新，單路寶，賀德強(qiáng)，唐銳.缺失數(shù)據(jù)的處理方法及其發(fā)展趨勢(shì)[J].統(tǒng)計(jì)與決策，2019，35（23）：28-34.

[3]王敏. 基于成分?jǐn)?shù)據(jù)的缺失值補(bǔ)全方法研究[D].山西大學(xué)，2016.

[4]曄沙.數(shù)據(jù)缺失及其處理方法綜述[J].電子測(cè)試，2017（18）：65-67+60.

[5] TROYANSKAYA O， CANTOR M， SHERLOCK G， et al. Missing value estimation methods for DNA microarrays. Bioinformatics， 2001， 17（6）： 520-525.

[6]楊日東，李琳，陳秋源，周毅.LKNNI：一種局部K近鄰插補(bǔ)算法[J].中國(guó)衛(wèi)生統(tǒng)計(jì)，2019，36（05）：780-783.

[7]劉春英.基于屬性依賴度的缺失值順序填充算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（09）：215-218.

[8]謝霖銓，趙楠，徐浩，畢永朋.基于屬性相關(guān)性的K N N近鄰填補(bǔ)算法改進(jìn)[J].江西理工大學(xué)學(xué)報(bào)，2019，40（01）：95-101.

[9]張曉琴，王敏.基于主成分分析的成分?jǐn)?shù)據(jù)缺失值插補(bǔ)法[J].應(yīng)用概率統(tǒng)計(jì)，2016，32（01）：101-110.

[10]王黎明，吳香華，趙天良，程國(guó)勝，張祥志，湯莉莉，賈夢(mèng)唯，陳煜升.基于距離相關(guān)系數(shù)和支持向量機(jī)回歸的PM_（2.5）濃度滾動(dòng)統(tǒng)計(jì)預(yù)報(bào)方案[J].環(huán)境科學(xué)學(xué)報(bào)，2017，37（04）：1268-1276.

作者簡(jiǎn)介：唐晗，女，1993年11月，漢，江西省吉安市，工學(xué)學(xué)士，江西應(yīng)用工程職業(yè)學(xué)院，數(shù)據(jù)挖掘。