集成学习综述

集成学习综述

集成学习(ensemble learning)本身不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器来完成学习任务。也就是我们常说的“博采众长”。集成学习可以用于分类问题集成，回归问题集成，特征选取集成，异常点检测集成等等，可以说所有的机器学习领域都可以看到集成学习的身影。

1. 集成学习概况

从下图，我们可以对集成学习的思想做一个概括。对于训练集数据，我们通过训练若干个个体学习器（individual learner），通过一定的结合策略，就可以最终形成一个强学习器，以达到博采众长的目的。

图1:集成学习示意图

也就是说，集成学习有两个主要的问题需要解决，第一是如何得到若干个个体学习器，第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器。

2. 集成学习之个体学习器

集成学习的第一个问题就是如何得到若干个个体学习器。这里有两种选择。第一种就是所有的个体学习器都是一个种类的，或者说是同质的（homogeneous），同质集成中的个体学习器也称为“基学习器”（base learner），相应的学习算法称为“基学习算法”（base learning algorithm）。比如都是决策树个体学习器，或者都是神经网络个体学习器。第二种是所有的个体学习器不全是一个种类的，或者说是异质的（heterogeneous）。比如我们有一个分类问题，对训练集采用支持向量机个体学习器，逻辑回归个体学习器和朴素贝叶斯个体学习器来学习，再通过某种结合策略来确定最终的分类强学习器。这时个体学习器一般不称为基学习器，而称作“组件学习器”（component leaner）或直接称为个体学习器。

弱学习器（weak learner）：指泛化性能略优于随机猜测的学习器：例如在二分类问题上精度略高于50%的分类器。

前面提到，集成学习的直觉是结合多个个体的能力，获得远超个体的集体能力优势。这种直觉在实际上对于“弱学习器”是非常符合的。故很多集成学习的研究也都是针对弱学习器，而基学习器有时也被直接称为弱学习器。

一般经验中，如果把好坏不一的东西掺杂在一起，那么最终结果很可能是整体效果比最坏的东西要好一些，但又比最好的那个要坏一些，那么这种情况下不如就让最好的单独去工作，而不要参与混合。但是集成学习还是对多个学习器进行了结合，那它怎么保证整体的效果会比最好的那个单一学习器的效果更好呢。

用一个简单的例子来进行说明：在一个二分类任务中，假设三个分类器在三个测试样本上的表现如下图所示。假设集成学习的结果通过三个个体学习器用投票发（voting）产生，即“少数服从多数”，那么当三个个体学习器分别对三个测试例有不同的判别优势时，集成的效果也会不一样。

图2:集成好而不同

在（a）中，每个分类器原本只有66.6%的精度，集成学习却达到了100%；（b）中，每个分类器都是一样的，集成之后性能没有任何提高；在（c）中，每个分类器的精度只有33.3%，集成之后结果反而变得更糟。

这个例子表明：要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的准确性，即学习器不能太坏，并且要有“多样性”（diversity），即学习器间具有差异。

根据个体学习器生成方式的不同，目前集成学习方法大致可分为两大类，第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成的序列化方法，代表算法是boosting系列算法，第二个是个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成，代表算法是bagging和随机森林（Random Forest）系列算法。

3. 集成学习之boosting

Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。

4. 集成学习之bagging

Bagging的算法原理和 boosting不同，它的弱学习器之间没有依赖关系，可以并行生成。

图3:baging 采样

从图3可以看出，bagging的个体弱学习器的训练集是通过随机采样得到的。通过3次的随机采样，我们就可以得到3个采样集，对于这3个采样集，我们可以分别独立的训练出3个弱学习器，再对这3个弱学习器通过集合策略来得到最终的强学习器。

对于这里的随机采样有必要做进一步的介绍，这里一般采用的是自助采样法（Bootstap sampling）,即对于 m 个样本的原始训练集，我们每次先随机采集一个样本放入采样集，接着把该样本放回，也就是说下次采样时该样本仍有可能被采集到，这样采集 m 次，最终可以得到 m 个样本的采样集，由于是随机采样，这样每次的采样集是和原始训练集不同的，和其他采样集也是不同的，这样得到多个不同的弱学习器。

注：Bootstrap方法是非常有用的一种统计学上的估计方法。 Bootstrap是一类非参Monte Carlo方法,其实质是对观测信息进行再抽样，进而对总体的分布特性进行统计推断。首先，Bootstrap通过重抽样，避免了Cross-Validation造成的样本减少问题，其次，Bootstrap也可以创造数据的随机性。Bootstrap是一种有放回的重复抽样方法，抽样策略就是简单的随机抽样。

随机森林（Random Forest，简称RF）是Bagging的一个扩展变体。其在以决策树作为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。

具体来说，传统决策树在选择划分属性时是在当前结点的属性集合（假定有 d 个属性）中选择一个最优属性；而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 k 个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数 k 控制了随机性的引入程度：若令 k=d ，则基决策树的构建与传统决策树相同；若令 k=1 ，则是随机选择一个属性用于划分；一般情况下，推荐值 $k=lo{g}_2^d$ 。bagging和随机森林算法的原理以后也会讲解。

