分类器融合（4）：随机森林

随机森林

bagging 通过投票或平均的方法，可以减少 variance；决策树功能强大， 但是有很大的 variance。能否将二者融合起来，优势互补？
［1/3］random forest（RF） = bagging + fully-grown C&RT tree。
random 描述了 bagging 中 bootstrapping 过程的随机性；forest 表示很多树的组合。

随机森林算法

---

对于$t=1,2,\ldots,T$，循环执行：

1. 通过 bootstrapping 方法从 $\mathcal D$ 中抽取大小为 $N’$ 的数据集 $\tilde{\mathcal D}_t$；
2. 通过决策树算法 $\mbox{DTree}(\tilde{\mathcal D}_t)$ 得到非剪枝的完全成长树 $g_t$。

返回 $G=\mbox{Uniform}(\{g_t\})$ 就是随机森林。

不同的 $g_t$ 是分类器融合的关键。一种得到不同的 $g_t$ 的方法是在 bagging 阶段，通过 bootstrapping 的方法制造数据集的随机性。另一种得到不同 $g_t$ 的方法是制造特征的随机性，在 C&RT 阶段从 $\mathbf x$ 中随机抽取 $d’$ 维特征：

• 随机抽取索引为 $i_1,i_2,\ldots,i_{d’}$ 的特征，特征空间从高维到低维投影，$\Phi(\mathbf x)=\left(x_{i_1},x_{i_1},\ldots,x_{i_{d’}}\right)$；
• $\mathcal Z\in\mathbb R^{d’}$ 是 $\mathcal X\in\mathbb R^d$ 的随机子空间（random subspace）；
• 通常 $d’\ll d$，对大的 $d$ 这样更高效¹；

RF 的原作者建议 C&RT 每次计算 $b(\mathbf x)$ 时，重新抽取特征，得到 $d’$ 维特征子空间，让得到的树更不一样：
［2/3］RF ＝ bagging ＋ random-subspace C&RT。
随机从 $\mathbf x$ 中采样 $d’$ 维特征可记为 $\Phi(\mathbf x)=\mathbf P\mathbf x$，利用 $\mathbf P$ 的行随机抽取 1 维特征，这样的行属于自然基（natural basis）。树的节点在特征的 $d’$ 维随机子空间进行最优分支[1]，在森林成长过程中保持 $d’$ 不变。

C&RT 利用特征的随机抽样组合，通过 $\mathbf p_i$ 对特征进行投影（组合）实现，$\phi_i(\mathbf x)=\mathbf p_i^T\mathbf x$，可以得到更强大的特征空间。通常采用低维投影，$\mathbf p_i$ 只有 $d’’$ 个非零元素：
［3/3］RF ＝ bagging ＋ random-combination C&RT。
采用随机组合方式的 C&RT，每个分支函数 $b(\mathbf x)$ 相当于感知器（线性分类器）。随机子空间是 $d’’=1$ 的特殊情况，且 $\mathbf p_i$ 属于自然基。

Quora 给出了随机森林通俗的解释。随机森林产生不同 $g_t$（也就是 C&RT）需要的随机性来源于两方面：bootstrap 对数据集的随机抽样和 C&RT 中对特征的随机抽样组合。

随机森林的泛化误差由两方面决定[2]：

1. 森林中任意两棵树的相关性增加，随机森林的误差增加；
2. 单颗树的能力越强，随机森林的误差越低。

特征抽取数量 $d’$ 是随机森林敏感的唯一可调节参数（另一个参数是森林中树的数量），可通过后文的 $E_{oob}$ 确定。减小 $d’$，能够降低树之间的相关性，同时也削弱了树的能力。

基于 OOB 数据集的验证

［左］：out-of-sample数据点；［右］：验证集

采用 bagging 的时候，没被选中数据点称为 out-of-bag（OOB）数据，如上图左所示，星号标注的 OOB 数据没有参与训练 $g_t$。当 $N’=N$ 时，对任意 $g_t$，任一数据点 $(\mathbf x_n,y_n)$ 是 OOB 的概率是 $\left(1-{1\over N}\right)^N$，$N$ 很大时，这个概率是 ${1\over e}$。训练每个 $g_t$ 时，OOB 数据集大小约为 ${Ne^{-1}}$，也就是大约 1/3 的数据没有参与训练。当 $N’=pN$ 时，OOB 数据集大小约为 ${Ne^{-p}}$。

