基于改进权值更新和选择性集成的AdaBoost算法.doc

基于改进权值更新和选择性集成的AdaBoost算法
摘 要:针对传统AdaBoost算法中样本权值更新缺陷造成的分类准确率降低,以及冗余弱分类器造成的分类速度慢、计算开销大等问题,提出一种基于改进权值更新和选择性集成的AdaB分类器,将剩下的弱分类器组合成强分類器,从而进一步提高分类性能;谢元澄等[18]通过删除弱分类器中性能差的分类器进行选择性集成;王忠民等[19]通过计算弱分类器的双误差异性增量值并结合近邻传播聚类算法,将T个弱分类器分成K个簇,选取每簇的中心分类器组合成强分类器。
为解决AdaBoost算法存在的上述问题,本文提出一种基于改进权值更新和选择性集成的AdaBoost算法,该算法分别在弱分类器训练阶段和弱分类器组合阶段进行改进。
在弱分类器训练阶段,针对AdaBoost算法仅依靠前一次分类情况决定样本的权值变化太过片面,并且容易导致噪声样本权值无限扩大的缺点,提出一种改进权值更新方式的AdaBoost算法。改进更新方式根据各个样本在前t次训练中的加权平均正确率更新样本权值,所有样本都在前t次训练的基础上提升其权值。前t次的分类正确率越高,权值提升越小。最后再对提升后的权值归一化,在一定程度上抑制了噪声样本权值的无限扩大,令所有样本的权值更新更均衡。
在弱分类器组合阶段,针对弱分类器冗余导致的分类速度慢、计算开销大等问题,提出一种新的弱分类器相似度度量方式,并基于该相似度度量方式和层次聚类算法[20-21]进行选择性集成,将相似度超过阈值的弱分类器归入一类,取分类准确率最高的弱分类器组合成强分类器,从而剔除冗余的弱分类器,提高分类速度,减少计算开销。 基于KDDCUP99、wavetorm和image-segmentation三个数据集对所提方案进行性能仿真与验证,实验结果表明,改进权值更新方式的AdaBoost算法提高了分类准确率。选择性集成不仅剔除了冗余的弱分类器,并且能够保持相同甚至更高的分类准确率。
1 AdaBoost算法及分析
AdaBoost算法
AdaBoost算法是一种将多个弱分类器组合成一个强分类器的迭代算法,通过T次迭代训练出T个弱分类器,算法框架如图1所示。
算法流程如下:①在第t次迭代时,根据此次样本权值分布Wt,从初始训练集D中随机抽取N个样本作为此次训练样本集Dt,并根据Dt训练得到第t个弱分类器h.;②,得到ht的分类准确率。根据该准确率计算ht的权重ac,,准确率越高,权重越大;③根据步骤②的分类结果对Wt进行更新,提升错误分类样本的权值,降低正确分类样本的权值,使得错分样本在下一次迭代中被选中的概率更大;④将训练得到的弱分类器组合成一个强分类器H,弱分类器的加权投票结果作为强分类器的输出。
AdaBoost算法分析
AdaBoost算法通过训练多个弱分类器对待分类样本进行分类,并投票决定样本类别,利用弱分类器之间的互补性提高强分类器的分类精度。相比于单个分类器,在一定程度上提高了分类准确率,但其缺点也很明显。
(1)样本权值更新时对所有正确(或错误)分类的样本同等看待,并且仅凭第t次训练结果决定一个样本在下一次迭代中的权值太过片面。例如,在前t-1次训练中,样本xp被多次分错,而样本xq被多次分对,但在第t次训练中二者都分类错误。那么,令xp和xq的权值有同样变化是不公平的,而应令xp的权值比xq有更大提升,使其在第t+1次训练中更容易被选中。除此之外,一味降低分对样本的权值、提升分错样本的权值,容易导致噪声样本权值无限增大,从而使非噪声样本被选中的概率降低,最终分类准确率也可能随之降低。
(2)由于弱分类器训练阶段采用有概率的随机抽样方法选取训练样本,有可能使得两次训练抽取到的训练集十分相似,从而得到两个差异性很小的弱分类器。这些冗余的弱分类器不仅对分类性能没有帮助,反而会降低分类速度,增加计算开销。
2 AdaBoost算法改进
针对AdaBoost算法缺点,本文提出一种基于改进权值更新和选择性集成的AdaBoost算法,该算法分为弱分类器训练和弱分类器组合两个阶段。
该方法不需要预先设置K值,并且保证最后得到的K个类中任意两个类之间的相似度小于或等于δ,每个类内的任意两个弱分类器相似度大于δ。剔除冗余的弱分类器,保留相互之间差异性较大的弱分类器,既提高了分类速度,又保证了较高的准确率。
3 性能仿真与分析
实验数据集
本文使用3个数据集对所提算法进行性能仿真,分别是KDDCUP1999、wavetorm和image-segmentation,如表1所示。KDDCUP