森林顾名思义就是有很多树,这里的树当然就是决策树。实际上随机森林就是将 fully-grown C&RT decision tree 作为 bagging 基模型(base model)。
\]
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 } )\) 实现如下:
\]
同时建议 \(d^{\prime} \ll d\),这样的话对于 \(d\) 很大时,可以提高效率。
所以随机森林的一种表现形式为:
\]
特征扩展(Expansion)
特征扩展实际上也是特征映射,只是其映射函数不同而已,这里认为映射函数则是乘上一个映射矩阵。
\]
在特征映射中,则是一个 \(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}\) 个非零项。
所以随机森林的另一种表现形式为:
\]
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\) 相当大时:
\]
也就是说 OOB 的样本数量大概为:\(\frac { 1 } { e } N\)
虽然说 \(g_t\) 的 OOB 可以用于验证 OOB,但是并不常用,这是因为 bagging 这种算法针对的是全部的 \(g_t\) 的融合后的性能,那么这里提出 \(G _ { n } ^ { - }\),其数学表达如下:
\]
其中 \(n\) 代表了样本的索引,\(T^-\) 代表未使用第 \(n\) 个样本的 \(g_t\) 个数, \((i_1,i_2,\cdots,i_{T^-})\) 表示的是这\(n\) 个样本索引集合。
那么OOB误差为:
\]
所以 \(E _ { \mathrm { oob } }\) 是 bagging/RF 的自我验证(self-validation),且在实际运用中可以准确估计 RF 的性能。
那么 bagging/RF 的验证流程可以写出:
\]
即不需要将数据集 \(\mathcal{D}\) 分为 \(\mathcal{D}_{\text{train}}\) 和 \(\mathcal{D}_{\text{val}}\)。不需要在验证后再次训练了。那么该验证方法便可以用于选择特征扩展中的 \(d^{\prime \prime}\) 了。
特征选择
特征选择实际上就是删除冗余特征(redundant features,比如年龄与生日)和不相关特征(irrelevant features,比如保险类型用于预测癌症)。
经过特征选择之后:
\]
这样做的优点:
- 效率:更简单假设函数和更短预测时间
- 泛化:消除了特征噪声
- 可解释性:因为重要才对这些特征进行研究
这样做事物缺点:
- 计算消耗:特征选择需要很高的时间消耗
- 过拟合:可能会选择到可能很好,实际上不一定
- 不可解释:只能解释关联性,但不能解释因果关系
决策树(decision tree)则是一种在构建过程中,同时筛选了特征的过程。
由于特征选择可能存在爆炸性组合,那么通过重要性选择(Feature Selection by Importance)可能可以一定程度上代替特征组合穷举。重要性选择指的是将每个特征进行打分,通过分数的高低选择特征。
也就是说计算
\]
然后根据分数选择 top-\(d^\prime\) 的特征。
线性模型(Linear Model)
因为在线性模型中,输出的分数(不是特征的重要性)是由 \(d\) 维特征线性组合得到的。当特征值 \(x_i\) 之间相差不大时,每个维度的特征的权重比较大时,那么这个特征可能更重要。所以先训练出一个线性模型:
\]
之后使用权重的绝对值作为该特征的评判分数:
\]
但是如果使用非线性模型(数据非线性可分)的情况下,该方法不太适用。
排列测试(Permutation Test)
随机测试指的是如果某个特征很重要,那么如果向特征加入随机噪声,那么一定会降低算法的性能。但是在机器学习的可行性分析中,可以得知,机器学习算法是基于独立同分布这个前提的,也就是说如果在特征 \(i\) 中加入随机噪声,那么该特征的分布 \(P(x_i)\)。那么这样操作的话,同时加入了分布的影响,所以比较合理的方法是间原来的第 \(i\) 维数据重新排列(Permutation),这样的话分布不会改变。
那么根据这个思路写出重要性(分数)计算公式如下:
\]
对于任意的非线性模型,排列测试(Permutation Test)都是一个常用的统计学工具。
由于需要使用验证进行性能测试,所以在随机森林中,则使用 permuted OOB 和 OOB 在验证的同时计算特征的重要性分数。
\]
随机森林通过 permutation + OOB 实现特征选择,这一操作常常是有效且实用的,所以在实践过程中如果遇到 non-linear 的特征选择问题,常常选择随机森林进行初步的特征选择。
举例说明
A Simple Data Set
左侧是第900颗决策树,实用 bootstrap 获取的,其中 \(N^{\prime} = N/2\)。右侧是使用900颗决策树的随机森林,可以看出决策树越多,边界越趋于平滑且类似(趋)于大间隔(边界位于正负样本之间)。
A Complicated Data Set
可以看出随着决策树个数增加,更容易处理非线性问题。
A Complicated and Noisy Data Set
可以看出随着树的增加,噪声随着投票可能会得到纠正(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)
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:机器学习技法 之 随机森林(Random Forest) - Python技术站