低关联度的Boosting类集成算法研究

关 超，高敬阳，尚 颖

（北京化工大学 信息科学与技术学院计算机系，北京100029）

0 引 言

Boosting类算法和Bagging类算法是目前神经网络集成研究中个体网络生成方法最为流行的。其中Adaboost及其改进算法［1－4］的提出解决了Boosting类算法虽然能提高网络的泛化能力但稳定性差且很难运用于实际的问题，使得Boosting类算法在很多领域得到应用和改进［5－8］。

但Adaboost存在过分调整权值的问题，学者Chun－Xia Zhang提出的Local Boost方法采用局部误差计算方法，调整权值时更容易有区分的修改权值，能避免噪声数据权值的累积，因此在有噪声训练的情况下表现良好，甚至优于Bagging方法。但有学者研究发现，Local Boost这类动态调整权值的方法在采用不稳定的训练方法时有可能会陷入某局部最优解［9］。且由于采用了邻居算法，在一定程度上Local Boost的方法会使个体网络之间的差异度变小，网络之间的相关程度较高，学者通过引入Q－statistics统计方法来计算个体网络之间的相关度，相关度较高的集成在某些领域并不适用，其泛化能力较低［10］。

我们在实验过程中发现，Local Boost方法具有使局部表现较差的样本在迭代过程中显现出来的特性，容易将出现这类情况的网络丢弃，在迭代次数有限时易导致训练失败。Lazy Bagging方法采用邻居方法围绕测试样本生成训练样本集［11］，使网络对测试样本训练更有针对性，能很好地用于特定样本的识别，能生成足够的个体网络用于集成。

基于上述考虑，本文将Lazy Bagging选取训练样本的方法融入Local Boost算法，提出了Boosting类新算法BSE（boosting seeded ensemble）。BSE算法和Local Boost算法一样能使 “较难”样本通过计算邻居误差显现出来，引入Lazy Bagging选取训练样本的方法，采用 “较难”样本作为种子样本生成个体网络训练集。把生成的样本集针对“较难”种子样本做 “平滑”处理，即当 “较难”样本是噪声样本时，则该样本生成的训练样本集将弱化噪声对网络的影响，使整体网络的稳定性得到提高，并且使得并行训练成为可能，从而通过种子样所生成的训练样本集并非完全通过权值选取，随机性较高避免了Local Boost方法生成的个体网络之间高关联度的问题，且节省了训练时间开销。模型及相关度计算见第1章，利用Matlab及UCI数据集［12－14］验证新算法对比Local Boost方法在采用不稳定训练方法时迭代过程对样本过于敏感，易陷入局部最优解的实验及其分析见第2章。

1 模型及相关度计算

BSE方法继承了Local Boost能在迭代过程中通过局部误差计算方法找出那些 “较难”样本的特性，并将这些“较难”样本作为Lazy Bagging方法的测试样本，生成与其相关的训练样本集。

为了度量个体网络之间的相关度，我们引入了Q－statistics统计量，计算如下：设样本 （xl，yl）∈样本集Y，样本个数为N，分类器Ci与Ck之间的相关度统计量矩阵关系如表1所示。

表1 Q统计量个体网络相关

N＝A＋B＋C＋D，相关度Q统计量

针对M个个体网络的集成，相关度度量值定义为

BSE算法将权值高的样本作为种子样本，从训练集中选择K个邻居形成邻居子样本集，再由原始样本集中随机选取N－K个样本形成随机子样本集，两个子集构成了训练个体网络的样本集，具体如下：

设初始训练样本集L共包含 N个样本 ｛x1，x2...xN｝，每个样本x1的权值D （i）为1/N，样本输出为 ｛y1，y2...yN｝，其中yi＝ ｛－1，＋1｝，目标迭代次数为T，Ct为第t个网络，初始时t＝1。

迭代步骤：

（1）在L中挑选权值最大的M个种子样本 ｛S1，S2...SN｝。当t＝1（初始训练时）或上一轮训练失败时，在L中Lt＝L随机选取M个种子样本。

（2）针对种子样本Si挑选K个邻近样本组成子集subL1，选取方法如下：

定义1 迭代过程中较难识别样本的权值会增大，挑选时更容易被选到，样本xi与其邻居样本xj的加权距离

dis’（xi，xj）从邻居 Nei（xi）中选取 K个加权距离dis’（xi，xj）值最大的样本构成子集subL1。距离越近权值越大的样本越容易被选中。

再由L中随机挑选N－K个样本组成子集subL2，则针对种子样本Si的训练样本集L＝subL1∪subL2，i＝1，2…M，如此组成第t轮的训练样本集 ｛L1，L2...LN｝。

（3）将 ｛L1，L2...LN｝应用于训练子分类器，i＝1，2…M，将得到的M个子分类器集成

由于测试种子样本各不相同，所生成的测试样本集之间互相独立，因此在第一次结果集成时得到的个体网络之间相关度较低。

（4）计算个体网络误差

