庞 俊，黄 恒，张 寿，舒智梁，赵宇海

1.武汉科技大学计算机科学与技术学院，武汉430070

2.智能信息处理与实时工业系统湖北省重点实验室，武汉430070

3.东北大学计算机科学与工程学院，沈阳110169

1 引言

演化算法（evolutionary algorithms，EA）是一类启发式优化算法，通过变异繁殖和优势选择模拟自然的演化，能有效解决全局搜索优化问题[1-2]。目前，演化算法和分析方法的结合是机器学习领域的一个研究热点[3-5]。文献[3]采用演化算法和决策树算法相结合，优化了生成的股票选择模型。文献[4]将社交网络表示为一个无加权的无向图，并使用不同节点的自适应算法从节点角度分析社交网络的演化，提升了预测性能。

作为一种基于种群迭代的演化算法，差分进化算法通过个体的变异、交叉和选择，使种群向更好的方向进化，具有简单易用、鲁棒性高和较强全局寻优能力等优点[6-7]。此外，针对大多数数值函数的优化问题，DE（differential evolution）算法在收敛速度和稳定性方面均优于其他演化算法[8-9]。因此，本文研究将DE与基于ELM的半监督分类算法相结合，优化ELM的网络参数，提高算法性能。该问题的研究刚刚起步，已报道的相关工作很少。文献[10]采用协同训练（tri-training）技术实现了多个ELM（extreme learning machine）基分类器的协同训练，然后采用标准的DE算法进行优化，得到了一种半监督分类算法Tri-DE-ELM（tritraining-DE-ELM）；虽然分类准确率有提高，但是分类准确率尚不够高，不能完全满足市场决策的需求。

针对上述问题，本文提出了一种基于DE和ELM的半监督分类方法（semi-supervised classification algorithm based on DE and ELM，DE-ELM-SSC），选择适合目标数据集的差分进化策略，实现了分类准确率的提高。由于不同种类的进化策略一般适宜不同函数特征的应用场景[6]（例如：单峰函数适合采用de/best/1策略，多峰函数适合采用de/rand/1策略），且不同数据集有可能具有不同的函数特征，因此针对不同数据集，宜采用与数据集特征相适应的进化策略，以增强ELM网络参数优化效果。DE-ELM-SSC的简要步骤是：首先于预处理阶段针对目标数据集离线选出最优进化策略：以均方根误差（root mean square error，RMSE）为评价标准，从de/rand/1、de/best/1、de/best/2这3种具有代表性的进化策略中选出最优的策略；然后，将上一步选出的最优进化策略应用于DE算法，从而达到优化ELM网络参数的目的；最后，将优化后的ELM作为基分类器，与Tri-training技术[11]相融合，生成半监督分类预测模型。DE-ELM-SSC和Tri-DE-ELM均采用了DE和协同训练技术，分别优化了ELM网络参数和实现了半监督分类，但是DE-ELM-SSC从多种典型差分进化策略中选择出最适合目标数据集的策略，用于差分进化，获得了比Tri-DE-ELM更强的网络参数优化能力。

虽然通过使用策略选择技术，DE-ELM-SSC算法获得了比Tri-DE-ELM算法更高的分类准确率。但仍存在不足：固定缩放因子F值为1。首先，“1”超出了F取值的经验范围。根据文献[12]的研究，一般情况下，F的最佳取值范围为[0.2，0.9]；但当优化问题含有10个以上变量时，F的最佳取值范围为[0.2，0.6]。其次，缩放因子应当能自适应调整。缩放因子对差分进化算法的优化能力有较大影响：如果缩放因子过小，存在降低种群多样性和容易导致早熟收敛的问题；反之，种群迭代后期容易在最优解附近徘徊，导致搜索速度慢，求解精度低。为了达到较为理想的效果，缩放因子应采用自动调整的方式进行取值。

针对上述不足，本文采用缩放因子自适应方法，在差分进化算法种群迭代过程中，调整缩放因子的取值，从而加快收敛速度并提高网络参数的寻优能力。不失一般性，本文采用了文献[13]提出的一种惯性策略方法，并优化了自适应函数，实现了缩放因子自适应，从而得到了DE-ELM-SSC的一种改进算法DE-ELMSSC+。原惯性策略方法基本思想是：为了保持种群多样性从而有利于全局搜索，在种群迭代初期使F取较大值；为了利于局部搜索并提高收敛速度，种群迭代后期F取较小值；迭代过程中，F取值线性逐代缩小。为取得更好的寻优效果，本文将迭代过程中的F取值按非线性方式逐代缩小：为了更好地保持种群多样性，种群迭代初期，F取值缩小速度比线性的慢；为了更快地收敛，种群迭代后期，F取值缩小速度比线性的快（详情参见第4章），与DE-ELM-SSC方法相比，DE-ELM-SSC+算法任意选取并改进一种现有缩放因子自适应方法，进一步增强算法网络参数的优化能力。本文提出的算法经扩展，可以解决多分类问题。

