下图是基于树的算法的发展历程

1、Bagging

Bagging [Breiman, 1996a] 是并行式集成学习方法最著名的代表.

1.1、Bagging原理

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

• 随机采样(bootsrap)就是从我们的训练集里面采集固定个数的样本，但是每采集一个样本后，都将样本放回。也就是说，之前采集到的样本在放回后有可能继续被采集到。对于我们的Bagging算法，一般会随机采集和训练集样本数m一样个数的样本。这样得到的采样集和训练集样本的个数相同，但是样本内容不同。如果我们对有m个样本训练集做T次的随机采样，，则由于随机性，T个采样集各不相同。
  注意到这和GBDT的子采样是不同的。GBDT的子采样是无放回采样，而Bagging的子采样是放回采样。

对于一个样本, 它在某一次含 m m m个样本的训练集的随机采样中，每次被采集到的概率是 1 m \frac{1}{m} m1​， 不被采集到的概率 1 − 1 m 1-\frac{1}{m} 1−m1​。如是果 m m m次采样都没有被采集到的概率 ( 1 − 1 m ) m (1-\frac{1}{m})^m (1−m1​)m。当 → ∞ \rightarrow \infty →∞ 时, ( 1 − 1 m ) m → 1 e ≃ 0.368 \left(1-\frac{1}{m}\right)^{m} \rightarrow \frac{1}{e} \simeq 0.368 (1−m1​)m→e1​≃0.368也就是说, 在 bagging的每轮随机采样中，训练集中大约有36.8%的数据没有被采样集采集中。对于这部分大约36.8%的没有被采样到的教据, 我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。

• bagging对于弱学习器没有限制，这和Adaboost一样。但是最常用的一般也是决策树和神经网络

• bagging的集合策略也比较简单，对于分类问题，通常使用简单投票法，得到最多票数的类别或者类别之一为最终的模型输出。对于回归问题，通常使用简单平均法，对T个弱学习器得到的回归结果进行算术平均得到最终的模型输出。

• 由于Bagging算法每次都进行采样来训练模型，因此泛化能力很强，对于降低模型的方差很有作用。当然对于训练集的拟合程度就会差一些，也就是模型的偏倚会大一些。

从偏差方差分解的角度看， Bagging 主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效用更为明显.

2、随机森林

2.1 算法原理

随机森林是对bagging的进化，随机森林在bagging的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离bagging的范畴。
具体来说，传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性;而在RF中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分. 这里的参数k控制了随机性的引入程度;若令k = d ， 则基决策树的构建与传统决策树相同;若令k = 1， 则是随机选择一个属性用于划分; 一般情况下，推荐值k = l o g 2 d log_2 d log2​d。
Bagging 中基学习器的"多样性"仅通过样本扰动(通过对初始训练集采样)而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升.

随着个体学习器数目的增加，随机森林通常会收敛到更低的泛化误差. 值得一提的是，随机森林的训练效率常优于Bagging，因为在个体决策树的构建过程中， Bagging使用的是" 确定型" 决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的" 随机型"决策树则只需考察一个属性子集。

2.2 随机森林的特点

• 在当前所有算法中，具有极好的准确率
• 能够有效地运行在大数据集上
• 能够处理具有高维特征的输入样本，而且不需要降维
• 能够评估各个特征在分类问题上的重要性
• 在生成过程中，能够获取到内部生成误差的一种无偏估计
• 对于缺省值问题也能够获得很好得结果
• 既可以用于回归也可以分类

2.3 随机森林的生成

• 1）如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；（每棵树的训练集都是不同的，而且里面包含重复的训练样本）
• 2）如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；
• 3）每棵树都尽最大程度的生长，并且没有剪枝过程。

---

注意

• 为什么要随机抽样训练集？
  　　如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；
• 为什么要有放回地抽样？
  如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是"有偏的"，都是绝对"片面的"（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是"求同"，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是"盲人摸象"。
• 随机森林分类效果（错误率）与两个因素有关：
  森林中任意两棵树的相关性：相关性越大，错误率越大；
  森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。

减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。

