3.6 集成学习
3.6.1 什么是集成学习，主要由什么组成
通常把正确率比较高的分类算法称为强分类器，把正确率比较低的分类算法称为弱分类器。构建一个强分类器是最理想的情况，但现实中往往很难，相反，构建弱分类器是比较容易的。那么如何把弱分类“提升”为一个强分类器就是很有意义的问题。
俗话说得好，“三个臭皮匠抵一个诸葛亮”。集成（Ensemble）学习就是利用了这样的思想，通过把多个分类器组合在一起的方式，构建出一个强分类器；这些被组合的分类器也称为基分类器。
事实上，随机森林就属于集成学习的范畴。通常，集成学习具有更强的泛化能力，大量弱分类器的存在降低了分类错误率，也对于数据的噪声有很好的包容性。
集成学习的前提是构建大量的基分类器。很自然的要求是，这些基分类器不能是相同的，否则学习结果和单一的基分类器的结果一样，集成学习也就失去了“集成”的意义。但是，已知一个训练样本往往只能构建一个分类器，怎样从一个训练样本中构建出多个不同的基分类器？又如何将这些基分类器的结果组合在一起呢？Boosting与Bagging就是两种常用的技巧。
3.6.2 试介绍并比较Boosting与Bagging方法
Bagging方法是通过构造不同的训练样本集来构造不同的分类器。具体指利用自助采样法（boostrap sampling）——即多次、有放回地对训练样本进行采样；采取的样本间是相互独立的，而每一次的采样数据集都可以训练出一个基分类器，经过M次采样得到M个基分类器。在组合的部分，Bagging是依据“少数服从多数”的原则组合多个基分类器的分类结果，即与最多的基分类器一致的分类结果是最终的分类结果。
Boosting方法没有改变训练样本集，但通过重赋权（re-weighting）的方式影响了基分类器的损失函数，从而构建出不同的基分类器。具体是指对每一轮的训练数据样本赋予一个权重，在上一轮分类错的点会获得更高的权重，这样进行M次迭代后就构建了M个基分类器。这样每一轮的基分类器依赖于前一轮的基分类器，在组合时也不是简单的投票，而是将M个基分类器根据其“好坏”程度（预测误差的大小程度）采用加权的方式进行组合，预测误差越小的分类器权重越大。
两种方法对比见表3-1。
表3-1 Bagging与Boosting的算法对比
此外，还可以从方差和偏差的角度来理解Bagging与Boosting，模型误差可以分解为估计值方差与偏差平方的和。Bagging的方法将大量基分类器的结果平均化，类似于样本的方差是总体方差除以样本数量，起到了降低方差的作用；而Boosting的通过加大分错样本的权重，使分错的样本在下一轮训练时得到更大的关注，提高了模型的准确率，起到降低偏差的作用。
总之两种算法的区别如下：
1）在样本选择上，Bagging使用boostrap从原始训练集中有放回地重复抽样构建样本，构建的每个训练集都是相互独立的。Boosting的训练集是不变的。
2）在样本权重上，Bagging的每个样本权重一样。Boosting的样本权重则与基模型的分类相关，分类错误的样本具有更高的权重。
3）在预测函数上，Bagging由所有基函数等权重投票组合。Boosting的基函数则是加权相加的。
4）在并行计算上，Bagging可以实现并行运算。Boosting由于基模型的参数根据上一轮的模型结果而来，难以并行计算。
以决策树作为基分类器，这两个方法可以组合成多种集成学习算法。其中随机森林是Bagging方法的典型代表之一；AdaBoost则是Boosting的典型方法之一。在某种程度上，这两种集成学习方法与机器学习算发的关系可以用下面3个式子来粗略表示。
Bagging+决策树=随机森林
AdaBoost+决策树=提升树
Gradient Boosting+决策树=GBDT
3.6.3 AdaBoost算法介绍
以决策树作为基分类器，这两个方法可以组合成多种集成学习算法。其中随机森林是Bagging方法的典型代表之一；AdaBoost则是Boosting的典型算法框架之一。该算法于1995年由Freund与Schapire提出，其中Ada是指“adaptive”，所以也被译为“提升”方法，正所谓将弱的学习算法“提升”为强的学习算法。如何理解AdaBoost的“提升”呢？以二分类问题为例，一个超平面将样本点划分在两个区域。那么可以想象，超平面内部的点很容易被分到正确的区域，得到正确的分类结果，而靠近超平面的点很容易被分错区域。Adaboost算法就是利用Boosting的思想原理，将更多注意力放在这些被分错的点上，争取提升这些点的分类效果，以进行整体模型的分类算法。
AdaBoost的一个重要特点是被基分类器分类错误的样本点的权值会扩大，而分类正确的样本点的权值会缩小——不改变训练数据，而不断改变训练数据权值的分布，使训练数据在基学习器的学习中起到不同的作用。在计算分类误差率时，也会利用样本点的权值，增大分类误差率小的弱分类器的权值，使其在表决中起较大作用，减小分类分类误差率大的弱分类器的权值，使其在表决中起较小的作用。一般在开始时，训练集中所有样本点具有相同的权值。
这里以M个单层决策树作为基分类器Gm(x)的Adaboost算法为例，即每个基分类器只选取一个特征进行一次划分。具体实施步骤如下。
1）初始化样本的权值分布为均匀分布
，令m=1。
2）遍历样本集的所有特征及其取值，并带入权重Wm计算相应的分类误差率：
其中wmi表示在第m轮建模时第i个样本的权重，满足
，故em的取值范围是[0,1]。
选择使2）中分类误差最小的特征及其取值，构建一个单层决策树，记为Gm(x)，其分类误差率为em。
计算基分类器Gm(x)的权重系数：
更新样本的权值分布：
其中Zm为规范化因子，使得权重满足分布条件（即
）。
令m=m+1，重复2）～5）的步骤，得到Gm(x)与am，m=1,2,…,M。
组合M个基分类器：
得到最终的分类器：
G(x)=sign(f(x))
需要注意的是，Adaboost实施过程有这样几个关键的地方：
1）Adaboost涉及两个权重。一个是样本的权重，作用于计算基分类器的分类误差率；另一个是基分类器的权重，作用于最后将所有的基分类器进行线性组合。
2）初始化下的样本权值W1为均匀分布，即所有样本点权重相同。这相当于在原始数据上构建一个没有权重的分类器。
3）理解模型权重αm的意义。根据定义公式，αm反比于分类错误率em，且当
时（通常一定成立），αm≥0成立。这表明基分类器的分类错误率越小，组合的权重越大；当错误率大于0.5，即比完全随机猜测的错误率还低时，说明此时模型将大部分数据分在了相反的类型，这时αm取值小于0，可以看作是把模型的分类结果先调整后再加权重。
4）理解样本权值Wm+1是如何迭代更新的。根据公式，迭代样本权值Wm+1时，若xi被正确分类，则有
，其中
恒小于1，即权重被缩小了；反之
，即分类错误的样本的权值被放大了。
3.6.4 如何理解Adaboost的模型误差部分
Adaboost算法框架成立的思想核心在于通过迭代加权，使得最终组合模型的分类误差率不断减少。本小节从理论的角度对模型误差做简要的分析。
事实上，Adaboost的训练模型误差满足下面3个公式：
上面式（3-3）可由式（3-1）与式（3-2）推理得到，而式（3-1）与式（3-2）本文不再加以证明。根据式（3-3），AdaBoost的模型训练误差是以指数速率下降的。从理论上证明了该方法的有效性与准确性。
3.6.5 AdaBoost模型的优缺点是什么
优点：
1）采用了权重思想的AdaBoost是一种准确率很高的分类器，能比较好地解决过拟合问题。
2）Adaboost其实是运用boosting的一个学习算法框架，具有很好的包容性，其基分类器可以采用各种方法，甚至用构造非常简单的基分类器也能有不错的效果。
3）相较于随机森林，Adaboost还考虑了基分类器的权重。
4）当采用简单的基分类器时，Adaboost的模型结果具有可解释性。相较于随机森林，Adaboost还考虑了基分类器的权重。
缺点：
1）加权的思想使得模型对离群点和噪声比较敏感。
2）模型训练较为耗时，每一次迭代依赖于上一次的结果，无法并行运算。
3）Adaboost的迭代次数不好确认，一般用CV的方法。
3.6.6 什么是前向分步算法
上文里，AdaBoost算法中αm、Wm+1等的计算公式是直接给出的。实际上，这些公式的背后是有推导意义支撑的，都可以由前向分步算法推导出来，因为AdaBoost其实是前向分步算法的一个特例。而前向分步算法则是由加法模型而来。
1.加法模型
加法模型的思想类似于随机森林，也是认为单个个体的能力较弱，于是通过将基分类器组合在一起的方式以增强模型的准确性和稳定性。而基分类器组合的方式就是如其名所示：加权相加。
模型具体如下：
该模型表示总模型是由共M个基函数b(x;γm)相加得到的，其中βm表示基函数的权重，γm表示基函数的参数。
值得一提的是，加法模型中的“加法”有加强的意义；理想的状况是，多个模型（基函数）的优缺点各异，某模型的缺点在一定程度上被大量其他模型抵消，而突出的优点则会得到加强。但是，若基函数的多样性不够，会有相同的缺点出现，就会造成模型冗余，无法提升性能。通俗地讲，最不理想的情况就是，让十个“臭皮匠”在一起最多也只是一个“臭皮匠”，不会变得更差。
为此，会用最小化损失函数的方式学习加法模型：
2.前向分步算法
已知加法模型的损失函数包含大量的参数，最小化损失函数需要同时计算这么多参数，难度较大。为了解决该问题，可利用前向分步算法（Forward stagewise algorithm）。已知要同时求解2×m×M个未知参数，较为复杂，故前向分步算法的主要思想就在于，将叠加在一起的M个模型像拉拉面一样抖开，然后从左到右、从前到后、从第一个到第M个，每一步只关注一个基模型，求得基函数参数及其权重，最终得到多个基模型相加的总的模型。
具体实现步骤如下。
1）令初始基函数为0：f0=0，令m=1。
2）极小化损失函数得到参数βm、γm：
3）更新模型：
fm(x)=fm-1(x)+βmb(x;γm)
4）令m=m+1，重复2）、3）的步骤；直到m=M+1。
5）得到加法模型：
这样，前向分步算法就完成了先“拉拉面”再汇总的模型求解问题。
3.前向分步算法与AdaBoost
事实上，AdaBoost也是加法模型，它是前向分步算法的一个特例，当加法模型的基函数是AdaBoost算法的基分类器并把损失函数设为指数函数时，用前向分步算法求解加法模型就可以推导出AdaBoost算法。
已知，AdaBoost算法的分类器为：
由形式可知，这就是基函数为Gm(x)、基函数权重为αm的加法模型。下面只需证明该向前分步算法的损失函数为指数损失函数。
假设经过m-1轮迭代的前向分步算法，要在第m轮迭代得到αm和Gm。其中，αm和Gm为：
上式等价于
其中smi=exp{-yifm-1(x)}，只依赖于m与i。
先求Gm
再求αm
二者都与AdaBoost模型中的结果完全一致，因此可以证明二者等价，即AdaBoost是前向分步算法的一个特例。