本文的主要贡献如下所示：

（1）提出了一种基于DE和ELM的半监督分类方法DE-ELM-SSC。针对不同目标数据集，选择合适的差分进化策略，优化了ELM的网络参数。

（2）采用非线性方法改进现有的一种基于惯性策略的缩放因子自适应方法，进而优化了DE-ELMSSC算法。并分析了策略选择、DE-ELM-SSC算法和改进的DE-ELM-SSC算法的关键步骤的时间复杂度。

（3）在5个UCI标准真实数据集上进行了大量的实验，验证了本文提出方法的有效性。

2 相关工作

2.1 差分进化算法

差分进化算法是由Storn和Price[8]于1995年提出的一种演化算法，被认为是最有效的演化算法之一。DE算法的数学问题可以形式化描述为：minf(x),x=[x1,x2,…,xd],pj≤xj≤qj，其中j=1,2,…,d，d是解空间维数；pj和qj分别表示变量x第j维的上界和下界。差分进化算法是基于种群迭代的随机搜索算法，其基本思想[6]是通过种群个体的变异、交叉和选择，使种群向更好的方向进化，从而逼近问题最优解。

为适应不同类型的优化问题，Price和Storn先后提出了10种不同策略差分进化算法[14]。由于出色的寻优能力，差分进化算法已成功应用到许多科学和工程领域[15-17]。缩放因子是用于控制变异过程中差异矢量的缩放程度，在差分进化算法中有至关重要的作用。于是，大量关于缩放因子自适应的方法被提出，产生了许多DE算法的变体[18-19]。本文根据目标数据集，从de/rand/1、de/best/1和de/best/2这3种具有代表性的策略中进行策略选择。此外，不失一般性，选择了一种惯性策略方法实现缩放因子自适应，并且通过非线性方法对其进行了改进。

2.2 基于超限学习机的半监督分类

超限学习机[20]是Huang等人提出的一种单隐层前馈神经网络，通过随机初始化输入层到隐层神经元的输入权重和隐层偏置，采用最小二乘法求解隐层神经元到输出节点之间的输出权重，实现全局逼近。其数学模型可以表示为：j=1,2,…,N。wi表示输入层到第i个隐层节点的输入权重，bi表示第i个隐含节点的偏置，βi表示第i个隐含节点的输出权重。相对于采用梯度下降迭代调整网络权值参数的传统神经网络算法，由于不需要对神经元网络参数进行调优，超限学习机具有学习速度快的特点[21-22]。原始超限学习机[20]为解决有监督学习问题而设计，不适合处理半监督学习问题。因此基于超限学习机的半监督分类算法应运而生[23-28]。

现有基于超限学习机的半监督分类方法根据实现方式的不同主要分为两类：基于图的方法[23-27]和基于差异化协同训练方法[10,28]。第一类方法通过构造图模型（将样本作为顶点），计算顶点之间的相似度，用有标签的样本信息预测无标签样本的信息，从而实现基于ELM的半监督分类。文献[24]提出了SSELM（semi-supervised ELM）算法，通过构造图的拉普拉斯正则化来解决多分类问题。虽然SS-ELM能利用无标签数据辅助分类，但忽略了无标签数据间的成对约束。因此，文献[25]实现了一种基于ELM的流形和成对约束正则化的半监督分类。文献[26]针对SS-ELM对异常值敏感的问题，提出了RSS-ELM（robust SS-ELM）算法，采用非凸平方损失函数增强算法的鲁棒性。文献[27]通过结合SS-ELM方法与ZGS（zero-gradient-sum）分布式优化策略，提出了DSS-ELM（distributed SS-ELM）算法，解决了时变通信网络中分布式的半监督学习问题。第二类方法通过有标签数据训练多个ELM基分类器对无标签数据进行标记，将置信度高的无标签数据加入到有标签数据中扩大有标签数据集。文献[28]通过co-training方法从无标签数据中获得置信度高的数据并打上标签，逐步扩大已标记的训练集，从而实现ELM的半监督分类。虽然方法比较简单，但需要两个视图充分且条件独立。文献[10]提出了一种基于协同训练、差分进化与ELM的半监督分类方法（Tri-DE-ELM），解决半监督分类问题。Tri-DE-ELM先采用差分进化方法改进ELM，达到优化ELM算法中网络参数随机取值的目的；然后将改进后的ELM算法作为基分类器，采用协同训练技术，实现了半监督分类算法。Tri-DE-ELM是目前最新的将演化计算和基于ELM的半监督分类相结合的算法，取得了较高的分类准确率。但是其分类准确率尚不够高，不能完全满足市场决策的需求。第一类方法适用于相似特征的数据点趋向于在同一个类别内的情况；第二类方法适用于数据特征具有天然的子集划分的情况[29]。Tri-DEELM是第二类方法，也是研究演化计算和基于ELM的半监督分类算法结合的最新方法。本文提出的方法虽然与Tri-DE-ELM都使用了DE和Tri-training技术，但是本文采用了策略选择和改进的缩放因子自适应算法来优化ELM算法的随机网络参数，从而进一步提高了算法的分类准确率。

