Adaboost 算法的原理与推导.pdf

结结构构之之法法 算算法法之之道道 七七月月算算法法 （（面面试试、、算算法法、、机机器器学学习习））：：hhttttpp ::////wweebb..jjuull eedduu..ccoomm//。。 AAddaabboooosstt 算算法法的的原原理理与与推推导导 分类： 30.Machine LData Mining 2014-11-02 23:31 13877人阅读 评论 (37) 收藏 举报       AAddaabboooosstt 算算法法的的原原理理与与推推导导 00 引引言言     一直想写Adaboost来着，但迟迟未能动笔。其算法思想虽然简单：听取多人意见，最后综合决策，但一般书上对其算法的流程描述实在是过于晦涩。昨日11月1日下午，邹 博在我组织的机器学习班第8次课上讲决策树与Adaboost，其中，Adaboost讲得酣畅淋漓，讲完后，我知道，可以写本篇博客了。     无心啰嗦，本文结合邹博之决策树与Adaboost 的PPT，跟他讲Adaboost指数损失函数推导的PPT （第85~第98页）、以及 《统计学习方法》等参考资料写就，可以定义为一 篇课程笔记、读书笔记或学习心得，有何问题或意见，欢迎于本文评论下随时不吝指出，thanks。 11 AAddaabboooosstt的的原原理理 11..11 AAddaabboooosstt是是什什么么            AdaBoost，是英文Adaptive Boosting （自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到 加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。     具体说来，整个Adaboost 迭代算法就3步： 1. 初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。 2. 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么 它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。 3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而 降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。 11..22 AAddaabboooosstt算算法法流流程程     给定一个训练数据集T= {(x1, 1), (x2, 2)…(xN, N)}，其中实例 ，而实例空间 ， i属于标记集合 {-1,+1}，Adaboost的目的就是从训练数据中学习一 系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。     Adaboost的算法流程如下： 步步骤骤11.. 首先，初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值：1/N。 步步骤骤22.. 进行多轮迭代，用m = 1,2, ..., M表示迭代的第多少轮 aa. 使用具有权值分布Dm的训练数据集学习，得到基本分类器 （选取让误差率最低的阈值来设计基本分类器）： bb. 计算Gm (x)在训练数据集上的分类误差率 由上述式子可知，Gm (x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。 cc. 计算Gm (x)的系数，am表示Gm (x)在最终分类器中的重要程度 （目的：得到基本分类器在最终分类器中所占的权重）： 由上述式子可知，em = 1/2时，am = 0，且am随着em的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大。 dd. 更新训练数据集的权 值分布 （目的：得到样本的新的权值分布），用于下一轮迭代 使得被基本分类器Gm (x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的