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最近邻填补法的时间复杂度较高，很难应用于处理样本数量大的数据集。