一种基于小生境的负相关神经网络集成算法

盛伟国，单鹏霄

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)



一种基于小生境的负相关神经网络集成算法

盛伟国，单鹏霄

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

提出了一种基于小生境的负相关神经网络集成算法.所提方法结合了负相关学习和进化算法，采用同时训练的方式对多个神经网络进行训练，不仅能使网络之间产生有效的差异度，而且能促进网络之间的交互性和合作性.此外，在进化过程中引入了一种改进的小生境技术，能更有效地维持网络种群的多样性，从而保证神经网络集成的差异度.所提方法在6个分类数据集上进行了测试，并且与一些相关神经网络集成方法进行对比.实验结果表明所提方法能得到一个有效的神经网络集成.

神经网络；集成学习；负相关学习；小生境；进化算法

神经网络(Neural network)方法已经广泛地应用于许多领域[1-2]，但是依然存在诸多问题.例如，神经网络在训练过程中很不稳定，且容易陷入局部最优等，这都将限制神经网络的泛化能力.当训练的神经网络框架越大时，上述问题表现得越为严重.Hansen等[3]于1990年开创性地提出了神经网络集成(Neural network ensemble)方法，即组合多个训练好的神经网络，这种方法能有效地提高神经网络的稳定性和泛化能力.理论和实验结果[4-5]进一步指出一个有效的神经网络集成方法不仅要提高集成中单个网络的精确度，而且要使网络之间产生差异度，差异度是指个体网络位于相同输入的不同部分的误差.迄今为止，已经有大量的方法被提出致力于构造个体网络精确度高且个体网络间差异度大的神经网络集成.其中大多数方法采用独立训练方式和顺序训练方式对集成中个体网络进行训练，如Bagging[6]和Boosting[7]方法.然而，Liu等[8]提出了一种负相关学习方法，采用同时训练方式训练集成中的网络，并且在每个网络的误差函数中加入一个相关性的惩罚项，该惩罚项能使个体网络之间生成负相关的误差.因为负相关学习方法能使个体网络间产生有效的差异度，所以受到了很多关注和发展[9-10].研究指出负相关学习方法与进化算法相结合具有更好的性能.如Liu等[11]提出了负相关学习与进化算法相结合的方式来训练神经网络集成.Chandra等[12]提出了Diverse and accurate ensemble learning algorithm (DIVACE)用于训练神经网路集成,在DIVACE中使用了多目标进化算法(Multi-objective evolutionary algorithm).这些算法不仅能促进神经网络集成的差异度，而且能鼓励集成中个体网络的合作.然而，使用传统的进化算法[13]存在一些严重的问题，容易发生“早熟”或非全局性收敛等，这会导致进化过程中网络之间的差异度得不到很好的维持，最终影响神经网络集成的性能.因此如何在进化过程中维持种群内的多样性是至关重要的.

鉴于上述的研究状况，笔者提出了一种基于小生境的负相关神经网络集成算法，结合了负相关学习方法和进化算法，并在此基础上又引入了一种改进的小生境技术[14-15]，能更有效地维持种群的多样性，确保神经网络集成的差异度.

1 基于小生境的负相关神经网络集成算法

所提方法使用了负相关学习方法对多个神经网络同时训练，使个体网络之间存在负相关性；同时，结合了进化算法，并且引入了一种改进的小生境技术维持种群的多样性，保证了神经网络集成的差异度.算法的具体步骤如下：

Step 1 初始化神经网络种群，采用了随机初始化的方式对每个网络框架内隐结点数量和权值进行赋值.

Step 2 计算种群中每个网络的适应度值，适应度值为网络误差的倒数.

Step 3 将种群中所有个体网络进行组合构造成神经网络集成，并且计算神经网络集成的泛化误差E，如果E

Step 4 使用改进的小生境方法选择个体进行交叉和变异操作.

Step 5 计算每个网络负相关学习的泛化误差Ei，并使用BP算法对网络内的权值进行优化调整.

Step 6 合并父代和子代，使用轮盘法选择个体生成新的种群，返回至Step 3.

1.1 编码方式

1.2 遗传操作

为了减轻单点交叉操作带来的permutationproblem，所提方法采用双点交叉操作，具体实现过程分别为

P1：

P2：

