1 集成学习算法

先讲一点预备知识。

前面我们讲了决策树和随机森林，决策树是弱学习器，随机森林是集成了弱学习器的强学习器。

事实上，集成算法有三种：Bagging，Boosting 和 Stacking。

随机森林就是一种经典的bagging算法。

1.1 bagging

Bagging 全称叫 Bootstrap aggregating，看到 Bootstrap 我们立刻想到著名的开源前端框架（抖个机灵，是 Bootstrap 抽样方法） ，每个基学习器都会对训练集进行有放回抽样得到子训练集，比较著名的采样法为 0.632 自助法。每个基学习器基于不同子训练集进行训练，并综合所有基学习器的预测值得到最终的预测结果。Bagging 常用的综合方法是投票法，票数最多的类别为预测类别。

1.2 stacking

Stacking 是先用全部数据训练好基模型，然后每个基模型都对每个训练样本进行的预测，其预测值将作为训练样本的特征值，最终会得到新的训练样本，然后基于新的训练样本进行训练得到模型，然后得到最终预测结果。

1.3 boosting

Boosting 训练过程为阶梯状，基模型的训练是有顺序的，每个基模型都会在前一个基模型学习的基础上进行学习，最终综合所有基模型的预测值产生最终的预测结果，用的比较多的综合方式为加权法。

那么，为什么集成学习会好于单个学习器呢？原因可能有三：

1. 训练样本可能无法选择出最好的单个学习器，由于没法选择出最好的学习器，所以干脆结合起来一起用；

2. 假设能找到最好的学习器，但由于算法运算的限制无法找到最优解，只能找到次优解，采用集成学习可以弥补算法的不足；

3. 可能算法无法得到最优解，而集成学习能够得到近似解。比如说最优解是一条对角线，而单个决策树得到的结果只能是平行于坐标轴的，但是集成学习可以去拟合这条对角线。

这一节我们介绍的就是Adboost，一种boosting算法。

2 Adboost

AdaBoost（Adaptive Boosting，自适应增强），其自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

这么说可能比较笼统抽象，我们具体来看。

2.1 单层决策树

单层决策树是决策树的最简化版本，只有一个决策点，也就是说，如果训练数据有多维特征，单层决策树也只能选择其中一维特征来做决策，并且还有一个关键点，决策的阈值也只有一个。

单层决策树

对于单层决策树，以下两种情况都是不可取的：

一个单层决策树不可以有两个决策点

一个单层决策树不可以有两个特征维度

adboost就是将多个单层决策树进行叠加，假设我们的数据有k个特征，第i层根据某一个特征对数据进行二分类，因此，adboost是一个二分类算法，请看下面这张图：

这是一个构建好的三层Adboost决策树，图中蓝色圆点标签y=1,黄色圆点标签y=0；橙色分割线是第一层决策树，绿色分割线是第二层决策树，蓝色分割线是第三层决策树；绿色圆点是待分类样本。

根据第一层（橙色分割线）我们将它分为0；根据第二层（绿色分割线）我们将它分为0；根据第三层（蓝色分割线）我们最终将待预测点分类为1.。这就是使用Adboost预测的基本原理，他就是把平面分割成许多大大小小的区域，每个区域有不同的标签值。

关于决策树的内容，我们在之前的一节花了很多功夫讲过，其中比较重要的关于每一个特征维度的阈值分割，使用到了信息论的知识，包括信息增益、基尼系数等。这一节的单层决策树的分割，我们仅仅使用错分率来衡量，具体分割过程如下：

1. 在当前维度xi上，取每相邻两个点的中间值作为分割值

2. 计算错分率

3. 错分率最小的值作为该层决策树的分割阈值

刚刚已经介绍了单层决策树的原理，但这里有一个问题，如果训练数据保持不变，那么在数据的某个特定维度上单层决策树找到的最佳决策点每一次必然都是一样的，也就是上图中的绿色分割线和蓝色分割线，必然会计算得出同一个值。

另一个问题是这么多层决策树对每一个待预测样本都有自己的结论，那我们怎么综合所有决策树的意见呢？

接下来就要引出关于Adaboost的两种权重了。

2.2 关于Adaboost的两种权重

