NO.44.tip：随机森林

背景

随机森林（random forest）或随机决策森林是由多棵决策树组成的、用于分类、回归和其他任务的集成学习（ensemble learning）方法。一个随机森林是由多棵决策树组成的。其工作原理是随机选择在同一训练集的不同数据样本上创建决策树，从每棵树上得到预测，并通过投票的方式选择最佳解决方案。随机森林的目的是降低方差。对于分类问题，按照多棵分类树投票决定最终分类结果；对于回归问题，由多棵树的预测值的均值决定最终预测结果。这被称为"投票"加"平均"原理。

随机森林是一种有监督学习算法，灵活且容易使用。森林中包含的树越多，森林就越健壮。生长得很深的决策树往往会学习到高度不规则的模式，甚至过拟合其训练集。而随机森林纠正了决策树对其训练集过拟合的习惯。随机森林通常优于决策树，但其准确性稍低于梯度提升树。

1995 年，何天琴利用随机子空间法创建了第一个随机决策森林算法，建立了由超平面分割树组成的森林，只要随机限制森林对所选定的特征属性敏感，就可以随着森林的变大而获得更好的精度，且不会受到过度训练的影响。只要随机强制对某些特征维度不敏感，其他分割方法也会有类似的效果。需要说明的是，更大规模的森林模型几乎是单调地使预测变得更准确，这与人们普遍认为的分类器的复杂度增长到一定程度上会被过拟合所限制的观点形成了鲜明的对比。

对随机森林的正式介绍最早是在 Leo Breiman 等人的一篇论文中给出的，他们将"Random Forests"注册为商标（截至 2019 年，由 Minitab 公司拥有）。该扩展结合了套袋思想和随机选择特征，建立由无关树构成的森林。他们使用袋外误差作为泛化误差的估计，通过置换方法测量变量的重要性。

源与流

随机森林的基本原理

随机森林在企业中经常被用作"黑箱"模型，因为它可以在广泛的数据中产生合理的预测。

机器学习模型的目标是对它从未见过的新数据进行良好的泛化。当决策树模型容量很大时，就会出现过拟合。决策树基本上是通过紧密拟合来记忆训练数据的。问题在于，模型不仅学习训练数据中的实际关系，还会学习或记忆任何存在于这些训练数据中的噪声。

如果学习到的参数（如决策树的结构）会随着训练数据的变化而有很大的变化，那么这个模型就会有高方差。如果它对训练数据做出了假设，例如，线性分类器做出了样本数据服从线性分布的假设，那么它就不具有适应非线性关系的灵活性，更无法很好地泛化到新数据上。在这种情况下，模型就会有高偏差。在高方差模型的训练数据上得到的模型会有偏差，模型可能连非线性关系都没有能力拟合，更无法很好地泛化到新数据上。

当我们不限制决策树的最大深度时，决策树可以完美地对所有的观测值进行分类，但树被深地学习不同偏差与方差下的数据分布，模型的预测能力是不足的。如果将决策树的最大深度限制为 2，即只做一次分割，分类将不再是 100% 正确的，这就是我们降低决策树的方差，但代价是增加了偏差，作为限制决策树深度优化预测性能的原理。

多次决策树组合成单一的集成模型，形成随机森林。

构造随机森林的步骤

构造随机森林的 4 个步骤如下：

