Adaptive k-Nearest Neighbor Missing Value Imputation Method Based on Probability Density
-
摘要:
基于k近邻的缺失值填充方法通常使用样本间的距离来度量样本的相似性，在计算距离时，没有区分样本各属性的权重，即所有属性对距离的贡献是一样的。然而，在非均匀分布的不平衡数据集中，样本的异质性往往体现在取值不常见的属性上，即样本之间的相似性受属性取值概率影响，此时用传统的距离公式来度量相似性是不够准确的。因此，文章针对非均匀分布的不平衡数据集提出了一种自适应k近邻缺失值填充方法(AkNNI)：首先，引入属性的概率密度，动态调整各个属性的重要性，凸显稀疏值与缩小频繁值在距离计算上的贡献，从而更好地表达样本的异质性以及捕捉样本之间的相似性；然后，针对高缺失率下数据集中完备样本稀少的情况，综合考虑了样本的相似性和完整性，设计了新的k近邻的选择流程。实验选取了6个非均匀分布数据集，对比了AkNNI方法与其他5种经典填充方法的填充效果，验证了填充后的数据集在k近邻分类器的分类效果，深入探索了3种评估指标的相互关系。实验结果表明AkNNI方法具有更高的填充准确度和分类准确度：在6种缺失值填充算法中，AkNNI方法在各个数据集上取得的平均RMSE最低、平均皮尔逊相关系数最高以及平均分类准确率最高。同时，在高缺失率下，AkNNI方法在各个数据集上仍能保持较低的RMSE、较高的皮尔逊相关系数和较高的分类准确度。
Abstract:Missing value imputation methods based on k-nearest neighbor typically use the distance between samples to measure the similarity of the samples and do not differentiate the weights of the attributes when calculating the distance, i.e., all attributes contribute equally to the distance. However, in a non-uniform distributed imba-lanced dataset, the heterogeneity of the samples is often reflected in the attributes with uncommon values, and the similarity between the samples is affected by the probability of the attributes' values, and the similarity calculated by traditional distance formula is not accurate enough at this time. Therefore, an adaptive k-nearest neighbor missing value imputation method named AkNNI is proposed in the article for non-uniformly distributed imbalanced datasets. Firstly, the probability density of the attributes is introduced to dynamically adjust the importance of each attribute, highlighting the contribution of sparse values and reducing the contribution of frequent values in the calculation of distances, so as to better express the heterogeneity of samples as well as capture the similarity between samples; then, for the case of scarcity of complete samples in the dataset under high missing rates, the new selection process of k-nearest neighbors is designed by considering the sample similarity and completeness together. Experiments were conducted to select six non-uniformly distributed datasets, compare the imputation effect of the AkNNI method with other five classical imputation methods, verify the classification effect of the imputed datasets in the k-nearest neighbor classifier, and also explore the interrelationships of the three evaluation metrics in depth. The experimental results demonstrate that AkNNI method has higher imputation accuracy and classification accuracy: among the six missing value imputation methods, the AkNNI method achieves the lowest average RMSE, the highest average Pearson correlation coefficient, and the highest average classification accuracy on each dataset. Meanwhile, AkNNI still maintains lower RMSE, higher Pearson's correlation coefficient, and higher classification accuracy at high missing rates on each dataset.
-
随着群智协同、社交化教学系统等方面研究的逐渐深入，协同智能与智慧教育正迅速融入教育体系，由此带来的教育数据的爆发性增长为深入理解学生学习过程、提升教学效果提供了巨大的机会。然而，随着数据量的不断增加，数据集的质量成为制约教育研究和实践的一个重要瓶颈。当数据集出现缺失值时，数据的完整性不能得到保证，易导致数据质量受到影响[1]。此外，教育数据涉及多个维度，包括学科、年级和学生个体差异等，因此数据集通常具有高度的多样性和复杂性，导致数据集中普遍存在取值分布不均匀的特征，为填充缺失值增加了一定的困难。因此，对非均匀分布数据集实施合理有效的填充是十分必要和重要的[2]。
填充法分为基于统计学的和基于机器学习的两大类方法[1,3-4]。基于统计学的填充法中，常见的有均值填充法(Mean Imputation，MI)[5]、回归填充法(Regression Imputation，RI)[6]和链式方程多重插补法(Multiple Imputation by Chained Equations，MICE)[7]。其中，MI法通过属性的平均值来填充数值型属性的缺失值；RI法通过对特定样本的单个观测值建立回归模型，然后将样本的观测值作为输入，从而对缺失值进行预测并填充；MICE法首先使用多个相关属性来建立一系列回归模型，然后结合多个模型迭代地对缺失数据进行预测[5]。尽管基于统计学的填充方法在处理缺失值时各有优势，但也存在一定的局限性：MI法忽略了属性间的相关性，导致填充效果较差；RI法和MICE法考虑了属性间的相关性，填充效果相对较好，但都必须假设缺失值所在的属性与其他属性之间存在回归关系[8]。此外，在处理复杂的数据分布时，RI法使用单一属性建模，无法充分捕捉数据的潜在规律；MICE法由于对多个属性建模且需进行多轮填充，导致耗时较长。
基于机器学习的方法能够利用强大的学习算法，通过学习数据样本分布规律来生成更为准确的填充值，在一定程度上克服了统计学方法的局限性[5,9]。自TROYANSKAYA等[10]首次提出利用k近邻进行填充的方法(k Nearest Neighbor Imputation，kNNI)后，学者们围绕提升kNNI方法的性能展开了诸多研究。如：PAN等[11]采用互信息来衡量特征相关性，提出了一种特征加权灰色k近邻(Feature Weighted Grey k Nearest Neighbor，FWGkNN)填充算法；DATTA等[12]提出了一种结合k近邻和带特征加权的惩罚相异度量方法来处理缺失值问题；TSAI和CHANG[13]提出了一种两步算法，该算法结合了实例选择和缺失值填充，从数据集中过滤掉噪声数据，提高了分类器的分类性能；FAN等[14]提出了一种加权kNNI方法，使用欧氏距离倒数作为待填充样本的k近邻的权重，提高了分类准确率；CHENG等[15]提出了一种通过提升k近邻的纯度来提高缺失值填充性能的k近邻填充法。
然而，这些基于k近邻的缺失值填充方法在应用于非均匀分布的不平衡数据集时仍存在一些不足：(1)通过传统的距离公式计算出的样本相似度不够准确，不能体现样本间真实的相似性。因为在非均匀分布特征明显的数据集中，各属性取值的概率跨度非常大，而样本的异质性往往体现在取值不常见(即概率密度低)的属性上，导致了属性取值对度量样本间距离的贡献度是存在差异的。然而，传统的距离计算公式却未能体现这种差异，以常见的欧式距离公式为例，所有属性均被赋予相同的权重，此时计算出的距离显然不能反映真实的相似性。而且，后续基于距离的加权策略，如主流的加权k近邻填充法(Weighted k Nearest Neighbor Imputation，WkNN)[14]中的加权策略，均严重依赖于相似性计算的准确性。因此，这种传统距离度量产生的偏差将会进一步对加权策略的权值造成严重影响。(2)在k近邻的选择上，已有的方法[10-11,13-14]仅以完整样本作为候选集，忽略了缺失率的影响。然而，参数k依赖于候选集的样本数量。当数据集的缺失率较高时，可能导致候选集中的样本不足，从而限制了参数k取值的取值上限。而且，由于候选集不包含带缺失值的样本，导致无法深入挖掘不完整样本中的可用信息，也会在一定程度上影响数据分析的效果。
为了解决上述问题，本文针对非均匀分布的不平衡数据集，提出了一种新的k近邻缺失值填充方法，称为自适应k近邻缺失值填充方法(Adaptive k Nearest Neighbor Imputation，AkNNI)。该方法在相似性度量上考虑了属性取值概率对距离的影响，借助属性概率密度对距离进行适当的放缩，从而自适应地调整各个属性对距离计算的贡献。同时，针对非均匀分布数据集在高缺失率且完整样本稀缺的情景，设计一种新的k近邻选择流程，采用带缺失值的样本作为近邻样本候选集，综合考虑了样本的完整性和相似性。最后，选择了4个具有非均匀分布特性的标准数据集，同时人工构造了2个典型的非均匀分布的数据集，对比了AkNNI算法与其他5种经典填充方法的填充准确度，并进一步验证填充后的数据集在k近邻分类器的分类效果。
1. 自适应k近邻缺失值填充方法
k近邻缺失值填充方法涉及2个主要步骤：一是通过距离来度量样本间相似性，以确定待填充样本的最近邻；二是利用最近邻样本，通过取均值或取众数等策略对缺失值进行填充[10,14]。因此，本文针对上述2个步骤进行了改进，提出了自适应k近邻缺失值填充方法。具体改进包括：(1)基于自适应欧氏距离的相似性计算；(2)改进的k近邻选择流程。本章首先以欧氏距离为例，分析了在非均匀分布数据集下传统基于距离度量相似性方法存在的问题；进而，通过引入概率密度来调整属性对距离的贡献，提出了自适应欧氏距离，以提高度量样本相似性的准确度；最后，针对数据集中完整样本较少的情况，提出了一种优化的k近邻选择流程。
1.1 传统基于距离度量相似性方法存在的问题
在使用距离来度量样本相似性的方法中，传统的距离计算公式没有考虑属性取值对距离的贡献，尤其在处理非均匀分布特征明显的数据集时，由该类公式得到的距离无法准确地度量样本之间真实的相似性。本文以欧氏距离为例展开讨论和说明。假设给定以下场景，样本分布如图 1所示，其中包含负类样本a、未知分类样本b和正类样本c。使用欧氏距离对3个样本的相似性进行度量，未知分类样本b与负类样本a之间的距离记为dist(b, a)，未知分类样本b与正类样本c之间的距离记为dist(b, c)，显然dist(b, c)=dist(b, a)，但实际上未知分类样本b与正类样本c的相似性异于未知分类样本b与负类样本a的相似性。因为未知分类样本b与正类样本c在x属性的取值均落在概率密度比较低的数值区间，而负类样本a在x属性的取值落在概率密度比较高的数值区间，又样本b、c、a在y属性上取值的概率密度相同，因此，未知分类样本b与正类样本c更相似。
![]()
图 1 正、负类样本和未知分类样本分布Figure 1. Sample distributions for positive, negative and unknown class samples通过概率分布曲线可以进一步解释dist(b, a)、dist(b, c)所表达的相似性与样本实际相似性之间的差异，从而理解属性取值概率对距离度量的影响。图 2给出了混合(正类和负类)、正类、负类样本在x属性上的概率密度。从概率分布的角度上看，假定dist(b,c)=k1σ1,dist(b,a)=k2σ2，其中σ1、σ2分别表示正、负类样本的标准差，k1和k2为常数，由图 2可知σ1>σ2，而欧氏距离dist(b, c)=dist(b, a)，则k1 < k2，故未知分类样本b被认为与正类样本c是同类的。可见，在非均匀的不平衡数据集上，基于距离的相似性计算应该考虑属性的概率密度，因为不同概率的属性取值对距离的贡献是不同的。
![]()
图 2 混合、正类、负类样本在x属性上的概率密度Figure 2. Probability densities of mixed samples, positive class samples, and negative class samples over the x attri-bute1.2 自适应欧氏距离
为了更准确地度量非均匀分布数据集中样本间的相似性，本文在计算距离时，引入了样本属性的概率密度，构造了自适应欧氏距离的计算公式。由于离散型随机变量并不存在概率密度函数，因此自适应欧式距离只适合计算数值型(连续型)的属性列。假定有m维数值型属性的样本xi和样本xj，即xi= (xi,1,xi,2,⋯,xi,m),xj=(xj,1,xj,2,⋯,xj,m)，样本xi与样本xj之间的自适应欧氏距离的计算公式如下：
di,j=1θ∗√∑mt=1((xi,t−xj,t)2∗wt)k。 (1) 式(1)中各参数的说明如下：
(1) 权重项wt的计算公式为
wt=pdft(xi,t)∗pdft(xj,t)∗S(xi,t)∗S(xj,t), 其中：pdft表示t属性的概率密度函数，pdft(xi, t)表示样本xi的t属性值为xi, t的概率密度函数值；S(x)取值为0或1，用于表示属性值是否缺失，当S(x)=0时表示属性值缺失，当S(x)=1时表示属性值存在。权重项wt的作用是对数值分布密集的区域进行拉伸，对数值分布比较稀疏的区域进行压缩[16]，其作用为消除方差影响。因此，使用自适应欧氏距离无需对数据进行标准化预处理。
(2) k为样本xi和样本xj共同非缺失属性的数目，其计算公式为
k=m∑t=1S(xi,t)∗S(xj,t)。 (3) θ的计算公式为
θ=m∑t=1(α+β)∗S(xj,t)∗S(xi,t), 其中：α为调节不均匀部分影响因子(常量)，β=e−pdf2t(xj,t)/(2σ2), 若α < β则表示在距离计算时不均匀属性部分占主导；β中的σ=k/m*δ，其中δ表示概率密度敏感阈值，默认为0.1。β依据属性取值概率对距离进行放缩，利用指数在偏离均值较大时迅速衰减的特性来表达属性内取值不均匀的差异性对距离的影响。t属性取值对应的概率密度(pdft(xj, t))越小，β越大，反之β越小。另外，随着概率密度低的属性数量的增加，θ值增大，导致距离被缩小的比例变大，从而提高了该属性的重要性，反之降低了重要性。当α=1，δ=0.1时，t属性列的距离缩放权值函数可表示为yt=1+e−pdf2t(xj,t)/(2σ2)。如图 3所示，随着t属性的概率密度pdft(xj, t)增大，t属性的贡献度(即距离缩放权值)降低，且σ取值越小时，t属性的贡献度的下降幅度越大。
![]()
图 3 t属性的概率密度与距离缩放权值的关系Figure 3. Relationship between probability density for attribute t and distance scaling weights1.3 改进的k近邻选择流程
在k近邻选择流程上，已有的基于k近邻的填充方法大都忽略了高缺失率可能造成的完整样本数目不足的影响，既限制了参数k取值的上限，又没有深入挖掘不完整样本的可用信息，从而造成了资源浪费。本文针对数据集中完整样本稀缺的情况，设计了一种新的k近邻选择流程(图 4)。具体步骤如下：首先，从数据集中选取与待填充样本距离最近的前m个样本；然后，进一步筛选这m个样本，以确保所选的k个近邻样本能够尽可能覆盖待填充样本的缺失属性；最后，使用k个最优近邻样本填充待填充样本的缺失值。迭代上述过程，直至待填充样本的所有缺失值被填充完毕或者循环达到最大轮数。新的k近邻选择流程不仅考虑了更为准确的样本相似性，还考虑了样本的完整性，从而有效地提高了缺失值填充的准确性。
2. 实验与结果分析
一般地，不完整数据集是从完整数据集中通过人工选择缺失率的方式构造而成的。本文对不完整数据集进行填充处理，并对填充后的数据实施分类任务，通过分类效果来进一步验证填充效果[3,17]。因此，为了综合评估AkNNI方法，实验包括两部分：一是填充评估实验，二是分类评估实验。实验中共用到了6个完整数据集，包括2个人工数据集和4个标准数据集，通过由小到大依次改变缺失率的方式构造得到多组缺失数据集。在填充评估实验中，使用AkNNI方法和其他5种缺失值填充方法分别对缺失数据进行填充，并用RMSE和皮尔逊相关系数2个指标来评估填充准确度；在分类实验中，采用了常见的k近邻分类器对上述填充后的数据集进行分类，比较其分类准确度。
2.1 不完整数据集的构造
在数据集上，通过对各属性采用混合高斯分布的方法，人工构造了2个典型的非均匀分布完整数据集D1000和D2000。此外，使用了4个具有非均匀分布特征的标准数据集(Pendigits[18]、Yeast[19]、Red wine quality[18]和Breast-cancer[12])。在2个人工数据集中，所有属性均为数值型，无分类标签属性。在4个标准数据集的所有属性中，除了最后一个属性是分类标签外，其他属性均为数值型。所有数据集的具体信息如表 1所示。
表 1 数据集的基本信息Table 1. Basic information of the datasets数据集 样本数目/条 属性数目/个 类/种 D1000 1 000 2 — D2000 2 000 15 — Pendigits 10 992 16 26 Yeast 1 484 8 10 Red wine quality 1 599 11 6 Breast-cancer 699 9 2 注：“—”表示无类别标签。 实验中，依据MAR(Missing at Random)缺失机制[11]对上述数据集进行缺失值模拟，依次构造了5种缺失率(10%、20%、30%、40%、50%)的不完整数据集。缺失率的计算公式[1]如下：
缺失率 = 缺失值数目 样本数目 ∗ 属性数目 ∗100% 。 (2) 对每个数据集，在每种缺失率下，均分别随机构造了10个不完整数据集来完成填充实验。因此，本实验总共构造了300个不完整数据集。
2.2 实验评估指标
在填充评估实验中，本文采用均方根误差[3]和皮尔逊相关系数[17]来衡量填充准确性。在分类评估实验中，本文采用分类准确率为评价指标。各评价指标的具体说明如下：
(1) 均方根误差(Root Mean Square Error，RMSE)：常用于将原始值与各种缺失值填充技术估计的填充值进行比较，是对平均误差的一种度量。其计算公式如下：
RMSE =√∑Ni=1(xobs −xmodel )2N, (3) 其中，xobs为原始值，xmodel为模型填充值, N为缺失值的个数。
(2) 皮尔逊相关系数: 用于衡量模型填充值与原始值之间的线性相关性以及模型填充值偏离平均值的程度，是从变化趋势来衡量填充后的属性列与原始值的属性列的一致性。某属性列的皮尔逊相关系数r的计算公式如下：
r=n∑i=1(xi−ˉx)(xmodel i−ˉxmodel )√n∑i=1(xi−ˉx)2n∑i=1(xmodel i−ˉxmodel )2, (4) 其中，xi、ximodel分别为该属性列第i个缺失值的原始值、模型填充值，ˉx,ˉxmodel 分别为该属性列所有原始值的平均值、所有模型填充值的平均值, n为该属性列的缺失值个数。有效的缺失值填充方法的皮尔逊相关系数应该接近1。
(3) 分类准确率。分类准确率是衡量分类结果好坏的标准。一般地，使用填充后的数据集来训练分类器，分类准确率越高，表明分类器对填充后的数据的分类效果越好，即填充的效果越好。
2.3 对比方法和实验设置
实验选择以下5种填充方法为对比方法：
(1) MI方法[5]：均值填充法。该方法利用属性的平均值来填充属性的缺失值。
(2) RI方法[6]：回归填充法。该方法假设缺失值与其他属性存在线性关系，通过线性回归模型来预测并填充缺失值。
(3) MICE方法[7]：链式方程多重插补法。该方法使用多个相关属性建立一系列回归模型，然后结合多个模型迭代地对缺失数据进行预测。
(4) kNNI方法[10]：k近邻填充法。该方法首先查找与待填充样本最相似的k个邻居样本，然后使用这些邻居样本的值来填充缺失数据。
(5) WkNNI方法[14]：加权k近邻填充法。该方法在kNNI方法的基础上发展而来，是一种加权k近邻填充法：通过对邻居样本赋予不同的权重，使得与待填充样本更相似的邻居样本对填充结果的贡献更大。
MICE方法的迭代轮数设定为10；kNNI方法和WkNNI方法均采用标准化欧氏距离，使用默认的近邻参数k=5；AkNNI方法使用默认的自适应欧氏距离参数(α=1、δ=0.1)和默认的近邻参数(k=5)。在分类实验中，使用了k近邻分类器，设定分类器参数k=5，训练集与测试集在各数据集中的比例为7 ∶ 3。
2.4 实验结果分析
2.4.1 填充效果分析
(1) 各缺失值填充方法在不同缺失率下填充效果的变化。由6种缺失填充方法在D1000、D2000、Pendigits、Yeast、Red wine quality、Breast-cancer数据集上的填充效果(图 5至图 10)可知：①随着缺失率的上升，各填充方法的填充准确度均呈下降趋势，表现为RMSE值的增加和皮尔逊相关系数的降低。其中，kNNI方法和WkNNI方法受缺失率影响最明显：当缺失率超过30%时，在Pendigits、Red wine quality、Breast-cancer数据集上，两者的填充效果出现剧烈的下滑。这表明在高缺失率情况下，kNNI方法和WkNNI方法在进行最近邻选择时面临候选集不足的困难，从而对其填充效果造成了负面影响。②与其他5种算法相比，在各个缺失率下，AkNNI方法都能够保持较低的RMSE值和较高的皮尔逊相关系数，这验证了其改进的k近邻选择流程的有效性。
![]()
图 5 6种缺失填充方法在不同缺失率的D1000数据集上的填充效果Figure 5. Imputation effects on the D1000 dataset with different missing ratios by six missing value imputation methods![]()
图 6 6种缺失填充方法在不同缺失率的D2000数据集上的填充效果Figure 6. Imputation effects on the D2000 dataset with different missing ratios by six missing value imputation methods![]()
图 7 6种缺失填充方法在不同缺失率的Pendigits数据集上的填充效果Figure 7. Imputation effects on the Pendigits dataset with different missing ratios by six missing value imputation methods![]()
图 8 6种缺失填充方法在不同缺失率的Yeast数据集上的填充效果Figure 8. Imputation effects on the Yeast dataset with different missing ratios by six missing value imputation methods![]()
图 9 6种缺失填充方法在不同缺失率的Red wine quality数据集上的填充效果Figure 9. Imputation effects on the Red wine quality dataset with different missing ratios by six missing value imputation methods![]()
图 10 6种缺失填充方法在不同缺失率的Breast-cancer数据集上的填充效果Figure 10. Imputation effects on the Breast-cancer dataset with different missing ratios by six missing value imputation methods(2) 各缺失值填充方法填充后的数据分布。特别地，通过对比填充前后的数据分布的一致性可以直观地看出填充效果。本文以缺失率为50%的人工数据集D1000为例，展示填充前后的数据分布。由结果(图 11和图 12)可知：RI方法和MICE方法假设属性间存在线性关系，这在非均匀分布的数据集上降低了其填充准确度，导致较差的填充效果；与kNNI方法和WkNNI方法相比，AkNNI方法(图 12A)能最大程度地保持原始数据分布的特性，所填充的值更接近原始值，这表明了自适应欧氏距离在提高填充效果方面的优越性。
![]()
图 11 完整的D1000数据集的原始数据分布Figure 11. Original data distribution of the complete D1000 dataset![]()
图 12 6种缺失填充方法在缺失率为50%的D1000数据集上填充后的数据分布Figure 12. Six imputation methods' data distribution after imputation for the D1000 dataset with 50% missing ratio(3) 各缺失值填充方法的整体填充效果。计算6个数据集(D1000、D2000、Pendigits、Yeast、Red wine quality和Breast-cancer)在5种不同缺失率下的平均RMSE和平均皮尔逊相关系数。由6种缺失值填充方法的填充评估结果(表 2)可知：
表 2 6种缺失值填充方法的填充评估实验结果Table 2. Experimental results of imputation evaluation of six missing value imputation methods评估指标 数据集 AkNNI kNNI WkNNI MICE RI MI 平均RMSE D1000 1.713 1.875 2.030 2.386 2.442 2.061 D2000 34.356 41.823 41.451 38.196 38.344 42.701 Pendigits 29.476 36.681 38.729 41.066 41.110 64.813 Yeast 0.148 0.151 0.162 0.160 0.163 0.153 Red wine quality 15.549 17.378 18.553 15.967 15.702 18.308 Breast-cancer 2.949 3.363 3.568 3.219 3.254 4.357 平均皮尔逊相关系数 D1000 0.927 0.916 0.899 0.859 0.854 0.892 D2000 0.882 0.836 0.839 0.860 0.859 0.830 Pendigits 0.960 0.935 0.925 0.930 0.929 0.833 Yeast 0.836 0.827 0.813 0.811 0.803 0.830 Red wine quality 0.881 0.848 0.836 0.860 0.879 0.833 Breast-cancer 0.920 0.892 0.875 0.904 0.902 0.834 ① AkNNI方法在所有数据集上都取得了最优的填充效果。具体来说，AkNNI方法在D1000、D2000、Pendigits、Yeast、Red wine quality、Breast-cancer数据集上的平均RMSE分别为1.713、34.356、29.476、0.148、15.549和2.949，平均皮尔逊相关系数分别为0.927、0.882、0.960、0.836、0.881和0.920。
② 从D1000数据集和D2000数据集的填充效果来看，以标准欧式距离作为相似性度量的kNNI方法和WkNNI方法的填充效果显著下降，分别由平均填充效果的第2、3位分别下降至第4、5位。究其原因为：随着不均匀属性列数的增加，标准欧氏距离在度量样本相似性时的准确率下降。
③ 在所有数据集上，AkNNI方法取得的平均RMSE均显著低于kNNI方法。特别地，在Pendi-gits、Red wine quality数据集上，AkNNI方法取得的平均RMSE分别比kNNI方法低7.205、1.829。这表明，与kNNI方法相比，AkNNI方法在减少填充误差方面有着显著优势。此外，在皮尔逊相关系数上，AkNNI方法在填充缺失值后，计算得到的皮尔逊相关系数高于kNNI方法，表明AkNNI方法具有更强的数据集中属性间相关性的恢复能力。例如，在Pendigits数据集上，AkNNI方法得到的平均皮尔逊相关系数达到了0.960，而kNNI方法得到的平均皮尔逊相关系数为0.935。主要原因为：AkNNI方法在距离计算中引入了属性概率密度，使得距离度量更符合数据的实际分布，从而提升了填充效果。综上，AkNNI方法通过自适应欧氏距离和优化的k近邻选择流程，更好地处理了非线性和复杂数据分布，表现出更好的鲁棒性和准确性。
2.4.2 分类效果分析
(1) 各缺失值填充方法在不同缺失率下分类效果的变化。由6种缺失填充方法在Pendigits、Yeast、Red wine quality、Breast-cancer数据集上的分类评估实验结果(图 13至图 16)可知：随着缺失率的增加，分类准确率在大部分情况呈现下降趋势。特别地，在Breast-cancer数据集上的分类评估实验中，尽管缺失率升高，但k近邻分类器在所有填充后的数据集上的分类准确率均呈上升趋势。这是因为Breast-cancer数据集的数据分布模型可能不够显著，导致使用相同参数设置的kNN分类器对完整原始数据进行分类时，分类准确率仅为95.6%。而经过填充处理后，虽然没有改变样本数目，却改变了样本分布，这使得填充后的数据可能更有利于分类，从而提高了分类器在填充后数据集的分类准确率。
![]()
图 13 6种缺失填充方法在不同缺失率的Pendigits数据集上的分类结果Figure 13. Classification results on the Pendigits dataset with different missing ratios by six missing value imputation methods![]()
图 14 6种缺失填充方法在不同缺失率的Yeast数据集上的分类结果Figure 14. Classification results on the Yeast dataset with diffe-rent missing ratios by six missing value imputation methods![]()
图 15 6种缺失填充方法在不同缺失率的Red wine quality数据集上的分类结果Figure 15. Classification results on the Red wine quality dataset with different missing ratios by six missing value imputation methods![]()
图 16 6种缺失填充方法在不同缺失率的Breast-cancer数据集上的分类结果Figure 16. Classification results on the Breast-cancer dataset with different missing ratios by six missing value imputation methods(2) 各缺失值填充方法的整体分类效果。由6种填充方法在4个标准数据集(Pendigits、Yeast、Red wine quality和Breast-cancer)上的平均分类准确率(表 3)可知：AkNNI方法的平均分类准确率显著高于其他5种填充方法。其中，在所有数据集上，AkNNI方法的平均分类准确率均高于kNNI方法。特别是在Yeast、Red wine quality数据集上，AkNNI方法的平均分类准确率分别比kNNI方法高1.7%、1.4%。这进一步验证了AkNNI方法不仅能够提高填充准确度，还能提升分类模型的预测效果。
表 3 6种缺失值填充方法的分类评估结果Table 3. Experimental results of classification evaluation of six missing value imputation methods数据集 平均分类准确率/% AkNNI kNNI WkNNI MICE RI MI Pendigits 98.6 98.4 98.4 97.7 97.7 96.4 Yeast 54.5 52.8 52.3 51.8 52.0 52.7 Red wine quality 47.9 46.5 46.6 47.6 47.5 45.6 Breast-cancer 97.2 96.8 96.4 96.6 96.6 96.7 2.5 3种评估指标的相关关系
对3种指标在5种缺失率下分别取平均值，结果显示：填充效果和分类效果在大部分情况下的表现是一致的，即填充效果良好的情况下，分类效果也较好。然而，这种一致性并非绝对，以Breast-cancer数据集为例，如图 10与图 16所示，随着缺失率增加，填充效果确实有所下降，但分类效果并不一定呈现相同的下降趋势。深入分析这一现象，其原因是当填充后的数据集与原始数据集的差异增大时，可能会导致部分难分类的样本被误分类的概率降低，使得分类效果反而有所提升。
综上所述，在使用上述3种指标来评估缺失值填充方法的优异性时，应结合具体任务场景进行综合考量：(1)在注重数值准确度的场景中，应选择RMSE和皮尔逊相关系数为填充数据与原始数据的一致性的主要评估指标。(2)在分类任务中，分类效果并不由填充效果唯一决定，因此应选择分类准确率为主要评估指标。
3. 总结
本文以非均匀分布数据的样本缺失值问题为研究对象，提出了自适应k近邻缺失值填充方法(AkNNI)。AkNNI方法充分考虑了数据的非均匀分布特性对样本相似性度量的影响，引入概率密度函数表征样本取值的不均匀特性，并基于此提出了自适应欧式距离，以更准确地度量样本间的相似性。同时，在近邻选择上从全样本集出发，即兼顾了带缺失值的样本，适用于非均匀分布且完整样本较少的数据集。AkNNI方法与其他5种典型的缺失值填充方法的对比实验表明AkNNI方法具有以下优势：(1)在非均匀分布的数据集上有较高的填充准确度和较高的分类准确度；(2)高缺失率下仍有较好的填充效果和较好的分类效果。
然而，当样本之间没有已知公共属性时，基于距离度量的样本相似性不能被计算。因此，在未来的研究中，可以考虑引入样本距离概率统计模型，解决在缺乏已知公共属性信息时进行相似性度量的问题，进而合理、有效地填充缺失值，提高数据的质量。
-
![]()
图 1 正、负类样本和未知分类样本分布
Figure 1. Sample distributions for positive, negative and unknown class samples
![]()
图 2 混合、正类、负类样本在x属性上的概率密度
Figure 2. Probability densities of mixed samples, positive class samples, and negative class samples over the x attri-bute
![]()
图 3 t属性的概率密度与距离缩放权值的关系
Figure 3. Relationship between probability density for attribute t and distance scaling weights
![]()
图 5 6种缺失填充方法在不同缺失率的D1000数据集上的填充效果
Figure 5. Imputation effects on the D1000 dataset with different missing ratios by six missing value imputation methods
![]()
图 6 6种缺失填充方法在不同缺失率的D2000数据集上的填充效果
Figure 6. Imputation effects on the D2000 dataset with different missing ratios by six missing value imputation methods
![]()
图 7 6种缺失填充方法在不同缺失率的Pendigits数据集上的填充效果
Figure 7. Imputation effects on the Pendigits dataset with different missing ratios by six missing value imputation methods
![]()
图 8 6种缺失填充方法在不同缺失率的Yeast数据集上的填充效果
Figure 8. Imputation effects on the Yeast dataset with different missing ratios by six missing value imputation methods
![]()
图 9 6种缺失填充方法在不同缺失率的Red wine quality数据集上的填充效果
Figure 9. Imputation effects on the Red wine quality dataset with different missing ratios by six missing value imputation methods
![]()
图 10 6种缺失填充方法在不同缺失率的Breast-cancer数据集上的填充效果
Figure 10. Imputation effects on the Breast-cancer dataset with different missing ratios by six missing value imputation methods
![]()
图 11 完整的D1000数据集的原始数据分布
Figure 11. Original data distribution of the complete D1000 dataset
![]()
图 12 6种缺失填充方法在缺失率为50%的D1000数据集上填充后的数据分布
Figure 12. Six imputation methods' data distribution after imputation for the D1000 dataset with 50% missing ratio
![]()
图 13 6种缺失填充方法在不同缺失率的Pendigits数据集上的分类结果
Figure 13. Classification results on the Pendigits dataset with different missing ratios by six missing value imputation methods
![]()
图 14 6种缺失填充方法在不同缺失率的Yeast数据集上的分类结果
Figure 14. Classification results on the Yeast dataset with diffe-rent missing ratios by six missing value imputation methods
![]()
图 15 6种缺失填充方法在不同缺失率的Red wine quality数据集上的分类结果
Figure 15. Classification results on the Red wine quality dataset with different missing ratios by six missing value imputation methods
![]()
图 16 6种缺失填充方法在不同缺失率的Breast-cancer数据集上的分类结果
Figure 16. Classification results on the Breast-cancer dataset with different missing ratios by six missing value imputation methods
表 1 数据集的基本信息
Table 1 Basic information of the datasets
数据集 样本数目/条 属性数目/个 类/种 D1000 1 000 2 — D2000 2 000 15 — Pendigits 10 992 16 26 Yeast 1 484 8 10 Red wine quality 1 599 11 6 Breast-cancer 699 9 2 注：“—”表示无类别标签。 
下载: 导出CSV
表 2 6种缺失值填充方法的填充评估实验结果
Table 2 Experimental results of imputation evaluation of six missing value imputation methods
评估指标 数据集 AkNNI kNNI WkNNI MICE RI MI 平均RMSE D1000 1.713 1.875 2.030 2.386 2.442 2.061 D2000 34.356 41.823 41.451 38.196 38.344 42.701 Pendigits 29.476 36.681 38.729 41.066 41.110 64.813 Yeast 0.148 0.151 0.162 0.160 0.163 0.153 Red wine quality 15.549 17.378 18.553 15.967 15.702 18.308 Breast-cancer 2.949 3.363 3.568 3.219 3.254 4.357 平均皮尔逊相关系数 D1000 0.927 0.916 0.899 0.859 0.854 0.892 D2000 0.882 0.836 0.839 0.860 0.859 0.830 Pendigits 0.960 0.935 0.925 0.930 0.929 0.833 Yeast 0.836 0.827 0.813 0.811 0.803 0.830 Red wine quality 0.881 0.848 0.836 0.860 0.879 0.833 Breast-cancer 0.920 0.892 0.875 0.904 0.902 0.834
下载: 导出CSV
表 3 6种缺失值填充方法的分类评估结果
Table 3 Experimental results of classification evaluation of six missing value imputation methods
数据集 平均分类准确率/% AkNNI kNNI WkNNI MICE RI MI Pendigits 98.6 98.4 98.4 97.7 97.7 96.4 Yeast 54.5 52.8 52.3 51.8 52.0 52.7 Red wine quality 47.9 46.5 46.6 47.6 47.5 45.6 Breast-cancer 97.2 96.8 96.4 96.6 96.6 96.7
下载: 导出CSV
-
[1] PHIWHORM K, SAIKAEW C, LEUNG C K, et al. Adaptive multiple imputations of missing values using the class center[J]. Journal of Big Data, 2022, 9(1): 52/1-25.
[2] 李霞, 马茜, 白梅, 等. RⅡM: 基于独立模型的在线缺失值填补[J]. 计算机科学, 2022, 49(8): 56-63. LI X, MA Q, BAI M, et al. RⅡM: Real-time imputation based on individual models[J]. Computer Science, 2022, 49(8): 56-63.
[3] NUGROHO H, UTAMA N P, SURENDRO K. Normalization and outlier removal in class center-based firefly algorithm for missing value imputation[J]. Journal of Big Data, 2021, 8: 1-18. doi: 10.1186/s40537-020-00387-6
[4] REN L, WANG T, SEKLOULI A S, et al. A review on missing values for main challenges and methods[J]. Information Systems, 2023: 102268/1-23.
[5] LIN W C, TSAI C F. Missing value imputation: a review and analysis of the literature (2006-2017)[J]. Artificial Intelligence Review, 2020, 53: 1487-1509. doi: 10.1007/s10462-019-09709-4
[6] LITTLE R J A. Regression with missing X's: a review[J]. Journal of the American Statistical Association, 1992, 87(420): 1227-1237.
[7] RAGHUNATHAN T E, LEPKOWSKI J M, VAN HOEWYK J, et al. A multivariate technique for multiply imputing missing values using a sequence of regression models[J]. Survey methodology, 2001, 27(1): 85-96.
[8] HAMMEED W M, ALI N A. Missing value imputation tech-niques: a survey[J]. UHD Journal of Science and Techno-logy, 2023, 7(1): 72-81.
[9] JAFRASTEH B, HERNÁNDEZ-LOBATO D, LUBIÁN-LÓPEZ S P, et al. Gaussian processes for missing value imputation[J]. Knowledge-Based Systems, 2023, 273: 110603/1-12.
[10] TROYANSKAYA O, CANTOR M, SHERLOCK G, et al. Missing value estimation methods for DNA microarrays[J]. Bioinformatics, 2001, 17(6): 520-525.
[11] PAN R L, YANG T S, CAO J H, et al. Missing data imputation by K nearest neighbours based on grey relational structure and mutual information[J]. Applied Intelligence, 2015, 43: 614-632.
[12] DATTA S, MISRA D, DAS S. A feature weighted penalty based dissimilarity measure for k-nearest neighbor classification with missing features[J]. Pattern Recognition Letters, 2016, 80: 231-237.
[13] TSAI C F, CHANG F Y. Combining instance selection for better missing value imputation[J]. Journal of Systems and Software, 2016, 122: 63-71.
[14] FAN G F, GUO Y H, ZHENG J M, et al. Application of the weighted k-nearest neighbor algorithm for short-term load forecasting[J]. Energies, 2019, 12(5): 916/1-19.
[15] CHENG C H, CHAN C P, SHEU Y J. A novel purity-based k nearest neighbors imputation method and its application in financial distress prediction[J]. Engineering Applications of Artificial Intelligence, 2019, 81: 283-299.
[16] 梁路, 黎剑, 霍颖翔, 等. 一种非均匀分布数据的非线性标准化方法[J]. 计算机科学, 2016, 43(4): 264-269. LIANG L, LI J, HUO Y X, et al. Nonlinear normalization for non-uniformly distributed data[J]. Computer Science, 2016, 43(4): 264-269.
[17] NUGROHO H, UTAMA N P, SURENDRO K. Class center-based firefly algorithm for handling missing data[J]. Journal of Big Data, 2021, 8(1): 37/1-14.
[18] KARMITSA N, TAHERI S, BAGIROV A, et al. Missing value imputation via clusterwise linear regression[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 34(4): 1889-1901
[19] NIKFALAZAR S, YEH C H, BEDINGFIELD S, et al. Missing data imputation using decision trees and fuzzy clustering with iterative learning[J]. Knowledge and Information Systems, 2020, 62: 2419-2437.
计量
- 文章访问数: 51
- HTML全文浏览量: 7
- PDF下载量: 16
