随机森林介绍

模型介绍

随机森林是一种有监督学习算法，随机森林非常简单，易于实现，计算开销也很小， 但是它在分类和回归上表现出惊人的性能，因此，随机森林被誉为"代表集成学习技术水平的方法”

随机森林(Random Forest, RF)是一种以决策树为基学习器的集成(ensemble)学习器， 它利用 Bootstrap 抽样方法从原始样本中抽取多个样本进行决策树(decision tree)建模，然后将这些决策树组合在一起， 通过对所有决策树结果的平均(Mean)或投票(Vote)得出最终预测的回归(Regression)或分类(Classification)的结果

大量的理论和实证研究都证明了随机森林：

• 随机森林既可以用于分类问题，也可以用于回归问题
• 具有较高的预测准确率
• 对异常值和噪声数据具有很好的容忍度
• 随机森林可以用类别型特征建模
• 随机森林可以处理缺失值
• 不容易出现过拟合
  • 过拟合是个关键的问题，可能会让模型在测试数据上的的结果变得糟糕， 但是对于随机森林来说，如果随机森林的树足够多，那么分类器就不会过拟合模型

随机森林的基学习器

随机森林的基学习器就是没有剪枝的决策树

随机森林的随机性

随机森林的随机性体现在数据集样本的随机抽样选择和待选特征的随机抽样选择

数据集样本的随机抽样选择：

• 从原始的数据集中采取有放回的抽样(Bootstrap 抽样)，构造子数据集，子数据集的数据量是和原始数据集相同的。 不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复

待选特征的随机抽样选择：

• 与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有的待选特征， 而是从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选取最优的特征

随机森林的优缺点

优点：

1. 由于采用了集成算法，本身精度比大多数单个算法要好，所以准确性高
2. 在测试集上的表现良好，由于两个随机性(样本随机、特征随机)的引入，使得随机森林不容易陷入过拟合
3. 在工业上，由于两个随机性的引入，使得随机森林具有一定的抗噪声能力，对比其他算法具有一定的优势
4. 由于使用决策树的组合，使得随机森林可以处理非线性数据，本身属于非线性分类(拟合)模型
5. 能够处理高维度的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据无需规范化
6. 训练速度快可以运用在大规模数据集上
7. 可以处理含有缺失值的特征(单独作为一类)，不用额外处理
8. 由于有袋外数据(OOB)，可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量
9. 由于每棵树可以独立、同时生成，容易做成并行化方法
10. 由于实现简单、精度高、抗过拟合能力强，当面对非线性数据时，适于作为基准模型

缺点：

1. 当随机森林中的决策树个数很多时，训练时需要的空间和时间会比较大
2. 随机森林中还有很多不好解释的地方，有点算是黑盒模型
3. 在某些噪音较大的样本集上，随机森林容易陷入过拟合
4. 不能很好地处理非平衡数据
   • 由于随机森林在构建过程中，训练集是随机选取的，使用 Bootstrap 随机抽样时，由于原训练集中的少数类本身就比较少， 因此被选中的概率就很低，这使得 M 个随机选取的训练集中含有的少数类数量比原有的数据集更好或没有， 这反而加剧了数据集的不平衡性，使得基于此数据集训练出来的决策树的规则就没有代表性
   • 由于数据集本身少数类占有的比例就低，使得训练出来的决策树不能很好地体现占有数量少的少数类的特点， 只有将少数类的数量加大，使数据集中的数据达到一定的程度平衡，才能使得算法稳定
5. 需要对连续性变量进行离散化
6. 随机森林的分类精度需要进一步提升
   • 数据集的维度和样本的平衡性
   • 算法本身的决策树分裂规则、随机抽样

随机森林的构建过程

随机森林的产生，是为了克服决策树在回归和分类预测方面有诸多缺点， 结合单个树学习器组合成多个学习器的思想生成多棵决策树，这些决策树不需要都有很高的精度， 并让所有的决策树通过投票的形式进行决策

参数符号使用声明：

1. $n\_tree$：构建的决策树数量
2. $M$：所有样本数量
3. $m$：Bootstrap 抽样的样本数量
4. $P$：所有特征数量
5. $p$： 随机抽取的特征数量

随机森林构建大致过程：