一个容量为 $N$ 的样本集合，做有放回的抽取 $N$ 次，每次抽取 1 个，最终形成了 $N$ 个样本训练集。用这样选择出的 $N$ 个样本训练生成一个决策树。这里 $N$ 的值是一个超参数。一般地， $N \geq N^{'} \geq (2/3) N$ 。
假设每个样本有 $M$ 个特征属性，在构建决策树时，只从这 $M$ 个特征属性中选取 $m$ 个特征属性，且满足条件 $m ≪ M$ 。一般地， $m$ 可以取分类中所有预测因子总数的平方根。对于回归问题， $m$ 可以取所有预测因子的总数除以 3。在森林生长过程中， $m$ 的值保持不变。
按照普通决策树构建方法，例如基于信息增益、信息增益率或基尼指数等，以这 $m$ 个属性为基础构建决策树。注意整个决策树形成过程中没有进行剪枝。
按照步骤 1~3 建立大量的决策树，这样就构成了随机森林。

这种方法在不增加偏差的情况下降低了方差，从而带来了更好的性能。这意味着，即使单个树模型的预测对训练集的噪声非常敏感，但对于多个树模型，只要这些树并不相关，这种情况就不会出现。但是，简单地在同一个数据集上训练多个树模型会产生强相关的树模型（甚至是完全相同的树模型）。因此，需要对训练集进行一些采样，使得后续产生的决策树模型不会是随机相关。套袋法采样就是这样一种降低树模型之间关联性的方法，后文将做详细介绍。

随机森林里各个决策树的构建过程中，进行节点分割时，不是所有的特征属性都参与，而是随机选择某几个特征属性参与比较。这样做是为了使每棵决策树之间的特征属性的相关性减少，同时提升每棵决策树的分类精度，从而提升整个随机森林的性能。特征属性的选择通常有两种策略：

Forest-RI（随机输入特征属性选择）策略。随机森林可以使用套袋法结合随机特征属性选择来建立。生成 $k$ 棵决策树的随机森林的一般过程如下。对于每次迭代 $i (i = 1, 2, \dots, k)$ ，训练集 $D_{i}$ 是对数据集 $D$ 进行放回采样得到的。每个 $D_{i}$ 都是 $D$ 的一个套袋内样本集合，因此一些样本可能会在 $D_{i}$ 中出现不止一次，而其他样本可能会被排除在外。设 $m$ 为每次迭代的特征属性数， $m ≪ M$ 。为了构建决策树分类器 $T_{i}$ ，在每个节点上随机选取 $m$ 个属性作为该节点分割的候选属性，采用常见的决策树分裂属性选择指标，如基尼指数、信息增益或信息增益率等，确定最终的分割属性。接下来确定下一个节点的分割属性时，再次随机选取 $m$ 个属性作为该节点分割的候选属性。允许树长到最大尺寸，不进行修剪。
Forest-RC（随机线性组合）策略。另一种形式使用输入特征属性的随机线性组合，不是随机选择一个原始特征属性子集，而是创建新的属性（或特征），这些特征属性是现有特征属性的线性组合。也就是说，通过指定 $L$ ，即要组合的原始属性的数量来生成一个新属性。为了构建决策树分类器 $T_{i}$ ，在给定的节点上，随机选取 $L$ 个属性，并随机选取 $L$ 个系数，该系数为 $[- 1, 1]$ 上均匀分布的随机数。共产生 $m$ 个线性组合而成的属性值，在这些组合上进行搜索，以获得最佳分割。当只有少量属性可用时，这种形式的随机森林是有用的，这样可以减少各个分类器之间的相关性。

选择最优的随机特征属性数量

如何选择最优的随机特征属性数量 $m$ ？要解决这个问题，主要依据是袋外错误率。随机森林有一个重要的优点：没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的无偏估计。它可以在内部进行评估，也就是说在生成的过程中就可以对误差建立无偏估计。

应用套袋法（bootstrap aggregating）时，会创建两个独立的集合：一个是套袋内样本集合，是通过无权重放回采样选择的"袋内"数据；另一个是袋外集合，即 OOB（Out Of Bag）集合，是所有在采样过程中没有被选择过的数据。当这个过程重复进行时，就会建立起随机森林，产生许多套袋内样本集合和 OOB 集合。对于每个决策树，数据被分成袋内与袋外两组。

套袋过程可以根据模型的需要进行定制。为了保证模型的准确性，套袋内训练样本的大小应该接近或等于原始数据集的大小。（对于一个具有 $m$ 个样本的训练集，我们有放回地抽取 $m$ 个样本进行训练，那么每个样本不被抽到的概率为 $p = (1 - 1/ N)^{N}$ ，当 $N$ 越来越大时， $p$ 趋于 $1/3$ 。也就是森林形成的过程中有三分之一的数据是没有被用到的。）

由于每一个 OOB 集合都不是用来训练模型的，所以它是对模型性能的很好的测试。

OOB 错误率是指每个训练样本的袋外平均预测误差。OOB 错误率的具体计算方法取决于模型，但一般计算方法如下：

对于每一个 OOB 集合中的样本，找出所有没有被该实例样本训练过的决策树集合。
取随机森林对该样本的预测结果（即步骤 1 中得到的这些决策树对该样本的预测值的多数票），与该样本的真实值进行比较，计算出该样本的 OOB 错误率。
对每个 OOB 数据集中所有样本的 OOB 错误率进行统计，求平均值得出随机森林的 OOB 错误率。

OOB 错误率应用于剪枝。OOB 错误率会在多次迭代后趋于稳定。OOB 错误率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的 K 折交叉验证。

例如，对于处理分类问题的随机森林，假设随机森林生成了 500 棵树，对于一个样本 $x$ ，它在 200 棵树中属于袋外集合。使用这 200 棵树对样本 $x$ 进行预测时，有 160 棵树将其预测为类 1，另外 40 棵树将其预测为类 2。在这种情况下，随机森林最终预测结果是类 1。这种情况下的预测正确概率是 0.8，即 160/200，所以该样本 $x$ 的 OOB 错误率为 0.2。

套袋法

套袋法[bagging 或 bootstrap aggregating（引导聚集算法）]又称装袋法，是机器学习领域的一种集成学习算法，最初由 Leo Breiman 于 1994 年提出。套袋法可与其他分类、回归算法结合，在提高其准确率、稳定性的同时，通过降低结果的方差避免过拟合的发生。

bootstrap 这个奇怪的名字来源于文学作品 The Adventures of Baron Munchausen（《吹牛大王历险记》），这部作品中的一个角色用提着鞋带的方法把自己从湖底提了起来。因此采用意译的方式也叫作自助法，顾名思义，从样本自身中再生成很多可用的同等规模的新样本，不借助其他样本数据。这种方法在样本比较小的时候很有用，这种情况下我们希望留出一部分样本用作验证，而按照传统方法做训练集-验证集分割的话，样本就更小了，偏差会更大，这是我们不希望的。而自助法不会降低训练样本的规模，又能留出验证集（因为训练集有重复的，但是这种重复又是随机的），因此有一定的优势。

套袋法是以可重复的随机采样为基础的，每个样本是初始数据集的有放回采样。在可重复采样生成多个训练子集时，存在于初始训练集 $D$ 中的所有样本都有被抽取的可能，但在重复多次后，总有一些样本是没有被抽取的，每个样本未被抽取的概率为 $(1 - 1/ N)^{N}$ 。

$(1 - \frac{1}{N})^{N} = \frac{1}{( \frac{N}{N - 1} ) ^{N}} = \frac{1}{( 1 + \frac{1}{N} ) ^{N}} \approx \frac{1}{e} \approx 0.368$

随机森林是套袋法的一个典型应用。因此，随机森林在生成每棵决策树时，无权重放回随机抽取的样本，每棵决策树会有大概 $1/3$ 的样本未抽取到，这些样本就是每棵树的袋外样本（OOB 样本）。以这些为验证集的方式叫作袋外估计（out-of-bag estimate），可以计算出袋外错误率以指导随机森林的生成过程。

套袋法与随机森林的比较如下：

两者的收敛性相似，但是随机森林的起始性能相对较差，特别是只有一个基学习器时。
随着基学习器数量的增加，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率常优于套袋法，因为套袋法是"确定性"决策树，而随机森林使用"随机性"决策树。
其实套袋模型不止有随机森林，还可以集成 KNN 模型、决策树模型等。但是一般的 KNN 模型不适合做集成学习，因为很难随机让泛化能力变强。

套袋法的算法流程

套袋法是每个分类器对原始数据的随机抽取进行学习，最后进行投票的方法。例如，给定包含 $m$ 个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中。这样，我们可以采样出 $T$ 个含 $m$ 个训练样本的采样集（这个过程称为自助），然后基于每个采样集训练出一个基分类器（这个过程称为聚集），然后将这些基分类器进行集成，获得套袋器。在对预测输出进行集成时，通常对分类任务使用简单投票法，对回归任务使用简单平均法，这就是套袋法的基本流程。

输入：训练集 $D = {(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{m}, y_{m})}$ ；基学习算法 $ζ$ ；训练轮数 $T$

过程：

for $t = 1, 2, \dots, T$ do

$h_{t} = ζ (D, D_{b s})$

end for

输出： $H (x) = ar g y \in Y max t = 1 \sum T (h_{t} (x) = y)$

套袋法的偏差和方差

套袋法训练多个分类器取平均，其函数如下：

对于套袋法来说，每个基模型的权重等于 $1/ m$ 且期望近似相等（子训练集都是从原训练集进行子采样），故可以进一步简化得到：

$E (F) = γ i = 1 \sum m E (f_{i}) = \frac{1}{m} m μ = μ$

$Var (F) = m^{2} γ^{2} σ^{2} ρ + m γ^{2} σ^{2} (1 - ρ) = m^{2} \frac{1}{m ^{2}} σ^{2} ρ + m \frac{1}{m ^{2}} σ^{2} (1 - ρ) = σ^{2} ρ + \frac{σ ^{2} ( 1 - ρ )}{m}$

根据上式，整体模型的期望近似于基模型的期望，这也就意味着整体模型的偏差和基模型的偏差近似。同时，整体模型的方差小于或等于基模型的方差（当相关性为 1 时取等号），随着基模型数（ $m$ ）的增多，整体模型的方差减少，从而防止过拟合的能力增强，模型的准确率得到提高。但是，模型的准确率一定会无限逼近于 1 吗？并不一定，当基模型数增加到一定程度时，方差公式中第二项的改变对整体方差的作用很小，防止过拟合的能力达到极限，这便是准确率的极限了。另外，套袋法中的基模型一定要为强模型，否则就会导致整体模型的偏差度低，即准确率低。

简单来说，套袋法主要关注降低方差，而降低方差可以降低过拟合的风险，所以套袋法通常在弱分类和复杂模型上表现得很好。

套袋法的优缺点

套袋法的优点：

许多弱的学习器聚集在一起，通常比单个学习器在整个数据集上的表现要好，而且过拟合程度较低。
消除了高方差、低偏差数据集的变异。
可以并行进行，因为每个单独的基学习器在组合之前都可以单独处理。

套袋法的缺点：

对于具有高偏差的数据集，套袋法也会将高偏差带入其中。
丧失了模型的可解释性。
根据数据集的不同，计算成本可能会很高。

随机森林的参数设置与调优

我们通常将随机森林作为一个黑盒子，输入数据然后给出预测结果，无须担心模型是如何计算的。这个黑盒子本身有几个影响精度和性能的参数，在使用时需要关注和调整。随机森林算法中需要设置的主要参数如下：

随机森林中决策树的数量（ntree）。
随机森林内部各个子树随机选择属性的个数（mtry）。

一般来讲，决策树的数量越多，算法的精度越高，但程序的速度会有所下降。内部各个子树随机选择属性的个数是影响算法精度的主要因子，随机森林内决策树的强度和相关度与随机选择属性的个数相关，如果随机选择属性的个数足够小，树的相关性趋向于减弱，另外，决策树模型的分类强度随着随机选择属性的个数的增加而提高。

随机森林的优缺点

随机森林的优点：

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

随机森林的缺点：

当随机森林中的决策树个数很多时，训练时需要的空间和时间会比较大。
在某些噪声较大的样本集上，随机森林容易陷入过拟合。
不能很好地处理非平衡数据。
在随机森林的构建过程中，训练集是随机选取的，使用自助法随机采样时，由于原训练集中含有的少数类占比低，因此被选中的概率就很低。这使得 $M$ 个随机选取的训练集集中少数类数量比原有的数据集更少或没有，反而加剧了数据集的不平衡性，使得基于此数据集训练出来的决策树的规则没有代表性。
由于数据集中少数类占比低，使得训练出来的决策树不能很好地体现少数类的特点，只有将少数类的数量加大，使数据集中的数据达到一定程度的平衡，才能使得算法稳定。
需要对连续性变量进行离散化。

概率统计100问

NO.44.tip： 随机森林

背景

源与流

NO.44.tip：随机森林