Adaboost算法实例解析

Adaboost算法流程

对于这个算法需要介绍的是&＃xff1a;

　　1. 算法开始前&＃xff0c;需要将每个样本的权重初始化为1/m,这样一开始每个样本都是等概率的分布&＃xff0c;每个分类器都会公正对待。

　　2. 开始迭代后&＃xff0c;需要计算每个弱分类器的分类错误的误差&＃xff0c;误差等于各个分错样本的权重和&＃xff0c;这里就体现了样本权重的作用。如果一个分类器正确分类了一个权重大的样本&＃xff0c;那么这个分类器的误差就会小&＃xff0c;否则就会大。这样就对分类错误的样本更大的关注。

　　3. 获取最优分类器后&＃xff0c;需要计算这个分类器的权重&＃xff0c;然后再更新各个样本的权重&＃xff0c;然后再归一化

　　4. 算法迭代的次数一般不超过弱分类器的个数&＃xff0c;如果弱分类器的个数非常之多&＃xff0c;那么可以权衡自己性价比来折中选择。

　　5. 迭代完成后&＃xff0c;最后的分类器是由迭代过程中选择的弱分类器线性加权得到的。

1.3 Adaboost实例解析

   例1. 下面&＃xff0c;给定下列训练样本&＃xff0c;请用AdaBoost算法学习一个强分类器。

求解过程&＃xff1a;初始化训练数据的权值分布&＃xff0c;令每个权值W1i &＃61; 1/N &＃61; 0.1&＃xff0c;其中&＃xff0c;N &＃61; 10&＃xff0c;i &＃61; 1,2, ..., 10&＃xff0c;然后分别对于m &＃61; 1,2,3, ...等值进行迭代。

    拿到这10个数据的训练样本后&＃xff0c;根据 X 和 Y 的对应关系&＃xff0c;要把这10个数据分为两类&＃xff0c;一类是“1”&＃xff0c;一类是“-1”&＃xff0c;根据数据的特点发现&＃xff1a;“0 1 2”这3个数据对应的类是“1”&＃xff0c;“3 4 5”这3个数据对应的类是“-1”&＃xff0c;“6 7 8”这3个数据对应的类是“1”&＃xff0c;9是比较孤独的&＃xff0c;对应类“-1”。抛开孤独的9不讲&＃xff0c;“0 1 2”、“3 4 5”、“6 7 8”这是3类不同的数据&＃xff0c;分别对应的类是1、-1、1&＃xff0c;直观上推测可知&＃xff0c;可以找到对应的数据分界点&＃xff0c;比如2.5、5.5、8.5 将那几类数据分成两类。当然&＃xff0c;这只是主观臆测&＃xff0c;下面实际计算下这个过程。

迭代过程1

对于m&＃61;1&＃xff0c;在权值分布为D1&＃xff08;10个数据&＃xff0c;每个数据的权值皆初始化为0.1&＃xff09;的训练数据上&＃xff0c;经过计算可得&＃xff1a;

1. 阈值v取2.5时误差率为0.3&＃xff08;x <2.5时取1&＃xff0c;x > 2.5时取-1&＃xff0c;则6 7 8分错&＃xff0c;误差率为0.3&＃xff09;&＃xff0c;
2. 阈值v取5.5时误差率最低为0.4&＃xff08;x <5.5时取1&＃xff0c;x > 5.5时取-1&＃xff0c;则3 4 5 6 7 8皆分错&＃xff0c;误差率0.6大于0.5&＃xff0c;不可取。故令x > 5.5时取1&＃xff0c;x <5.5时取-1&＃xff0c;则0 1 2 9分错&＃xff0c;误差率为0.4&＃xff09;&＃xff0c;
3. 阈值v取8.5时误差率为0.3&＃xff08;x <8.5时取1&＃xff0c;x > 8.5时取-1&＃xff0c;则3 4 5分错&＃xff0c;误差率为0.3&＃xff09;。

所以无论阈值v取2.5&＃xff0c;还是8.5&＃xff0c;总得分错3个样本&＃xff0c;故可任取其中任意一个如2.5&＃xff0c;弄成第一个基本分类器为&＃xff1a;

