如果Boosting 你懂、那 Adaboost你懂么？
作者：崔家华
编辑：王抒伟
转载请注明作者和出处：
https://zhuanlan.zhihu.com/ml-jack
机器学习知乎专栏：
https://zhuanlan.zhihu.com/ml-jack
CSDN博客专栏：
http://blog.csdn.net/column/details/16415.html
Github代码获取：
https://github.com/Jack-Cherish/Machine-Learning/
Python版本：
Python3.x
运行平台：
Windows
IDE：
Sublime text3
前面的文章已经介绍了五中不同的分类器，它们各有优缺点。我们可以很自然地将不同的分类器组合起来，而这种组合结果则被成为集成方法(ensemble method)或者元算法(meta-algorithm)。
使用集成方法时会有多种形式：可以是不同算法的集成，也可以是同一种算法在不同设置下的集成，还可以是数据集不同部分分配给不同分类器之后的集成。
本文出现的所有代码和数据集，均可在我的github上下载，欢迎Follow、Star：https://github.com/Jack-Cherish/Machine-Learning
集成方法：
分析：
集成方法（ensemble method）通过组合多个基分类器（base classifier）来完成学习任务，颇有点“三个臭皮匠顶个诸葛亮”的意味。基分类器一般采用的是弱可学习（weakly learnable）分类器，通过集成方法，组合成一个强可学习（strongly learnable）分类器。
所谓弱可学习，是指学习的正确率仅略优于随机猜测的多项式学习算法；强可学习指正确率较高的多项式学习算法。
集成学习的泛化能力一般比单一的基分类器要好，这是因为大部分基分类器都分类错误的概率远低于单一基分类器的.
集成方法主要包括Bagging和Boosting两种方法，Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法，即将弱分类器组装成强分类器的方法
1、Bagging:
自举汇聚法（bootstrap aggregating），也称为bagging方法。Bagging对训练数据采用自举采样（boostrap sampling），即有放回地采样数据，主要思想：
从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）,共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
2、Boosting
Boosting是一种与Bagging很类似的技术。Boosting的思路则是采用重赋权（re-weighting）法迭代地训练基分类器，主要思想：
每一轮的训练数据样本赋予一个权重，并且每一轮样本的权值分布依赖上一轮的分类结果。
基分类器之间采用序列式的线性加权方式进行组合。
3、Bagging、Boosting二者之间的区别
样本选择上：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
样例权重：
Bagging：使用均匀取样，每个样例的权重相等。
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
预测函数：
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
并行计算：
Bagging：各个预测函数可以并行生成。
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
4、总结
这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。
下面是将决策树与这些算法框架进行结合所得到的新的算法：
Bagging + 决策树 = 随机森林
AdaBoost + 决策树 = 提升树
Gradient Boosting + 决策树 = GBDT
集成方法众多，本文主要关注Boosting方法中的一种最流行的版本，即AdaBoost，让我们一探究竟！
AdaBoost算法：
AdaBoost算法是基于Boosting思想的机器学习算法，AdaBoost是adaptive boosting（自适应boosting）的缩写，其运行过程如下：
1、计算样本权重
训练数据中的每个样本，赋予其权重，即样本权重，用向量D表示，这些权重都初始化成相等值。假设有n个样本的训练集：
设定每个样本的权重都是相等的，即1/n。
2、计算错误率
利用第一个弱学习算法h1对其进行学习，学习完成后进行错误率ε的统计：
3、计算弱学习算法权重
弱学习算法也有一个权重，用向量α表示，利用错误率计算权重α：
4、更新样本权重
在第一次学习完成后，需要重新调整样本的权重，以使得在第一分类中被错分的 样本的权重，在接下来的学习中可以重点对其进行学习：
其中，h_t(x_i) = y_i表示对第i个样本训练正确，不等于则表示分类错误。Z_t是一个归一化因子：
这个公式我们可以继续化简，将两个公式进行合并，化简如下：
5、AdaBoost算法
重复进行学习，这样经过t轮的学习后，就会得到t个弱学习算法、权重、弱分类器的输出以及最终的AdaBoost算法的输出，分别如下：
其中，sign(x)是符号函数。具体过程如下所示：
AdaBoost算法总结如下：
基于单层决策树构建弱分类:
建立AdaBoost算法之前，我们必须先建立弱分类器，并保存样本的权重。弱分类器使用单层决策树（decision stump），也称决策树桩，它是一种简单的决策树，通过给定的阈值，进行分类。
1、数据集可视化
为了训练单层决策树，我们需要创建一个训练集，编写代码如下：
点击图片放大查看代码
现在来看看代码运行结果：
可以看到，如果想要试着从某个坐标轴上选择一个值（即选择一条与坐标轴平行的直线）来将所有的蓝色圆点和橘色圆点分开，这显然是不可能的。这就是单层决策树难以处理的一个著名问题。通过使用多颗单层决策树，我们可以构建出一个能够对该数据集完全正确分类的分类器。
2、构建单层决策树
我们设置一个分类阈值，比如我横向切分，如下图所示：
蓝横线上边的是一个类别，蓝横线下边是一个类别
显然，此时有一个蓝点分类错误，计算此时的分类误差，误差为1/5 = 0.2。这个横线与坐标轴的y轴的交点，就是我们设置的阈值，通过不断改变阈值的大小，找到使单层决策树的分类误差最小的阈值。同理，竖线也是如此，找到最佳分类的阈值，就找到了最佳单层决策树，编写代码如下：
点击图片放大查看代码
代码运行结果如下：
代码不难理解，就是通过遍历，改变不同的阈值，计算最终的分类误差，找到分类误差最小的分类方式，即为我们要找的最佳单层决策树。
这里lt表示less than，表示分类方式，对于小于阈值的样本点赋值为-1，gt表示greater than，也是表示分类方式，对于大于阈值的样本点赋值为-1。
经过遍历，我们找到，训练好的最佳单层决策树的最小分类误差为0.2，就是对于该数据集，无论用什么样的单层决策树，分类误差最小就是0.2。
这就是我们训练好的弱分类器。
接下来，使用AdaBoost算法提升分类器性能，将分类误差缩短到0，看下AdaBoost算法是如何实现的。
好长好长累了吧？ 快给作者和编辑鼓掌！！！
还有么? 有！！！
未完待续。。。
还有adaboost（二）、（三）？
休息一下，坐等更新哇。
PS：
1. 考虑到文章太长，就给大家写成分段“函数”了。
2. 本文作者崔家华，厉害啊，去全球最大的同性交友平台---github找他啊。（邪恶.gif）
3.如果你懂一些boosting相关知识，更好喔，如果你不懂，留言给小编，小编给你好好打一下基础。
那么重点来了,什么是adaboost， 听我一一道来。
我：同学们，你们知道Boost吧？
学生：Boost谁不知道啊
我：那adaboost呢？
同学们面面相觑，我暗暗窃喜，正当我准备科普的时候。
突然惊出一声：老师我知道！！！
我沉下脸：哦？ 你说说看。
学生：adaboost是阿迪达斯出版的boost！
全班哄哄大笑
我：小明，你给我出去！！！
hello? 兄弟，脑洞可以当三峡大坝了啊！
看把你能的，他们怎么没聘请你做教授。
如果你坚持看到这里了，那么恭喜你，段子来了，仅供大家休闲一乐。
写段子不易，多谢大家支持公众号。
关于本文adaboost 相关知识和其他问题
欢迎大家加群在群中探讨
欢迎留言或赞赏。
扫描燕哥微信号，
拉你进机器学习大牛群。
福利满满，名额已不多…
群里目前包括：
清华张长水教授，
清华顾险峰教授，
北大黄铁军教授，
西安电子科技大学焦李成教授，
新加坡南洋理工大学黄广斌教授，
北交李清勇教授
等等……
目前100000+人已关注我们微信公众号