3.1.3　K最近鄰填補法

K最近鄰填補法是一種基于K最近鄰算法實現的缺失值填補方法。K最近鄰算法是機器學習領域基本的分類方法，針對各個待分類樣本，找到與該樣本距離最近的K個樣本，并將多數近鄰樣本所屬類別作為分類結果。K最近鄰填補法參照其思路，尋找與各不完整樣本距離最近或相關度最高的K個完整樣本，并將各完整樣本現有值的加權平均作為填補值。該方法包含兩個關鍵步驟，即選擇近鄰樣本和計算近鄰樣本權重。下面對二者依次進行說明。

1.選擇近鄰樣本

選擇近鄰樣本是指針對各不完整樣本，通過計算與其他樣本的距離或相關性，找到與該樣本距離最近的K個完整樣本。閔可夫斯基距離是該方法中常用的距離度量指標。對于不完整數據集X，基于式（3-1）所定義的數據缺失情況，對于樣本x_i、x_k，在計算閔可夫斯基距離前應先為樣本中數據缺失的位置添加一個占位數值，使該位置的數值能夠參與運算，二者的閔可夫斯基距離如式（3-8）所示：

式（3-8）中，p為閔可夫斯基距離公式的參數。當p=2時，閔可夫斯基距離即轉化為歐式距離，記為d_Euc(x_i,x_k)。通常稱基于不完整樣本計算的歐式距離為局部距離（Partial Distance），可記為d_Part(x_i,x_k)。

閔可夫斯基距離僅適用于處理數值型屬性，但現實應用時，數據集中經常同時存在數值型屬性和非數值型屬性。灰色關聯分析法是一種能夠同時處理上述兩種類型屬性的樣本相關性度量方法，其基本思想是通過比較兩樣本在各屬性的取值來度量其相似程度^[4]。該方法通常包含三個階段：選擇屬性、計算灰色相關系數（Gray Relational Coeff icient，GRC）、計算灰色相關度（Gray Relational Grade，GRG）。對于不完整數據集X，假設第i個樣本x_i為不完整樣本，第一階段為屬性選擇階段，通常選擇該樣本的完整屬性參與后續計算，此處采用J_co,i表示該樣本完整屬性的下標集合。第二階段為計算該不完整樣本與各完整樣本的灰色相關系數。記數據集X中完整樣本的集合為X_co，若數據集X中的第k個樣本為完整樣本，則樣本x_i與x_k在第j個屬性的灰色相關系數如式（3-9）所示：

式（3-9）中，ρ∈[0,1]被稱為分辨系數（Distinguishing Coeff icient），其值越小，表示灰色相關系數的數值越分散，通常可取ρ=0.5，也可根據實際情況進行調整。根據式（3-9）可依次計算樣本x_i各完整屬性與樣本x_k的灰色相關系數。第三階段為計算兩樣本各屬性灰色相關系數的均值，并將其作為樣本間的灰色相關度，如式（3-10）所示：

式（3-10）中，|J_co,i|表示樣本x_i中完整屬性的數量。依次計算樣本x_i與數據集X中各完整樣本的灰色相關度，選擇灰色相關度最大的K個樣本作為其近鄰樣本。在式（3-9）、式（3-10）中，數值型屬性和非數值型屬性被同等對待，因此灰色關聯分析法能夠有效處理包含上述兩種類型屬性的不完整數據集。

真實數據集中通常存在部分噪聲樣本，若選擇的近鄰樣本中包含噪聲樣本，將會影響填補結果對真實值的還原度。消除近鄰噪聲的K最近鄰（Elimina_te Neighbor Noise-K Nearest Neighbor，ENN-KNN）填補法根據投票思想度量各近鄰樣本為噪聲樣本的可能性，并剔除可能性大的噪聲近鄰樣本，從而消除其對缺失值填補產生的影響^[5]。假設數據集X中第i個樣本x_i為不完整樣本，基于局部距離為其選擇K個近鄰樣本，并構成集合N(x_i)。對于所有x_nei∈N(x_i)，獲取x_nei的K個近鄰樣本，并將得到的全部樣本構成集合NN(x_i)，稱其為x_i的二次近鄰集合，其中樣本記為x_p，如圖3-2所示。

圖3-2　ENN-KNN方法示意圖

ENN-KNN填補法通過雙向投票的方式計算近鄰集合N(x_i)中各樣本為非噪聲樣本的可靠性，首先基于近鄰集合N(x_i)對二次近鄰集合NN(x_i)中的各樣本進行正向投票，接著利用二次近鄰集合NN(x_i)對近鄰集合N(x_i)的樣本進行逆向投票。