1. 从原始训练数据集中使用 Bootstrap 方法随机有放回采样取出 $m$ 个样本， 共进行 $n\_tree$ 次采样，生成 $n\_tree$ 个训练集
2. 从原始训练数据集中使用不放回抽样随机抽取出 $p$ 个特征
3. 对 $n\_tree$ 个训练集，分别训练 $n\_tree$ 个决策树模型
   • 对于单个决策树模型，每次分裂时根据 “信息增益/信息增益率/基尼指数” 从 $p$ 个特征中选择最好的特征进行分裂
   • 每棵树都一直这样分裂下去，直到该节点的所有训练样本都属于同一类。在决策树的分裂过程中不需要剪枝
4. 将生成的多棵决策树组成随机森林
   • 对于分类问题，按照多棵树分类器投票决定最终分类结果
   • 对于回归问题，由多棵树预测值的均值决定最终预测结果

注意：OOB(out-of-bag)：每棵决策树的生成都需要自助采样， 这时就有 $\frac{1}{3}$ 的数据未被选中，这部分数据就称为袋外数据

决策树样本抽样

Bootstrap 抽样产生训练集

每棵决策树都对应一个训练集数据，要构建 $n\_tree$ 棵决策树， 就需要产生对应数量($n\_tree$)的训练集， 从原始训练集中产生 $n\_tree$ 个训练子集要用到统计抽样技术

现有的统计抽样技术很多，按照抽样是否放回主要包括以下两种：

• 不放回抽样(简单随机抽样)
  • 抽签法(小样本)
  • 随机数法(大样本)
• 放回抽样
  • 无权重放回抽样(Bootstrap 抽样)
    • 无权重放回抽样，也叫 Bagging 方法，是一种用来提高学习算法准确度的方法
    • 该方法于 1996 年由 Breiman 提出的。Bagging 方法是以可重复的随机抽样为基础的， 每个样本是初始数据集有放回抽样。在可重复抽样生成多个训练子集时， 存在于初始训练集 $D$ 中的所有的样本都有可能被抽取的可能， 但在重复多次后，总有一些样本是不能被抽取的，每个样本不能被抽取的概率为 $(1-\frac{1}{m})^m$
  • 有权重放回抽样
    • 有权重抽样，也叫 Boosting 方法，也叫更新权重抽样
    • Boosting 方法抽样，首先有放回随机抽样产生一组($m \leq M$)训练集， 然后对这组训练集中每一个训练集设定权重为 $\frac{1}{m}$， 在设定权重后，对每个带权重的训练集进行测试(决策树训练)， 在每次测试结束后，对分类性能差的训练集的权重进行提升， 从而产生一个新的权重系列，经过多次训练后，每个训练集就有一个和其对应的权重， 在投票时，这些权重就可以对投票的结果产生影响。从而影响最终的决策结果

Bagging 和 Boosting 方法都是有放回的抽样方法，但两者间存在很大的差别：

• Bagging 方法在训练的过程中采用独立随机的方式。而 Boosting 方法在训练的过程中， 每次训练都是在前一次的基础上进行的，因此 Boosting 是一种串行的关系， 这对算法的执行是一个很大的挑战，以为每次执行都要等待上次的结果才能继续。 而 Bagging 方法就不存在这个问题，这为算法的并行处理提供了很好的支持
• Bagging 方法抽取出来的训练集是没有权重的各训练集的待遇是相同的， 而 Boosting 方法在抽取的过程中，对每个训练集都设置权重， 使得抽取结束后每个训练集的待遇是不一致的

随机森林算法在生成的过程中，主要采用 Bagging 方法，也就是 Bootstrap 抽样：

• 从原始训练集中产生 $m$ 个训练子集，每个训练子集的大小约为原始训练集的 $\frac{2}{3}$， 每次抽样均为随机且放回抽样，这样使得训练子集中的样本存在一定的重复， 这样做的目的是为了使得随机森林中的决策树不至于产生局部最优解

构建决策树

随机森林算法为每个 Bootstrap 抽样训练子集分别建立一棵决策树， 生成 $m$ 棵决策树从而形成 “森林”。每棵树任其生长，不需要剪枝。 其中涉及两个主要过程：

• 随机特征的选取
• 节点分裂

随机特征的选取

