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

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

引言

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

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

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

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

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

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

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

1.2K-局部投影

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

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

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

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

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

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

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

1.3.2 特征選擇

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

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

1.3.3 順序選擇

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

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

1.3.4 極端情況

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

1.4算法的實現(xiàn)

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

2實驗結(jié)果及分析

2.1 實驗方法

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

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

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

3結(jié)語

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

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

參考文獻

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

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

[4]曄沙.數(shù)據(jù)缺失及其處理方法綜述[J].電子測試，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近鄰插補算法[J].中國衛(wèi)生統(tǒng)計，2019，36（05）：780-783.

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

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

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

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

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