随机森林(Random Forest,RF)基于 Bagging 的想法,训练多个学习器集成所有的方式降低模型在训练数据集上的方差,并且各个学习器可以并行操作。

1. Random Forest 算法

  随机森林算法的随机体现在两个方面:

  1. 每个学习器训练样本的随机
  2. 决策树划分节点时特征集选取的随机

  假设输入为样本集为

  基学习器记作 $G(x)$,迭代次数为 $T$:

  1. 对于 $t = 1,2 \ldots , T$:

    1. 对训练集进行第 $t$ 次随机采样,共采集 $m$ 次,得到包含 $m$ 个样本的采样集 $D_t$
    2. 用采样集 $D_t$ 训练第 $t$ 个基学习器 $G_t(x)$,在训练决策树划分结点的时候,在结点上所有的样本特征中随机选出一部分样本特征,在这些随机选择出来的样本特征中找出最优的划分特征来划分当前结点
  2. 如果是分类算法预测,则 $T$ 个基学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法,$T$ 个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

  随机森林的其基学习器是 CART (强学习器),选择特征子集而非全量特征集来划分节点的方式能够提高模型的泛化能力。一般来说,特征子集越小,模型就越健壮,当然此时对数据的拟合程度就会变差;即 variance 越小,bias 越大。随机性使得偏差增大,但由于随机森林集成“平均”的特性,使得方差变小的程度大过了偏差增大的程度,总体来说效果还是好的。

  在每一次 branching 时,做特征 Random 的两种方式:

  1. Bagging + Random-Subspace CART
    • 每个结点做划分的时候都随机选择 $F$ 个属性作为候选属性。
  2. Bagging + Random-Combination CART
    • 使用输入特征的随机线性组合,不是随机选择一个特征子集,而是设定一个组合特征大小 $L$
    • 随机选择 $L$ 个特征组合成一个新的特征,组合方式是随机从 $[-1, 1]$ 选取系数做线性加和
    • 一共产生 $F$ 个线性组合的新特征,然后在其中找到最佳划分
    • 此方法当只有少量特征可用,为了降低个体分类器之间的相关性时可用

  之后就是对采样之后的数据使用完全分裂的方式建立出决策树,这样决策树的某一个叶子节点要么是无法继续分裂的,要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法有剪枝操作,这里不这样干,由于之前的两个随机采样的过程保证了随机性,所以就算不剪枝,也不会出现 over-fitting。

  一般选择特征子集的大小为 $\log_2n+1$,其中 $n$ 为样本特征总数。

2. 袋外数据(Out Of Bag, OOB)

  因为随机森林采用的是 Boostrap,有放回的抽样,一定会有一部分数据不会被抽到,那么在每次训练一个学习器的时候可以用没有被抽到的样本作为测试集。

3. 随机森林的特征技巧

  因为 OOB 的存在,在训练好随机森林后,可以借用没有抽到的袋外数据找到特征的重要性,甚至可以做特征选择的工作。

3.1 特征重要性

  特征重要性的计算可以利用基尼系数,计算所有使用特征 $i$ 作为划分特征的节点,计算其划分前后基尼系数差值并累加起来,然后用这个加和除以在所有节点上使用对应特征划分结点时划分前后的基尼系数差值的累加和。

  其中有:

  • $\text{ni}_{j}$ 为节点 $j$ 的重要性
  • $w_j$ 是到达节点 $j$ 的加权样本数量
  • $C_j$ 是节点 $j$ 的不纯度值
  • $\text{left}(j)$ 表示在节点 $j$ 划分后的左子树
  • $\text{right}(j)$ 表示在节点 $j$ 划分后的右子树

  一个决策树上的每一个特征重要性计算如下:

  其中有:

  • $\text{fi}_{i}$ 表示特征 $i$ 的重要性
  • $\text{ni}_{i}$ 表示节点 $j$ 的重要性

  然后将特征重要性归一化一下:

  最终在整个随机森林层面上的特征重要性就是每个决策树的平均结果:

  其中:

  • $\text {RFfi}_{i}$ 表示随机森林模型中特征 $i$ 的特征重要性
  • $\text{normfi}_{ij}$ 在第 $j$ 颗树上特征 $i$ 的归一化特征重要性
  • $T$ 表示树的数量

