跳转到内容

AdaBoost

维基百科,自由的百科全书

AdaBoost为英文"Adaptive Boosting"(自适应增强)的缩写,是一种机器学习方法,由约阿夫·弗罗因德罗伯特·沙皮尔提出。[1]AdaBoost方法的自适应在于:前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中,AdaBoost方法相对于大多数其它学习算法而言,不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱(比如出现很大错误率),但只要它的分类效果比随机好一点(比如两类问题分类错误率略小于0.5),就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的,因为在最终得到的多个分类器的线性组合中,可以给它们赋予负系数,同样也能提升分类效果。

AdaBoost方法是一种迭代算法,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重,表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。通过这样的方式,AdaBoost方法能“聚焦于”那些较难分(更富信息)的样本上。在具体实现上,最初令每个样本的权重都相等,对于第k次迭代操作,我们就根据这些权重来选取样本点,进而训练分类器Ck。然后就根据这个分类器,来提高被它分错的样本的权重,并降低被正确分类的样本权重。然后,权重更新过的样本集被用于训练下一个分类器Ck[2]。整个训练过程如此迭代地进行下去。

AdaBoost算法

用xi和yi表示原始样本集D的样本点和它们的类标。用Wk(i)表示第k次迭代时全体样本的权重分布。这样就有如下所示的AdaBoost算法:

  1. 初始化:输入参数为训练集D={x1,y1,...,xn,yn},最大循环次数kmax,采样权重Wk(i)=1/n,i=1,...,n;
  2. 迭代计数器k赋值为0;
  3. 计数器k自增1;
  4. 使用Wk(i)采样权重对弱学习器Ck进行训练;
  5. 对弱学习器Ck的训练结果进行评估并记录进误差矩阵Ek中;
  6. 当k=kmax时停止训练
  7. 返回结果 Ck和αk,k=1,...,kmax(带权值分类器的总体)
  8. 结束

注意第5行中,当前权重分布必须考虑到分类器Ck的误差率。在第7行中,Zk只是一个归一化系数,使得Wk(i)能够代表一个真正的分布,而hk(xi)是分量分类器Ck给出的对任一样本点xi的标记(+1或-1),hk(xi) = yi时,样本被正确分类。第8行中的迭代停止条件可以被换为判断当前误差率是否小于一个阈值。

最后的总体分类的判决可以使用各个分量分类器加权平均来得到:

这样,最后对分类结果的判定规则是:

软件实现

参考书目

  1. ^ Freund, Yoav; Schapire, Robert E. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting. 1995. CiteSeerX: 10.1.1.56.9855可免费查阅. 
  2. ^ O. Duda, Peter E. Hart, David G. Stork, Pattern Classification, 2nd Edition, Wiley, 2000, ISBN 978-0-471-05669-0