即使 $g_t$ 效果不理想，融合后的分类器 $G$ 仍然可以达到很好的效果，因此不需要验证每个 $g_t$。利用 OOB 数据集替代验证集，评估随机森林的泛化性能。$G_n^-$ 表示融合所有以 $(\mathbf x_n,y_n)$ 作为 OOB 数据点的分类器，这样可以使用于验证的 OOB 数据都没被训练污染。由上图左最下一行可得一种以 $(\mathbf x_N,y_N)$ 为 OOB 数据点的分类器融合方式 $G_N^-=\mbox{average}(g_2,g_3,\ldots,g_T)$。利用OOB数据集的分类器误差（错误率）定义为 \begin{equation} E_{oob}(G)={1\over N}\sum_{n=1}^Nerr\left(y_n,G_n^-(\mathbf x_n)\right)， \end{equation} 也就是通过 $G_n^-$ 对每个 OOB 数据点的分类错误估计总体误差。增加树的同时可计算树在 OOB 数据上的误差，在随机森林训练结束之后再综合可得 $E_{oob}(G)$，使用过程中动态增加树不需重新训练和验证。基于 OOB 数据集估计的误差和交叉验证相近，但交叉验证计算复杂度高，$E_{oob}(G)$ 可代替 $E_{val}(G)$ 作为随机森林泛化误差的无偏估计²。

［左］：验证集方法［右］：OOB集方法

上图是基于 $E_{val}$ 和基于 $E_{oob}$ 的验证方法对比，当森林中有足够多的树时，$E_{oob}$ 通常能更准确的衡量 $G$ 的性能[3]。利用 $E_{oob}$ 进行 $d’’$ 等参数选择，不需要像交叉验证一样针对每份验证集重新训练分类器，也没有选择了 $g_{m^*}^-$ 再回到整个训练集得到的 $g_{m^*}$ 的步骤。利用 $E_{oob}(G)$，bagging 和 RF 实现了自验证（self-validation）。

特征选择

特征选择就是移除冗余（redundant）和不相关（irrelevant）的特征。特征选择的主要优点包括：

• 高效：让假设集合简单，预测时间变短；
• 提升泛化能力：移除特征的同时也移除了特征中的噪声；
• 增强可理解性：剩余的特征对结果的解释性更强；

但也存在相应的缺点：

• 计算量大：从特征空间选择重要的特征子集本身是组合优化问题；
• 过拟合：恰好选到那些结果看似很好的特征组合；
• 误解释：特别是存在过拟合时，可能得到结果的错误解释，或者只能得出关联性而非因果关系。

决策树本身具备特征选择的能力，每次在某个特征上进行分割，用到的那些特征就是被选择的特征，这和 decision stump 类似。

特征选择的简单理想情况是不考虑特征组合的影响，计算每个特征的重要性，从 $d$ 维特征中选择最重要的 $d’$ 维特征。通过线性模型容易实现 \[ \text{score} = \mathbf w^T\mathbf x=\sum_{i=1}^dw_ix_i， \] 对良好的 $\mathbf w$（能对特征合理评分），第 $i$ 维特征的重要性为 $\mbox{importance}(i)=|w_i|$，重要性大的对得分贡献就大，也就是重要的特征。$\mathbf w$可通过数据学习到。对于非线性模型，特征选择通常比较复杂。虽然 RF 是非线模型，但是由于内在的机制，采用随机测试（random test）也能方便选择特征。如果特征 $i$ 很重要，用随机值 $\mathbf x_{n,i}$ 代替该特征就会极大降低性能。产生这些随机值的方法包括：

• 通过均匀分布或高斯分布产生：真实数据的分布 $P(x_i)$ 可能并不服从这些分布，不仅加入了噪声，而且改变了分布，不是理想的方法。
• bootstrap 或者组合（permutation）方法：重新排列特征（类似洗牌），这样可保持第 $i$ 维特征的分布 $P(x_i)$ 不变。

