集成学习

2019-01-10

集成学习是将几种机器学习技术组合成一个预测模型的元算法，以达到减小方差（bagging）、偏差（boosting）或改进预测（stacking） 的效果。

集合方法可分为以下两类：

  • 序列集成方法，其中参与训练的基础学习器按照顺序生成（例如 AdaBoost）。序列方法的原理是利用基础学习器之间的依赖关系。通过对之前训练中错误标记的样本赋值较高的权重，可以提高整体的预测效果。
  • 并行集成方法，其中参与训练的基础学习器并行生成（例如 Random Forest）。并行方法的原理是利用基础学习器之间的独立性，通过平均可以显著降低错误。

一般来说，按照基本分类器之间的类型关系可以把集成学习方法划分为异态集成学习和同态集成学习。同态集成学习主要有Bagging和Boosting方法，异态集成学习有Stacking方法。集成学习要求基本的学习器错误率不能超过0.5，否则集成学习结果会提高错误率。

1 Bagging

Bagging是Bootstrap Aggregating的简称，对训练数据擦用自助采样(Boostrap sampling)，即有放回地采样；每一次的采样数据集训练出一个基分类器，经过$M$次采样得到$M$个基分类器。对于训练得到的$M$个基分类器，分类问题可以采用投票方法，回归问题可以采用平均的方法来进行对测试样例的判断。具体的过程如下：

  1. 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping（有放回）的方法抽取$n$个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行$K$轮抽取，得到$K$个训练集。（我们这里假设$K$个训练集之间是相互独立的，事实上不是完全独立）
  2. 每次使用一个训练集得到一个模型，$K$个训练集共得到$K$个模型。但是是同种模型。（注：$K$个训练集虽然有重合不完全独立，训练出来的模型因为是同种模型也是不完全独立。这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
  3. 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）
    • Voting 投票策略：就是每个模型对测试样例进行投票，票数多的为测试的结果，如果出现投票数相同，要么随机选择一个，要么重新训练一个模型进行再分类。
    • Average 均值策略：就是对所有的结果进行平均，一个改进的版本可以用加权的方式进行平均。例如$A$、$B$、$C$三个分类器得到的结果先进行排序，根据排序的不同赋予不同的权重

Bagging算法中，基分类器之间不存在依赖关系，基分类器可以并行生成。

Bagging的性能依赖于基分类器的稳定性，如果基分类器是不稳定的，bagging有助于减低训练数据的随机扰动导致的误差，但是如果基分类器是稳定的，即对数据变化不敏感，那么bagging方法就得不到性能的提升，甚至会减低。

注意： 对于Bagging需要注意的是，每次训练集可以取全部的特征进行训练，也可以随机选取部分特征训练，例如随机森林就是每次随机选取部分特征。
bagging

1.1 随机森林(Random Forest)

随机森林是以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性选择。随机森林主要用于分类和回归。

随机森林是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。在建立每一棵决策树的过程中，有两点需要注意——采样与完全分裂。

  • 采样： 首先是两个随机采样的过程，Random Forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为$N$个，那么采样的样本也为$N$个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现过拟合。然后进行列采样，从$M$个属性中随机选择$m$个( $m << M$ )。
  • 完全分裂： 之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤——剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现过拟合。

决策树的构建过程：

  1. 假如有$N$个样本，则有放回的随机选择$N$个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的$N$个样本用来训练一个决策树，作为决策树根节点处的样本。
  2. 当每个样本有$M$个属性时，在决策树的每个节点需要分裂时，随机从这$M$个属性中选取出$m$个属性，满足条件$m << M$【推荐值$m=\log_2 M$】。然后从这$m$个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。
  3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。
  4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。

优点：

  • 在数据集上表现良好
  • 在当前的很多数据集上，相对其他算法有着很大的优势
  • 它能够处理很高维度(feature很多)的数据，并且不用做特征选择
  • 在训练完后，它能够给出哪些feature比较重要
  • 在创建随机森林的时候，对generlization error(泛化误差)使用的是无偏估计
  • 训练速度快
  • 在训练过程中，能够检测到feature间的互相影响
  • 容易做成并行化方法
  • 实现比较简单

缺点：

  • 当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大
  • 随机森林模型还有许多不好解释的地方，有点算个黑盒模型

2 Boosting

Boosting利用一种迭代的方法，每一次训练的数据都在前一次训练的基础上产生。具体来说就是在每一次训练的时候会更加关心分类错误的样例，给这些分类错误的样例增加更大的权重。然后进行迭代训练，最后将这些分类器进行加权得到最后的分类器。但是Boosting方法虽然会比Bagging更容易得到好的效果，也会存在过拟合的问题。具体过程如下：

  1. 开始的时候在训练集$T$上，每一个训练样本都被赋予一个初始权重，然后训练一个弱分类器，计算该分类器的误差，然后利用该误差计算该分类器的权重系数；
  2. 根据上一步的结果对训练集$T$进行权值调整，训练集$T$中数据被赋予新的权值：对错分的样本数据增加权重，对正确分类的样本数据进行降低权重；得到权值调整后，更新好的训练集$T'$；
  3. 在权值调整后的训练集$T'$上，进行弱分类器的学习训练；
  4. 迭代步骤2，直到弱学习器数达到事先指定的数目$X$或误差低于阈值；
  5. 最终将弱学习器通过结合策略进行整合，得到最终的强学习器。