3 DE-ELM-SSC算法

3.1 算法概述

DE-ELM-SSC首先进行预处理，选择差分进化策略；然后将选出的策略应用于标准的DE算法，增强对ELM网络参数优化效果，接着无缝融合Tritraining算法实现3个基分类器的协同训练，构造半监督分类预测模型。其算法概述如图1所示。

DE-ELM-SSC算法包含两个阶段：（1）预处理阶段，选择差分进化策略；（2）训练阶段，构建预测模型（测试阶段因过程类似而未进行介绍）。预处理阶段针对给定数据集，从de/rand/1、de/best/1和de/best/2进化策略中选出与数据集相适应的最优策略，主要包括两步：获取有标签训练数据集L、验证数据集V和计算不同策略的均方根误差与策略选中次数。第一步采用随机采样的方法将给定数据集中的有标签数据集D均分成有标签训练数据集L和验证数据集V。第二步采用均方根误差的值作为不同策略在数据集上的性能评价指标，在训练数据集L上分别训练采用de/rand/1、de/best/1和de/best/2差分进化策略的ELM模型；然后，分别用获得的3个模型在验证数据集V上进行标签预测，通过与验证数据集V的真实标签比较，计算各模型在验证数据集的均方根误差。均方根误差值越小，性能就越好，获得均方根误差最小的策略被选中次数加1。通过125次独立重复选择实验（为了实验结果稳定，进行了125次实验）将选中次数最多的策略作为最终的进化策略并输出（详情见3.2节）。

训练阶段基于Tri-training思想，首先将前一阶段选出的最优进化策略用于差分进化算法，然后用该差分进化算法优化ELM，接着以优化后的ELM（extreme learning machine based on strategy selection and differential evolution，SS-DE-ELM）为基分类器生成半监督分类预测模型。简言之，首先通过重采样从有标签数据L采集3个子数据集，并分别训练出3个基分类器（SS-DE-ELM）；然后通过给定数据集中的无标签数据U迭代更新基分类器，当达到迭代停止条件时终止迭代，得到由3个稳定的基分类器构成的预测模型（具体步骤见3.3节）。

Fig.1 Overview of DE-ELM-SSC algorithm图1 DE-ELM-SSC算法概述

3.2 策略选择

策略选择（strategy selection，SS）旨在从多种差分进化策略中选出适合已知数据集的策略。其基本思想是：由于不同策略有不同的使用场景，因此采用常用的均方根误差作为评价指标（均方根误差值越小，策略优化的性能越好），进行进化策略的选择。具体而言，每次实验计算并比较不同策略的均方根误差，其中均方根误差值最小的策略是当前实验的最优策略。通过多次独立实验，统计各策略被选中次数，获得被选中次数最多的策略，即最终所求的目标策略。若存在两种策略被选中次数相同且同为最大值的情况，则选择均方根误差总和最小的策略。其算法伪代码如算法1所示。

算法1策略选择

