PROSAGA-机器学习-机器学习十大算法-AdaBoost

<div style="width:595.0pt;margin-bottom:72.0pt;margin-top:72.0pt;margin-left:90.0pt;margin-right:90.0pt;">
 AdaBoost
 Input:
 Training set <img src="/user/files/skK-syJ86RR-mKbEGn7YyLNK1IpdESTu3l4DCD4jVYI.png" width="111.0pt" height="100%">, <img src="/user/files/EJudNTFuoAWgRSpD6c68Ob8ruMvkJBu8_A89BiGUKQI.png" width="45.75pt" height="100%">
 Training labels <img src="/user/files/J8VUQhMwq8ozsF7L1blzUQxs2juXP-YiHLU9L1l2XAQ.png" width="110.25pt" height="100%">, <img src="/user/files/cBzEPk02kDYYKhaQg2ooXCDpcSDPp7jKsKKhldUCFLU.png" width="76.5pt" height="100%">
 Convergence threshold <img src="/user/files/MAzgJMX_X1WN4X6y4uoaf7kWPZ_MpSoLhm0kKKAyiSo.png" width="33.75pt" height="100%">
 Output:
 Classification function <img src="/user/files/nq1oPNf59MC_68h6savf5eiH2dA9ydsCSDum9TxCdDU.png" width="103.5pt" height="100%">
 Initialization//初始化
 Weights, uniform <img src="/user/files/Cul4AiU-3d5SsgP7ZnP73uWap_3okoNjBiOFef2ZY2w.png" width="150.0pt" height="100%">
 Edge <img src="/user/files/erRfzycAWWvQwQWqJK2VjwV63vldHCcJDSzGocKFaFY.png" width="42.75pt" height="100%"> //边界
 Hypothesis count <img src="/user/files/0qXXj3IVXfz5o41CcNaOY05HrGZjjP3be5UImyzMup8.png" width="38.25pt" height="100%">
 Iterate
 <img src="/user/files/NSXKSpnPREd1010Kr12xZp1E14gAQw9NSU-64JegCSk.png" width="187.5pt" height="100%">
 if <img src="/user/files/RNgeYGXs64R3IidAo8PCOVArLIIfFwJ4KhB5d_0QlTk.png" width="143.25pt" height="100%"> then
 
 break
 <img src="/user/files/n9YPqY3RqAycelVRv3Uhyjdu29FIxTQDuH8i4KvhWSw.png" width="46.5pt" height="100%">
 <img src="/user/files/3V6fk9-N8ZjLEl6eWe6aUKZCZoydp3HZCckYzKA3mkM.png" width="66.0pt" height="100%">
 <img src="/user/files/pKVZ7i8fSW4qnHLlaq9ooHScQnnJLm-Ucfq3Mp8m0jg.png" width="54.0pt" height="100%"> solution of the LPBoost dual
 <img src="/user/files/VTwVACF29aDmaQHsl0V0DKpt9SuIr--_z0ATUoZLobY.png" width="30.0pt" height="100%"> Lagrangian multipliers of solution to LPBoost dual problem
 <img src="/user/files/t4zFGwF8L9KDcyyMLaa7ZIy55jyJm775j_29pHIwM90.png" width="176.25pt" height="100%">
 1.3 Adaboost的一个例子
     下面，给定下列训练样本，请用AdaBoost算法学习一个强分类器。
     <img src="/user/files/hnP9k6kFWLN5YdtuQAPcSS7ECJohPzuFwnDpSrmBRsI.jpeg" width="459.0pt" height="100%">
     求解过程：初始化训练数据的权值分布，令每个权值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然后分别对于m = 1,2,3, ...等值进行迭代。
     拿到这10个数据的训练样本后，根据 X 和 Y 的对应关系，要把这10个数据分为两类，一类是“1”，一类是“-1”，根据数据的特点发现：“0 1 2”这3个数据对应的类是“1”，“3 4 5”这3个数据对应的类是“-1”，“6 7 8”这3个数据对应的类是“1”，9是比较孤独的，对应类“-1”。抛开孤独的9不讲，“0 1 2”、“3 4 5”、“6 7 8”这是3类不同的数据，分别对应的类是1、-1、1，直观上推测可知，可以找到对应的数据分界点，比如2.5、5.5、8.5 将那几类数据分成两类。当然，这只是主观臆测，下面实际计算下这个具体过程。
 迭代过程1
 对于m=1，在权值分布为D1（10个数据，每个数据的权值皆初始化为0.1）的训练数据上，经过计算可得：
 阈值v取2.5时误差率为0.3（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.3），
 阈 值v取5.5时误差率最低为0.4（x < 5.5时取1，x > 5.5时取-1，则3 4 5 6 7 8皆分错，误差率0.6大于0.5，不可取。故令x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.4），
 阈值v取8.5时误差率为0.3（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.3）。
 可以看到，无论阈值v取2.5，还是8.5，总得分错3个样本，故可任取其中任意一个如2.5，弄成第一个基本分类器为：
 <img src="/user/files/Bowd_POjum4BZoxbWpICqVEoreO4RPDIWlA46GzwNLQ.jpeg" width="202.5pt" height="100%">
 上面说阈值v取2.5时则6 7 8分错，所以误差率为0.3，更加详细的解释是：因为样本集中
 0 1 2对应的类（Y）是1，因它们本身都小于2.5，所以被G1(x)分在了相应的类“1”中，分对了。
 3 4 5本身对应的类（Y）是-1，因它们本身都大于2.5，所以被G1(x)分在了相应的类“-1”中，分对了。
 但6 7 8本身对应类（Y）是1，却因它们本身大于2.5而被G1(x)分在了类"-1"中，所以这3个样本被分错了。
 9本身对应的类（Y）是-1，因它本身大于2.5，所以被G1(x)分在了相应的类“-1”中，分对了。 
 从而得到G1(x)在训练数据集上的误差率（被G1(x)误分类样本“6 7 8”的权值之和）e1=P(G1(xi)≠yi) = 3*0.1 = 0.3。
 然后根据误差率e1计算G1的系数：
 <img src="/user/files/E6CChKWYriSXJCVoms5eXtIieaKJLRiV0UJD7G30BvY.jpeg" width="185.25pt" height="100%">
 更新训练数据的权值分布： 
 <img src="/user/files/Rbi9BP1a9XJuzmipPdjFz45FwjqVNhLJykE3Lj_c6K4.jpeg" width="264.0pt" height="100%">
 D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分错的样本“3 4 5”的权值变大，其它被分对的样本的权值变小。 这个a1代表G1(x)在最终的分类函数中所占的权重，为0.4236。 接着更新训练数据的权值分布，用于下一轮迭代： 
 <img src="/user/files/qrvxcusnSivoRuQfrlKbOBNBYfo4AYoxSJY8VEtqTMk.jpeg" width="264.0pt" height="100%">
 值得一提的是，由权值更新的公式可知，每个样本的新权值是变大还是变小，取决于它是被分错还是被分正确。
 即如果某个样本被分错了，则yi * Gm(xi)为负，负负得正，结果使得整个式子变大（样本权值变大），否则变小。
 第一轮迭代后，最后得到各个数据新的权值分布D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715,0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出，因为样本中是数据“6 7 8”被G1(x)分错了，所以它们的权值由之前的0.1增大到0.1666，反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到0.0715。
 分类函数f1(x)= a1*G1(x) = 0.4236G1(x)。
 此时，得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点（即6 7 8）。
     从上述第一轮的整个迭代过程可以看出：被误分类样本的权值之和影响误差率，误差率影响基本分类器在最终分类器中所占的权重。
   迭代过程2
 对于m=2，在权值分布为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的训练数据上，经过计算可得：
 阈值v取2.5时误差率为0.1666*3（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.1666*3），
 阈值v取5.5时误差率最低为0.0715*4（x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.0715*3 + 0.0715），
 阈值v取8.5时误差率为0.0715*3（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.0715*3）。
 所以，阈值v取8.5时误差率最低，故第二个基本分类器为：
 <img src="/user/files/WWFT6blJoAAo31hPGyhNwlYXPcEfVYRvmRmKeAQTEPo.jpeg" width="204.0pt" height="100%">
 面对的还是下述样本：
 <img src="/user/files/hnP9k6kFWLN5YdtuQAPcSS7ECJohPzuFwnDpSrmBRsI.jpeg" width="459.0pt" height="100%">
 很明显，G2(x)把样本“3 4 5”分错了，根据D2可知它们的权值为0.0715, 0.0715,  0.0715，所以G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。
 计算G2的系数：
 <img src="/user/files/eSYBtHwYQgyFfSBEqqf800xxHWvEyPl0pQP84eU0eYc.jpeg" width="189.75pt" height="100%">
 f2(x)=0.4236G1(x) + 0.6496G2(x) 
 此时，得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点（即3 4 5）。
   迭代过程3
 对于m=3，在权值分布为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的训练数据上，经过计算可得：
 阈值v取2.5时误差率为0.1060*3（x < 2.5时取1，x > 2.5时取-1，则6 7 8分错，误差率为0.1060*3），
 阈值v取5.5时误差率最低为0.0455*4（x > 5.5时取1，x < 5.5时取-1，则0 1 2 9分错，误差率为0.0455*3 + 0.0715），
 阈值v取8.5时误差率为0.1667*3（x < 8.5时取1，x > 8.5时取-1，则3 4 5分错，误差率为0.1667*3）。
 所以阈值v取5.5时误差率最低，故第三个基本分类器为：
 <img src="/user/files/OVSCzyzjhc1lMGKFVVqvrSm3LeiPvM3NR-4N-8nNDRQ.png" width="138.0pt" height="100%">
 依然还是原样本：
 <img src="/user/files/hnP9k6kFWLN5YdtuQAPcSS7ECJohPzuFwnDpSrmBRsI.jpeg" width="459.0pt" height="100%">
 此时，被误分类的样本是：0 1 2 9，这4个样本所对应的权值皆为0.0455，
 所以G3(x)在训练数据集上的误差率e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820。
 计算G3的系数：
 <img src="/user/files/Y0fkkiAaEKZywYW-X2SAjcVSVsT95ZiRs3sdhtt5J4k.jpeg" width="187.5pt" height="100%">
 更新训练数据的权值分布：
 <img src="/user/files/6zV9tObXjUKflpfOAvHJ1WUrvjTinKBgsbxGxICd1HM.jpeg" width="264.75pt" height="100%">
 D4 = (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。被分错的样本“0 1 2 9”的权值变大，其它被分对的样本的权值变小。
 f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)
 此时，得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此，整个训练过程结束。
     现在，咱们来总结下3轮迭代下来，各个样本权值和误差率的变化，如下所示（其中，样本权值D中加了下划线的表示在上一轮中被分错的样本的新权值）：
 训练之前，各个样本的权值被初始化为D1 = (0.1, 0.1,0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1)；
 第一轮迭代中，样本“6 7 8”被分错，对应的误差率为e1=P(G1(xi)≠yi) = 3*0.1 = 0.3，此第一个基本分类器在最终的分类器中所占的权重为a1 = 0.4236。第一轮迭代过后，样本新的权值为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)；
 第二轮迭代中，样本“3 4 5”被分错，对应的误差率为e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143，此第二个基本分类器在最终的分类器中所占的权重为a2 = 0.6496。第二轮迭代过后，样本新的权值为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)；
 第三轮迭代中，样本“0 1 2 9”被分错，对应的误差率为e3= P(G3(xi)≠yi) = 0.0455*4 = 0.1820，此第三个基本分类器在最终的分类器中所占的权重为a3 = 0.7514。第三轮迭代过后，样本新的权值为D4 = (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。
     从上述过程中可以发现，如果某些个样本被分错，它们在下一轮迭代中的权值将被增大，反之，其它被分对的样本在下一轮迭代中的权值将被减小。就这样，分错样 本权值增大，分对样本权值变小，而在下一轮迭代中，总是选取让误差率最低的阈值来设计基本分类器，所以误差率e（所有被Gm(x)误分类样本的权值之和） 不断降低。
     综上，将上面计算得到的a1、a2、a3各值代入G(x)中，G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ]，得到最终的分类器为：
 G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]。
 
 
 AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，是一种<a href="http://zh.wikipedia.org/wiki/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0" \o "机器学习">机器学习 </a>方法，由Yoav Freund和Robert Schapire提出。<a href="http://zh.wikipedia.org/wiki/AdaBoost" \l "cite_note-1">[1] </a>AdaBoost 方法的自适应在于：
 前一个分类器分错的样本会被用来训练下一个分类器。
 AdaBoost方法对于噪声数据和异常数据很敏感。
 但在一些问题 中，AdaBoost方法相对于大多数其它学习算法而言，不会很容易出现过拟合现象。
 
 AdaBoost方法中使用的分类器可能
 很弱（比如出现很大错误 率），
 但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。
 而错误率高于随机分类器的弱分类器也是有用 的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，
 同样也能提升分类效果。
 AdaBoost方法是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。
 每一个训练样本都被赋予一个权重，表明 它被某个分类器选入训练集的概率。
 如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确 地分类，那么它的权重就得到提高。
 通过这样的方式，AdaBoost方法能“聚焦于”那些较难分（更富信息）的样本上。
 在具体实现上，最初令每个样本的权 重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器Ck<a href="http://zh.wikipedia.org/wiki/AdaBoost" \l "cite_note-2">[2] </a>。整个训练过程如此迭代地进行下去。
 AdaBoost算法
 用 xi 和 yi 表示原始样本集D的样本点和它们的类标。用 Wk(i) 表示第k次迭代时全体样本的权重分布。这样就有如下所示的AdaBoost算法：
 
 begin initial D={x1，y1，...，xn，yn}，kmax(最大循环次数)，Wk(i)=1/n，i=1，...，n
 k ← 0
 do k ← k+1
 训练使用按照 Wk(i) 采样的 D 的弱学习器 Ck
 Ek ← 对使用 Wk(i) 的 D 测量的 Ck 的训练误差
 <img src="/user/files/Tp9TY3GWjOhwKo6_Pv_yWSKXoQSfcvTpUn6EzUgQ9gs.png" width="109.5pt" height="100%">
 <img src="/user/files/wkxhKjEdxa3PZMF4hzFr5niV_squSdR4vlOuzfbTnOE.png" width="273.0pt" height="100%">
 until k=kmax
 return Ck和αk，k=1，...，kmax（带权值分类器的总体）
 end
 注意第5行中，当前权重分布必须考虑到分类器 Ck 的误差率。在第7行中， Zk 只是一个归一化系数，使得 Wk(i) 能够代表一个真正的分布，而 hk(xi) 是分量分类器 Ck 给出的对任一样本点 xi 的标记（+1或-1）， hk(xi) = yi 时，样本被正确分类。第8行中的迭代停止条件可以被换为判断当前误差率是否小于一个阈值。 最后的总体分类的判决可以使用各个分量分类器加权平均来得到：
 <img src="/user/files/c_1O3lTIzbohBri9x1rdZonzCepGI-tNJt_6lLJ96lI.png" width="132.0pt" height="100%">
 这样，最后对分类结果的判定规则是:
 <img src="/user/files/BGobSffOysODQI-oK9qPnRrkuM_08Co5838vbziW01M.png" width="118.5pt" height="100%">
 
 
 
 四 Adaboost 举例
 也许你看了上面的介绍或许还是对adaboost算法云里雾里的，没关系，百度大牛举了一个很简单的例子，你看了就会对这个算法整体上很清晰了。
 　　下面我们举一个简单的例子来看看adaboost的实现过程：
 <img src="/user/files/dphW-L-Qurn-RF6uRl4XkZ8eAAYWcRA-KhNYBfAw1UI.png" width="276.0pt" height="100%">
 　　图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。
 　　第一步：
 <img src="/user/files/dphW-L-Qurn-RF6uRl4XkZ8eAAYWcRA-KhNYBfAw1UI.png" width="768.0pt" height="100%">
 　　根据分类的正确率，得到一个新的样本分布D2，一个子分类器h1
 　　其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本做了加权。
 也许你对上面的ɛ1，ɑ1怎么算的也不是很理解。下面我们算一下，不要嫌我啰嗦，我最开始就是这样思考的，只有自己把算法演算一遍，你才会真正的懂这个算法的核心，后面我会再次提到这个。
 算法最开始给了一个均匀分布 D 。所以h1 里的每个点的值是0.1。ok，当划分后，有三个点划分错了，根据算法误差表达式<img src="/user/files/IJZI4wh1HZAADd-HWVQVatwEbXC5XZ_8dLLrgCI0OD8.png" width="171.75pt" height="100%">得到 误差为分错了的三个点的值之和，所以ɛ1=(0.1+0.1+0.1)=0.3，而ɑ1 根据表达式 的可以算出来为0.42. 然后就根据算法 把分错的点权值变大。如此迭代，最终完成adaboost算法。
 　　第二步：
 <img src="/user/files/dphW-L-Qurn-RF6uRl4XkZ8eAAYWcRA-KhNYBfAw1UI.png" width="768.0pt" height="100%">
 　　根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2
 　　第三步：
 <img src="/user/files/dphW-L-Qurn-RF6uRl4XkZ8eAAYWcRA-KhNYBfAw1UI.png" width="362.25pt" height="100%">
 　　得到一个子分类器h3
 　　整合所有子分类器：
 <img src="/user/files/dphW-L-Qurn-RF6uRl4XkZ8eAAYWcRA-KhNYBfAw1UI.png" width="469.5pt" height="100%">
 　　因此可以得到整合的结果，从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果，在例子中所有的。
 五 Adaboost 疑惑和思考
   到这里，也许你已经对adaboost算法有了大致的理解。但是也许你会有个问题，为什么每次迭代都要把分错的点的权值变大呢？这样有什么好处呢？不这样 不行吗? 这就是我当时的想法，为什么呢？我看了好几篇介绍adaboost 的博客，都没有解答我的疑惑，也许大牛认为太简单了，不值一提，或者他们并没有意识到这个问题而一笔带过了。然后我仔细一想，也许提高错误点可以让后面的 分类器权值更高。然后看了adaboost算法，和我最初的想法很接近，但不全是。 注意到算法最后的表到式为<img src="/user/files/HCUf_MXWdft-I2VoZMQyPPg1pk6fQmY_z9h73uiib5M.png" width="161.25pt" height="100%">，这里面的a 表示的权值，是由<img src="/user/files/Oo6W-VXabJfhQM84Ad2jXD4TSilKK6i4E14SCbh5ooQ.png" width="139.5pt" height="100%">得 到的。而a是关于误差的表达式，到这里就可以得到比较清晰的答案了，所有的一切都指向了误差。提高错误点的权值，当下一次分类器再次分错了这些点之后，会 提高整体的错误率，这样就导致 a 变的很小，最终导致这个分类器在整个混合分类器的权值变低。也就是说，这个算法让优秀的分类器占整体的权值更高，而挫的分类器权值更低。这个就很符合常理 了。到此，我认为对adaboost已经有了一个透彻的理解了。
 
 六 总结
 　　最后，我们可以总结下adaboost算法的一些实际可以使用的场景：
 　　1）用于二分类或多分类的应用场景
 　　2）用于做分类任务的baseline
 　　无脑化，简单，不会overfitting，不用调分类器
 　　3）用于特征选择（feature selection)
 　　4）Boosting框架用于对badcase的修正
 　　只需要增加新的分类器，不需要变动原有分类器
 　　由于adaboost算法是一种实现简单，应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器，同时具有分类错误率上界随着训练增加而稳定下降，不会过拟合等的性质，应该说是一种很适合于在各种分类场景下应用的算法。
 
</div>

机器学习十大算法-AdaBoost(机器学习十大算法)