Boosting算法中，基分类器之间存在强依赖关系，基分类器需要串行生成。
boosting

2.1 AdaBoost

AdaBoost算法是基于Boosting思想的机器学习算法，AdaBoost是一种迭代型的算法，其核心思想是针对同一个训练集训练不同的学习算法，即弱学习算法，然后将这些弱学习算法集合起来，构造一个更强的最终学习算法。为了构造出一个强的学习算法，首先需要选定一个弱学习算法，并利用同一个训练集不断训练弱学习算法，以提升弱学习算法的性能。

Adaboost算法在分类问题中的主要特点：通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类性能。

Adaboost算法仅适用于二分类任务。

Adaboost算法使用的是指数损失函数:$exp(-f(x)h(x))$。

整个Adaboost 迭代算法就3步：

  1. 初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
  2. 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。 迭代的终止条件是强分类器的错误率达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。
  3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

adaboost伪代码
对于第4行计算基分类器$h_t(x)$在加权训练集上的分类误差率：

\[\epsilon_t=P(h_t(x) \neq f(x))=\sum_{h_t(x_i) \neq f(x_i)}w_{ti}\]

这里，$w_{ti}$表示第$t$轮中第$i$个实例的权值，$\sum_{i=1}^Nw_{ti}=1$。这表明，$h_t(x)$在加权训练集上的分类误差是被$h_t(x)$误分类样本的权重之和。

对于第6行计算基分类器$h_t(x)$的权重系数$\alpha_t$,$\alpha_t$表示基分类器$h_t(x)$在最终分类器中的重要性，当$\epsilon_t\leq 0.5$时，$\alpha_t\geq 0$，并且$\alpha_t$随着$\epsilon_t$的减小而增大，所以分类误差率越小的基分类器在最终分类器中的作用越大。

对于第7行是在更新训练集的权重分布，其中$Z_t$是规范化因子。

\[D_{t+1}(x)=(w_{t+1,1},...,w_{t+1,i},...,w_{t+1,N}) w_{t+1,i}=\begin{cases}\frac{w_{ti}}{Z_t}e^{-\alpha_t}&h_t(x)=f(x)\\\\ \frac{w_{ti}}{Z_t}e^{\alpha_t}&h_t(x)\neq f(x)\end{cases} Z_t=\sum\limits_{i=1}^Nw_{ti}exp(-\alpha_tf(x_i)h_{t}(x_i))\]

由此可知，被基分类器$h_t(x)$误分类样本的权重值会得以扩大，而正确分类的样本权重值会缩小。

2.2 提升树(Boosted Decision Tree)

提升决策树是指以分类与回归树(CART) 为基本分类器的提升方法。

提升方法采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（Boosting tree）。对分类问题构建的决策树是二叉分类树，对回归问题构建决策树是二叉回归树。回归问题的提升树是迭代多棵回归树来共同决策，采用平方误差损失函数，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树，残差的意义如公式：残差=真实值-预测值 。提升树模型可以表示为决策树的加法模型：

\[f_M(x)=\sum\limits_{m=1}^MT(x;\Theta_m)\]

其中$T(x;\Theta_m)$表示决策树；$\Theta_m$为决策树的参数，$M$为树的个数。
提升树算法采用前向分步算法。首先确定初始提升树$f_0(x)=0$，第m步的模型为：

\[f_m(x)=f_{m-1}(x)+T(x;\Theta_m)\]

其中，$f_{m-1}(x)$为当前模型，通过经验风险极小化确定下课决策树的参数$\Theta_m$:

\[\hat\Theta_m=\mathop{\arg\min}\limits_{\Theta_m}\sum\limits_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m))\]

不同问题的提升树学习算法，其主要区别在于损失函数不同。平方损失函数常用于回归问题，用指数损失函数用于分类问题，以及绝对损失函数用于决策问题。

2.2.1 二叉分类树

对于二类分类问题，提升树算法只需要将AdaBoost算法例子中的基本分类器限制为二叉分类树即可，可以说此时的决策树算法时AdaBoost算法的特殊情况。

2.2.2 二叉回归树

已知训练集$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$，$x_i\in X \subseteq R^n$，$X$为输入空间，$y_i\in Y \subseteq R^n$，$Y$为输出空间。如果将输入空间$X$划分为$J$个不相交的区域$R_1,R_2,...,R_J$，并且在每个区域上确定输出的常量$c_j$，那么树可以表示为：

\[T(x,\Theta)=\sum\limits_{j=1}^Jc_jI(x\in R_j)\]

其中，$I(x)$为指示函数，参数$\Theta=\{(R_1,c_1),(R_2,c_2),...,(R_J,c_J)\}$表示树的区域划分和各区域上的常数。$J$是回归树的复杂度即叶子结点个数。

回归问题提升树使用以下前向分步算法：