随机特征是指随机森林算法在生成的过程中，参与节点分裂的特征。 由于随机森林在节点分裂时，不是所有的特征都参与分裂指标的计算， 而是随机地选择某些特征参与比较，参与节点分裂的特征就称之为随机特征

随机特征是为了使每棵决策树之间的相关性减少，同时提升每棵决策树的分类精度， 从而提升整个随机森林的性能而引入的。其基本思想是，在进行节点分裂时， 让所有的特征按照某种概率分布随机选择其中某几个属性参与节点分裂过程。 在随机森林算法中，随机特征变量的产生方法主要有两种：

• 随机选择输入变量(Forest-RI)
  • Forest-RI 是对输入变量($P$ 个)随机分组(每组变量的个数 $p$ 是一个定值)， 然后对于每组变量，利用 CART 方法产生一棵树，并让其充分生长，不进行剪枝
  • 在每个节点上，对输入该节点的变量，重复前面的随机分组，再重复 CART 方法，直到将所有节点均为叶节点为止
  • 一般 $p$ 有两种选择，首先是 $p=1$，其次取 $p$ 为小于 $log_{2}(P+1)$ 的最大整数。 假如只有很少的输入变量，比如 $P$ 值不大，用 Forest-RI 法从 $P$ 中随机选择 $p$ 个作为随机特征变量， 这样可能提高每棵树模型的精度，但同时也增大了各棵树之间的相关系数
• 随机组合输入变量(Forest-RC)
  • Forest-RC 是先将随机特征进行线性组合，然后再作为输入变量来构造随机森林的方法

最常用的随机森林算法都是使用 Forest-RI 方法构建，在每棵子树的生长过程中， 不是将全部 $P$ 个输入变量参与节点分裂，而是随机抽取指定 $p$($p \leq P$)个随机特征变量， $p$ 的取值一般为 $log_{2}(P+1)$ ，以这 $p$ 个属性上最好的分裂方式对节点进行分裂， 从而达到节点分裂的随机性

节点分裂

随机森林常用的决策树生成方法有 C4.5、CART

随机森林的形成

通过建立大量($n\_tree$ 棵)的决策树，就形成了随机森林。算法最终的输出结果采取大多数投票法实现。 根据随机构建的 $n\_tree$ 决策子树将对某测试样本进行分类，将每棵子树的结果汇总， 所得票数最多的分类结果将作为算法最终的输出结果

随机森林的特征选择功能

用随机森林进行特征重要性评估的思想就是看每个特征在随机森林中的每棵树上做了多大的贡献， 然后取平均值(每个特征在所有决策树上的贡献平均值)，最后比一比特征之间的贡献的大小；

特征在决策树上的贡献的大小度量通常使用基尼指数(Gini Index)或者袋外数据(OOB)错误率作为评估指标来衡量

特征选择的步骤

在特征重要性的基础上，特征选择的步骤如下：

1. 计算每个特征的重要性，并按降序排列
2. 确定要剔除的比例，依据特征重要性剔除相应比例的特征，得到一个新的特征集
3. 用新的特征集重复上述过程，直到剩下 $p$ 个特征($p$ 为提前设定的值)
4. 根据上述过程得到的各个特征集合对应的 OOB 误差率，选择 OOB 误差率最低的特征集

特征重要性的估计方法

特征重要性的估计通常有两种方法：

1. 使用 uniform 或者 gaussian 抽取随机值替换特征
2. 通过 permutation 的方式将原来的所有 $M$ 个样本的第$i$ 个特征重新打乱分布；

第二种方法更加科学，保证了特征替代值与原特征的分布是近似的。这种方法叫做 permutation test， 即在计算第 $i$ 个特征的重要性的时候，将 $P$ 个特征的第 $i$ 个特征重新洗牌， 然后比较 D 和表现的差异性，如果差异很大，则表明第 $i$ 个特征是重要的

随机森林的性质、性能、参数

性质讨论

泛化误差的收敛性

随机森林中的决策树的泛化误差都收敛于：

$$\underset{n \rightarrow \infty}{\lim}PE^{*}=P_{xy}(P_{\Theta}(k(X,\Theta)=Y)-\underset{j\neq Y}{\max}P_{\Theta}(k(X,\Theta)\neq Y) > 0)$$

