机器学习笔记-Random Forest

一种可行的方法如下：针对每一个样本，我们看看在什么时候这个样本可以用做$validation$的资料。例如对于表一中的最后一个样本$(x_N, y_N)$，这个样本可以当成$g_3$的$validation$的资料，也可以当成是可以当成$g_T$的$validation$的资料，因为$(x_N, y_N)$并没有参与其中任意一个$g$的构建，所以$(x_N, y_N)$可以当成是某个 $G^-_N$ 的$validation$的资料，其中的$G^-_N$可以是$bagging(g_3, g_T)$， 这样我们就可以看看 $G^-_N$ 在 $(x_N, y_N)$ 上的表现如何（将$x_N$带入到$G^-$中看结果和$y_n$的差距）。那么对于每一个样本，我们都可以得到一个$G^-_n$（其中$n\in[1, N]$）来看看其在$(x_n, y_n)$上的表现如何。这就很像我们以前做$validation$的时候提到的$leave\ one\ out\ cross\ validation$：把每一笔资料都当做$validation\ set$，来计算模型的表现如何最后做平均。所以通过这样的方法我们可以定义很多$G^-$来大概的知道最终的$G$的表现如何。

利用$OOB$来验证$G$的表现：对于每一笔资料$(x_n, y_n)$构建一个$G^-$，并计算$G^-$在该资料上的表现，最后对所有的资料做平均，计算公式如下：

所以$bagging$或者是$random\ forest$算法就有这样的优势：在得到了一个$G$之后，我们就能计算出该$G$好或者是不好。因为其中的$bootstrap$的过程使得这些算法可以做$self\ validation$。这样就可以来对$Bagging$或者是$Random\ Forest$中的参数进行调优。

以前为了做模型的选择需要将资料划分为$train\ set\ \mathcal{D_{train}}$和$validation\ set\ \mathcal{D_{val}}$，首先在$\mathcal{D_{train}}$上做训练，然后在$\mathcal{D_{val}}$上验证算法的好坏，通过不断的选择得到了好的模型之后还需要在$\mathcal{D}$上再进行一次模型的训练得到最终的结果。
现在有了$OOB$之后，不需要进行数据集的划分，将所有的资料$\mathcal{D}$都用于模型的训练，然后使用$E_{OOB}$来进行模型的评估。

$OOB$的错误在实际应用中对于衡量$G$的表现来说通常相当的准确。

3 - Feature Selection

上一小节讲述了$OOB$可以用来衡量$random\ forest$的表现。这一节我们看看这样的方法还可以用在什么地方。我们这一小节关注一个新的问题：$Feature\ Selection$。 $Feature\ Selection$指的是当数据的维度很高的时候，我们可能想要把一些冗余的或者没有用的特征移除掉，也可以认为是我们想要学到一个从高维度到低纬度的转换， 通过这样的方式来选择好的特征或者是输入。 $Feature\ Selection$的好处有：会使得不管是训练还是测试都更加的有效和简单；删除掉的维度可能是一些噪声， 这样能避免$overfitting$的发生。

$Decision\ tree$中需要选择好的特征来构建子树（或者说选择好的特征做分支条件$branch\ criteria$），所以在这个模型中有自己的$feature\ selection$。在$adaboost\ decision\ stump$中也有做$feature\ selection$的过程。

我们做$Feature\ Selection$的主要思路是：不考虑特征的交互关系，利用某种方法给每一个$feature$打一个分数来表示该$feature$的重要性。这样排序之后取$Top\ N$得到的就是$N$个比较重要的$feature$。

3.1 - 线性模型中的特征选择

这样的想法在线性模型中特别容易实现，因为在最终的线性模型中我们使用每一个特征和该特征的权重$w$的乘积然后求和作为最后的得分，之后再将该分数应用到不同的问题当中，例如$regression$或者是$classifiction$。所以当特征$x$彼此之间取值的范围差不多，并且$w$还不错的话，$w$的大小就是我们想要特征$feature$的重要性，所以使用$w$的大小当做$feature$的重要性，经过排序取$top\ N$就能达到特征选择的效果。所以当做完一个$linear\ model$之后，从模型返回的$w$中就可以得出每一个特征的重要性，就可以完成一次特征选择。在特征选择之后，再决定是不是要利用这些特征做第二阶段或者是第三阶段的线性的或者非线性的学习。