其中：P1和P2分别为父代个体，分别包含3个隐节点和4个隐节点.在交叉操作过程中，P1的第1个隐节点的权值与P2的第2个隐节点的权值进行交换，产生子代off1和off2，即

off1：

off2：

对于突变操作，所提算法采用了三种类型用于增加网络框架的多样性，包括：权值的高斯突变、节点间链接的删除和节点间链接的增加.

2 负相关神经网络集成算法

集成学习的相关理论分析指出，平衡集成中个体的精确度和个体间的差异度是至关重要的.对于该问题，负相关学习方法是一种有效的神经网络集成算法.

2.1 集成学习的理论分析

对于回归问题的集成学习，Krogh等[16]提出了Ambiguity分解，并且通过该分解给出了集成学习的泛化误差公式为

fens(x))2

(1)

(2)

从式(1)中可以看出：集成学习的泛化误差取决于个体的泛化误差和集成的差异度.因此要降低集成的泛化误差，必须尽量减小个体的泛化误差，同时增大集成中个体的差异度.不幸的是提高集成中个体的精确度必然降低个体间的差异度，反之亦然.因此，如何平衡集成中个体的精确度与个体间的差异度的关系仍是一个研究难点和热点.关于分类问题的集成学习，毫无疑问存在相同的问题.对于该问题，负相关学习是一种很有潜力的方法.

2.2 负相关学习

假设给定一个训练集T，T={(x(1),t(1)),(x(2),t(2)),…,(x(n),t(n))},其中x为网络的输入，t为网络的期望.

Step 1 计算整个神经网络集成的输出F(n)，其表达式为

(3)

式中：M为集成中成员网络的数量；Fi(n)为成员网络i在第n个训练样本上的输出；F(n)为集成在第n个训练样本上的输出.

Step 2 计算第i个成员网络的误差函数，其表达式为

(4)

式中：第一项为第i个成员网络在训练集上的误差；第二项是相关惩罚项，λ(0≤λ≤1)是惩罚项的参数，用于调整惩罚强度；最小化Pi的目的是使每个网络与集成中剩余的网络产生负相关的误差，相关惩罚项的计算方法为

(5)

Step 3 使用BP算法和引入了惩罚项的新误差函数来训练神经网络并调整权值.

3 小生境技术

在使用进化算法训练神经网络集成时，保证种群中个体网络间存在差异度是至关重要的.该问题的关键在于怎样从上一代种群中选择具有差异度的个体网络.小生境技术[14-15]能够维持种群的多样性并且允许算法扩大搜索的范围.因此，所提方法引入一种改进的适应度共享机制的小生境技术[17-18]，能更好地维持网络种群的多样性，从而保证神经网络集成的差异度.改进的小生境技术优点：1)采用自适应的方式设置共享半径δs；2)维持种群中网络框架的多样性；3)鼓励相似的个体网络进行竞争.

传统的适应度共享机制的小生境技术根据个体网络之间的相似程度，将整个网络种群划分成一系列的小生境群体，然后利用适应度共享机制对每个小生境群体中的个体网络的适应度进行重新调整，从而降低相似的个体网络的选择概率.适应度共享机制的具体操作如下：

首先给定一个共享函数sh(dij)，用于计算小生境群体中个体网络之间的距离.在使用小生境维持神经网络种群的过程中，如何计算两个网络之间的距离尤为重要，因为网络之间的距离代表着网络之间的差异度，使用合适的方式计算距离能使进化过程有效地维持网络种群内个体网络间的差异度.在所提方法中使用如下公式来计算个体网络之间的距离为

(6)

式中：N为训练样本数量；fi(xn)和fj(xn)分别为个体网络i和个体网络j在第n个样本上的输出.

然后计算小生境群体的共享度，共享度是指个体网络与小生境内剩余个体网络之间共享函数的总和sh，其表达式为

(7)

式中：m为种群中个体网络的数量；dij为网络i和网络j之间的距离；sh(dij)为共享函数，计算式为

(8)

式中δs为共享半径.如果两个网络的相似度大于δs，那么它们不存在共享适应度;当两个网络之间的相似度小于δs才能共享适应度.

最后基于共享度重新调整种群中网络的适应度值，计算方式为

(9)

式中：fsi为网络共享后的适应度；fi为网络共享前的适应度.