3.2 特征选择

  特征选择一般有两个目标:

  1. 找到与应变量高度相关的特征变量
  2. 选择出数目较少的特征变量并且能够充分的预测应变量的结果

  随机森林特征选择的步骤:

  1. 初步估计和排序
    1. 对随机森林中的特征变量按照 VI(Variable Importance)降序排序。
    2. 确定删除比例,从当前的特征变量中剔除相应比例不重要的指标,从而得到一个新的特征集。
    3. 用新的特征集建立新的随机森林,并计算特征集中每个特征的 VI,并排序。
    4. 重复以上步骤,直到剩下 $m$ 个特征。
  2. 根据步骤 1 中得到的每个特征集和它们建立起来的随机森林,计算对应的袋外误差率(OOB err),将袋外误差率最低的特征集作为最后选定的特征集。

4. ExtraTree

  极端随机树(Extremely randomized trees,ET 或 Extra-Trees)是由 Pierre Geurts 等人于 2006 年提出。该算法与随机森林算法十分相似,都是由许多决策树构成。但该算法与随机森林有两点主要的区别:

  1. 随机森林应用的是Bagging模型,而ET是使用所有的训练样本得到每棵决策树,也就是每棵决策树应用的是相同的全部训练样本;

  2. 随机森林是在一个随机子集内得到最佳分叉属性,而ET是完全随机的得到分叉值,从而实现对决策树进行分叉的。

5. 总结

  随机森林有四个部分需要掌握:

  1. 随机选择样本(放回抽样);
  2. 随机选择特征;
  3. 构建决策树;
  4. 随机森林投票(平均)。

  由于 Bagging 的思想可以分布式地实现若干个基学习器的学习,Random Forest 的一大优势是能够高度并行化,在大数据时可大有作为。一般可以用随机森林跑出一个模型,然后查看特征的重要性

  随机森林的优点

  1. 训练可以高度并行化,在大数据时代的大样本训练环境下极具优势
  2. 具有极高的准确率
  3. 随机性的引入,使得随机森林不容易过拟合
  4. 随机性的引入,使得随机森林有很好的抗噪声能力
  5. 由于可以随机选择决策树划分结点的特征,这样在样本特征维度较高时,仍能保持高效的训练,不用做特征选择
  6. 在训练后,可以给出各个特征对于输出结果的重要性
  7. 由于采用了随机采样,训练出的模型方差小,泛化能力强
  8. 相对于 Boosting 的 Adaboost 和 GBDT,RF 比较好实现
  9. 对部分特征确实不敏感
  10. 实践中,既能处理离散型数据,也能处理连续型数据,可以对输入数据不用做太多处理(能够处理 binary features, categorical features, numerical features)

  随机森林的缺点

  1. 在某些噪声比较大的样本集上,容易陷入过拟合
  2. 对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响(偏向取值较多的特征,随机选的时候选中的概率比较高!),所以随机森林在这种数据上产出的属性权值是不可信的
  3. 训练好的模型比较大,预测时较慢
  4. 相比于单一决策树,它的随机性让我们难以对模型进行解释

6. 问答思考(Q & A)

6.1 GBDT 和 Random Forest 哪一个的决策树可以更深?

  随机森林的决策树训练可以更深,因为其每个基学习器的样本是随机抽取的子集,且划分节点的特征也是随机抽取的子集,这些操作降低了模型的方差,但是提高了偏差。那么随机森林可以在训练每个决策树时任其完全生长,尝试在一定程度上降低偏差。

References

  1. Bagging与随机森林算法原理小结
  2. RF、GBDT、XGBoost面试级整理
  3. 随机森林之特征选择
  4. The Mathematics of Decision Trees, Random Forest and Feature Importance in Scikit-learn and Spark
  5. Variable selection using Random Forests