5. Bagging与Boosting对比

为什么bagging是减少variance，而boosting是减少bias?

Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance（事实上，各模型的分布也近似相同，但不独立）。由于 $E[\frac{\sum X_i}{n}]=E[X_i]$ ，所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有 $Var[\frac{\sum X_i}{n}]=\frac{Var[X_i]}{n}$ ，此时可以显著降低variance。若各子模型完全相同，则 $Var[\frac{\sum X_i}{n}]=Var[X_i]$ ，此时不会降低variance。bagging方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance。为了进一步降低variance，Random forest通过随机选取变量子集做拟合的方式de-correlated了各子模型（树），使得variance进一步降低。

boosting从优化角度来看，是用forward-stagewise这种贪心法去最小化损失函数 $L(y_i,{\sum }_i{a}_i{f}_i(x))$。例如，常见的AdaBoost即等价于用这种方法最小化exponential loss：$L(y,f(x))=exp(-yf(x))$ 。所谓forward-stagewise，就是在迭代的第 n 步，求解新的子模型 $f(x)$ 及步长 $a$ （或者叫组合系数），来最小化 $L(y,f_{n-1}(x)+af(x))$ ，这里 $f_{n-1}(x)$ 是前 n-1 步得到的子模型的和。因此boosting是在sequential地最小化损失函数，其bias自然逐步下降。但由于是采取这种sequential、adaptive的策略，各子模型之间是强相关的，于是子模型之和并不能显著降低variance。所以说boosting主要还是靠降低bias来提升预测精度。

6. 集成学习之结合策略

假设集成中包含 T 个基学习器 $h_1,h_2,\cdots ,h_T$，其中 $h_i$ 在示例 x 上的输出为 $h_i(x)$ 。那么对 $h_i$ 进行结合的常见策略有以下几种：

6.1 平均法

对于数值类的回归预测问题，通常使用的结合策略是平均法，也就是说，对于若干个弱学习器的输出进行平均得到最终的预测输出。最简单的平均是算术平均，也就是说最终预测是:

$$H(x)=\frac{1}{T}\sum _{i=1}^T{h}_i(x)$$

如果每个个体学习器有一个权重 $\omega$ ，则最终预测是:

$$H(x)=\sum _{i=1}^T{\omega }_i{h}_i(x)$$

其中 $\omega$ 是个体学习器 $h_i$ 的权重， ${\omega }_i>=0,{\sum }_{i=1}^T{\omega }_i=1$。

一般而言，在个体学习器的性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。

6.2 投票法

对于分类问题的预测，我们通常使用的是投票法。假设我们的预测类别是 { c 1 , c 2 , ⋯   , c K } \lbrace c_1,c_2 ,\cdots,c_K \rbrace {c1​,c2​,⋯,cK​} ，对于任意一个预测样本 x ，我们的 T 个弱学习器的预测结果分别是 ($h_1(x),h_2(x),\cdots ,h_T(x)$)。

最简单的投票法是相对多数投票法（plurality voting），也就是我们常说的少数服从多数，也就是 T 个弱学习器的对样本 x 的预测结果中，数量最多的类别 $c_i$ 为最终的分类类别。如果不止一个类别获得最高票，则随机选择一个做最终类别。

稍微复杂的投票法是绝对多数投票法（majority voting），也就是我们常说的要票过半数。在相对多数投票法的基础上，不光要求获得最高票，还要求票过半数。否则会拒绝预测。

更加复杂的是加权投票法（weighted voting），和加权平均法一样，每个弱学习器的分类票数要乘以一个权重，最终将各个类别的加权票数求和，最大的值对应的类别为最终类别。

6.3 学习法

上两节的方法都是对弱学习器的结果做平均或者投票，相对比较简单，但是可能学习误差较大，于是就有了学习法这种方法，对于学习法，代表方法是stacking，当使用stacking的结合策略时， 我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们将训练集弱学习器的学习结果作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果。

在这种情况下，我们将弱学习器称为初级学习器，将用于结合的学习器称为次级学习器。对于测试集，我们首先用初级学习器预测一次，得到次级学习器的输入样本，再用次级学习器预测一次，得到最终的预测结果。

7. 集成学习之Stacking

将训练好的所有基模型对训练基进行预测，第j个基模型对第i个训练样本的预测值将作为新的训练集中第i个样本的第j个特征值，最后基于新的训练集进行训练。同理，预测的过程也要先经过所有基模型的预测形成新的测试集，最后再对测试集进行预测：

图4:stacking流程

Stacking算法分为2层，第一层是用不同的算法形成T个弱分类器，同时产生一个与原数据集大小相同的新数据集，利用这个新数据集和一个新算法构成第二层的分类器。

Stacking 就像是 Bagging的升级版，Bagging中的融合各个基础分类器是相同权重，而Stacking中则不同,Stacking中第二层学习的过程就是为了寻找合适的权重或者合适的组合方式。