上面说阈值v取2.5时则6 7 8分错&＃xff0c;所以误差率为0.3&＃xff0c;更加详细的解释是&＃xff1a;因为样本集中

1. 0 1 2对应的类&＃xff08;Y&＃xff09;是1&＃xff0c;因它们本身都小于2.5&＃xff0c;所以被G1(x)分在了相应的类“1”中&＃xff0c;分对了。
2. 3 4 5本身对应的类&＃xff08;Y&＃xff09;是-1&＃xff0c;因它们本身都大于2.5&＃xff0c;所以被G1(x)分在了相应的类“-1”中&＃xff0c;分对了。
3. 但6 7 8本身对应类&＃xff08;Y&＃xff09;是1&＃xff0c;却因它们本身大于2.5而被G1(x)分在了类"-1"中&＃xff0c;所以这3个样本被分错了。
4. 9本身对应的类&＃xff08;Y&＃xff09;是-1&＃xff0c;因它本身大于2.5&＃xff0c;所以被G1(x)分在了相应的类“-1”中&＃xff0c;分对了。
   

从而得到G1(x)在训练数据集上的误差率&＃xff08;被G1(x)误分类样本“6 7 8”的权值之和&＃xff09;e1&＃61;P(G1(xi)≠yi) &＃61; 3*0.1 &＃61; 0.3。

然后根据误差率e1计算G1的系数&＃xff1a;

这个a1代表G1(x)在最终的分类函数中所占的权重&＃xff0c;为0.4236。
接着更新训练数据的权值分布&＃xff0c;用于下一轮迭代&＃xff1a;

值得一提的是&＃xff0c;由权值更新的公式可知&＃xff0c;每个样本的新权值是变大还是变小&＃xff0c;取决于它是被分错还是被分正确。

即如果某个样本被分错了&＃xff0c;则yi * Gm(xi)为负&＃xff0c;负负等正&＃xff0c;结果使得整个式子变大&＃xff08;样本权值变大&＃xff09;&＃xff0c;否则变小。

