原文链接

一、集成学习和个体学习器的概念

集成学习：通过构建并结合多个学习器来完成任务，有时也被称为多分类器系统、基于委员会的学习等。
个体学习器：也就是常见的学习算法，如逻辑回归，神经网络等，根据个体学习器间的强弱依赖关系，可以分类两类集成学习算法。一类是具有强依赖性，个体学习器必须串行生成的序列化方法，代表算法是Boosting。
另一类的具有弱依赖性，个体学习器可同时生成的并行化方法，代表算法是Bagging和”随机森林”。
下图显示出集成学习的一般结构：
image.png
图1. 集成学习的一般结构
先产生一组”个体学习器”，再用某种策略将他们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生，例如C4.5决策树算法、BP神经网络算法等，此时集成中只包含同种类型的个体学习器，例如”决策树集成”中全是决策树，”神经网络集成”中全是神经网络，这样的集成叫同质集成，同质集成中的个体学习器也叫”基学习器”，相应的学习算法叫”基学习算法”。集成也可包含不同类型的个体学习器，例如同时包含决策树和神经网络，这样的集成叫异质集成，异质集成中的个体学习器由不同的学习算法生成，这时的个体学习器叫做组间学习器或者直接叫个体学习器。
集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。这对”弱学习器”尤为明显，因此集成学习的很多理论都是针对弱学习器进行的，而基学习器有时也被称为弱学习器，但要注意的是，虽然理论上来说使用弱学习器集成足以获得好的性能，但在实践中处于种种考虑，例如希望使用较少的个体学习器，或是重用关于常见学习器的一些经验等，人们往往会使用比较强的学习器。

弱学习器常指泛化性能略优于随机猜测的学习器

原则

  1. 集成学习的结果通过投票法产生，即”少数服从多数”。
  2. 个体学习器要有一定的准确性，至少不差于若学习器，即”学习器不能太坏”。
  3. 个体学习器要有多样性，即学习器间有差异。

    二、Boosting

    Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。
    ♠ 随机森林算法理论 - 图2
    图2. Boosting训练流程
    Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过”重赋权法”实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。对无法接受带权样本的基学习算法，则可通过”重采样法”(re-sampling)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。一般而言，这两种做法没有显著的优劣差别。需注意的是，Boosting算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件，即检查当前基分类器是否比随机猜测的好，一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。在此种情形下，初始设置的学习轮数T也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。若采用”重采样法”，则可获得“重启动”机会以避免训练过程中过早停止，即在抛弃不满足条件的当前基学习器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基学习器，从而使得学习过程可以持续到预设的T轮完成。
    从偏差-方差分解的角度看，Boosting主要关注降低偏差，因此Boosting能基于泛化性能相当弱的学习器构建出很强的集成。

    三、Bagging

    由前面介绍可知，想要得到泛化能力强的集成，集成中的个体学习器应尽可能相互独立；虽然”独立”在现实任务中无法做到，但可以设法使基学习器尽可能具有较大的差异。给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据不同，我们获得的基学习器可望具有较大的差异。然而，为获得好的集成，我们还希望个体学习器不能太差。如果采样出的每个子集都完全不同，则每个基学习器只用到了一小部分训练数据，甚至不足以进行有效学习，这显然无法确保产生出比较好的基学习器。为了解决这个问题，我们可以考虑使用相互有交叠的采样子集。
    ♠ 随机森林算法理论 - 图3
    图3. Bagging算法训练流程

Bagging是并行式集成学习方法最著名的代表。它直接基于自助采样法(bootstrap sampling)，给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过m次随机采样操作，我们得到含m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现。
照这样，我们可采样出T个含m个样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合，这就是Bagging的基本流程。在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形，则最简单的做法是随机选择一个，也可进一步考察学习器投票的置信度来确定最终胜利者。
为处理多分类或者回归任务。Adaboost需进行修改，与标准AdaBoost只适用于二分类任务不同，Bagging能不经修改的用于多分类、回归等任务。而且自助采样过程还给Bagging带来另一个优点：由于每个基学习器只使用了初始训练集中部分样本（63.2%），剩下的样本（36.8%）的样本可用作验证集来对泛化性能进行”包外估计”(out-of-bag estimate)。

自助法：我们希望评估的是用D训练出的模型。但在留出法和交叉验证法中，由于保留了一部分样本用于测试，因此实际估计的模型所使用的训练集比D小，这必然会引入一些因训练样本规模不同而导致的估计偏差。留一法受训练样本规模变化的影响较小，但计算复杂度又太高。”自助法”是一个好的解决办法，它直接以自助采样法为基础。给定包含m个样本的数据集D，我们对他进行采样产生数据集D1：每次随机从D中挑选一个样本，将其拷贝放入D1，然后再将该样本放回初始数据集D中，使得该样本在下次采样时扔有可能被采到；这个过程重复执行m次后，我们就得到了包含m个样本的数据集D1，这就是自助采样的结果。显然，D中有一部分样本会出现多次，而另一部分样本不出现。样本在m次采样中始终不被采样的概率是 ♠ 随机森林算法理论 - 图4 ，取极限得到0.368。即通过采样法，初始数据集D中约有36.8%的样本未出现在采样数据集D1中。于是我们可将D1用作训练集，♠ 随机森林算法理论 - 图5用作测试集。这样，实际评估的模型与期望评估的模型都是用m个训练样本，而我们仍有♠ 随机森林算法理论 - 图6的，没在训练集出现的样本用于测试。这样的测试结果也叫”包外估计”。