式中：yj——样本输出，Ct（xj）——由输入样本xj得到的输出，I为判断Ct（xj）与yj是否相等的函数，如果相等则I＝0，否则I＝1。如果εt（xi）＞0.5则放弃网络Ct，将所有样本的权值置为1/N，返回第 （1）步。否则保存个体网络Ct到个体网络集CS，CS＝ ｛C1，C2...CR｝，R≦T继续执行第 （5）步。

（5）根据误差更新样本权值

（6）如果未达到迭代次数，返回第 （1）步，否则输出结果，并集成。

结果集成

其算法流程如图1所示。

2 实验及分析

2.1 算法性能分析

数据分析实验采用UCI数据集，并采用BP网络训练分类器，计算4种集成方法的训练误差和泛化误差，结果见表2。

图1 算法训练流程

由表2可以看出，多次试验的结果统计显示对分类数较少的Ionosphere和Iris样本集，Boosting类算法训练误差、泛化误差都明显优于Bagging算法，而BSE的泛化误差波动幅度明显较小，且泛化误差较低。

采用噪声比例为10%的Ionosphere样本，设置迭代次数为20，得到训练次数与泛化误差的关系 （见图2）。

图2 训练次数与泛化误差的关系

表2 4种集成方法的训练误差/%和泛化误差/%

由于Boosting类算法对某些积累的噪声样本过分匹配，造成整体网络倾向于某一投票 （权值）较多的结果，迭代使个体网络只对特定的 “较难”样本适应，陷入某一局部最优解。从图1可以看出，随着训练次数增加，Boosting类算法泛化误差明显增加，BSE方法的泛化误差增加较少。因为BSE算法采取了Bagging生成个体网络，由于Bagging集成的分类器初始权值不同，即使某一分类器陷入局部最优解，只要其它分类器不会陷入同一局部最优解，整体网络陷入某一局部最优解的概率大大降低，得到的结果保证了差异度，从而提高了网络的泛化能力。

从表3可以看出，样本Ionosphere的Q统计量，BSE方法的相关度均值总是低于Local方法，而Local方法的相关度波动幅度最小，特别当个体网络学习强度增加时，Local方法由于生成的个体网络相关度较高，那些过分匹配的噪声样本较低相关度的集成方法更容易积累，虽然整体抗噪性能提高，但容易受到个体网络学习算法的影响，当个体网络出现过分匹配时其泛化误差的增长较为迅速 （见图2），因此，个体网络之间的相关度较低的BSE算法在这一问题上表现较为突出。

表3 噪声比例为10%情况下4种方法的相关度

2.2 算法稳定性分析

选取Ionosphere的训练集和测试集，设置目标迭代次数20，LB个体网络数为10，得到不同噪声水平时的泛化误差 （%），见表4。

从表4可以看出，当样本噪声增加后，BSE算法的泛化误差增加幅度较Local Boost和AdaBoost算法小，比Bagging方法更为稳定，且波动幅度小。Bagging方法不会造成噪声积累 （见图2），其集成结果趋于稳定，而Ada－Boost和Local Boost则由于训练步长的增加，对积累的噪声样本过分匹配，导致泛化误差增加。BSE算法中的个体网络是一种Bagging集成，个体网络之间互不相关，且在重取训练样本集时将噪声样本 “平滑”处理 （如果某一噪声样本被分配以较高权值，在重取训练样本时还能从该噪声样本邻居中挑选类似样本），比随机处理更有效。

表4 噪声对4种集成方法的影响

AdaBoost的误差是全局误差，只要整体样本误差不超过50%，个体网络就可以被接受。Local Boost算法对某些“较难”样本过分匹配时，计算的局部误差很容易超过50%，而抛弃该个体网络，从而使Local Boost相对Ada－Boost而言对样本更敏感，生成的个体网络数也更少，其分类器对初始时的权值敏感度更高。BSE算法由于引入了二次集成，个体网络本身是一次Bagging集成，在挑选子样本集时对 “较难”样本做了平滑处理，减弱了在迭代过程中对某些样本的过分匹配，保证了生成的个体网络数。

个体网络数多不表示其精度高，只是在相同条件下，BSE算法更为稳定，对分类器的初始时的权值依赖性更少。从图3可以看出，随着种子个数的增加，整体网络集成的泛化误差降低，但对于Iris样本当种子个数大到一定程度后整体网络的泛化误差趋于稳定。这说明当个体网络集成的分类器个数增多后，整体网络对单个分类器初始权值的依赖性降低，集成结果更为稳定。

为了比较各集成算法的时间消耗，我们比较了几组训练样本的训练时间，在串行处理的情况下得到的统计数据如表5所示。

表5 串行训练时间/s

图3 种子个数的选取对集成结果的影响

从表5可以看出，新模型的时间消耗是很大的，这一点继承了Lazy Bagging模型和Local Boosting模型的特点，Local Boosting模型在训练前均需要对训练样本进行预处理，计算其邻居，这一点新模型中也需要，而新模型中的个体网络由另外一次集成得到，挑选新样本训练集只能通过所得到权值最高的几个样本确定，这是一个非常耗时的过程，由上表可以看出，BSLB算法的个体网络数仅为10，在Ionosphere问题中，所耗时间是Bagging的近6倍，而样本数较多的Letter问题中，BSLB耗费的时间是Bagging的近12倍。