传统的适应度共享机制的小生境方法存在一个严重的问题，共享半径需要被人为提前设定.然而，在很多应用中无法得到适应度搜索空间的先验知识，所以不能有效预先设定一个合适的共享半径.为了克服该问题，笔者采用了自适应的方式设定共享半径δs，其表达式为

(10)

式中：m为种群中个体网络的数量；dij为网络i和网络j之间的距离.

在进化过程中，维持个体网络框架的多样性也是很有必要的.因为神经网络的性能在很大程度上取决于网络框架，尤其是网络框架中隐节点的数量.不同框架的个体网络拥有不同的学习能力，可以促进个体网络间产生差异度.为此，在初始化过程中，采用随机方式初始化网络框架中的节点数量，并且使用了双点交叉的方法.在交叉过程中，两个含有相同或不同隐节点数量的网络都会被允许交换隐节点的权值，从而维持网络框架中隐节点数量的多样性.此外，由于相似度远的个体网络进行交叉往往会导致生成表现型差的后代，所以改进的小生境技术鼓励相似度近的个体网络进行交叉操作.具体实现过程：在选择交叉过程中，首先种群随机选取一个网络P1，然后在种群中随机选择若干个体网络组成一个交叉池，在这里交叉池中个体数量设为3，最后在交叉池中选取与P1最相似(距离最小)的网络P2进行交叉.通过使用改进的小生境技术，能够更好地维持种群的多样性，并且促进搜索更优的个体网络.

4 实验与分析

实验过程选择了Australian credit card，Diabe-

tes，Glass，Breast cancer，Image和Heart 6个分类数据集进行测试，这些数据集来源于The university of california at irvine (UCI) machine learning repository，并且有着不同的特征，如表1所示.

表1 6个分类数据集的特征

在实验测试过程中，采用了10-fold交叉验证方法，先将每个数据集分成数目相同的10子集，每次训练网络时，循环选择其中的9个子集用于训练，剩余1个子集用于测试.下述的实验结果是在数据集上独立运行30次然后取其平均值.此外，在实验过程中还有一些参数需要被提前设置，种群大小为30，隐结点的初始值范围为3～15，权值的初始范围为-1～1，神经网络集成的泛化误差为0.05.负相关学习中，惩罚项参数λ=0.8，BP算法的学习率和学习动量分别为0.3和0.8.实验中使用的这些参数值并不意味着是最优值.

所提方法先在Australian credit card和Diabetes这两个数据集上进行测试，并观察神经网络集成的分类错误率的变化.如图1所示，所提出的方法能在进化20代后就得到一个分类错误率较低的神经网络集成，这说明所提出的方法能快速设计一个有效的神经网络集成.

图1 笔者方法在2个数据集上的分类错误率变化Fig.1 The variance of two classification error rate on two data sets of this method

为了进一步证明所提方法的有效性，实验测试了一些相关的神经网络集成方法，如Bagging，Boosting和传统的负相关学习，并且将其实验结果进行对比.这些实验结果的对比的目的不是为了说明所提方法优越于其他方法，而是为了对所提方法有一个更深入的了解.

表2列出了4种方法在6个数据集上的实验结果，表中可以看出，在所有实验的数据集上所提方法取得了最低的分类错误率.传统的负相关学习方法的性能有效地被提高.如传统的负相关学习方法在Glass数据集上分类错误率为0.312，所提方法的错误分类率为0.269，提高了0.053.这是因为所提方法加入了基于改进的小生境算法，能有效地维持神经网络集成的差异度.与Bagging和Boosting方法相比，所提方法能有效地提高神经网络集成的泛化能力.如Bagging和Boosting在Australian credit card上的分类错误率分别为0.148和0.157，所提方法的分类错误率为0.121.原因在于所提方法通过结合了负相关学习和进化算法同时多个训练神经网络，使网络之间进行信息交流和合作，产生有效的差异度.

表2 4种神经网络集成方法在6个数据集上分类错误率的比较

Table 2 Comparing the classification error rate of four methods on six classification problems

5 结 论

笔者提出了一种基于小生境的神经网络集成算法，用于提高神经网络集成的泛化能力.所提方法集合了负相关学习和进化算法，促进了集成中个体网络之间的交互性和合作性.此外，引入了一种基于共享适应度的小生境技术，用于维持网络种群在进化过程中的多样性，保证了神经网络集成的差异度.实验证明，所提方法具有很好的泛化能力.下一步研究工作主要是如何合适地设置负相关学习中惩罚项的参数来平衡神经网络集成中的精确度和差异度，提高负相关学习的能力.