2.4 袋外错误率（oob error）

上面我们提到，构建随机森林的关键问题就是如何选择最优的m，要解决这个问题主要依据计算袋外错误率oob error（out-of-bag error）。
　　随机森林有一个重要的优点就是，没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。
　　我们知道，在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第k棵树的oob样本。
　　而这样的采样特点就允许我们进行oob估计，它的计算方式如下：
　　（note：以样本为单位）
　　1）对每个样本，计算它作为oob样本的树对它的分类情况（约1/3的树）；
　　2）然后以简单多数投票作为该样本的分类结果；
　　3）最后用误分个数占样本总数的比率作为随机森林的oob误分率。

3 结合策略

3.1 平均法

假定集成包含 T T T 个基学习器 { h 1 , h 2 , … , h T } , \left\{h_{1}, h_{2}, \ldots, h_{T}\right\}, {h1​,h2​,…,hT​}, 其中 h i h_{i} hi​ 在示例 x x x 上的输出 为 h i ( x ) . h_{i}(\boldsymbol{x}) . hi​(x). 本节介绍几种对 h i h_{i} hi​ 进行结合的常见策略.

对数值型输出 h i ( x ) ∈ R , h_{i}(\boldsymbol{x}) \in \mathbb{R}, hi​(x)∈R, 最常见的结合策略是使用平均法 (averaging).

• 简单平均法(simple averaging)
  H ( x ) = 1 T ∑ i = 1 T h i ( x ) H(\boldsymbol{x})=\frac{1}{T} \sum_{i=1}^{T} h_{i}(\boldsymbol{x}) H(x)=T1​i=1∑T​hi​(x)
• 加权平均法(weighted averaging)
  H ( x ) = ∑ i = 1 T w i h i ( x ) H(\boldsymbol{x})=\sum_{i=1}^{T} w_{i} h_{i}(\boldsymbol{x}) H(x)=i=1∑T​wi​hi​(x)
  其中 w i w_{i} wi​ 是个体学习器 h i h_{i} hi​ 的权重, 通常要求 w i ⩾ 0 , ∑ i = 1 T w i = 1 w_{i} \geqslant 0, \sum_{i=1}^{T} w_{i}=1 wi​⩾0,∑i=1T​wi​=1.

加权平均法的权重一般是从训练数据中学习而得，现实任务中的训练样本通常不充分或存在噪声，这将使得学出的权重不完全可靠.尤其是对规模比较大的集成来说?要学习的权重比较多，较容易导致过拟合.因此，实验和应用均显示出，加权平均法未必一起优于简单平均法[Xu et al., 1992; Ho et al., 1994;Kittler et al., 1998]. 一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法.

3.2 投票法

• 绝对多数投票法，某标记超过半数，则预测为改标记，否则拒绝预测。
• 相对多数投票法，预测为最多的标记，如果平票，则随机一个。
• 加权投票法，再分类器中添加权重，再做相对多数投票法。

3.3 学习法

当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合.Stacking[Wolpert,1992；Breiman,1996b]是学习法的典型代表.这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器或元学习器（meta-learner).

次级学习器的输入属性表示和次级学习算法对Stacking集成的泛化性能有很大影响.有研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归（Multi-response Linear Regression，简称MLR）作为次级学习算法效果较好[Ting and Witten，1999]，在MLR中使用不同的属性集更佳[Seewald，2002]

4 为什么说bagging是减少variance，而boosting是减少bias？

最后，简单总结一下，基于树的算法可以分为Bagging与Boosting。

• Bagging：训练数据是有放回随机采样N个训练数据，结果基于投票机制；弱学习器没有限制，这和Adaboost一样。但是最常用的一般也是决策树和神经网络。
• 随机森林：训练数据是有放回抽样N个训练数据，特征也是随机抽取k个（共d个），结果基于投票机制。注意：随机森林的树没有剪枝过程。
• 由于是随机抽样，所以大约会有1/3的数据未被抽到，称作袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。
• bagging是减少variance，而boosting是减少bias。
• Bagging的算法既可以回归也可以分类，取决于采用的是CART回归还是分类。