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

一、随机森林（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_i$，则所有这些弱评估器输出结果的方差可以被表示为Var($X_i$)。假设现在我们执行回归任务，则森林的输出结果等于森林中所有树输出结果的平均值，因此森林的输出可以被表示为$\bar{X}=\frac{\sum X_i}{n}$，因此随机森林输出结果的方差可以被表示为Var($\bar{X}$)，也可以写作Var($\frac{\sum X_i}{n}$)。

  在数学上我们很容易证明：

当森林中的树互相独立时，Var($\bar{\mathbf{X}}$)永远小于Var(${\mathbf{X}}_{\mathbf{i}}$)

  为了完成这个证明，我们需要几个定理：

• Var(A + B) = Var(A) + Var(B)，其中A和B是相互独立的随机变量
• Var(aB) = a${}^2$Var(B)，其中a是任意常数

  假设任意树输出的方差Var($X_i$) = ${\sigma }^2$，则有：

$$\begin{array}{rl}Var(\bar{X})& =Var\left(\frac{1}{n}\sum _{i=1}^n{X}_i\right)\\ & =\frac{1}{n^2}Var\left(\sum _{i=1}^n{X}_i\right)\\ & =\frac{1}{n^2}\left(Var(X_1)+Var(X_2)+...+Var(X_n)\right)\\ & =\frac{1}{n^2}n{\sigma }^2\\ & =\frac{{\sigma }^2}{n}\end{array}$$

  当$n$为正整数、且弱评估器之间相互独立时，必然有Var($\bar{X}$) 永远小于Var($X_i$)，这是随机森林的泛化能力总是强于单一决策树的根本原因。

5.3、Bagging有效的基本条件有哪些？Bagging的效果总是强于弱评估器吗？

  Bagging当然不总是有效的，Bagging能够提升模型效果的条件有以下三个：

• 1、弱评估器的偏差较低，特别地来说，弱分类器的准确率至少要达到50%以上；
• 2、弱评估器之间相关性弱，最好相互独立；
• 3、弱评估器是方差较高、不稳定的评估器；

  第一个条件非常容易解释。Bagging集成算法是对基评估器的预测结果进行平均或用多数表决原则来决定集成评估器的结果。在分类的例子中，假设我们建立了25棵树，对任何一个样本而言，平均或多数表决原则下，当且仅当有13棵以上的树判断错误的时候，随机森林才会判断错误。假设单独一棵决策树在样本i上的分类准确率在0.8上下浮动，那一棵树判断错误的概率大约就有0.2(ε)，那随机森林判断错误的概率（有13棵及以上的树都判断错误的概率）是：

$$e_{random\_forest}=\sum _{i=13}^{25}{C}_{25}^i{\epsilon }^i(1-\epsilon {)}^{25-i}=0.000369$$

  可见，判断错误的几率非常小，这让随机森林的表现比单棵决策树好很多。

  对于第二个条件，在证明Bagging降低方差的数学过程中已经申明了很多次，唯有弱评估器之间相互独立、弱评估器输出的结果相互独立时，方差计算公式的前提假设才能被满足，Bagging才能享受降低方差的福利。

  然而在现实中，森林中的弱评估器很难完全相互独立，因为所有弱评估器都是在相同的数据上进行训练的、因此构建出的树结构也大同小异。幸运的是，我们能够衡量弱评估器之间相关性。以随机森林回归为例，假设任意弱评估器之间的相关系数为$\rho$（读音Rho），则随机森林输出结果的方差等于：

$$Var(\bar{\mathbf{X}})=\frac{{\sigma }^2}{n}+\frac{n-1}{n}\rho {\sigma }^2$$

  这个公式是根据比奈梅定义(Bienaymé’s Identity)与协方差相关的公式推导出来的，这暗示随机森林输出结果的方差与森林中弱评估器之间的相关性是负相关的，弱评估器之间的相关性越强，随机森林输出的结果的方差就越大，Bagging方法通过降低方差而获得的泛化能力就越小。因此在使用随机森林时，我们需要让弱评估器之间尽量相互独立，我们也可以通过这一点来提升随机森林的水平。

5.4、Bagging方法可以集成决策树之外的算法吗？

  强大又复杂的算法如决策树、支持向量机等，往往学习能力较强，倾向于表现为偏差低、方差高，这些算法就比较适合于Bagging。而线性回归、逻辑回归、KNN等复杂度较低的算法，学习能力较弱但表现稳定，因此倾向于表现为偏差高，方差低，就不太适合被用于Bagging。

5.5、怎样增强Bagging中弱评估器的独立性？

  在实际使用数据进行训练时，很难让Bagging中的弱评估器完全相互独立，主要是因为：

• 训练的数据一致
• 弱评估器构建的规则一致

  导致最终建立的弱评估器都大同小异，Bagging的效力无法完整发挥出来。为了弱评估器构建规则一致的问题，我们有了Averaging和Voting这样的模型融合方法：基本来看，就是使用Bagging的逻辑来融合数个不同算法的结果。而当我们不使用模型融合时，我们可以使用“随机性”来削弱弱分类器之间的联系、增强独立性、提升随机森林的效果。

  在随机森林中，天生就存在有放回随机抽取样本建树的机制，因此才会有bootstrap、max_samples等参数，才会有袋外数据、袋外评估指标oob_score等属性，意在使用不同的数据建立弱评估器。除了有放回随机抽样之外，还可以使用max_features随机抽样特征进行分枝，加大弱评估器之间的区别。

5.6、除了随机森林，你还知道其他Bagging算法吗？

  Bagging方法的原理简单，因此Bagging算法之间的不同主要体现在随机性的不同上。在上世纪90年代，对样本抽样的bagging、对特征抽样的bagging、对样本和特征都抽样的bagging都有不同的名字，不过今天，所有这些算法都被认为是装袋法或装袋法的延展。在sklearn当中，除了随机森林之外还提供另一个bagging算法：极端随机树。极端随机树是一种比随机森林更随机、对方差降低更多的算法。

• sklearn.ensemble.ExtraTreesClassifier
• sklearn.ensemble.ExtraTreesRegressor

  与随机森林一样，极端随机树在建树时会随机挑选特征，但不同的是，随机森林会将随机挑选出的特征上每个节点都进行完整、精致的不纯度计算，然后挑选出最优节点，而极端随机树则会随机选择数个节点进行不纯度计算，然后选出这些节点中不纯度下降最多的节点。这样生长出的树比随机森林中的树更不容易过拟合，同时独立性更强，因此极端随机树可以更大程度地降低方差。

  当然了，这种手段往往也会带来偏差的急剧下降，因此极端随机树是只适用于方差过大、非常不稳定的数据的。除非特殊情况，我们不会考虑使用极端随机树，但了解这个算法的存在也是一件好事。