[1] 吕刚，郝平.基于神经网络的数字验证码识别研究[J].浙江工业大学学报，2010，38(4):433-436.

[2] 张洪涛，计时鸣.基于改进的BP神经网络钢板表面缺陷分类算法研究[J].浙江工业大学学报，2010，38(4):388-390.

[3] HANSEN L K， SALAMON P. Neural network ensembles[J]. IEEE transactions on pattern analysis & machine intelligence，1990，12(10):993-1001.

[4] 傅向华，冯博琴，马兆丰,等.一种异构神经网络集成协同构造算法[J].小型微型计算机系统，2005，26(4):641-645.

[5] ISLAM M M， XIN Y， MURASE K. A constructive algorithm for training cooperative neural network ensembles[J]. IEEE transactions on neural networks，2003，14(4):820-834.

[6] BREIMAN L. Using iterated bagging to debias regressions[J]. Machine learning，2001，45(3):261-277.

[7] FREUND Y， SCHAPIRE R E. A decision theoretic generalization of on-fine learning and an application to boosting[J]. Journal of computer & system sciences，1997，55(1):119-139.

[8] LIU Y， YAO X. Ensemble learning via negative correlation[J]. Neural networks，1999，12(10):1399-1404.

[9] 谢铮桂，韦玉科，钟少丹.基于负相关神经网络集成算法及其应用的研究[J].计算机应用与软件，2009，26(10):27-29.

[10] 周志华，陈世福.神经网络集成[J].计算机学报，2002，25(1):1-8.

[11] LIU Y， YAO X. Simultaneous training of negatively correlated neural networks in an ensemble[J]. IEEE transactions on systems man & cybernetics part B cybernetics，1999，29(6):716-725.

[12] CHANDRA A， YAO X. Ensemble learning using multi-objective evolutionary algorithms[J]. Journal of mathematical modelling & algorithms，2006，5(4):417-445.

[13] EIBEN A E， MICHALEWICZ Z， SCHOENAUER M， et al. Parameter control in evolutionary algorithms[J]. IEEE transactions on evolutionary computation，1999，3(2):124-141.

[14] SARENI B， KRAHENBUHL L. Fitness sharing and niching methods revisited[J]. IEEE transactions on evolutionary computation，1998，2(3):97-106.

[15] 董辉，黄胜.二维排样中小生境粒子群算法的研究与应用[J].浙江工业大学学报，2014，43(3):257-259.

[16] KROGH A， VEDELSBY J. Neural network ensembles， cross validation， and active learning[J]. Advances in neural information processing systems，1995，7:231-238.

[17] 崔挺，孙元章，徐箭,等.基于改进小生境遗传算法的电力系统无功优化[J].中国电机工程学报，2011，31(19):43-50.

[18] KIM K J， CHO S B. Evolutionary ensemble of diverse artificial neural networks using speciation[J]. Neurocomputing，2008，71(7/8/9):1604-1618.

(责任编辑：刘 岩)

Negative correlation neural network ensemble based on a niching algorithm

SHENG Weiguo， SHAN Pengxiao

(College of Computer Science and Technology， Zhejiang University of Technology， Hangzhou 310023， China)

This paper proposes a niching evolutionary algorithm with negatively correlation learning (NCL) for training neural network (NN) ensemble. The proposed algorithm combining NCL with evolutionary algorithm trains simultaneously the NN individuals in the ensemble, which not only can create the diversity among the NN individuals, but also helps to promote the interaction and collaboration among the NN individuals. In addition, an improved niching method is introduced for preserving the diversity of population during training, thus ensure the diversity of the NN ensemble. The proposed algorithm is evaluated on six classification problems and compared with related ensemble learning algorithms. The experimental results show that the proposed algorithm can be used to design a satisfactory NN ensemble.

neural network; ensemble learning; NCL; niching; evolutionary algorithm

2016-03-11

国家自然科学基金资助项目(61573316)；浙江省自然科学基金资助项目(LY15F020032)

盛伟国(1977—)，男，浙江温州人，教授，博士，研究方向为智能算法和数据挖掘，E-mail：wsheng@zjut.edu.cn.

TP391

A

1006-4303(2016)05-0482-05