Adaboost算法中有两种权重，一种是数据的权重，另一种是弱分类器的权重。其中，数据的权重主要用于弱分类器寻找其分类误差最小的决策点，找到之后用这个最小误差计算出该弱分类器的权重（发言权）；分类器权重越大说明该弱分类器在最终决策时拥有更大的发言权。

1. 数据的权重

举个例子，在以前没有权重时（其实是平均权重时），一共10个点时，对应每个点的权重都是0.1，分错1个，错误率就加0.1；分错3个，错误率就是0.3。现在，每个点的权重不一样了，还是10个点，权重依次是[0.01,0.01,0.01,0.01,0.01,0.01, 0.01,0.01,0.01,0.91]，如果分错了第1一个点，那么错误率是0.01，如果分错了第3个点，那么错误率是0.01，要是分错了最后一个点，那么错误率就是0.91。这样，在选择决策点的时候自然是要尽量把权重大的点（本例中是最后一个点）分对才能降低误差率。由此可见，权重分布影响着单层决策树决策点的选择，权重大的点得到更多的关注，权重小的点得到更少的关注。

还是用这张图来解释：

第一层（橙色分割线）分割后，右边的点标签为1，是分类正确的，到了第二层（绿色分割线）的时候，我们就更加关注那些上一层被错分为0的蓝色点，以此类推。这就是数据权重的作用。

在Adaboost算法中，每训练完一个弱分类器都就会调整权重，上一轮训练中被误分类的点的权重会增加，在本轮训练中，由于权重影响，本轮的弱分类器将更有可能把上一轮的误分类点分对，如果还是没有分对，那么分错的点的权重将继续增加，下一个弱分类器将更加关注这个点，尽量将其分对。

这样，达到“你分不对的我来分”，下一个分类器主要关注上一个分类器没分对的点，每个分类器都各有侧重。

这样，即便在同一个维度进行分割，每一层都能够得到不一样的“最佳分割值”。

2. 单层决策树的权重

由于Adaboost中若干个分类器的关系是第N个分类器更可能分对第N-1个分类器没分对的数据，而不能保证以前分对的数据也能同时分对。所以在Adaboost中，每个弱分类器都有各自最关注的点，每个弱分类器都只关注整个数据集的中一部分数据，所以它们必然是共同组合在一起才能发挥出作用。所以最终投票表决时，需要根据弱分类器的权重来进行加权投票，权重大小是根据弱分类器的分类错误率计算得出的，总的规律就是弱分类器错误率越低，其权重就越高。

还是以这张图举例，第一层（橙色分割线）将A1区域错分为0；第二层（绿色分割线）将上一层错分为0的A1区域，分类正确为1；但第三层（蓝色分割线）却不能依然将上一层分类正确的A1区域再次错分为0。因此在最终输出的时候，我们只要给第二层决策树一个较高的权重，就能保证最后我们得到的A1区域分类正确。这就是决策树权重的作用。

3. 图解Adaboost加权表决结果

比如在一维特征时，经过3次迭代，并且知道每次迭代后的弱分类器的决策点与发言权，看看如何实现加权投票表决的。

如图所示，3次迭代后得到了3个决策点，

最左边的决策点是小于（等于）7的分为+1类，大于7的分为-1类，且分类器的权重为0.5；

中间的决策点是大于（等于）13的分为+1类，小于13分为-1类，权重0.3；

最右边的决策点是小于（等于19）的分为+1类，大于19分为-1类，权重0.4。

对于最左边的弱分类器，它的投票表示，小于（等于）7的区域得0.5，大与7得-0.5，同理对于中间的分类器，它的投票表示大于（等于）13的为0.3，小于13分为-0.3，最右边的投票结果为小于（等于19）的为0.4，大于19分为-0.4，如下图：

求和可得：

最后进行符号函数转化即可得到最终分类结果：

2.3 损失函数

现在我们已经弄明白了数据权重与决策器权重各自的含义，接下来介绍损失函数，也就是具体怎么计算数据权重与决策器权重，有推导过程。

第 k 轮的强学习器为：

定义损失函数为 n 个样本的指数损失函数：

利用前向分布学习算法的关系可以得到：

因为 已知，所以令 ，随着每一轮迭代而将这个式子带入损失函数，损失函数转化为：

我们求，可以得到：

将 带入损失函数，并对求导，使其等于 0，则就得到了：

其中，  即为我们前面的分类误差率。

2.4 正则化

2.5 算法步骤总结

