森林顾名思义就是有很多树,这里的树当然就是决策树。实际上随机森林就是将 fully-grown C&RT decision tree 作为 bagging 基模型(base model)。

\[\text{random forest (RF) = bagging + fully-grown C\&RT decision tree}
\]

bagging 会减小方差(variance),而一颗完全长成树的方差会很大,两种相互补足。所以随机森林有以下优点:

  • highly parallel/efficient to learn(效率高,可并行处理)
  • inherit pros of C&RT(继承 C&RT 的优点)
  • eliminate cons of fully-grown tree(弥补 完全长成树的缺点)

随机特征空间(Feature Expansion/Projection)

在 bagging 中使用 bootstrap 获取随机数据,实现多样化。那么还有什么方法呢,那便是从特征出发,类似于非线性转换函数,挖掘出不一样的特征空间。随机森林中提出两种方法特征映射和特征扩展。

特征映射(Projection)

特征映射实际上是从原来的特征 \(\mathbf{x}\) 中随机选择选取 \(d^{\prime}\) 个特征。该映射函数 \(\Phi ( \mathbf { x } )\) 实现如下:

\[\text { when sampling index } i _ { 1 } , i _ { 2 } , \ldots , i _ { \alpha ^ { \prime } } : \Phi ( \mathbf { x } ) = \left( x _ { i _ { 1 } } , x _ { i _ { 2 } } , \ldots , x _ { i _ { d ^ { \prime } } } \right)
\]

同时建议 \(d^{\prime} \ll d\),这样的话对于 \(d\) 很大时,可以提高效率。

所以随机森林的一种表现形式为:

\[\text{RF = bagging + random-subspace C\&RT}
\]

特征扩展(Expansion)

特征扩展实际上也是特征映射,只是其映射函数不同而已,这里认为映射函数则是乘上一个映射矩阵。

\[\Phi ( \mathbf { x } ) = \mathrm { P } \cdot \mathbf { x }
\]

在特征映射中,则是一个 \(d^{\prime}\)\(N\) 列的矩阵,且每一行每列均为单位向量(natural basis)。在特征扩展中,则该映射矩阵的维度不变,但是每一行都是一个随机生成的向量(不再是单位向量),映射后的每一个特征则是多个特征的线性组合(combination),即\(\text { projection (combination) with random row } \mathbf { p } _ { i } \text { of } \mathrm { P } : \phi _ { i } ( \mathbf { x } ) = \mathbf { p } _ { i } ^ { T } \mathbf { x }\),,但是建议该向量是一个稀疏向量只有 \(d^{\prime \prime}\) 个非零项。

所以随机森林的另一种表现形式为:

\[\text{RF = bagging + random-combination C\&RT}
\]

OOB 估计(Out-Of-Bag Estimate)

由于在 bagging 中使用了 bootstrap 获取随机样本,那么便会导致有很多数据未被采样到,这些样本并未被用于获取 \(g_t\),所以这些样本叫做 \(g_t\) 的袋外样本(out-of-bag (OOB) examples)。

那么对于一个样本量为 \(N\) 的数据集,一个样本在 bootstraping 中未被采样的概率是 \(\left( 1 - \frac { 1 } { N } \right) ^ { N }\)

\(N\) 相当大时:

\[\left( 1 - \frac { 1 } { N } \right) ^ { N } = \frac { 1 } { \left( \frac { N } { N - 1 } \right) ^ { N } } = \frac { 1 } { \left( 1 + \frac { 1 } { N - 1 } \right) ^ { N } } \approx \frac { 1 } { e }
\]

也就是说 OOB 的样本数量大概为:\(\frac { 1 } { e } N\)

虽然说 \(g_t\) 的 OOB 可以用于验证 OOB,但是并不常用,这是因为 bagging 这种算法针对的是全部的 \(g_t\) 的融合后的性能,那么这里提出 \(G _ { n } ^ { - }\),其数学表达如下:

\[G _ { n } ^ { - } ( \mathbf { x } ) = \operatorname { average } \left( g _ { i_1 } , g _ { i_2 },\cdots , g _ { i_{T^- }} \right)
\]

其中 \(n\) 代表了样本的索引,\(T^-\) 代表未使用第 \(n\) 个样本的 \(g_t\) 个数, \((i_1,i_2,\cdots,i_{T^-})\) 表示的是这\(n\) 个样本索引集合。

那么OOB误差为:

\[E _ { \mathrm { oob } } ( G ) = \frac { 1 } { N } \sum _ { n = 1 } ^ { N } \operatorname { err } \left( y _ { n } , G _ { n } ^ { - } \left( \mathbf { x } _ { n } \right) \right)
\]

所以 \(E _ { \mathrm { oob } }\) 是 bagging/RF 的自我验证(self-validation),且在实际运用中可以准确估计 RF 的性能。

那么 bagging/RF 的验证流程可以写出:

\[\begin{aligned} G _ { m ^ { * } } & = \mathrm { RF } _ { m ^ { * } } ( \mathcal { D } ) \\ m ^ { * } & = \underset { 1 \leq m \leq M } { \operatorname { argmin } } E _ { m } \\ E _ { m } & = E _ { \mathrm { oob } } \left( \mathrm { RF } _ { m } ( \mathcal { D } ) \right) \end{aligned}
\]