首先获取验证数据集V和有标签训练数据集L：采用随机取样的方法从有标签数据集D中抽取1/2数量的样本组成V，剩余样本构成L（步骤1）；然后，在有标签训练数据集L上，训练3个分别采用de/rand/1、de/best/1和de/best/2差分进化策略的DE优化后的ELM模型；接下来，用训练得到的3个模型在验证数据集上进行计算，获得预测结果；计算预测结果与验证数据集真实标签结果的均方根误差，分别统计采用3种不同策略的模型在验证数据集上的均方根误差，将均方根误差最小的策略的被选中次数Cj（j=1,2或3）增加1次（C1、C2和C3分别表示de/rand/1、de/best/1和de/best/2被选中的次数），循环125次（设置1 000、500、250、125、64和32等不同次数进行实验，结果表明当次数在125及以上时结果比较稳定，因此进行了125次实验），得到各策略的均方根误差总和为Sumj（j=1,2或3）（步骤2～步骤8）。如果Cj是被选中次数中唯一的最大值，则返回Cj对应的策略作为输出（步骤9）。如果Cj和Ck同时是被选中次数的最大值，则比较它们的均方根误差总和Sumj与Sumk，输出其中较小者对应的策略（步骤10）。由于总次数125不能被3整除，因此不存在C1、C2和C3同时取最大值的情况。此外由于神经元网络的参数是随机生成的，并且均方根误差的总和可计算到小数点后10位，因此Sumj=Sumk（j≠k）取值相同的概率趋近于0（SS算法的示意图如图2所示）。

例1已知一个有标签数据集D，从D中随机抽取一半数据V作为验证数据集，剩下数据作为有标签训练数据集L，使用数据集L分别训练采用de/rand/1、de/best/1和de/best/2这3种进化策略的DE-ELM算法，获得3个预测模型H1、H2和H3。然后分别计算H1、H2和H3在验证数据集V上的均方根误差R1、R2和R3。假设R1=min{R1,R2,R3}，则R1对应的进化策略de/rand/1被选择。如此重复125次，假设策略de/rand/1被选择次数为100次（即唯一的最大值），那么最终被选择的进化策略是de/rand/1。假设策略de/rand/1与de/best/1被选择次数都是60次（即同时为最大值），且de/rand/1的均方根误差总和小于de/best/1的均方根误差总和，那么最终被选择的进化策略是de/rand/1。

Fig.2 Illustration diagram of strategy selection图2 策略选择示意图

接下来分析策略选择算法关键步骤的时间复杂度。策略选择包含两大关键步骤：使用传统ELM算法计算输出权重β和使用DE算法优化ELM网络参数。对于传统ELM算法计算输出权重β，其时间复杂度为O(l3d+Nl2d+Nlmd+d)[30]。其中，l表示隐层神经元个数，d是输入样本向量的维度，N为给定训练样本的数量，m表示样本类标签向量的维度。对于第二大关键步骤，设种群规模大小为N2，最大迭代次数为G。使用DE算法优化ELM网络参数需要经过多次迭代，其中1次迭代又包含3个关键步骤：（1）对种群所有个体进行变异产生新个体，其时间复杂度为O(N2(dl+l))[31]；（2）对所有变异的个体和与之对应的当前个体进行交叉获得新的个体，其时间复杂度为O(N2(dl+l))[31]；（3）计算所有交叉后获得的新个体在ELM算法中的输出权重的范数和在训练数据集上的RMSE，并在交叉后获得的新个体和与之对应的当前个体之间进行选择；将选择结果作为下一代个体，从而得到下一代种群。根据策略选择算法，容易分析出：单个个体在ELM算法中获得输出权重范数的时间复杂度为O(l3d+Nl2d+Nlmd+d+lm)，单个个体在训练数据集上RMSE的计算时间复杂度为O(Nm)，步骤3的时间复杂度为O(N2(l3d+Nl2d+Nlmd+d+lm+Nm))。此外，最坏情况下，需要迭代G次。则使用DE算法优化ELM网络参数的时间复杂度为O(GN2(l3d+Nl2d+l(Nmd+m+2d+2)+Nm+d))，可简化为O(GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d))。

3.3 算法内容描述

本节采用Tri-training对SS-DE-ELM进行协同训练得到DE-ELM-SSC算法。其基本思想是：首先根据已知有标签数据集分别计算de/rand/1、de/best/1、de/best/2对应的RMSE，实现进化策略的选择；然后通过重采样的方法从有标签数据集获取3个子集训练，并以SS-DE-ELM为基分类器，通过Tri-training算法构造由3个稳定分类器组成的预测模型。DEELM-SSC算法的伪代码如算法2所示。

算法2DE-ELM-SSC算法