Adaboost 迭代算法有三步：

初始化训练样本的权值分布，每个样本具有相同权重；

训练弱分类器，如果样本分类正确，则在构造下一个训练集中，它的权值就会被降低；反之提高。用更新过的样本集去训练下一个分类器；

将所有弱分类组合成强分类器，各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，降低分类误差率大的弱分类器的权重。

2.6 二分类与多分类

和其它二分类算法拓展到多分类算法一样，这里不再赘述。

2.7 优缺点

优点

分类精度高；

可以用各种回归分类模型来构建弱学习器，非常灵活；

不容易发生过拟合。

缺点

对异常点敏感，异常点会获得较高权重。

3 bagging与boosting

这里我们延伸一点方差与偏差的内容，基础知识请看调参那一节。

我们常说集成学习中的基模型是弱模型，通常来说弱模型是偏差高（在训练集上准确度低）方差小（防止过拟合能力强）的模型，但并不是所有集成学习框架中的基模型都是弱模型。Bagging 和 Stacking 中的基模型为强模型（偏差低，方差高），而Boosting 中的基模型为弱模型（偏差高，方差低）。

在 Bagging 和 Boosting 框架中，通过计算基模型的期望和方差我们可以得到模型整体的期望和方差。为了简化模型，我们假设基模型的期望为  ，方差 ，模型的权重为 ，两两模型间的相关系数 相等。由于 Bagging 和 Boosting 的基模型都是线性组成的，那么有：

模型总体期望：

模型总体方差（公式推导参考协方差的性质，协方差与方差的关系）：

模型的准确度可由偏差和方差以及噪声共同决定：

3.1 Bagging 的偏差与方差

对于 Bagging 来说，每个基模型的权重等于 1/m 且期望近似相等，故我们可以得到：

通过上式我们可以看到：

整体模型的期望等于基模型的期望，这也就意味着整体模型的偏差和基模型的偏差近似。

整体模型的方差小于等于基模型的方差，当且仅当相关性为 1 时取等号，随着基模型数量增多，整体模型的方差减少，从而防止过拟合的能力增强，模型的准确度得到提高。但是，模型的准确度一定会无限逼近于 1 吗？并不一定，当基模型数增加到一定程度时，方差公式第一项的改变对整体方差的作用很小，防止过拟合的能力达到极限，这便是准确度的极限了。

在此我们知道了为什么 Bagging 中的基模型一定要为强模型，如果 Bagging 使用弱模型则会导致整体模型的偏差提高，而准确度降低。

Random Forest 是经典的基于 Bagging 框架的模型，并在此基础上通过引入特征采样和样本采样来降低基模型间的相关性，在公式中显著降低方差公式中的第二项，略微升高第一项，从而使得整体降低模型整体方差。

3.2 Boosting 的偏差与方差

对于 Boosting 来说，由于基模型共用同一套训练集，所以基模型间具有强相关性，故模型间的相关系数近似等于 1，针对 Boosting 化简公式为：

通过观察整体方差的表达式我们容易发现：

整体模型的方差等于基模型的方差，如果基模型不是弱模型，其方差相对较大，这将导致整体模型的方差很大，即无法达到防止过拟合的效果。因此，Boosting 框架中的基模型必须为弱模型。

此外 Boosting 框架中采用基于贪心策略的前向加法，整体模型的期望由基模型的期望累加而成，所以随着基模型数的增多，整体模型的期望值增加，整体模型的准确度提高。

基于 Boosting 框架的 Gradient Boosting Decision Tree 模型中基模型也为树模型，同 Random Forrest，我们也可以对特征进行随机抽样来使基模型间的相关性降低，从而达到减少方差的效果。

3.3 小结

我们可以使用模型的偏差和方差来近似描述模型的准确度；

对于 Bagging 来说，整体模型的偏差与基模型近似，而随着模型的增加可以降低整体模型的方差，故其基模型需要为强模型；

对于 Boosting 来说，整体模型的方差近似等于基模型的方差，而整体模型的偏差由基模型累加而成，故基模型需要为弱模型。

4. 参考链接

Adaboost入门教程——最通俗易懂的原理介绍（图文实例）

https://blog.csdn.net/px_528/article/details/72963977

【机器学习】决策树（中）——Random Forest、Adaboost、GBDT （非常详细）

https://zhuanlan.zhihu.com/p/86263786