缺失数据的混合式重建方法

于本成，丁世飞

（1. 中国矿业大学 计算机科学与技术学院，江苏 徐州 221116; 2. 徐州工业职业技术学院 信息与电气工程学院，江苏 徐州 221004）

鉴于缺失数据重建的重要性，研究人员已经就缺失数据重建问题提出了多种解决方法。粒子群优化 (particle swarm optimization，PSO)在1995年由Kennedy和Eberhart提出[1-2]。PSO通过群体内个体之间的信息共享来对问题的解进行协同搜索[3]，即初始化一群随机粒子，并通过迭代找到最优解。在每一次迭代中，粒子通过跟踪局部最优值和全局最优值来更新自己的速度与位置[4]。文献[5]通过调整惯性权重的取值，提出了自适应混沌粒子群优化算法，该算法避免了粒子早熟收敛情况。文献[6]中Krishna和Ravi提出了一种基于粒子群优化和矩阵协方差结构的数据重建方法，他们使用PSO重建缺失值。

进化聚类算法(evolving clustering method，ECM)是一步到位的快速聚类算法，在ECM中，由用户定义的阈值参数会影响群集合数量的估计，值太大或太小都不利于找出群集合数量[7-8]。Ravi等[9-10]提出了4种用于重建的混合方法。在线重建中使用了具有广义回归神经网络的ECM(ECM+GRNN)，在离线重建中使用了K-means+GRNN和K-medoids+GRNN以及具有多层感知机的K-medoids(K-medoids+MLP)。他们虽然提出了基于ECM的数据重建，但值选择涉及了试错法，结果都不同程度地受到值的影响。

极限学习机(extreme learning machine，ELM)是由Huang等[11-12]提出的，它是一种新颖的前馈神经网络，不需要权重更新。目前ELM的理论与算法研究主要集中在随机生成参数的优化、最优外权的求解、最优隐藏层节点个数的选取、ELM核函数、在线极限学习机算法等方面[13]。文献[14]发现自联想的极限学习机(auto associative extreme learning machine，AAELM)在同一个数据集合中的不同运行产生了不同的结果。有时，连接输入层和隐藏层的随机加权会使结果出现很大的波动。在文献[15]中Ravi和Krishna为重建提出了多种在线和离线方法，即粒子群优化训练后的自动关联神经网络(PSOAANN)、粒子群优化训练后的自动关联子波神经网络(PSOAAWNN)、径向基函数自动关联神经网络(RBFAANN)、广义回归自动关联神经网络(GRAANN)，这些算法仍有待于进一步改进。

1 基础理论

1.1 PSO算法

1)随机初始化群体，设定粒子的位置和速度；

2)根据适应度函数计算粒子的适应度值，选取具有最优适应度值的粒子位置作为，每个粒子当前位置为；

3)根据式(1)、式(2)更新粒子的速度和位置；

6)检查是否满足终止条件，如果满足则终止迭代，否则返回2)。

1.2 ECM算法

2)如果输入数据流的所有样本都已处理完毕，则算法结束。否则，取当前样本，计算与已经创建的所有个集群中心之间的距离，

1.3 ELM算法

式中H表示隐藏层的矩阵。H矩阵第i行代表输入层中第i个实例在隐藏层所有神经元上的输出，H矩阵的第j列代表所有训练样本在第j个隐藏层神经元上的输出，即

在已知权值和偏置的情况下，上面问题的求解就转化为求解线性系统的最小范数最小二乘解：

2 提出的混合式重建方法

2.1 PSOECM方法

PSOECM方法步骤：

5) 重复 1)～4)直至收敛。

计算平均绝对百分比误差(mean absolute percentage error，MAPE)值：

2.2 MAAELM方法

MAAELM方法采用PSOECM与AAELM混合重建缺失数据。MAAELM结构如图1所示。

图1 MAAELM结构Fig. 1 Architecture of the MAAELM

MAAELM方法步骤：

1)将数据归一化至[0,1]范围内。

2)将数据集合分为完整记录集合和不完整记录集合。

3)在1)中执行基于PSOECM的重建，确定群集中心。

5)执行PSOECM方法的3)。

6)计算得到各个群集中心之间的归一化欧几里德距离。

为了估算出隐藏层和输出层之间的权重，在6)得到的距离中应用激活函数并进行非线性转换，再应用Moore-Penrose广义逆矩阵得出。

最后，根据文献[12]使用Moore-Penrose广义逆矩阵求解估算出隐藏层和输出层之间的权重，其中为权向量，为目标向量。利用式(12)计算平均绝对百分误差(MAPE)值。

3 选取实验数据集与激活函数