首先，根据算法1从de/rand/1、de/best/1和de/best/2策略中选出较为合适的策略C（步骤1），使用策略选择后的DE算法优化ELM，获得使用策略C的SS-DE-ELM算法，简称H（步骤2）。然后，从有标签训练数据重采样得到3个子集L1′、L2′和L3′，并分别在L1′、L2′和L3′上使用算法H学习得到3个不同的基分类器H1、H2和H3（步骤3、步骤4）。接着，以H1为主分类器，采用辅分类器H2和H3预测无标签数据集U的标签。将H2和H3模型预测结果相同的标签作为置信度高的标签，并打上标签。将具有置信度高的标签样本组成数据集L1，同时使用MeasureError(H2&H3)计算H2和H3模型在L上的分类错误率（在不引起歧义的前提下，下文简称为分类错误率）。MeasureError(H2&H3)=(H2与H3在L上预测结果相同且同时预测错误的样本数量)/(H2与H3在L上预测结果相同的样本数量)（预测错误的样本数量是指预测的标签类别与真实的标签类别不同的样本的数量）。为了保证引入的高置信度标签的可靠性，分类错误率初始值统一设置为0.5。若当前分类错误率比上一轮的小，则判定需要用L∪L1对主分类器H1进行更新；否则，则判定不需要。类似地，依次以H2、H3为主分类器进行处理。最后，对需要更新的基分类器进行更新，当通过分类错误率判定3个基分类器都不再需要更新时，认定Tri-training算法获得由3个稳定基分类器组成的预测模型，停止循环；否则，继续使用3个基分类器利用无标签数据进行迭代更新（步骤5～步骤13）。其中，步骤7～步骤11是用于遍历更新3个基分类器对应的置信度高的无标签数据集，进行判断和记录各基分类器是否需要更新。并根据记录信息对需要更新的分类器进行更新（步骤12）。最后，当所有基分类器不再更新（即达到稳定）时，获得基分类器的输出权重（步骤14）。

下文分析DE-ELM-SSC算法关键步骤的时间复杂度。DE-ELM-SSC算法主要包含3个关键步骤：（1）利用两个辅助分类器从大小为N3的无标签数据集中获得高置信度数据集。根据DE-ELM-SSC算法，可知计算两个辅助分类器模型的时间复杂度为O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d))，计算高置信度数据的时间复杂度为O(2N3lmd)。因此，该步骤的时间复杂度为O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d)+2N3lmd)。（2）使用MeasureError()函数计算辅助分类器的分类错误率，并与上一轮计算得到的分类错误率进行比较，从而判断是否需要用扩展后的数据集对主分类器进行更新。因为通过两个辅助分类器判断其分类错误率，因此该步骤时间复杂度为O(2GN2(l3d+Nl2d+l(Nmd+m+d+1)+Nm+d)+2Nlmd)。（3）若需要对分类器更新，则扩大后的数据集大小为N+N4（N4表示主分类器对应的高置信度数据集的大小）；然后利用扩大后的数据集对分类器进行更新。经分析，该步骤时间复杂度为O(GN2(l3d+(N+N4)l2d+l((N+N4)md+m+d+1)+(N+N4)m+d))。

4 DE-ELM-SSC+算法

缩放因子F(F∈[0,2])是DE算法中用于控制差异矢量的缩放程度，对算法收敛速度和求解精度有重要影响[8]。为了取得更优的优化效果，缩放因子取值应在迭代演化过程中变化[32]。不失一般性，本文采用了文献[13]提出的一种惯性策略自适应方法，并使用非线性方法进行改进：为了更好地保持种群多样性，种群迭代初期，F取值缩小速度比线性的慢；为了更快地收敛，种群迭代后期，F取值缩小速度比线性的快，获得一种非线性的缩放因子自适应方法。将该缩放因子自适应方法应用于DE-ELM-SSC中，提出一种改进的DE-ELM-SSC算法DE-ELM-SSC+，提高了DE-ELM-SSC算法性能。本文通过差分进化策略选择、缩放因子自适应调整和Tri-training技术融合等步骤实现了DE-ELM-SSC+算法。由于差分进化策略选择与Tri-training技术融合等步骤与DE-ELM-SSC相同，本章主要介绍缩放因子的自适应调整。

文献[13]提出的惯性策略方法基本思想如下：为了保持种群的多样性从而有利于全局搜索，在种群迭代初期使F取较大值；为了利于局部搜索并提高收敛速度，种群迭代后期F取较小值。迭代过程中，F取值按公式逐代缩小。Fmax为初始第0代时的缩放因子，Fmin为最后一代的缩放因子，t为当前种群进化到的代数，T是种群进化的最大代数。本文通过非线性方法改进迭代过程中F的取值，使其按以下公式逐代缩小：

根据假设条件，种群处于第0代个体时（即t=0），缩放因子取值为Fmax，可得：

