2. 徐州工业职业技术学院 信息与电气工程学院,江苏 徐州 221004
2. School of Information and Electrical Engineering, Xuzhou College of Industrial Technology, Xuzhou 221004, China
鉴于缺失数据重建的重要性,研究人员已经就缺失数据重建问题提出了多种解决方法。粒子群优化(particle swarm optimization,PSO)在1995年由Kennedy和Eberhart提出[1-2]。PSO通过群体内个体之间的信息共享来对问题的解进行协同搜索[3],即初始化一群随机粒子,并通过迭代找到最优解。在每一次迭代中,粒子通过跟踪局部最优值和全局最优值来更新自己的速度与位置[4]。文献[5]通过调整惯性权重的取值,提出了自适应混沌粒子群优化算法,该算法避免了粒子早熟收敛情况。文献[6]中Krishna和Ravi提出了一种基于粒子群优化和矩阵协方差结构的数据重建方法,他们使用PSO重建缺失值。
进化聚类算法(evolving clustering method,ECM)是一步到位的快速聚类算法,在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),这些算法仍有待于进一步改进。
鉴于以上研究中存在的PSO重建缺失值效率低、
在D维搜索空间中,由
$v_{id}^{k + 1} = \omega v_{id}^k + {a_1}{r_1}\left( {{p_{id}} - z_{id}^k} \right) + {a_2}{r_2}\left( {{p_{gd}} - z_{id}^k} \right)$ | (1) |
$z_{id}^{k + 1} = z_{id}^k + v_{id}^{k + 1}$ | (2) |
式中:
1)随机初始化群体,设定粒子的位置和速度;
2)根据适应度函数计算粒子的适应度值,选取具有最优适应度值的粒子位置作为
3)根据式(1)、式(2)更新粒子的速度和位置;
4)把每个粒子的适应度值与
5)把每个粒子的适应度值与
6)检查是否满足终止条件,如果满足则终止迭代,否则返回2)。
1.2 ECM算法创建新群集
1)创建第一个群集
2)如果输入数据流的所有样本都已处理完毕,则算法结束。否则,取当前样本
3)如果存在群集中心
4)从已经创建的所有
5)如果
6)如果
ECM算法不保持已传递样本的任何信息,但任一群集
在ECM算法中,向量
$\left\| {{{x}} - {{y}}} \right\| = {{{{\left( {\sum\limits_{i = 1}^q {{{\left| {{{{x}}_i} - {{{y}}_i}} \right|}^2}} } \right)}^{1/2}}}/ {{q^{1/2}}}}\begin{array}{*{20}{c}} ,\;{{{x}},{{y}} \in {{\bf{R}}^q}} \end{array}$ | (3) |
在5)、6)中
输入层的节点个数为
${{X}}=\left[ {\begin{array}{*{20}{c}} {{x_{11}}}&{{x_{12}}}& \cdots &{{x_{1N}}} \\ {{x_{21}}}&{{x_{22}}}& \cdots &{{x_{2N}}} \\ \vdots & \vdots &{}& \vdots \\ {{x_{n1}}}&{{x_{n2}}}& \cdots &{{x_{nN}}} \end{array}} \right]$ | (4) |
${{T}}=\left[ {\begin{array}{*{20}{c}} {{t_{11}}}&{{t_{12}}}& \cdots &{{t_{1N}}} \\ {{t_{21}}}&{{t_{22}}}& \cdots &{{t_{2N}}} \\ \vdots & \vdots &{}& \vdots \\ {{t_{n1}}}&{{t_{n2}}}& \cdots &{{t_{nN}}} \end{array}} \right]$ | (5) |
第
$\sum\limits_{j = 1}^L {{\beta _j}G\left( {{a_j},{b_j},{x_i}} \right)} = {t_i},\quad i= 1,2, \cdots ,N$ | (6) |
式(6)也可以表示为
${{H\beta }} = {{T}}$ | (7) |
式中H表示隐藏层的矩阵。H矩阵第i行代表输入层中第i个实例在隐藏层所有神经元上的输出,H矩阵的第j列代表所有训练样本在第j个隐藏层神经元上的输出,即
$\begin{gathered} {{H}}\left( {{a_1}, \cdots ,{a_L},{b_1}, \cdots ,{b_l},{x_1}, \cdots ,{x_n}} \right) = \\ {\left[ {\begin{array}{*{20}{c}} {G\left( {{a_1},{b_1},{x_1}} \right)}&{...}&{G\left( {{a_L},{b_L},{x_1}} \right)} \\ \vdots &{}& \vdots \\ {G\left( {{a_1},{b_1},{x_N}} \right)}&{...}&{G\left( {{a_L},{b_L},{x_N}} \right)} \end{array}} \right]_{N \times L}} \\ \end{gathered} $ | (8) |
$ {{\beta }} = {\left[ {\begin{array}{*{20}{c}} {{{\beta}} _1^{\rm{T}}} \\ {{{\beta}} _2^{\rm{T}}} \\ \vdots \\ {{{\beta}} _L^{\rm{T}}} \end{array}} \right]_{L \times m}}\;\;{{T}} = {\left[ {\begin{array}{*{20}{c}} {{{t}}_1^{\rm{T}}} \\ {{{t}}_2^{\rm{T}}} \\ \vdots \\ {{{t}}_N^{\rm{T}}} \end{array}} \right]_{N \times m}} $ | (9) |
在已知权值和偏置的情况下,上面问题的求解就转化为求解线性系统
$\hat {{\beta}} ={{{H}}^{{{\dagger } }}}{{T}}$ | (10) |
式中:
全部数据记录
PSOECM方法步骤:
1)计算出
2)在具有PSO随机初始化
3)对
${D_j} = \sum\limits_{i = 1;i \ne k}^n {{{\left| {{x_i} - C{'_j}} \right|}^2}} $ | (11) |
式中:
4)数据重建后计算
5) 重复1)~4)直至收敛。
计算平均绝对百分比误差(mean absolute percentage error,MAPE)值:
${\rm{MAPE}} = \frac{1}{n}\sum\limits_{i = 1}^n {\left| {\frac{{{x_i} - {{\hat x}_i}}}{{{x_i}}}} \right|} \times 100{\rm{\% }}$ | (12) |
式中:
PSOECM方法采用与文献[6]相同的适应度函数
MAAELM方法采用PSOECM与AAELM混合重建缺失数据。MAAELM结构如图1所示。
Download:
|
|
MAAELM方法步骤:
1)将数据归一化至[0,1]范围内。
2)将数据集合分为完整记录集合和不完整记录集合。
3)在1)中执行基于PSOECM的重建,确定群集中心。
4)在2)中使用1)中得出的最佳
5)执行PSOECM方法的3)。
6)计算得到各个群集中心之间的归一化欧几里德距离。
为了估算出隐藏层和输出层之间的权重,在6)得到的距离中应用激活函数并进行非线性转换,再应用Moore-Penrose广义逆矩阵得出
最后,根据文献[12]使用Moore-Penrose广义逆矩阵求解
实验选取UCI机器学习数据库中的6个标准数据集来进行验证,实验数据集如表1所示。同时,在选取的实验数据集上使用9个激活函数来研究它们对文章所提方法的影响。实验选取激活函数如表2所示。所选数据集中除Auto-mpg中的马力属性值存在缺失,其他5个数据集均不存在属性缺失值,所以通过随机删除原始数据集的一些值来进行实验,并创建了除目标变量以外的所有变量中的缺失值。每一个数据集被分成10个相等的小集合,其中9个小集合经过聚类处理,剩下的1个留下为缺失值备用。
为了在每一个小集合中创建缺失值,随机删除了近10%的值(单元),并确保从每个记录中删除至少一个单元。因此,在10倍交叉验证中,有不同缺失记录的10个小集合。
对于完整记录集合中的各个小集合,将它们从全部记录中分理并用于聚类。在完整记录集合中应用ECM算法,并通过最近群集中心属性的对应值重建出不完整记录集合中的属性缺失值。
使用PSO优化算法和文献[6]提及的两个适应度函数为PSOECM选出最佳
不同激活函数作用于MAAELM所得的MAPE值以及PSOECM、MAAELM与其他算法比较的结果如图2和图3所示。
Download:
|
|
Download:
|
|
根据图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算法的结果进行对比,对比结果显示了最佳
在Auto-mpg 数据集合方面,只有K-medoids+GRNN、ECM+GRNN和GRAANN这3种混合法的结果与PSOECM方法接近,分别落后1.31%、1.65%和0.19%。PSOECM 通过选择最佳
在Boston Housing数据集合方面,除了GRAANN方法与PSOECM方法相差0.88%之外,其他方法的MAPE值至少比PSOECM高3%。PSOECM 通过选择最佳
在Forest fires数据集合方面,可以观察到与Boston Housing数据集合相似的性能。除了GRAANN落后PSOECM的结果0.13%之外,其他方法的MAPE值比PSOECM至少高4%。PSOECM 通过选择最佳
除了在Spectf 数据集合中,PSOECM略逊于GRAANN之外,在Iris、Spectf 和Wine recognition数据集合中,PSOECM与MAAELM同样表现出了类似在Auto-mpg、Boston Housing、Forest fires数据集合中的优势。
经上述实验结果的分析得出:1)PSOECM 通过选择最佳
本文提出了2种新颖的缺失数据的混合式重建方法,并使用6个数据集验证了所提方法的有效性。发现由PSO为ECM选出的最佳
[1] | KENNEDY J. Particle swarm optimization[M]//SAMMUT C, WEBB G I. Encyclopedia of Machine Learning. Boston, MA: Springer, 2010. (0) |
[2] | EBERHART R C, SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization[C]//Proceedings of the 2000 Congress on Evolutionary Computation. La Jolla, USA, 2000: 84−88. (0) |
[3] |
张庆科. 粒子群优化算法及差分进行算法研究[D]. 济南: 山东大学, 2017. ZHANG Qingke. Research on the particle swarm optimization and differential evolution algorithms[D]. Ji'nan: Shandong University, 2017. (0) |
[4] |
王永贵, 林琳, 刘宪国. 基于改进粒子群优化的文本聚类算法研究[J]. 计算机工程, 2014, 40(11): 172-177. WANG Yonggui, LIN Lin, LIU Xianguo. Research on text clustering algorithm based on improved particle swarm optimization[J]. Computer engineering, 2014, 40(11): 172-177. DOI:10.3969/j.issn.1000-3428.2014.11.034 (0) |
[5] |
徐林. 粒子群优化算法的改进及其应用研究[J]. 西安文理学院学报(自然科学版), 2017, 20(4): 51-54. XU Lin. Research on improvement and application of the particle swarm optimization algorithm[J]. Journal of Xi’an University (natural science edition), 2017, 20(4): 51-54. DOI:10.3969/j.issn.1008-5564.2017.04.012 (0) |
[6] | KRISHNA M, RAVI V. Particle swarm optimization and covariance matrix based data imputation[C]//Proceedings of 2013 IEEE International Conference on Computational Intelligence and Computing Research. Enathi, India, 2013: 1–6. (0) |
[7] | KASABOV N K, SONG Qun. DENFIS: dynamic evolving neural-fuzzy inference system and its application for time-series prediction[J]. IEEE transactions on fuzzy systems, 2002, 10(2): 144-154. DOI:10.1109/91.995117 (0) |
[8] | KASABOV N, SONG Qun, MA Tianmin. Fuzzy-neuro systems for local and personalized modelling[M]//NIKRAVESH M, KACPRZYK J, ZADEH L A. Forging New Frontiers: Fuzzy Pioneers II. Berlin, Heidelberg: Springer, 2008: 175−197. (0) |
[9] | NISHANTH K J, RAVI V. A computational intelligence based online data imputation method: an application for banking[J]. Journal of information processing systems, 2013, 9(9): 633-650. (0) |
[10] | GAUTAM C, RAVI V. Evolving clustering based data imputation[C]//Proceedings of 2014 International Conference on Circuits, Power and Computing Technologies. Nagercoil, Tamil Nadu, India, 2014: 1763–1769. (0) |
[11] | HUANG Guangbin, ZHU Qinyu, SIEW C K. Extreme learning machine: a new learning scheme of feedforward neural networks[C]//Proceedings of 2004 IEEE International Joint Conference on Neural Networks. Budapest, Hungary, 2004: 985–990. (0) |
[12] | HUANG Guangbin, ZHU Qinyu, SIEW C K. Extreme learning machine: theory and applications[J]. Neurocomputing, 2006, 70(1/2/3): 489-501. (0) |
[13] |
任阳晖. 极限学习机算法及应用研究[D]. 沈阳: 沈阳航空航天大学, 2017. REN Yanghui. Extreme learning machine alorithm and application[D]. Shenyang: Shenyang Aerospace University, 2017. (0) |
[14] | GAUTAM C, RAVI V. Data imputation via evolutionary computation, clustering and a neural network[J]. Neurocomputing, 2015, 156: 134-142. DOI:10.1016/j.neucom.2014.12.073 (0) |
[15] | RAVI V, KRISHNA M. A new online data imputation method based on general regression auto associative neural network[J]. Neurocomputing, 2014, 138: 106-113. DOI:10.1016/j.neucom.2014.02.037 (0) |
[16] | 申小征. 基于维数约简的区域协方差矩阵及其在人脸识别中的应用[D]. 云南: 云南财经大学, 2017. (0) |
[17] | ANKAIAH N, RAVI V. A novel soft computing hybrid for data imputation[C]//Proceedings of the 7th International Conference on Data Mining. Las Vegas, Nevada, USA, 2011. (0) |