\[f_0(x)=0 \\ f_m(x)=f_{m-1}(x)+T(x;\Theta_m),m=1,2,3,...,m \\ f_M(x)=\sum\limits_{m=1}^MT(x;\Theta_m)\]

在前向分布算法的第$m$步，给定当前模型$f_{m-1}(x)$，需求解：

\[\hat\Theta_m=\mathop{\arg\min}\limits_{\Theta_m}\sum\limits_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i,\Theta_m))\]

得到$\hat\Theta_m$，即第$m$棵树的参数。
当采用平方误差损失函数时：

\[L(y,f(x))=(y-f(x))^2\]

将平方误差损失函数展开为：

\[L(y_i,f_{m-1}(x)+T(x,\Theta_m))=[y-f_{m-1}(x)-T(x,\Theta_m)]^2=[r-T(x,\Theta_m)]^2\]

其中，$r=y-f_{m-1}(x)$是当前模型你和数据的残差。所以，对回归问题的提升树算法来说，只需要简单地拟合当前模型的残差。
提升树

2.3 梯度提升决策树(Gradient Boosting Decision Tree)

Gradient Boosting也是一种Boosting的方法，它主要的思想是：每一次建立模型是在之前建立模型损失函数的梯度下降方向。损失函数(loss function)描述的是模型的不靠谱程度，损失函数越大，则说明模型越容易出错。如果我们的模型能够让损失函数持续的下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度（Gradient)的方向上下降。

GBDT可以用来做分类和回归。是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。GBDT的基学习器是决策树，且是CART回归树，不管是分类问题还是回归问题，GBDT使用的都是CART回归树。理解GBDT重点首先是Gradient Boosting，其次才是 Decision Tree。GBDT 是 Gradient Boosting 的一种具体实例，只不过这里的弱分类器是决策树。

在说GBDT前，我们先说下它的俩前缀Gradient Boosting：

  • Boosting: 这是一种迭代算法，每一次训练都是在前面已有模型的预测基础上进行。最简单地说，先训练一个初始模型，对比真实值和预测值的残差；用残差再训练一个模型，再计算残差；再训练。这样，每一个模型都专注于修正前面模型最不给力的效果方面。于是，通过这种方式联合多个弱分类器，就能得到一个强分类器。
  • Gradient: 梯度。对于单个变量来说，就是一阶导数。前面Boosting要计算残差，方法就很多了，你可以直接相减，也可以定义个函数。这里Gradient就是说用梯度来计算残差。

所以说Gradient Boosting是一种算法框架，它是用Grdient计算残差的Boosting过程，而GBDT只是用决策树来训练的一种具体实现。

我们也可以利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中残差的近似值，拟合一个回归树。
损失函数的负梯度为：

\[-\left[\dfrac{dL(y_i,f(x_i))}{df(x_i)}\right]_{f(x)=f_{m-1}(x)}\approx r_{mi}\]

梯度提升算法

3 Stacking

Stacking本质上是一种分层的结构，第一层通常是我们使用的不同基础模型，例如NN、决策树、KNN等。然后最后一层模型一般使用逻辑回归（LR）对这些模型进行进一步训练。

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

4 总结

4.1 Bagging和Boosting的区别

  1. 样本选择上：
    • Bagging： 训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的；
    • Boosting： 每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。
  2. 样例权重：
    • Bagging： 使用均匀取样，每个样例的权重相等；
    • Boosting： 根据错误率不断调整样例的权值，错误率越大则权重越大。
  3. 预测函数：
    • Bagging： 所有基分类器的权重相等；
    • Boosting： 每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。
  4. 并行计算：
    • Bagging： 各个预测函数可以并行生成；
    • Boosting： 理论上各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。计算角度来看，两种方法都可以并行。
  5. Bagging是减少variance(方差)，而Boosting是减少bias(偏差)。

4.2 Random Forest与Bagging的区别

  1. 输入样本数目： Random Forest是选与输入样本的数目相同多的次数（可能一个样本会被选取多次，同时也会造成一些样本不会被选取到），而Bagging一般选取比输入样本的数目少的样本；
  2. 特征数目： Bagging是用全部特征来得到分类器，而Random Forest是需要从全部特征中选取其中的一部分来训练得到分类器； 一般Random Forest效果比Bagging效果好！

4.3 GBDT和随机森林的对比

相同点：

  1. 都是由多棵树组成
  2. 最终的结果都是由多棵树一起决定

不同点：

  1. 组成随机森林的树可以是分类树，也可以是回归树；而GBDT只由回归树组成
  2. 组成随机森林的树可以并行生成；而GBDT只能是串行生成
  3. 对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来
  4. 随机森林对异常值不敏感，GBDT对异常值非常敏感
  5. 随机森林对训练集一视同仁，GBDT是基于权值的弱分类器的集成
  6. 随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能

参考文献

从Boosting到Stacking，概览集成学习的方法与性能
机器学习–>集成学习–>Bagging,Boosting,Stacking
GBDT学习笔记
集成学习研究
【机器学习】模型融合方法概述
说说随机森林
Adaboost 算法的原理与推导
第06章：深入浅出ML之Boosting家族
【十大经典数据挖掘算法】AdaBoost