机器学习技法笔记 – Random Forest(随机森林)

Random Forest Algorithm

一言概之,随机森林即Bagging与Decision Tree的Aggregation:

其中,Bagging是指通过bootstrap的方式从数据集\(D\)中,随机抽选\(N\)组数据,重复\(T\)次,每次得到的数据集称之为\(\widetilde{D}_t\),然后通过C&RT等方法在\(\widetilde{D}_t\)上生成决策树,得到\(g_t\),最后通过Blending的方式对\(g_t\)线性组合,得到最后的\(G(x)=Uniform(g_t)\):

这里简要的回顾一下决策树与C&RT算法:

即在原始数据集\(D\)上通过Decision Stump训练出不纯度最低的\(b(x)\),再将数据集一分为二,然后将一分为二的数据集视为原始数据集,递归的训练重复上述步骤,直到不纯度为\(0\)或者数据集不可再分,最后进行剪枝。

值得注意的是,在Random Forest中,训练每一个决策树\(g_t(x)\)的过程是可以并行化的,因为每一个Bagging与Bootstrap操作与C&RT算法的执行互相独立。

Random Forest中对于每一颗由C&RT生成决策树来说,由于Bagging而从数据集的差异性上获得了\(g_t\)的差异性。

但是在实际应用中,Random Forest通常还会使用被称之为Feature Projection或者Feature Expansion的方法强化训练数据集的差异性,从而使得训练出的\(g_t\)经过Blending后表现更好。

所谓Feature Projection,即在\(n\)维数据集\(D\)中每次并非选取\(n\)维的数据,而是选取更低维度的数据,这种选取方式等效于对\(d’\)维向量\(x\)乘以一个对角线上部分为latex 0$的单位对角矩阵:

通过Feature Projection得到的Random Forest可以由以下形式概括:

而所谓Feature Expansion,是在经过Feature Projection操作后得到的\(d’\)维数据集\(\widetilde{D}\)的\(x\)向量的某一或多个维度上再乘以矩阵\(x\),得到一些具有新特征的向量:

通过FeatureExpansion得到的Random Forest可以由以下形式概括:

Out-Of-Bag Estimate

回顾Random Forest的Bagging过程,对于每一颗训练出的决策树\(g_t\),与数据集\(D\)有如下关系:

对于星号的部分,即是没有选择到的数据,称之为Out-of-bag(OOB)数据,当数据足够多,对于任意一组数据\((x_n, y_n)\)是OOB的概率为:

对于这些OOB数据,可以用来验证Random Forest最后的\(G(x)\):

当用于验证\(G(x)\),其Cost Function具有以下形式:对于Random Forest,通常使用上式评价其表现。

Feature Selection

对于一个\(N\)维向量\(x\),即\(x\)向量具有\(N\)个特征,但是并不是每一个维度的特征都和最终的\(G(x)\)是相关的。

这一点非常重要,特征提取是一个重要话题,当原始数据集\(D\)的维度非常大时,在使用某种机器学习算法前,特征提取是必要的,这样可以很大程度减少后续训练的时间与空间复杂度。

在Random Forest中,我们使用一种被称之为Permutation Test的方法来做Feature Selection,它具有以下形式:

其中,\(performance(D)\)是Random Forest在原始数据集\(D\)上的表现,而\(performance(D^{(p)})\)是将原始数据集\(D\)上的第\(x_i\)维度与\(x_j\)调换位置后得到的\(D^{(p)}\)上的表现,所以\(importance(i)\)即描述了\(x_i\)的重要程度,更进一步的,所谓\(performance(D)\)即\(E_{oob}(D)\):

上式也说明了我们使用OOB数据做Permutation Test。

Random Forest in Action

下图是21颗决策树组成的随机森林在二位数据上的表现:

以上是对Random Forest在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Gradient Boosted Decision Tree。