利用组合方法重排特征进行性能测试称为组合测试（permutation test）， \[ \mbox{importance}(i)=\mbox{importance}(\mathcal D)-\mbox{importance}\left(\mathcal D^{(p)}\right)， \] $\mathcal D^{(p)}$ 表示 $\mathcal D$ 的第 $i$ 维特征 $\{x_{n,i}\}$ 经过重新“洗牌”。组合测试是一种统计工具，可以用于类似RF的其它非线性模型。计算 $\mbox{importance}\left(\mathcal D^{(p)}\right)$ 通常需要在 $\mathcal D^{(p)}$ 上重新训练和验证，但是 RF 可以不重新训练， \[ \mbox{importance}(i)=E_{oob}(G)-E_{oob}^{(p)}(G)， \] 在计算 $E_{oob}(G)$ 过程中，当 $g_t$ 需要第 $i$ 维特征 $x_{n,i}$ 时，随机选择 $g_t$ 的一个 OOB 数据点的第 $i$ 维特征替代（确保验证数据没有参与训练），这样就可得到 $E_{oob}^{(p)}(G)$。

在实际中，利用 RF 通过 “permutation + OOB” 进行特征选择，通常高效可行，可作为处理其它非线性问题的特征选择工具。

随机森林的特性

Leo Breiman 和 Adele Cutler 这样说[4]

---

• It is unexcelled in accuracy among current algorithms.
• It runs efficiently on large data bases.
• It can handle thousands of input variables without variable deletion.
• It gives estimates of what variables are important in the classification.
• It generates an internal unbiased estimate of the generalization error as the forest building progresses.
• It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing.
• It has methods for balancing error in class population unbalanced data sets.
• Generated forests can be saved for future use on other data.
• Prototypes are computed that give information about the relation between the variables and the classification.
• It computes proximities between pairs of cases that can be used in clustering, locating outliers, or (by scaling) give interesting views of the data.
• The capabilities of the above can be extended to unlabeled data, leading to unsupervised clustering, data views and outlier detection.
• It offers an experimental method for detecting variable interactions.

随机森林不会过拟合，可以尽情的增加树的数量[4]。通常随机森林需要的树越多越好🌲🌲🌲🌲，$\bar g=\lim_{T\rightarrow\infty} G$。通过增减树判断随机森林是否稳定，确保有足够多的树，如果不够，继续增加🌲。

设随机森林中有$K$棵树$\{g_k\}_{k=1}^K$，$K$是奇数，若每棵树0/1误差为$E_{out}(g_k)=e_k$。当至少有$K+1\over 2$棵树都对某个数据分错时$G$才会将其错分，也就是每个错分点最少要“消耗”掉$K+1\over 2$棵树，随机森林中错分的数据量为$N\cdot E_{out}(G)$，$K$棵树最多可能的错分数据量为$\sum_{k=1}^KN\cdot e_k$，那么有 \[ {K+1\over 2}\cdot N\cdot E_{out}(G)\leq \sum_{k=1}^KN\cdot e_k， \] 由此可以得到随机森林的误差上界 \[ E_{out}(G)\leq {2\over K+1}\sum_{k=1}^KE_{out}(g_k)。 \]

台湾大学在 KDDCup 2013 中发现，随机森林的$E_{val}$表现依赖初始的种子点，最终通过将树增加到 12000 课，固定种子为1，夺得了冠军🏆。

以下图片展示了随机森林的优点：

通过多棵树得到平滑和类似最大边界的判别界

容易得到鲁棒的非线性模型

通过投票机制消除噪声的干扰

随机森林的应用

基于R语言的randomForest应用范例[1]。

参考资料

1. [1]A. Liaw and M. Wiener, “Classification and regression by randomForest,” R news, vol. 2, no. 3, pp. 18–22, 2002.
2. [2]L. Breiman, “Random forests,” Machine learning, vol. 45, no. 1, pp. 5–32, 2001.
3. [3]T. Bylander, “Estimating generalization error on two-class datasets using out-of-bag estimates,” Machine Learning, vol. 48, no. 1-3, pp. 287–297, 2002.
4. [4]L. Breiman and A. Cutler, “Random Forests.” . [Online]

脚注