并且根据假设条件，种群处于第T代个体时（即t=T），缩放因子取值为Fmin，可得：

等式（2）和等式（3）组成方程组（Ⅰ）：

求解方程组（Ⅰ），可得：

将方程组（Ⅰ）的计算结果代入等式（1），化简后得到改进后的自适应函数：

此外，由于Fmax和Fmin的取值将影响算法性能，因此本文设计了实验，寻找不同数据集的Fmax和Fmin的次优解。其基本思想是：首先确定F的取值范围，然后在取值范围内，通过验证数据集分类准确率确定不同数据集的次优Fmax和Fmin。因为F∈[0,2]且F＞1的情况很少出现[33]，所以本文将F取值范围设为[0,1]。首先将连续型变量F离散化，得到F的离散值取值范围{0.1,0.2,…,1.0}，然后在此范围内求解Fmax和Fmin的次优解：首先Fmin和Fmax在{0.1,0.2,…,1.0}中分别取值（Fmin≤Fmax），然后比较每组Fmin与Fmax条件下的训练模型在验证数据集上的准确率；准确率最高的组合相应的Fmin与Fmax为寻找的次优解。缩放因子取值固定，是自适应方法的一种特殊情况，即Fmin=Fmax。实验结果参见本文5.5节。

采用改进后的缩放因子自适应方法对SS-DEELM基分类器进行优化，相应算法的伪代码如算法3所示。

算法3采用缩放因子自适应的SS-DE-ELM算法

首先采用随机取样的方法从有标签数据集D中抽取1/2数量的样本组成验证数据集V，剩余样本构成有标签训练数据集L（步骤1）；然后随机生成由NP个个体组成的种群（一个个体表示神经元网络参数的一种随机取值），并计算每个个体的输出权重和均方根误差（步骤2、步骤3）；接着，在种群迭代更新之前，先根据公式计算当代缩放因子的值。再根据差分进化策略st进行变异、交叉和选择操作，种群不断迭代更新种群个体，直到到达种群最大迭代次数（步骤4～步骤9）。变异是指当前种群突变，下文以个体θi,g采用de/rand/1策略变异获得个体Vi,g为例讲述其过程：首先从种群中随机选择两个不同个体进行减法向量运算获取两者之间的差异向量，并用缩放因子对差异向量进行放大；然后随机从种群中选择第三个个体加上放大后的差异向量，获得变异后的个体Vi,g。交叉是为了增加干扰参数向量的多样性。对于N维个体，通过N个随机生成的0到1之间的随机数与交叉因子CR比较，决定交叉后新生成的个体ui,g的N个维度的取值。若第i维的随机数小于或等于CR，则将突变个体Vi,g的第i维赋值给ui,g的第i维；反之，将个体θi,g的第i维赋值给ui,g的第i维。选择操作是在当前个体θi,g与ui,g之间选择谁成为下一代个体。种群中交叉的个体ui,g能否成为种群的下一代，由个体的输出权重的范数与RMSE决定。交叉个体的输出权重范数比当代个体的输出权重范数小，或者交叉个体的RMSE取值更小，交叉的个体就作为种群的下一代个体。否则，当前个体保持不变作为下一代种群的个体（不同差分进化策略st变异的详细过程参考文献[6]）。最后返回种群的最优个体和该个体对应的输出权重。最优个体是优化后的ELM算法的输入权重和偏置参数（步骤10）。

例2对于给定的有标签数据集D，缩放因子最大值Fmax为0.6，最小值Fmin为0.2，神经元个数为30，种群大小为20，最大迭代次数为20。假设θ是第10代种群G中的某个个体，通过θ计算得到的网络输出权重的范数||βθ||为0.8，均方根误差为0.9。根据公式计算当代缩放因子F=0.6-(0.6-0.2)/(e-1)×(e10/20-1)≈0.448 9。θ经过变异和交叉产生个体u，然后进行选择产生下一代个体。若通过个体u计算得到的网络输出权值的范数||βu|||为1.1，均方根误差为1.0，则个体θ保持不变保留到下一代（1.1>0.8且1.0>0.9）。种群G中所有个体都进行变异、交叉和选择操作后，种群进化成为第11代种群，再重新计算缩放因子F=0.6-(0.6-0.2)/(e-1)×(e11/20-1)≈0.429 3，并重复变异、交叉和选择操作，更新种群直至满足迭代停止条件。最后返回种群G中的最优个体和与之对应的输出权重。