随着随机森林中决策树数量($n\_tree$)的增加，随机森林泛化误差($PE^{*}$)将趋向一个上界。 随机森林对未知实例有很好的扩展性，也就是说随机森林随着决策树数量的增多不易过拟合

决策树的相关度和强度对的泛化误差的影响

随机森林泛化误差的上界为：

$$PE^{*}\leqslant \frac{\bar{\rho}(1-s^{2})}{s^{2}}$$

其中：

• $\bar{\rho}$ 为决策树之间的相关度的平均值
• $s$ 为决策树的平均强度

要使随机森林的泛化性能好，则应该尽量减小决策树之间的相关性($\rho$)，增大单棵树的分类性能($s$)

• 每棵树的分类强度越大，则随机森林的分类性能越好
• 森林中树之间的相关度越小，则随机森林的分类性能越好

性能评价指标

随机森林分类性能主要受内外两方面因素的影响：

• 外部因素：训练样本的正负类样本分布，即训练样本的平衡
• 内部因素：单棵树的分类强度和树之间的相关度

分类效果

• 分类精度：准确度(acccuracy of measurement)，是指使用算法得出的分类结果与真实之间的接近程度
• 二分类数据的混淆矩阵
  • 分类精度(accuracy)：$Accuracy=\frac{TP+TN}{TP+TN+FP+FN}$
  • 灵敏度(Sensitivity)(正类的的分类精度)：$Sensitivity=\frac{TP}{TP+FN}$
  • 特异度(Specificity)(负类的的分类精度)：$Specificity=\frac{TN}{FP+TN}$
  • 几何均值(G-mean)：$G-mean=\sqrt{\frac{TP}{TP+FN}\times \frac{TN}{FP+TN}}$
  • 负类的查全率(Recall)：$Recall=\frac{TP}{TP+FN}$
  • 负类的查准率(Precision)：$Precision=\frac{TP}{TP+FP}$
  • 负类的检验值(F-value)：$F-value=\frac{(1+\beta^{2})\cdot recall \cdot precision}{\beta^{2}\cdot recall \cdot precision}，\beta \in (0，1]$

泛化误差

泛化误差(generalization error)是反应泛化能力(generalization ability)的一个指标。 随机森林的泛化误差理论上是可以计算出来的，然而，在实际环境中，样本的期望输出和分布情况都是不知道的， 无法直接通过计算泛化误差来评估随机森林的泛化能力。但是泛化误差可以通过以下方法进行估计：

• 交叉验证(Cross-Validation，CV)(验证集上的)
  • 运算量很大
• OOB 估计
  • 随机森林是使用 Bootstrap 来进行每棵树训练集的生成，在生成这些训练集时， 初始训练集中有一些样本是不能被抽取的，这些样本的个数占初始数据集的比例是 $(1-\frac{1}{M})^M$。 可以证明，当$M$ 足够大时，$(1-\frac{1}{M})^M$ 将收敛于 $\frac{1}{e}\approx 0.368$， 说明将有近 $37\%$ 的样本不会被抽取出来，这些不能被抽取的样本组成的集合，称之为袋外数据(OOB)
  • 使用 OOB 数据来估计随机森林算法的泛化能力称为 OOB 估计：以每棵决策树为单位， 利用 OOB 数据统计该树的 OOB 误分率；将所有决策树的误分率取平均得到随机森林的 OOB 误分率， 就可以得到一个 OOB 误差估计
  • Breiman 通过实验已经证明，OOB 估计是随机森林的泛化误差的一个无偏估计
  • OOB 估计相比于 CV 估计，效率很高
• 运行效率

参数设置

随机森林算法中需要设置的主要参数有：

• 随机森林中决策树的数量($n\_tree$)

  • 一般来讲，决策树的数量越多，算法的精度越高，但程序的速度会有所下降；

• 随机森林内部节点随机选择属性的个数($p$)：一般为小于 $log_{2}(P+1)$ 的最大整数

  • 内部节点随机选择属性的个数(mtry)是影响算法精度的主要因子， 随机森林内决策树的强度和相关度和随机选择属性的个数相关， 如果随机选择属性的个数足够小，树的相关性趋向于减弱， 另一方面，决策树模型的分类强度随着随机选择属性的个数的增加而提高

• Random Forests-Leo Breiman and Adele Cutler