3.2 - 非线性模型中的特征选择

在非线性的模型中， 做特征选择通常就要困难很多，因为在非线性的模型中，特征之间的关系是交杂在一起的，所以很难厘清单独一个特征的重要性。$Random\ forest$虽然是一个非线性的模型，但是由于其中的一些机制，所以让这个模型做特征选择相对来说比较简单一些（这就是为什么$feature\ selection$这个课题会选择在这里讲的原因，因为是利用$random\ forest$的机制在做）。怎么做呢？基本的方法叫做$random\ test$，该方法的思路是如果某一个特征比较重要，那么当这个特征中被掺入了一些噪声的时候，学习算法的表现一定会变差。所以通过比较学习的结果在原来的特征下的表现和该特征掺杂噪声下的表现的差距，就能判断这个特征的重要性。

那么掺杂一些什么样子的特征呢？如果加一些常见的高斯分布的噪声，那么可能会影响到这个特征上原来取值的分布。所以这可能不是一个很好的选择。借鉴一下$bootstrap$，因为是在原始的资料中进行抽样，所以这样得到的结果在一定的程度上维持了原始的资料的分布和特点。这里我们采用另一种比较类似的机制：$permutation$，具体的做法是对所有样本在该特征下的取值做随机的置换。这样就产生了噪声，并且保证了该特征的分布不会改变。这样的做法在统计上称为$permutation\ test$。 所以衡量第 $i$ 个维度的特征的重要性的公式如下：

原始的$random\ forest$的作者建议可以使用$permutation\ test$来计算每一个维度的重要性。这样就可以拿来做特征的选择了。

根据$(1)$式，为了确定特征 $i$ 的表现，看起来我们需要计算$performance(\mathcal{D^{(p)}})$，那么通常的做法是需要在数据$\mathcal{D^{(p)}}$上重新训练模型，使用$validation$来验证表现。但是因为我们使用的是$random\ forest$，可能不需要$validation$，而使用$E_{oob}$来代替就好了。那么$(1)$式可以改为：

其中$G$是从$\mathcal{D}$得到的模型，$G^{(p)}$是从$\mathcal{D^{(p)}}$得到的模型。$G^{(p)}$依然需要经过重新的训练， 我们希望得到一个投机取巧的近似方式，省去再训练一个模型$G^{(p)}$的时间。我们的做法是将$E_{oob}(G^{(p)})$ 写成 $E^{(p)}_{oob}(G)$ ， 如果是这样的话， 就不需要再训练一个模型，而是仍然使用模型$G$， 只是在利用$OOB$的资料做$validation$的时候做手脚， 即在验证的时候做$permutation$，而不是在训练的时候做$permutation$。

具体的做法是：
假设我们现在感兴趣的是第 $i$ 个特征的重要性，在使用$OOB$的资料$(x_n, y_n)$做$leave\ one\ out\ validation$的时候，所有未使用该笔数据的$g_t$构成$G^-$，之前在计算$E_{OOB}$的时候直接计算$G^-$在$(x_n, y_n)$上的表现即可，即先计算每一个$g_t$在$(x_n, y_n)$上的得分，最后集成。但是现在有所不同， 在计算每一个$g_t$的时候，必然会用到第 $x_{n, i}$，这个时候就是我们可以做手脚的时候：针对$(x_n, y_n)$的输入中的第$i$个特征 $x_{n,i}$ 做 $permutation$，并且算法的作者要求使用对于$G^-$来说是$OOB$的资料来进行随机的替换。对所有的样本重复以上的工作，最后将$E_{oob}$平均就得到了在对特征 $i$ 做了$permutation$之后算法的表现。
使用这个的机制就可以得到每一个特征的重要性，之后就可以做特征的选择。这个方法的核心工具是：

1. 利用$OOB$的资料来做$validation$。
2. $permutation\ test$机制。

在实际的应用当中，$random\ forest$的特征选择非常好用，很多人在面临非线性的问题的时候，会先使用$random\ forest$来做一些初步的特征选择。

表一

4 - Random Forest算法的表现

4.1 - 资料1