即不需要将数据集 \(\mathcal{D}\) 分为 \(\mathcal{D}_{\text{train}}\)\(\mathcal{D}_{\text{val}}\)。不需要在验证后再次训练了。那么该验证方法便可以用于选择特征扩展中的 \(d^{\prime \prime}\) 了。

特征选择

特征选择实际上就是删除冗余特征(redundant features,比如年龄与生日)和不相关特征(irrelevant features,比如保险类型用于预测癌症)。

经过特征选择之后:

\[\begin{aligned}& \Phi ( \mathrm { x } ) = \left( x_ { i _ { 1 } } , x _ { i _ { 2 } } , \cdots, x _ { i _ { d ^ { \prime } } } \right) \\ &\text { with } d ^ { \prime } < d \text { for } g ( \Phi ( \mathbf { x } ) ) \end{aligned}
\]

这样做的优点:

  • 效率:更简单假设函数和更短预测时间
  • 泛化:消除了特征噪声
  • 可解释性:因为重要才对这些特征进行研究

这样做事物缺点:

  • 计算消耗:特征选择需要很高的时间消耗
  • 过拟合:可能会选择到可能很好,实际上不一定
  • 不可解释:只能解释关联性,但不能解释因果关系

决策树(decision tree)则是一种在构建过程中,同时筛选了特征的过程。

由于特征选择可能存在爆炸性组合,那么通过重要性选择(Feature Selection by Importance)可能可以一定程度上代替特征组合穷举。重要性选择指的是将每个特征进行打分,通过分数的高低选择特征。

也就是说计算

\[\text { importance } (i )\text { for } i = 1,2 , \ldots , d
\]

然后根据分数选择 top-\(d^\prime\) 的特征。

线性模型(Linear Model)

因为在线性模型中,输出的分数(不是特征的重要性)是由 \(d\) 维特征线性组合得到的。当特征值 \(x_i\) 之间相差不大时,每个维度的特征的权重比较大时,那么这个特征可能更重要。所以先训练出一个线性模型:

\[\text { score } = \mathbf { w } ^ { T } \mathbf { x } = \sum _ { i = 1 } ^ { d } w _ { i } x _ { i }
\]

之后使用权重的绝对值作为该特征的评判分数:

\[\text { importance } ( i ) = \left| w _ { i } \right| \text { with some 'good' } \mathrm { w }
\]

但是如果使用非线性模型(数据非线性可分)的情况下,该方法不太适用。

排列测试(Permutation Test)

随机测试指的是如果某个特征很重要,那么如果向特征加入随机噪声,那么一定会降低算法的性能。但是在机器学习的可行性分析中,可以得知,机器学习算法是基于独立同分布这个前提的,也就是说如果在特征 \(i\) 中加入随机噪声,那么该特征的分布 \(P(x_i)\)。那么这样操作的话,同时加入了分布的影响,所以比较合理的方法是间原来的第 \(i\) 维数据重新排列(Permutation),这样的话分布不会改变。

那么根据这个思路写出重要性(分数)计算公式如下:

\[\begin{array} { c } \text { importance } ( i ) = \text { performance } ( \mathcal { D } ) - \text { performance } \left( \mathcal { D } ^ { ( p ) } \right) \\\\ \text { with } \mathcal { D } ^ { ( p ) } \text { is } \mathcal { D } \text { with } \left\{ x _ { n , i } \right\} \text { replaced by permuted } \left\{ x _ { n , i } \right\} _ { n = 1 } ^ { N } \end{array}
\]

对于任意的非线性模型,排列测试(Permutation Test)都是一个常用的统计学工具。

由于需要使用验证进行性能测试,所以在随机森林中,则使用 permuted OOB 和 OOB 在验证的同时计算特征的重要性分数。

\[\text { importance } ( i ) = E _ { \mathrm { oob } } ( G ) - E _ { \mathrm { oob } } ^ { ( p ) } ( G )
\]

随机森林通过 permutation + OOB 实现特征选择,这一操作常常是有效且实用的,所以在实践过程中如果遇到 non-linear 的特征选择问题,常常选择随机森林进行初步的特征选择。

举例说明

A Simple Data Set

机器学习技法 之 随机森林(Random Forest)
左侧是第900颗决策树,实用 bootstrap 获取的,其中 \(N^{\prime} = N/2\)。右侧是使用900颗决策树的随机森林,可以看出决策树越多,边界越趋于平滑且类似(趋)于大间隔(边界位于正负样本之间)。

A Complicated Data Set

机器学习技法 之 随机森林(Random Forest)
可以看出随着决策树个数增加,更容易处理非线性问题。

A Complicated and Noisy Data Set

机器学习技法 之 随机森林(Random Forest)
可以看出随着树的增加,噪声随着投票可能会得到纠正(noise corrected by voting)。

可以看出理论上来说对于随机森林,决策树越多越好(the more, the ‘better’)。那么需要多少呢,因为不可能无穷多,并且需要考虑时间消耗和模型复杂度导致的过拟合。

因为随机森林很随机,所以如果整个过程都很随机,那么最好多次检测是否树的个数足够多,以保证算法稳定性。(if the whole random process too unstable should double-check stability of G to ensure enough trees)