Bagging

Bagging是Bootstrap AGGregatING的缩写。
Bagging基于自助采样法(bootstrap sampling)。给定包含m个样本的数据集，先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中。这样，经过m次随机采样操作，我们得到含m个样本的采样集，初始训练集中有的样本再采样集里多次出现，有的则从未出现。
采样出T个含有m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基本学习器进行结合。
Bagging通常对分了任务使用简单投票法，对回归任务使用简***均法。
与标准AdaBoost只适用于二分类任务不同，Bagging能不经修改地用于多分类，回归等任务。
自助采样过程还给Bagging带来了另一个优点：由于每个基学习器只使用了初始训练集约63.2%的样本，剩下约36.8%的样本可用作验证集来对泛化性能进行“包外估计”(out-of-bag estimate)。

包外估计用途

当基学习器是决策树时，可使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；
当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合。
Bagging主要关注降低方差，因此它在不剪枝决策树，神经网络等易受样本扰动的学习器上效用更为明显。

随机森林

随机属性选择

RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性选择。
传统决策树在选择划分属性时是在当前结点的属性集合中选择一个最优属性；而在RF中，基决策树的每个结点，先从该结点的属性集合（假定有d个属性）中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度:
若令k=d,则基决策树的构建与传统决策树相同；若令k=1，则是随机选择一个属性用于划分；一般情况下，推荐值 k = l o g 2 d 。

特征重要性计算

计算某个特征X的重要性时，具体步骤如下：

  1. 对每一颗决策树，选择相应的袋外数据（out of bag，OOB）​计算袋外数据误差，记为errOOB1.
    所谓袋外数据是指，每次建立决策树时，通过重复抽样得到一个数据用于训练​决策树，这时还有大约1/3的数据没有被利用，没有参与决策树的建立。这部分数据可以用于对决策树的性能进行评估，计算模型的预测错误率，称为袋外数据误差。
    ​这已经经过证明是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计。

  2. 随机对袋外数据OOB所有样本的特征X加入噪声干扰（可以随机改变样本在特征X处的值），再次计算袋外数据误差，记为errOOB2。

  3. ​假设森林中有N棵树，则特征X的重要性=∑（errOOB2-errOOB1）/N。这个数值之所以能够说明特征的重要性是因为，如果加入随机噪声后，袋外数据准确率大幅度下降（即errOOB2上升），说明这个特征对于样本的预测结果有很大影响，进而说明重要程度比较高。

优点

简单，容易实现，计算开销小。RF中基学习器的多样性不仅来自样本扰动，还来自属性扰动，使得最终集成的泛化性能可通过个体学习器之间的差异度的增加而进一步提升。