实验选取UCI机器学习数据库中的6个标准数据集来进行验证，实验数据集如表1所示。同时，在选取的实验数据集上使用9个激活函数来研究它们对文章所提方法的影响。实验选取激活函数如表2所示。所选数据集中除Auto-mpg中的马力属性值存在缺失，其他5个数据集均不存在属性缺失值，所以通过随机删除原始数据集的一些值来进行实验，并创建了除目标变量以外的所有变量中的缺失值。每一个数据集被分成10个相等的小集合，其中9个小集合经过聚类处理，剩下的1个留下为缺失值备用。

为了在每一个小集合中创建缺失值，随机删除了近10%的值(单元)，并确保从每个记录中删除至少一个单元。因此，在10倍交叉验证中，有不同缺失记录的10个小集合。

对于完整记录集合中的各个小集合，将它们从全部记录中分理并用于聚类。在完整记录集合中应用ECM算法，并通过最近群集中心属性的对应值重建出不完整记录集合中的属性缺失值。

使用PSO优化算法和文献[6]提及的两个适应度函数为PSOECM选出最佳值，并将相同的值提供给MAAELM。对于所有数据集合，对比了本文所提方法与文献[6, 9-10, 15, 17]所提多种混合方法的MAPE平均值。

表1 实验数据集Table 1 Data sets for the experiment

表2 激活函数表Table 2 Activation functions

4 实验结果和分析

不同激活函数作用于MAAELM所得的MAPE值以及PSOECM、MAAELM与其他算法比较的结果如图2和图3所示。

图2 不同激活函数对MAAELM的影响Fig. 2 Influence of different activation functions on the MAAELM

图3 不同算法的MAPE值Fig. 3 MAPE value of different algorithms

根据图2所展示的不同激活函数作用于MAAELM所得的MAPE值可以发现：Sigmoid在所有激活函数中的表现最佳，Hardlim激活函数表现最差，而其他激活函数对于MAAELM的MAPE值影响基本相同。Hardlim激活函数表现最差是因为它将一个输入空间只分割为0和1两个类别。

图3中将本文所提算法与Krishna M和Ravi V[6]的PSO_COV算法，Nishanth和Ravi[9]的K-means+GRNN、K-medoids+MLP、K-medoids+GRNN、ECM+GRNN等算法，Gautam和Ravi[10]的ECM Imputation算法，Ravi和 Krishna[15]的PSOAANN、PSOAAWNN、RBFAANN、GRAANN等算法，Ankaiah和 Ravi[17]的K-Means+MLP算法的结果进行对比，对比结果显示了最佳值在所提方法中可以更有效地进行基于ECM的重建，以及在大部分数据集合上局部学习和整体学习混合使用优于文献[6, 9-10, 15, 17]所提方法。

在Auto-mpg 数据集合方面，只有K-medoids+GRNN、ECM+GRNN和GRAANN这3种混合法的结果与PSOECM方法接近，分别落后1.31%、1.65%和0.19%。PSOECM 通过选择最佳值，在Auto-mpg数据集合中的表现优于ECM重建。将PSOECM得出的相同值带入MAAELM时，误差又降低了0.96%。

在Boston Housing数据集合方面，除了GRAANN方法与PSOECM方法相差0.88%之外，其他方法的MAPE值至少比PSOECM高3%。PSOECM 通过选择最佳值，在Boston Housing数据集合中的表现同样优于ECM重建。在MAAELM中应用PSOECM得出的最佳值之后，MAPE值便可以进一步降低0.32%。

在Forest fires数据集合方面，可以观察到与Boston Housing数据集合相似的性能。除了GRAANN落后PSOECM的结果0.13%之外，其他方法的MAPE值比PSOECM至少高4%。PSOECM 通过选择最佳值，MAPE同样有所下降。在MAAELM中应用PSOECM得出最佳值之后，误差又降低了0.68%。

除了在Spectf 数据集合中，PSOECM略逊于GRAANN 之外，在 Iris、Spectf 和 Wine recognition数据集合中，PSOECM与MAAELM同样表现出了类似在 Auto-mpg、Boston Housing、Forest fires数据集合中的优势。

经上述实验结果的分析得出：1)PSOECM 通过选择最佳值，在各个数据集合中的表现优于ECM重建；2)将PSOECM得出的相同值代入MAAELM时，所得MAPE值均有所降低。

5 结束语

本文提出了2种新颖的缺失数据的混合式重建方法，并使用6个数据集验证了所提方法的有效性。发现由PSO为ECM选出的最佳值在PSOECM和MAAELM的优异性能方面起到了重要作用，解决了值的选取困难和值对ECM重建结果的影响问题，同时去除了AAELM的随机性。下一步研究将增大实验数据集，验证本文所提方法在原始数据缺失不同百分比时的结果，以及使用更多的激活函数来进一步验证所提方法的有效性，并对所提方法与现有方法进行威尔克森符号秩检验，验证所提方法的显著性。