boosting
Bagging和boosting 概念及区别
Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法。即将弱分类器组装成强分类器的方法。
首先介绍Bootstraping，即自助法：它是一种有放回的抽样方法（可能抽到重复的样本）。
1、Bagging (bootstrap aggregating)
Bagging即套袋法，其算法过程如下：
A）从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行m轮抽取，得到m个训练集。（k个训练集之间是相互独立的）
B）每次使用一个训练集得到一个模型，m个训练集共得到m个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
C）对分类问题：将上步得到的m个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
2、Boosting
其主要思想是将弱分类器组装成一个强分类器。在PAC（概率近似正确）学习框架下，则一定可以将弱分类器组装成一个强分类器。
关于Boosting的两个核心问题：
1）在每一轮如何改变训练数据的权值或概率分布？
通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。
2）通过什么方式来组合弱分类器？
通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。
而提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。
3、Bagging，Boosting二者之间的区别
Bagging和Boosting的区别：
1）样本选择上：
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
2）样例权重：
Bagging：使用均匀取样，每个样例的权重相等
Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。
3）预测函数：
Bagging：所有预测函数的权重相等。
Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
4）并行计算：
Bagging：各个预测函数可以并行生成
Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。
4、总结
这两种方法都是把若干个分类器整合为一个分类器的方法，只是整合的方式不一样，最终得到不一样的效果，将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果，但是也增大了计算量。
下面是将决策树与这些算法框架进行结合所得到的新的算法：
1）Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT
1、AdaBoost:
Adaboost 算法很有名，全称是adaptive boosting。 曾被称为数据挖掘十大算法之一。
Adaboost是一种基于boost思想的一种自适应的迭代式算法。通过在同一个训练数据集上训练多个弱分类器(weak classifier)， 然后把这一组弱分类器ensmble起来， 产生一个强分类器（strong classifier）。可以说是一个meta algorithms。
该算法的优点如下：
(1) 具有较低的泛化误差（low generalization）
(2) 改善了分类器的分类正确率
(3) 可以将这个算法配合多个分类算法使用。 例如， 我们可以选择C4.5， CART， SVM, 贝叶斯分类器, 或者decision stump等作为我们的弱分类器。
(4)容易coding
(5)不容易出现overfiting(过拟合)现象
缺点如下：
对outliers（异常点）非常的sensitive。 因为异常点容易分错， 会逐级影响后面的产生的弱分类器。
Adaboost每一轮迭代的时候都会训练一个新的弱分类器。 直至达到某个预定的足够小的错误率。
Adaboost的自适应在于：
最开始， 所有的训练样本具有相同权重。 被前一个分类器分错的样本会被用于训练下一个分类器， 即提高这个分错的样本被选中进入下一个弱分类器选中的概率， 分对的样本被选中的概率会被降低。
Adaboost方法对于噪声数据和异常数据敏感。 Adaboos使用的弱分类器的分类效果只要比random guess(正确率为0.5)好可以了。 究竟正确率为多少， 不管， 只要大于0.5就好了。 最终， 我们会得到一个较好的模型。 对于错误率高于0.5的弱分类器也是有用的。 因为最终得到的多个弱分类器进行线性叠加的时候， 可以赋给它们系数， 同样也能提升分类效果。
Adaboost是boosting思想的运用， 弱分类器可以是一个decision stump classifier。
一个decision stump 就是具有一个节点的决策树。 一个decision stump 一次对一个特征进行决策。 这个decision tree只做一次split， 所以是一个stump。
下面我们举一个简单的例子来看看adaboost的实现过程：
图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。
1）、根据分类的正确率，得到一个新的样本分布(样本中每个元素的权重分布)D2，一个子分类器h1。其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本做了加权。
也许你对上面的ɛ1，ɑ1 怎么算的也不是很理解。算法最开始给了一个均匀分布 D 。所以h1 里的每个点的值是0.1。当划分后，有三个点划分错了，根据算法误差表达式
得到误差为分错的三个点的值之和，所以。εt=(0.1+0.1+0.1)=0.3,
2）、然后根据算法把分错点的权值变大，分错点的权值计算如下：
对于分类正确的7个点，其权值保持不变，为0.1；对于分类错误的3个点，其权值为
3）根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2。
4）根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2。
如上图所示，弱分类器h2 中有三个“-”符号分类错误，
分类错误的权值为：we2=0.1*3=0.3；
上图中十个点的总权值为：wt2=0.1*7+0.233*3=1.3990；
错误率为：ε2=we2/wt2=0.3/1.399= 0.2144;
对于分类错误的三个点，其权值为:
于是，分类错误的三个点误差增加为0.3664如此迭代
5）得到一个子分类器h3
如上图所示，弱分类器h3 中有两个“+”符号和一个“-”符号分类错误，分类错误的权值为we3=0.1*2+0.1*1=0.3；
上图中十个点的总权值为：wt3=0.1*4+0.233*3+0.3664*3=2.1982；
错误率为： εt=we3/wt3=0.3/2.1982= 0.1365;
对于分类错误的三个点，其权值为:
于是，分类错误的三个点误差增加为0.6326如此迭代
6）整合所有子分类器：
每个区域是属于哪个属性，由这个区域所在分类器的权值综合决定。比如左下角的区域，属于蓝色分类区的权重为h1 中的0.42和h2 中的0.65，其和为1.07；属于淡红色分类区域的权重为h3 中的0.92；属于淡红色分类区的权重小于属于蓝色分类区的权值，因此左下角属于蓝色分类区。
因此可以得到整合的结果如上图所示，从结果图中看，即使是简单的分类器，组合起来也能获得很好的分类效果。
我们可以看到adaboost的一个详细的算法过程。Adaboost是一种比较有特点的算法，可以总结如下：
1）每次迭代改变的是样本的分布，而不是重复采样（re weight)
2）样本分布的改变取决于样本是否被正确分类
总是分类正确的样本权值低
总是分类错误的样本权值高（通常是边界附近的样本）
3）最终的结果是弱分类器的加权组合
权值表示该弱分类器的性能
简单来说，Adaboost有很多优点:
1)adaboost是一种有很高精度的分类器
2)可以使用各种方法构建子分类器，adaboost算法提供的是框架
3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单
4)简单，不用做特征筛选
5)不用担心overfitting！
总之：adaboost是简单，有效。
五 、Adaboost 疑惑和思考
为什么每次迭代都要把分错的点的权值变大呢？这样有什么好处呢？
我看了好几篇介绍adaboost 的博客，都没有解答我的疑惑，也许大牛认为太简单了，不值一提，或者他们并没有意识到这个问题而一笔带过了。
然后我仔细一想，也许提高错误点可以让后面的分类器权值更高。
然后看了adaboost算法，和我最初的想法很接近，但不全是。 注意到算法最后的表到式为
，这里面的a
表示的权值，是由
得到的。而a是关于误差的表达式，到这里就可以得到比较清晰的答案了，所有的一切都指向了误差。
提高错误点的权值，当下一次分类器再次分错了这些点之后，会提高整体的错误率，这样就导致 a 变的很小，最终导致这个分类器在整个混合分类器的权值变低。
也就是说，这个算法让优秀的分类器占整体的权值更高，而挫的分类器权值更低。这个就很符合常理了。