二、集成学习：Bagging之随机森林算法（RandomForest Algorithm）

推荐阅读通俗解释随机森林算法

一、随机森林（RandomForest）基本原理

  随机森林是机器学习领域最常用的算法之一，其算法构筑过程非常简单：随机森林利用了随机采样， 对数据样本和特征进行抽样，训练出多个树分类器（决策树，通常为CART），避免了每树对所有样本及所有特征的学习，从而增加了随机性，避免了过拟合，并按照Bagging的规则对单棵决策树的结果进行集成（回归则平均，分类则少数服从多数）。

• 对训练样本数据进行有放回的抽样，生成K棵分类回归树；
• 假设特征空间有n个特征，每棵树的节点处随机抽取m个特征(m < n)；
• 使每棵树最大限度生长，不做任何剪枝；
• 通过多棵树组成森林，分类结果按树分类器投票多少决定；

随机森林的优缺点

优点

• 不同决策树可以由不同主机并行训练生成，效率很高；
• 随机森林算法继承了C&RT的优点；
• 将所有的决策树通过bagging的形式结合起来，避免了单个决策树造成过拟合的问题；
• 判断特征的重要程度、判断出不同特征之间的相互影响；
• 处理高维数据，处理特征遗失数据，处理不平衡数据；

缺点

• 不适合小数据或者低维数据（特征较少的数据），可能不能产生很好的分类。
• 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合；
• ，取值划分较多的属性会对随机森林产生更大的影响，随机森林在这种数据上产出的属性权值是不可信的；

二、Out-Of-Bag Estimate 袋外数据估计泛化误差

• 什么是 OOB？随机森林中 OOB 是如何计算的，它有什么优缺点？

  Bagging 方法中 Bootstrap 每次约有37%的样本不会出现在 Bootstrap 所采集的样本集合中，当然也就没有参加决策树的建立，把这的数据称为袋外数据 OOB（out of bag）,它可以用于取代测试集误差估计方法。所以我们或许可以不做交叉验证、不分割数据集，而只依赖于袋外数据来测试我们的模型即可。当然，这也不是绝对的，当树的数量n_estimators不足，或者max_samples太小时，很可能就没有数据掉落在袋外，自然也有无法使用oob数据来作为验证集了。

  实际上，这些袋外样本还有别的用途，例如个体学习器是决策树时，可以用这些袋外样本来辅助剪枝；当个体学习器是神经网络时，可以使用袋外样本来辅助早期停止以减少过拟合风险。

三、随机森林如何评估特征重要性。

  衡量变量重要性的方法有两种，Decrease GINI 和 Decrease Accuracy：

• Decrease GINI
  
    考察样本经过节点后不纯度减少的值的大小，值越大则特征越重要。

1. 对于分类问题，也就是离散变量问题，CART使⽤Gini指数作为评判标准，选择那个使得划分后基尼指数最小的属性作为划分属性。

2. 对于回归问题，直接使用 argmax(Var-VarLeft-VarRight)作为评判标准，即当前节点训练集的方差 Var 减去左节点的方差 VarLeft 和右节点的方VarRight。

• Decrease Accuracy

  通过包外数据（out of bag）计算特征加入噪声前后对模型预测准确率的影响，影响越大则特征越重要。

  好比对于一棵树 Tb(x)，我们用 OOB 样本可以得到测试误差 1；然后随机改变 OOB 样本的第 j 列：保持其他列不变，对第 j 列进行随机的上下置换，得到误差 2。至此，我们可以用误差 1-误差 2 来刻画变量 j 的重要性。基本思想就是，如果一个变量 j 足够重要，那么改变它会极大的增加测试误差；反之，如果改变它测试误差没有增大，则说明该变量不是那么的重要。

四、随机森林如何处理缺失值

  方法一（na.roughfix）简单粗暴，对于训练集,同一个 class 下的数据，如果是分类变量缺失，用众数补上，如果是连续型变量缺失，用中位数补。

  方法二：相似度矩阵填补：先用na.roughfix ⾏粗粒度填充，然后使⽤上述填补后的训练集来训练随机森林模型，并统计相似度矩阵（proximity matrix），再回头看缺失值，如果是分类变量，则⽤没有缺失的观测实例的相似度中的权重进⾏投票；如果是连续性变量，则⽤相似度矩阵进⾏加权求均值，然后迭代 4-6 次。

proximity matrix相似度矩阵

• 相似度矩阵就是任意两个观察实例间的相似度矩阵，原理是如果两个观侧实例落在同一颗树的相同节点次数越多，则这两个观侧实例的相似度越高。

五、其它常见问题

5.1、为什么Bagging算法的效果比单个评估器更好？

  泛化误差是模型在未知数据集上的误差，更低的泛化误差是所有机器学习/深度学习建模的根本目标。在机器学习当中，泛化误差一般被认为由偏差、方差和噪音构成。其中偏差是预测值与真实值之间的差异，衡量模型的精度。方差是模型在不同数据集上输出的结果的方差，衡量模型稳定性。噪音是数据收集过程当中不可避免的、与数据真实分布无关的信息。

  当算法是回归算法、且模型衡量指标是MSE时，模型的泛化误差可以有如下定义：

$$\begin{array}{rl}泛化误差& =偏{差}^2+方差+噪{音}^2\\ & =bia{s}^2+variance+nois{e}^2\end{array}$$

  Bagging的基本思想是借助弱评估器之间的“独立性”来降低方差，从而降低整体的泛化误差。这个思想可以被推广到任意并行使用弱分类器的算法或融合方式上，极大程度地左右了并行融合方式的实际使用结果。其中，“降低方差”指的是bagging算法输出结果的方差一定小于弱评估器输出结果的方差，因此在相同数据上，随机森林往往比单棵决策树更加稳定，也因此随机森林的泛化能力往往比单棵决策树更强。

5.2、为什么Bagging可以降低方差？

  我们很难从直觉上来理解“Bagging降低方差”这个抽象的结论，更难探究其背后的原因，但我们可以通过数学的方式来理解它。

  以随机森林为例，假设现在随机森林中含有$n$个弱评估器（$n$棵树），任意弱评估器上的输出结果是$X$