DE-ELM-SSC+的优点如下所示：（1）策略选择步骤从3种策略中选择一个性能较优且稳定的优化策略，使得网络参数的性能更优，从而使通过该网络参数训练得到的分类器性能更好；（2）改进的缩放因子自适应方法改善缩放因子取值固定的问题，优化差分进化对网络参数的局部和全局搜索，加速迭代并提高网络参数的搜索精度。由于DE-ELM-SSC+比DE-ELM-SSC仅多了计算缩放因子的步骤，且依等式（4）可知，缩放因子计算的时间复杂度是O(1)；因此DE-ELM-SSC+的关键步骤和其时间负责度与DEELM-SSC的相同。

5 实验与分析

本章首先介绍了实验数据集和实验环境，然后分别验证了本文提出算法的有效性。接着比较了各算法在不同比例的有标签数据下的准确率，并讨论了有标签数据量占比对分类准确率的影响，以及探索了不同数据集上缩放因子最大值Fmax与最小值Fmin的次优取值。最后研究了隐藏神经元个数对算法性能的影响。

5.1 数据集和实验环境

采用UCI数据集上的5个真实数据集进行实验：Australian Credit Approval（Australian）、Breast Cancer Wisconsin（Cancer）、Congressional Voting Records（Vote）、Wisconsin Diagnostic Breast Cander（Wdbc）和Mushroom（统计信息如表1所示）。表1中，L和U分别表示有标签训练数据集和无标签样本数据集，V和T分别表示验证和测试数据集，S表示所有数据的总和。本文实验代码采用Python编程语言，在如下配置的单机上运行：3.5 GHz CPU、8 GB内存、Windows7 64位操作系统和Python3.6.3。以最新的Tri-DE-ELM为baseline方法，并采用准确率（Accuracy）作为性能评价标准。Accuracy=（预测正确的样本数）/（预测的总样本数）。每次实验运行50次，报道平均实验结果。

Table 1 Datasets statistics表1 数据集统计信息

本文实验中测试数据占总数据的25%，训练数据占总数据的75%。训练数据由60%的有标签和40%的无标签数据U组成。随机抽取有标签数据D的50%作为验证数据集V，剩下50%作为有标签训练数据集L。本文所有实验中，如无特殊说明，算法参数均采用如下默认设置：差分进化的种群大小NP为20，变异因子CR为0.8，种群最大迭代次数Gmax为20。各算法在5个数据集上的神经元个数nh与缩放因子F的取值如表2所示。

Table 2 Number of neurons nh and scaling factor F表2 神经元个数nh 和缩放因子F

5.2 DE-ELM-SSC性能验证

文献[10]已在相同真实数据集上进行了大量实验，验证了Tri-DE-ELM算法的分类准确率高于ELM、DE改进后的DE-ELM、Tri-training优化后的Tri-ELM算法。因此为验证DE-ELM-SSC的有效性，比较了DE-ELM-SSC与Tri-DE-ELM算法的分类准确率。测试数据集的分类准确率结果如表3所示。从表3可知，在Wdbc、Mushroom和Australian数据集上，DE-ELM-SSC的分类准确率大于Tri-DE-ELM的；在Vote和Cancer数据集上，DE-ELM-SSC的分类准确率等于Tri-DE-ELM的。主要因为DE-ELM-SSC算法在Wdbc、Mushroom和Australian数据集上选择了与数据集自身相适应的进化策略de/rand/1、de/best/1和de/best/2；这些策略应用于ELM算法后，增强了ELM算法的寻优能力，进一步提高了基分类器的分类准确率，从而使最终算法取得了更高的分类正确率。由于DE-ELM-SSC在Vote和Cancer数据集上选出的进化策略与Tri-DE-ELM的一致（均为de/rand/1），因此它们的分类准确率相同。总之，选择适合不同目标数据集的进化策略，能增强网络参数寻优效果，实现分类性能的提升。

Table 3 Comparison of accuracy between Tri-DE-ELM and DE-ELM-SSC表3 Tri-DE-ELM与DE-ELM-SSC的准确率比较

5.3 DE-ELM-SSC+性能验证

本节在5个真实数据集上比较了DE-ELM-SSC与DE-ELM-SSC+在测试数据集的分类准确率和训练时间。实验结果如表4所示：与DE-ELM-SSC算法相比，DE-ELM-SSC+的训练时间更少，分类准确率更高。因为它采用了改进的自适应缩放因子策略，在种群迭代过程中既保持了初期种群的多样性，又加快了后期的收敛速度和搜索精度，进一步提高了基分类器SS-DE-ELM的分类准确率，从而提高了协同训练的分类准确率。因为策略选择在预处理阶段离线进行，所以表4中DE-ELM-SSC算法与DE-ELMSSC+算法的训练时间是从训练基分类器到构建分类预测模型的时间，而未包含策略选择所用时间。