采用Matlab2009a并行计算的时间消耗，为了比较各集成算法的时间消耗，比较了几组训练样本的训练时间，在并行处理的情况下得到的统计数据如表6所示。

表6 并行训练时间/s

从表6可以看出，虽然新模型的时间消耗很大，但由于采用了Bagging方法来生成个体网络，而Bagging方法各个体网络的生成互相独立，可以采用并行计算的方法来训练、生成，所有其时耗可以降低到与Local Boosting方法相近，但由于采用了计算邻居误差的方法，这样的计算时耗不能避免，即使采用了并行方法，时耗还是很高，而采用了并行计算的Bagging方法则不同，在实验机器上其时耗降低到原有时耗的近1/2。

新算法采用了Local Boosting来计算邻居及其局部误差，这样的计算较为耗时，而二次集成中个体网络的生成采用了Bagging方法，使得并行处理成为可能，这样的处理节省了训练时耗。

3 结束语

BSE算法通过Local Boost方法计算权值，采用加权距离来选取Lazy Bagging的种子样本集，减弱了分类器对初始权值的依赖性。实验结果显示，训练得到的网络更为稳定，集成结果的误差波动幅度较小，生成的个体网络之间的相关度较低；另外BSE算法吸收了Bagging类算法 “平滑处理”“较难”训练样本的优点，即使是不稳定的训练方法 （BP）也依然能给出较为稳定的输出结果，且在过度训练的情况下不会对特殊 “较难”样本过分匹配，各个体网络之间的相关度更低，减弱了个体网络学习算法对集成泛化能力的影响，因此泛化能力不会因为Boosting类集成算法在不稳定训练情况下受到影响，且采用了Bagging集成生成个体网络使得并行处理成为可能，从而节省了时间开销。

［1］Mohammad Assaad.Romuald bone a new boosting algorithm for improved time－series forecasting with recurrent neural networks ［J］.Information Fusion，2008，9 （1）：41－55.

［2］ZHANGChun－xia，ZHANG Jiang－she，ZHANG Gai－ying.Using boosting to prune double－bagging ensembles ［J］.Computational Statistics and Data Analysis，2009，53 （4）：1218－1231.

［3］ZHANG Huaxiang，LU Jing.Creating ensembles of classifiers via fuzzy clustering and deflection ［J］.Fuzzy Sets and Systems，2010，161 （13）：1790－1802.

［4］ZHANG Chun－xia，ZHANG Jiang－she，ZHANG Gai－ying.An efficient modified boosting method for solving classification problems［J］.Journal of Computational and Applied Mathematics，2008，214 （2）：381－392.

［5］QIAN Bo，LI Yan－ping，TANG Zhen－min，et al.Speaker recognition algorithm based on neural network ensemble and its simulation study ［J］.Journal of System Simulation，2008，20（5）：1285－1288 （in Chinese）.［钱博，李燕萍，唐振民，等.基于神经网络集成的说话人识别算法仿真研究 ［J］.系统仿真学报，2008，20 （5）：1285－1288.］

［6］BU Zhi－qiong，ZOU Wei－qiang，ZHOU Yun－xiang.License plate recognition based on ensemble neural networks ［J］.Computer Engineering and Design，2007，28 （19）：4741－4742（in Chinese）.［卜质琼，邹卫强，周运祥.基于神经网络集成的汽车牌照识别 ［J］.计算机工程与设计，2007，28（19）：4741－4742.］

［7］ZHANG Chun－xia，ZHANG Jiang－she.RotBoost：A technique for combining rotation forest and AdaBoost［J］.Pattern Recognition Letters，2008，29 （10）：1524－1536.

［8］Gonzalo Martlnez－Munoz，Alberto Suarez.Using boosting to prune bagging ensembles ［J］.Pattern Recognition Letters，2007，28 （1）：156－165.

［9］YANG Xinzhu，YUAN Bo，LIU Wenhuang.An empirical study of the convergence of RegionBoost ［G］.LNAI 5755：Proceedings of the 5th International Conference on Emerging Intelligent Computing Technology and Applications，2009：527－535.

［10］Mohammad Assaad.Romuald bone a new boosting algorithm for improved time－series forecasting with recurrent neural networks ［J］.Information Fusion，2008，9 （1）：41－55.

［11］ZHU Xingquan，YANG Ying.A lazy bagging approach to classification ［J］.Pattern Recognition，2008，41 （10）：2980－2992.

［12］ZHANG Defeng.The application of Matlab neural network design ［M］.Beijing：Machinery Industry Press，2009 （in Chinese）.［张德丰.Matlab神经网络应用设计 ［M］.北京：机械工业出版社，2009.］

［13］MA Li.MATLAB language tutorial［M］.Beijing：Tsinghua University Press，2010 （in Chinese）. ［马莉编.MATLAB语言实用教程 ［M］.北京：清华大学出版社，2010.］

［14］UCI repository of machine learning data bases［EB/OL］.http：//www.ies.uei.Edu/－mlearn/MLRepository.htm，1998.