第一轮迭代后&＃xff0c;最后得到各个数据新的权值分布D2 &＃61; (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出&＃xff0c;因为样本中是数据“6 7 8”被G1(x)分错了&＃xff0c;所以它们的权值由之前的0.1增大到0.1666&＃xff0c;反之&＃xff0c;其它数据皆被分正确&＃xff0c;所以它们的权值皆由之前的0.1减小到0.0715。

分类函数f1(x)&＃61; a1*G1(x) &＃61; 0.4236G1(x)。

此时&＃xff0c;得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点&＃xff08;即6 7 8&＃xff09;。

    从上述第一轮的整个迭代过程可以看出&＃xff1a;被误分类样本的权值之和影响误差率&＃xff0c;误差率影响基本分类器在最终分类器中所占的权重。

 迭代过程2

对于m&＃61;2&＃xff0c;在权值分布为D2 &＃61; (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的训练数据上&＃xff0c;经过计算可得&＃xff1a;

1. 阈值v取2.5时误差率为0.1666*3&＃xff08;x <2.5时取1&＃xff0c;x > 2.5时取-1&＃xff0c;则6 7 8分错&＃xff0c;误差率为0.1666*3&＃xff09;&＃xff0c;
2. 阈值v取5.5时误差率最低为0.0715*4&＃xff08;x > 5.5时取1&＃xff0c;x <5.5时取-1&＃xff0c;则0 1 2 9分错&＃xff0c;误差率为0.0715*3 &＃43; 0.0715&＃xff09;&＃xff0c;
3. 阈值v取8.5时误差率为0.0715*3&＃xff08;x <8.5时取1&＃xff0c;x > 8.5时取-1&＃xff0c;则3 4 5分错&＃xff0c;误差率为0.0715*3&＃xff09;。

所以&＃xff0c;阈值v取8.5时误差率最低&＃xff0c;故第二个基本分类器为&＃xff1a;

面对的还是下述样本&＃xff1a;

很明显&＃xff0c;G2(x)把样本“3 4 5”分错了&＃xff0c;根据D2可知它们的权值为0.0715, 0.0715,  0.0715&＃xff0c;所以G2(x)在训练数据集上的误差率e2&＃61;P(G2(xi)≠yi) &＃61; 0.0715 * 3 &＃61; 0.2143。

计算G2的系数&＃xff1a;

更新训练数据的权值分布&＃xff1a;

D3 &＃61; (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分错的样本“3 4 5”的权值变大&＃xff0c;其它被分对的样本的权值变小。
f2(x)&＃61;0.4236G1(x) &＃43; 0.6496G2(x)

此时&＃xff0c;得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点&＃xff08;即3 4 5&＃xff09;。

 迭代过程3

对于m&＃61;3&＃xff0c;在权值分布为D3 &＃61; (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的训练数据上&＃xff0c;经过计算可得&＃xff1a;

1. 阈值v取2.5时误差率为0.1060*3&＃xff08;x <2.5时取1&＃xff0c;x > 2.5时取-1&＃xff0c;则6 7 8分错&＃xff0c;误差率为0.1060*3&＃xff09;&＃xff0c;
2. 阈值v取5.5时误差率最低为0.0455*4&＃xff08;x > 5.5时取1&＃xff0c;x <5.5时取-1&＃xff0c;则0 1 2 9分错&＃xff0c;误差率为0.0455*3 &＃43; 0.0715&＃xff09;&＃xff0c;
3. 阈值v取8.5时误差率为0.1667*3&＃xff08;x <8.5时取1&＃xff0c;x > 8.5时取-1&＃xff0c;则3 4 5分错&＃xff0c;误差率为0.1667*3&＃xff09;。

所以阈值v取5.5时误差率最低&＃xff0c;故第三个基本分类器为&＃xff08;下图画反了&＃xff0c;待后续修正&＃xff09;&＃xff1a;

依然还是原样本&＃xff1a;

此时&＃xff0c;被误分类的样本是&＃xff1a;0 1 2 9&＃xff0c;这4个样本所对应的权值皆为0.0455&＃xff0c;

所以G3(x)在训练数据集上的误差率e3&＃61; P(G3(xi)≠yi) &＃61; 0.0455*4 &＃61; 0.1820。

计算G3的系数&＃xff1a;

更新训练数据的权值分布&＃xff1a;

D4 &＃61; (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。被分错的样本“0 1 2 9”的权值变大&＃xff0c;其它被分对的样本的权值变小。

f3(x)&＃61;0.4236G1(x) &＃43; 0.6496G2(x)&＃43;0.7514G3(x)

此时&＃xff0c;得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此&＃xff0c;整个训练过程结束。

    G(x) &＃61; sign[f3(x)] &＃61; sign[ a1 * G1(x) &＃43; a2 * G2(x) &＃43; a3 * G3(x) ]&＃xff0c;将上面计算得到的a1、a2、a3各值代入G(x)中&＃xff0c;得到最终的分类器为&＃xff1a;G(x) &＃61; sign[f3(x)] &＃61; sign[ 0.4236G1(x) &＃43; 0.6496G2(x)&＃43;0.7514G3(x) ]。

------- ----  用图解深入浅出的解释adaboost ---—————

也许你看了上面的介绍或许还是对adaboost算法云里雾里的&＃xff0c;没关系&＃xff0c;百度大牛举了一个很简单的例子&＃xff0c;你看了就会对这个算法整体上很清晰了。

　　下面我们举一个简单的例子来看看adaboost的实现过程&＃xff1a;

图中&＃xff0c;“&＃43;”和“-”分别表示两种类别&＃xff0c;在这个过程中&＃xff0c;我们使用水平或者垂直的直线作为分类器&＃xff0c;来进行分类。

　　第一步&＃xff1a;

根据分类的正确率&＃xff0c;得到一个新的样本分布D2­&＃xff0c;一个子分类器h1

　　其中划圈的样本表示被分错的。在右边的途中&＃xff0c;比较大的“&＃43;”表示对该样本做了加权。

也许你对上面的ɛ1&＃xff0c;ɑ1怎么算的也不是很理解。下面我们算一下&＃xff0c;不要嫌我啰嗦&＃xff0c;我最开始就是这样思考的&＃xff0c;只有自己把算法演算一遍&＃xff0c;你才会真正的懂这个算法的核心&＃xff0c;后面我会再次提到这个。

算法最开始给了一个均匀分布 D 。所以h1 里的每个点的值是0.1。ok&＃xff0c;当划分后&＃xff0c;有三个点划分错了&＃xff0c;根据算法误差表达式得到 误差为分错了的三个点的值之和&＃xff0c;所以ɛ1&＃61;(0.1&＃43;0.1&＃43;0.1)&＃61;0.3&＃xff0c;而ɑ1 根据表达式 的可以算出来为0.42. 然后就根据算法 把分错的点权值变大。如此迭代&＃xff0c;最终完成adaboost算法。

　　第二步&＃xff1a;

根据分类的正确率&＃xff0c;得到一个新的样本分布D3&＃xff0c;一个子分类器h2

　　第三步&＃xff1a;

得到一个子分类器h3

　　整合所有子分类器&＃xff1a;

因此可以得到整合的结果&＃xff0c;从结果中看&＃xff0c;及时简单的分类器&＃xff0c;组合起来也能获得很好的分类效果&＃xff0c;在例子中所有的。

五 Adaboost 疑惑和思考

  到这里&＃xff0c;也许你已经对adaboost算法有了大致的理解。但是也许你会有个问题&＃xff0c;为什么每次迭代都要把分错的点的权值变大呢&＃xff1f;这样有什么好处呢&＃xff1f;不这样不行吗? 这就是我当时的想法&＃xff0c;为什么呢&＃xff1f;我看了好几篇介绍adaboost 的博客&＃xff0c;都没有解答我的疑惑&＃xff0c;也许大牛认为太简单了&＃xff0c;不值一提&＃xff0c;或者他们并没有意识到这个问题而一笔带过了。然后我仔细一想&＃xff0c;也许提高错误点可以让后面的分类器权值更高。然后看了adaboost算法&＃xff0c;和我最初的想法很接近&＃xff0c;但不全是。 注意到算法最后的表到式为&＃xff0c;这里面的a 表示的权值&＃xff0c;是由得到的。而a是关于误差的表达式&＃xff0c;到这里就可以得到比较清晰的答案了&＃xff0c;所有的一切都指向了误差。提高错误点的权值&＃xff0c;当下一次分类器再次分错了这些点之后&＃xff0c;会提高整体的错误率&＃xff0c;这样就导致 a 变的很小&＃xff0c;最终导致这个分类器在整个混合分类器的权值变低。也就是说&＃xff0c;这个算法让优秀的分类器占整体的权值更高&＃xff0c;而挫的分类器权值更低。这个就很符合常理了。到此&＃xff0c;我认为对adaboost已经有了一个透彻的理解了。

六 总结

　　最后&＃xff0c;我们可以总结下adaboost算法的一些实际可以使用的场景&＃xff1a;

　　1&＃xff09;用于二分类或多分类的应用场景

　　2&＃xff09;用于做分类任务的baseline

　　无脑化&＃xff0c;简单&＃xff0c;不会overfitting&＃xff0c;不用调分类器

　　3&＃xff09;用于特征选择&＃xff08;feature selection)

　　4&＃xff09;Boosting框架用于对badcase的修正

　　只需要增加新的分类器&＃xff0c;不需要变动原有分类器

　　由于adaboost算法是一种实现简单&＃xff0c;应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器&＃xff0c;同时具有分类错误率上界随着训练增加而稳定下降&＃xff0c;不会过拟合等的性质&＃xff0c;应该说是一种很适合于在各种分类场景下应用的算法。

      这个是我看过对adaboost写的比较容易懂的文章了&＃xff0c;等有空的时候我自己运行下adaboost的python代码&＃xff0c;到时候再把这篇文章修改下。

      对了&＃xff0c;如果看到我的博客后&＃xff0c;有意愿和我技术沟通的&＃xff0c;可以加我QQ 340217138 讨论。

 参考&＃xff1a;

　　http://blog.csdn.net/tiandijun/article/details/48036025

     http://blog.csdn.net/haidao2009/article/details/7514787