Table 4 Strategy and classification accuracy comparison of two algorithms表4 两种算法选择策略和分类准确率比较

5.4 不同比例有标签样本对分类性能的影响

为检测不同比例有标签样本对提出算法的分类准确率的影响，从训练数据集中随机抽取30%作为验证数据集V，剩下70%数据作为训练数据L∪U。分别随机设置L∪U中20%、40%、60%和80%的数据作为有标签训练数据L，其余数据作为无标签训练数据U。Tri-DE-ELM与DE-ELM-SSC+在测试数据集上的分类准确率结果如表5所示。

表5表明随着有标签样本比例的增加，用于训练模型的数据增加，模型能够学到的信息越多，从训练数据中得到的模型的分类性能越来越好。本文以Australian数据集为例，当有标签数据为20%时，Tri-DE-ELM和DE-ELM-SSC+分类准确率分别为0.731 4和0.738 7；当有标签数据为80%时，它们的分类准确率上涨到0.802 4和0.812 3。相同条件下，因为进行策略选择和缩放因子自适应，DE-ELM-SSC+算法的准确率均高于Tri-DE-ELM。

5.5 Fmax 与Fmin 的求解

不失一般性，本节选择Mushroom数据集进行实验，说明求解Fmax与Fmin的过程。实验结果如表6所示。“—”表示对应的Fmin和Fmax取值组合不在讨论范围内。

表6表明缩放因子Fmax与Fmin的取值会对DE-ELM-SSC+分类准确率产生较大影响，不应固定为1。例如当Fmin=0.3，Fmax=0.5时，验证数据集和测试数据集的分类准确率分别为0.978 4和0.976 7。显然，其分类准确率大于固定F=1（即Fmin=Fmax=1.0）的0.944 7和0.945 6。由于当Fmin=0.3，Fmax=0.5时，验证数据集上的分类准确率取得最大值0.978 4，因此对于Mushroom数据集，Fmin取值为0.3，Fmax取值为0.5。此时，DE-ELM-SSC+算法的分类准确率相对于Tri-DE-ELM算法有较大提升。其他数据集的Fmax与Fmin求解过程与此类似，不再一一阐述。

Table 5 Classification accuracy comparison on datasets with different labeled proportions表5 不同比例有标签数据集上的分类准确率比较

Table 6 Classification accuracy comparison of different Fmax and Fmin表6 不同Fmax 和Fmin 的分类准确率比较

5.6 隐含层神经元个数性能评价

本节在Mushroom数据集上评估不同神经元个数对各算法分类准确率的影响。报道100次实验的平均结果。其实验结果如图3和图4所示。

Fig.3 Experimental results on training datasets with variable number of hidden neurons图3 不同隐含层神经元个数测试集上的实验结果

Fig.4 Experimental results on valid datasets with variable number of hidden neurons图4 不同隐含层神经元个数验证集上的实验结果

图3和图4显示：随着神经元个数的增加，Tri-DE-ELM、DE-ELM-SSC和DE-ELM-SSC+的准确率先不断增加，然后趋于稳定。当神经元个数在[5,38]范围内时，由于算法训练不充分，因此分类准确率随着神经元个数的增加而增加。当神经元个数在[38,40]范围内时，如果训练充分，训练和验证准确率均趋于平稳。对于相同的隐层神经元个数，DE-ELM-SSC+算法分类准确率高于Tri-DE-ELM和DE-ELM-SSC算法。因为DE-ELM-SSC+采用了策略选择和改进的缩放因子自适应技术。

6 结论

本文将差分进化演化算法与基于ELM的半监督分类方法相结合，提出了一种基于DE和ELM的方法DE-ELM-SSC，能有效处理半监督分类问题。针对不同差分进化策略适合不同数据特征数据集的特点，以均方根误差为选择标准，从多种典型策略中选出适合给定数据集的策略。并且，采用改进的缩放因子自适应方法对DE-ELM-SSC进行优化，得到DE-ELMSSC+方法。改进的非线性缩放因子自适应方法不但在差分进化的种群迭代初期保持了种群多样性，而且在种群迭代后期达到了局部精细化搜索的目的，从而进一步提高了分类准确率和加快了模型训练速度。5个真实数据集的大量实验结果表明，与Tri-DEELM相比，DE-ELM-SSC+具有更高的分类准确率。