一个简单的数据资料
这一小节看一下$random\ forest$算法的表现，同样针对二元分类的问题。

上图中左图是使用$CART+random\ combination$的结果；中图是使用$bootstrap$机制选择了$N'( = N/2)$个样本训练的$Decision\ Tree$决策树，使用的方法是$CART+random\ combination$，因为只是使用了原始数据的一半，所有存在一些划分错误的点；右图是使用一棵决策树组成的$random\ forest$，所以和中图得到的结果是一样的。
接下来我们想要观察的是，当树的个数增多的时候，$random\ forest$的表现，也就是右图的表现。

中图是使用$bootstrap$机制选择了$N'( = N/2)$个样本训练的$Decision\ Tree$决策树（第200棵）。右图表现的是综合200棵树的表现。

中图是使用$bootstrap$机制选择了$N'( = N/2)$个样本训练的$Decision\ Tree$决策树（第300棵）。右图表现的是综合300棵树的表现。

中图是使用$bootstrap$机制选择了$N'( = N/2)$个样本训练的$Decision\ Tree$决策树（第800棵）。右图表现的是综合800棵树的表现。

这时我们观察到由$CART+random\ combination$算法在$bagging$中的$bootstrap$机制得到的不同的训练样本上得到的$800$棵$Decision\ Tree$组成的$random\ forest$算法得到的边界（右图）大概会通过$\bigcirc$和$\times$的中间， 而只有一棵树的时候，通常是不会有这样的效果的（左图） 。通过$\bigcirc$和$\times$的中间正是我们在$SVM$中讲过的$large\ margin$。 另外使用$random\ forest$得到的边界要比单一的一棵树$CART$得到的边界要平滑的多。 所以$random\ forest$这样利用了很多棵树之后做出了平滑并且具有$large\ margin$性质的边界。

4.2 - 资料2

稍微复杂一点的资料。

左图是使用$bootstrapping\ N'( = N/2)$得到的边界；右图是使用这一棵树得到的$random\ forest$。

左图是使用$bootstrapping(N' = N/2)$得到的边界（在第21轮中）；右图是使用这21棵树得到的$random\ forest$的结果。这样的非线性边界比起左图中的边界要鲁棒很多，具有比较平滑比较稳定的特性。

4.3 - 资料3

资料2+10%噪声

左图是使用$bootstrapping\ N'( = N/2)$得到的边界；右图是使用这一棵树得到的$random\ forest$。可以看到在图中决策树给出的边界中有一部分在努力的去过拟合那些噪声。

左图还是一棵决策树的表现，右图是使用21棵树构成的$random\ forest$，可以看出边界已经很平滑，虽然还有少数的边界在拟合噪声。但是通过$random forest$这种投票的机制，已经可以避免很多由噪声产生的影响。$(noise\ corrected\ by\ voting)$

因为$random\ forest$的理论假设是当使用无限多棵树的时候，会得到比较好的结果，所以一般来说我们会使用尽量多的树。

小测试

下面的哪一个不是$random\ forest$的正确用法

1. 使用$bootstrapped$数据来训练每一棵树
2. 使用$E_{OOB}$来验证$random\ forest$的表现
3. 使用$permutation\ test$来进行$feature\ selection$
4. 固定树的数量

显然答案应该是4，树的数量要视具体的问题来决定。

5 - 总结

这篇介绍了$Random\ Forest$算法。这个算法的本质是将$bagging$算法中的$base\ algorithm$使用$decision\ tree$。通常我们会把$decision\ tree$的过程利用$randomly\ projected$添加一点随机性，也就是用通过随机结合的各式各样的$feature$来做切分的决策。同时在这个算法中由于使用了$bootstrap$的机制，所以我们可以得到一些$OOB$的数据来验证算法表现的好坏，而不必使用使用$validation\ data$来做$validation$。也就是这个算法可以$self\ validation$。 另外这个自我验证的方式可以配合$permutation\ test$可以来做$feature\ selection$。最后我们说到当树的数量够多的时候，我们可以得到相对平滑的边界。
$Random\ forest$是$bagging$和$decision\ tree$的结合。下一篇我们介绍的$boosted\ decision\ tree$是$AdaBoost$和$decision\ tree$的结合。