正向投票期間，N(x_i)中的樣本x_nei為自身近鄰樣本投票，投票時的權重如式（3-11）所示：

式（3-11）中，d_Part(x_i,x_nei)表示樣本間的局部距離。

由于在NN(x_i)內，某個樣本x_p可能同時位于N(x_i)中多個樣本的近鄰集合內，x_p所得的投票結果可能是多個權重值的累加，其投票結果的計算規則如式（3-12）所示：

式（3-12）中，N(x_nei)表示樣本x_nei的近鄰樣本所構成的集合，f(x_p,N(x_nei))用于判斷x_p是否隸屬于N(x_nei)。若x_p∈N(x_nei)，則函數值為1；否則為0。

反向投票期間，對于x_i的近鄰樣本x_nei，根據N(x_nei)中樣本的投票結果計算x_nei的可靠性，計算方法如式（3-13）所示：

最后，基于x_i各近鄰樣本的可靠性剔除其中的噪聲樣本，判斷噪聲樣本的標準如式（3-14）所示：

式（3-14）中，V_max表示可靠性最高的近鄰樣本獲得的可靠性評分，θ∈[0,1]被稱為淘汰系數。當θ=0時，ENN-KNN填補法相當于傳統的K最近鄰填補法；當θ=1時，ENNKNN填補法相當于僅根據可靠性最高的近鄰樣本填補缺失值。

2.計算近鄰樣本權重

計算近鄰樣本權重是指計算各近鄰樣本在缺失值填補中的貢獻程度，從而基于近鄰樣本的現有值和其權重獲取填補結果。傳統的K最近鄰填補法采用等權重的方式計算填補值，實際上等同于將各近鄰樣本現有值的均值作為填補結果。該方法忽視了近鄰樣本在分布位置的差異性，沒有對近鄰樣本的信息進行充分利用，在一定程度上影響了填補精度。

一種常見的思路是基于近鄰樣本與不完整樣本的局部距離計算其在填補過程中的權重，計算方法如式（3-11）所示。可見，該方法將樣本間距離的倒數作為近鄰樣本權重，近鄰樣本與不完整樣本距離越遠，其權重越小。此方法計算權重的方式較為直觀、易于理解，且應用方便，但權重計算方式不夠靈活，對樣本間的位置關系挖掘不夠充分，限制了其填補精度及應用范圍。

為了使樣本權重的求解更加靈活，適用范圍更廣，可將核函數引入權重計算過程^[6]。核函數是一類用于處理線性不可分問題的函數，蘊含著從低維空間到高維空間的映射，該映射能夠使低維空間中線性不可分的兩類樣本在高維空間中線性可分。常用的核函數包括多項式核（Polynomial Kernel）函數、高斯核（Gauss Kernel）函數、S型核（Sigmoid Kernel）函數。S型核函數的函數值和輸入數值呈正相關，而高斯核函數的取值與輸入數值呈負相關。為了使權重隨樣本間距離的增加而減小，通常采用高斯核函數進行權重計算。高斯核函數又稱徑向基核（Radial Basis Function Kernel，RBF Kernel）函數，基于不完整數據集X中的樣本x_i、x_k計算的高斯核函數如（3-15）式所示：

式（3-15）中，σ>0為高斯函數的帶寬（Width），其值越大，映射后的空間維度越低。當σ趨近于0時，理論上可將原始空間的樣本映射到無窮維的空間。

核函數的引入能夠使K最近鄰填補法在計算權重時更加充分地利用近鄰樣本位置信息，有助于提升該方法的填補精度。假設數據集X中第i個樣本x_i為不完整樣本，記其近鄰樣本構成集合N(x_i)，則對于x_nei∈N(x_i)，引入核函數的權重如式（3-16）所示：

式（3-16）中，λ>0是權重參數。λ越小，權重隨樣本間距離的增加而減小的速度就越快。當λ趨近于正無窮時，x_i的所有近鄰樣本具有相同的權重。此外，通過調整權重參數λ，能夠使K最近鄰填補法在不同K值下取得良好的填補效果，提高了該方法的魯棒性。

相比于均值填補法和熱平臺填補法，K最近鄰填補法正受到越來越多的關注，其理論體系較為成熟，已廣泛應用于工業、交通、醫療等多個領域。但由于為每個不完整樣本尋找近鄰樣本的過程都需遍歷全體完整樣本，導致K最近鄰填補法的時間復雜度較高，很難應用于處理樣本數量大的數據集。