事实上，包外估计还可用来在决策树时辅助剪枝；估计决策树中各节点的后验概率以辅助对零训练样本结点的处理；在基学习器是神经网络时，可用来辅助早起停止以减小基学习器是神经网络的过拟合风险。
从偏差-方差角度分析，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显。

四、结合策略

学习器结合可能会从三个方面带来好处：

  • 第一，从统计的方面来看，由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而导致泛化性能不佳，结合多个学习器则会减少这一风险；
  • 第二，从计算方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能可能糟糕，而通过多次运行之后进行结合，可降低糟糕局部极小点的风险；
  • 第三，从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间扩大，有可能学得更好的近似。
  1. 平均法：对于数值型输出，最常见的结合策略是使用平均法。一是简单平均法♠ 随机森林算法理论 - 图7，二是加权平均法♠ 随机森林算法理论 - 图8是学习器个数，♠ 随机森林算法理论 - 图9是个体学习器♠ 随机森林算法理论 - 图10的权重，通常♠ 随机森林算法理论 - 图11。加权平均法的权重一般是从训练数据中学习而得，例如估计出个体学习器的误差，然后令权重大小与误差大小成反比。现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠。尤其是对规模比较大的集成来说，要学习的权重比较多，较容易导致过拟合。因此，实验和应用均显示出，加权平均法未必一定由于简单平均法。一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。
  2. 投票法：即少数服从多数。聚合每个分类器的预测，然后将得票最多的结果作为预测类型，这种大多数投票分类器被称为硬投票分类器。
  3. 学习法：当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。

Stacking是学习法的典型代表。这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器。
stacking是一种分层模型集成框架。以两层为例，第一层由多个基学习器组成，其输入为原始训练集，第二层的模型则是以第一层基学习器的输出作为训练集进行再训练，从而得到完整的stacking模型。

五、随机森林

理解了bagging算法，随机森林(Random Forest)就好理解了。它是Bagging算法的进化版。首先，RF使用了CART决策树作为弱学习器。第二，在使用决策树的基础上，RF对决策树的建立做了改进，对于普通的决策树，我们会在节点上所有的n个样本特征中选择一个最优的特征来做决策树的左右子树划分，但是RF通过随机选择节点上的一部分样本特征，这个数字小于n，为m，然后在这些随机选择的m个样本特征中，选择一个最优的特征来做决策树的左右子树划分。这样进一步增强了模型的泛化能力。　　　　
　　如果m=n，则此时RF的CART决策树和普通的CART决策树没有区别。m越小，则模型约健壮，当然此时对于训练集的拟合程度会变差。也就是说m越小，模型的方差会减小，但是偏倚会增大。在实际案例中，一般会通过交叉验证调参获取一个合适的m的值。除了上面两点，RF和普通的bagging算法没有什么不同。

六、随机森林的推广

由于RF在实际应用中的良好特性，基于RF，有很多变种算法，应用也很广泛，不光可以用于分类回归，还可以用于特征转换，异常点检测等。下面对于这些RF家族的算法中有代表性的做一个总结。

extra trees

extra trees是RF的一个变种, 原理几乎和RF一模一样，仅有区别有：

  1. 对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。
  2. 在选定了划分特征后，RF的决策树会基于基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是extra trees比较的激进，他会随机的选择一个特征值来划分决策树。

从第二点可以看出，由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模
一般会大于RF所生成的决策树。也就是说，模型的方差相对于RF进一步减少，但是偏倚相对于RF进一步增大。在某些时候，extra trees的泛化能力比RF更好。

Totally Random Trees Embedding

Totally Random Trees Embedding(以下简称 TRTE)是一种非监督学习的数据转化方法。它将低维的数据集映射到高维，从而让映射到高维的数据更好的运用于分类回归模型。我们知道，在支持向量机中运用了核方法来将低维的数据集映射到高维，此处TRTE提供了另外一种方法。
　　TRTE在数据转化的过程也使用了类似于RF的方法，建立T个决策树来拟合数据。当决策树建立完毕以后，数据集里的每个数据在T个决策树中叶子节点的位置也定下来了。比如我们有3颗决策树，每个决策树有5个叶子节点，某个数据特征xx划分到第一个决策树的第2个叶子节点，第二个决策树的第3个叶子节点，第三个决策树的第5个叶子节点。则x映射后的特征编码为(0,1,0,0,0, 0,0,1,0,0, 0,0,0,0,1), 有15维的高维特征。这里特征维度之间加上空格是为了强调三颗决策树各自的子编码。映射到高维特征后，可以继续使用监督学习的各种分类回归算法了。

七、随机森林的优缺点

作为一个可以高度并行化的算法，RF在大数据时大有可为。
RF的主要优点有：

  1. 训练可以高度并行化，对于大数据的大样本训练速度有优势。
  2. 由于可以随机选择决策树节点划分特征，这样在样本特征维度很高的时候，仍然能高效的训练模型。
  3. 在训练后，可以给出各个特征对于输出的重要性。
  4. 由于采用了随机抽样，训练出来的模型的方差小，泛化能力强。
  5. 相对于Boosting系列的Adaboost和GBDT，RF实现比较简单。
  6. 对部分特征缺失不敏感。

RF的主要缺点：

  1. 在某些噪音比较大的样本集上，RF模型容易陷入过拟合。
  2. 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。