摘要
针对传统数据填补方法难以有效利用标签信息和缺失数据的随机信息的不足，提出面向混合型特征的粒子群优化填补算法。将连续型特征取值建模为高斯分布，均值和标准差作为优化参数。将离散型特征的取值概率作为参数进行优化。使用分类正确率作为优化目标，充分利用标签信息和缺失数据的随机信息。采用4种基于统计的方法和2种基于演化算法的填补方法作为对比，在6个典型的分类数据集上进行实验。结果表明，提出的方法在分类正确率指标上显著优于其他对比算法，同时具有较优的时间开销，能够有效解决混合特征数据缺失的问题。
Abstract
Aiming at the deficiency of traditional data imputation methods in effectively using the label information and random characteristics of missing data, a particle swarm optimization based imputation method for mixed features was proposed. The value of continuous feature was modeled as Gaussian distribution, and the mean and standard deviation were used as optimization parameters. The value probability of categorical features was optimized as a parameter. The classification accuracy rate was used as the optimization target to make full use of random information of label information and missing data. Four statistical methods and two evolutionary algorithm based imputation methods were used to compare the results on six typical classification datasets. The results show that the proposed method significantly outperforms other comparison algorithms in terms of classification accuracy indicator, and has better time overhead at the same time, which can effectively solve the data missing problems of mixed features.
Keywords
软件系统和应用程序中经常面临特征数据缺失的情况[1]，如物联网数据、医疗数据、材料数据等[2-4]，数据缺失可能导致学习算法或程序性能下降甚至不可用。导致数据缺失的原因较多，如调研项目无回应、意外丢失或传输错误等[5-7]。为了解决数据缺失问题，研究人员提出了一些有效的填补方法，按照采用技术的不同，可以分为基于统计学的方法和基于学习的方法[8]。基于统计学的方法利用已有数据的距离、频率、均值等信息，填补缺失数据；基于学习的方法通过训练学习模型，预测并填补缺失数据。
然而，传统方法的缺点导致其性能难以得到进一步的提升[9]：基于统计学的典型方法包括均值填充、期望最大填充、多重填补等，它们通常采用已有实例的统计信息进行填补，无法有效利用缺失数据的实例标签信息[10]；基于学习的典型方法包括基于支持向量机的方法、基于决策树的方法以及基于聚类的方法等，它们通常训练特定的学习模型参数，当参数确定时，会输出确定的填补值，未能在一定程度上考虑缺失数据的随机性[11]。
粒子群优化（particle swarm optimization， PSO）是一种寻优能力较强的演化算法，它具有参数设置方便、易于适配、部署实现简单等特点，在众多领域得到了广泛的应用[12-14]。
为了提升数据缺失情况下分类系统的性能，提出针对混合变量数据缺失问题的粒子群数据填补（data imputation based on particle swarm optimization，DIPSO）算法，将发生数据缺失的特征分为连续型特征和离散型特征；针对连续型特征，将其取值建模为高斯分布，均值和标准差作为参数；针对离散型特征，将不同取值的概率作为参数；采用粒子群优化算法对这些参数进行优化，通过高斯分布和概率值生成具有一定随机性的填补数据，充分利用标签信息和缺失数据的随机性，提升分类系统的精度和可用性。
1 针对混合特征的粒子群数据填补方法
DIPSO的算法流程如图1所示。
图1DIPSO流程图
Fig.1Flowchart of DIPSO
首先对数据集实例中发生数据缺失的特征进行记录，并根据数据源及已有数据的分布统计情况，通过人工的方式将其划分为连续型或离散型：若已有数据不重复且呈现出可通过曲线拟合的情况，则可以将其判定为连续型特征；若已有数据仅在几个值之间重复，可以将其判定为离散型特征。针对连续型特征，将其取值建模为高斯分布，均值和标准差作为参数；针对离散型特征，确定其不重复的值，将这些值出现的概率作为参数，确定参数的个数和对应的值域。
然后根据参数的个数（即粒子的维度）和对应的值域，初始化粒子群，通过粒子初始值与对应特征的填补方法，填补数据集并进行分类测试，采用分类指标计算粒子个体的适应度值。
进入粒子群优化迭代过程后，更新粒子速度，并移动粒子的位置，获得参数值；根据参数值和对应特征类型，采用相应的方法生成数据填补数据集，通过完整的数据集进行分类，使用分类指标评估当前粒子的适应度值；根据粒子的适应度值更新全局最优粒子；当达到最大循环次数后，停止迭代过程，输出最优粒子个体，即最优参数取值。
下面详细介绍连续型和离散型特征的填补方法，描述粒子群优化算法的主要步骤，给出DIPSO算法的伪代码，分析其时间复杂度。
1.1 连续型特征填补方法
众多实际系统和应用产生的数据均近似地服从高斯分布[15]。因此，针对连续型特征缺失数据的情况，将其取值的分布建模为高斯分布。假定数据集在连续型特征i上缺失了Ci个数据，可以将特征i的取值概率密度函数建模为：
(1)
式中，μi为均值，δi为标准差。显然，当均值和标准差变化时，特征i的取值分布会发生显著的改变。DIPSO将μi和δi作为优化参数编码成粒子，通过迭代产生较好的取值，根据μi和δi的值生成Ci个数据，将这些数据填补至数据集中。在优化迭代的过程中，需要设置优化参数的值域范围，即特征i对应的μi和δi在粒子中的上下界，值域范围的设置可以通过特征i在数据集中出现的值来确定，采用特征i出现的最大值和最小值作为μi和δi的上界和下界。
1.2 离散型特征填补方法
针对离散型特征缺失数据的情况，假设在特征j上缺失了Dj个值，统计该特征不重复的取值，将这些值出现的概率作为参数进行编码并优化。基于优化产生的概率值，经过归一化后，采用轮盘赌策略生成Dj个值进行填补。显然，每个参数的阈值范围为[0，1]。
下面分析参数的个数，即粒子的维度。假设C为发生数据缺失的连续型特征个数，D为发生数据缺失的离散型特征个数，则待优化的参数个数为，其中Dp为在特征p上出现的不重复值个数。
1.3 粒子群优化算法
PSO是一种受鸟类群体觅食行为启发的演化算法，能够从个体和群体信息中进行学习，其主要步骤包括粒子速度的更新以及位置的移动[16]。在t时刻，粒子个体i的速度更新为：
(2)
式中，表示粒子i在t-1时刻的速度；w为惯性权重，控制粒子在空间中的搜索范围；α和β是加速因子，控制粒子在群体和个体信息上的学习程度；g*表示全局最优解，是粒子i的历史最优解；是粒子i在t-1时刻的位置；r1和r2是满足均匀分布的随机数，取值范围为（0，1）。
粒子速度更新后，需要通过新的速度移动粒子的位置，即搜索新的解，粒子的位置移动方法为：
(3)
1.4 算法整体流程与复杂度分析
综上，DIPSO算法的伪代码如算法1所示。
算法1 DIPSO伪代码
Alg.1 Pseudo-code of DIPSO
现对DIPSO算法的时间复杂度做分析。假设T为算法的最大迭代次数，N为粒子的个数，L为粒子的维度，填补算法的复杂度为O（L），算法的时间复杂度为O（T×L×N）。
2 实验与分析
本节通过实验对DIPSO算法的性能进行比较分析。为了综合评估方法的性能，实验使用不同特征类型的6个完整数据集，在实验过程中通过控制数据集的缺失率来测试算法的填补能力。数据集来源于UCI机器学习网站（https ://archive .ics .uci .edu/ml/datasets），数据集的有关基本信息如表1所示。BCC是乳腺癌数据集，包括116个实例和9个连续型特征，预测类别为是否患癌；Park是帕金森病患者的语音数据集，包括197个实例和22个连续型特征，预测类别为是否患有帕金森病；Lymp是淋巴数据集，包括148个实例、18个离散型特征和4个预测类别；MONK是僧侣问题数据集，包括432个实例、7个离散型特征和2个预测类别；Zoo是动物数据集，包括101个实例、17个混合型特征和7个预测类别；StH是心脏病数据集，包括270个实例、13个混合型特征和2个预测类别。
表1实验数据集属性
Tab.1 Characteristics of experiment datasets
为了说明方法的有效性和优越性，选择4种广泛使用的统计学填补算法和2种基于学习的填补算法进行对比。4种统计学填补方法采用实际中应用广泛的均值填补（mean imputation method，MI）算法[17]、K近邻（K nearest neighbor，KNN）算法[18]、正则期望最大化（regularized expectation maximization，REM）算法[19]以及链式方程多元回归（multivariate imputation by chained equations，MICE）算法[20]。2种基于学习的算法包括近年来提出的性能优异的极限学习机-粒子群优化-模糊C均值（extreme learning machine-particle swarm optimization-fuzzy C means，EPF）算法[21]以及多目标遗传数据填补算法（multi-objective genetic algorithm for data imputation，MOGAImp）[22]，EPF使用粒子群算法优化模糊C均值填补方法的参数，MOGAImp通过多目标遗传方法优化填补值出现的位置。
采用Ubuntu20.04LTS操作系统、Intel Xeon E5-2630v4@2.2 GHz处理器、64 GB内存的实验平台。KNN算法的K值设置为5；REM算法采用文献[23]提供的开源代码，参数为默认值；MICE算法使用R语言的开源软件包，参数为默认值[24]；EPF算法的迭代次数设置为250，种群个数为100，其他参数与文献[17]设置一致；MOGAImp的迭代次数设置为250，种群个数为100，交叉率为0.7，变异率为0.02，由于该算法为多目标算法，搜索得到的帕累托解无优劣之分，因此从帕累托档案中随机选择一个帕累托解作为输出；DIPSO算法的迭代次数为250，种群个数为100，惯性权重w=0.5，加速因子α=β=1。MICE算法使用RStudio软件运行，其他算法使用MATLAB2018a软件运行。
实验使用K近邻分类器，K值设置为5。缺失率设置为5%、10%、20%、30%、40%和50%，采用分类正确率作为评估指标以及DIPSO的优化目标，其计算方法为：
(4)
式中，S表示样本总数，P表示正确分类的样本数。在每个测试条件下，算法独立运行20次，取分类正确率的平均值作为算法运行结果。
表2是7种方法在6个测试数据集上不同缺失率条件下的分类正确率实验结果。
表2分类正确率实验结果
Tab.2 Experimental results of accuracy indicator
从较好解统计的角度，对表2提供的结果进行分析。DIPSO在多数情况下均提供了较好的结果，经过统计，DIPSO一共提供了27个较好解，EPF一共提供了9个较好解，MOGAImp提供了1个较好解。进一步，在BCC上，当缺失率为5%、20%、30%和50%时，EPF提供了较优值，DIPSO在缺失率为10%和40%时表现较好；在Park上，EPF的表现与DIPSO相当，在缺失率为30%、40%和50%时，DIPSO提供了较好解；在Lymp、MONK和Zoo上，DIPSO好于其他对比算法，除了在MONK数据集上，当缺失率为30%时，MOGAImp提供了较优值；在StH上，DIPSO也优于其他对比算法，除了在缺失率为30%时，EPF提供了较优解。
从算法性能的提升程度上看，DIPSO在BCC数据集上的分类正确率比其他算法提升了约26.5%，在Park上提升了约5.9%，在Lymp上提升了约21.3%，在MONK上提升了约33.4%，在Zoo上提升了约16.6%，在StH上提升了约14.8%。从整体上看，DIPSO的性能相比其他算法提升了约19.8%。
下面从两个角度对结果进行深入分析。从技术角度看，较好解均是由基于学习的方法提供，这是由于基于统计的方法无法有效利用标签信息或标签与特征之间的关系，而基于学习的方法能够同时利用标签和特征的信息。从方法的角度看，DIPSO优于EPF和MOGAImp，这是由于EPF主要采用模糊C均值的方法填补数据，MOGAImp则是采用已有的数据填补缺失值，它们都无法有效利用缺失数据的随机性。这表明了DIPSO能够有效利用标签信息和缺失数据的随机性，验证了方法的有效性和优越性。
分析实验结果中产生的一个现象，很多方法在测试数据集上的指标值并没有因为缺失率的提高而降低，尤其在Lymp和MONK数据集上，DIPOS的指标值随着缺失率的提高反而出现了一定程度的提升。造成这种情况的原因可能是，特征之间具有较强的冗余性，在一定范围内的随机数据缺失并不会导致学习难度的提高，移除缺失数据或者采用有效的填补策略可能使分类超平面更加容易学习[25]。
下面通过实验分析DIPSO算法的时间复杂度。显然，基于统计方法的时间复杂度要小于基于学习的方法，因此这里仅对MOGAImp、EPF和DIPSO做详细的对比，3种方法在不同缺失率和数据集上的时间开销堆积直方图如图2所示。
图2时间开销堆积直方图
Fig.2Stacked histogram of time costs
从图2可以看出，在同一个数据集上，DIPSO的时间开销并没有因为缺失率的增加而发生显著的变化，这是由于DIPSO的粒子长度仅与连续型特征数以及离散型特征中的不重复值个数相关，与缺失数据的数量无关。
DIPSO的时间开销要低于EPF和MOGAImp。这是由于DIPSO仅对填补模型的参数进行优化，填补时通过参数生成填补值即可，时间开销较低；而EPF在迭代中需要使用模糊C均值操作，MOGAImp需要维护帕累托档案，导致增加了时间耗费。
上述实验表明，DIPSO具有较好填补性能的同时，也具有较优的时间开销，能够适用于实际业务系统，具有较好的实用性。
3 结论
数据缺失是系统常见的问题，可能导致算法性能下降或不可用。为了解决分类系统中的数据缺失问题，提出基于粒子群优化的数据填补方法DIPSO。将发生缺失数据的特征分为连续型特征和离散型特征，将连续型特征数据取值建模为高斯分布，均值和标准差作为参数，将离散型特征取值建模为概率参数，以分类正确率作为目标通过粒子群算法对参数进行优化。在6个数据集上与4种基于统计的方法和2种基于演化算法的方法进行对比，结果验证了DIPSO方法的有效性和优越性，同时具有较好的时间开销。
但是DIPSO仍然存在一些缺点：首先，目前仍然是通过人工的方式判定发生数据缺失的特征类型，缺少智能的判别方式；然后，没有考虑连续型特征取值不满足高斯分布的情况下，如何对数据分布进行建模；最后，没有深入探究如何通过缺失值附近的数据点来提升填补的准确性。下一步，将从这几个方面入手，进一步提升DIPSO方法的综合性能及其可扩展性。
