机器学习技法-lecture10：Random Forest

Random Forest

回顾

通过lecture9的学习，我们建立了决策树模型，其中我们主要介绍了CART树模型，本节课我们在此基础上学习随机森林。

Random Forest Algorithm

首先我们回顾下Bagging和决策树:Bagging就是通过bootstrap的方式产生多个数据集然后通过某个基本的演算法产生g，最后通过投票或者平均的方式将g组合起来得到G，由此可以发现Bagging的一个明显的特点即通过投票或取均值的动作能降低方差；决策树是通过递归式地生成子树或树叶，然后结合切割的条件形成最后的G，可以发现决策树的一个明显的特征是切割过程导致的较大的方差，这点在fully-grown tree中表现得尤为明显。

由于两者的特点互补，于是我们思考能不能将两者结合起来，结合的过程有点aggregation of aggregation的味道。

在结合两者的思路的指导下我们得到了random forest，字面上理解random主要指的是bagging过程中数据集的随机性，forest指的是决策树算法得到的fully-grown tree的组合。

于是我们可以总结下这个演算法的流程：1、资料集D通过bootstrap过程产生多个资料集，2、使用资料集建立多棵fully-grown tree，3、最后做投票得到G。

我们可以总结得到随机森林的优点如下：1、随机森林是一个高效的model；2、随机森林继承了CART树在处理缺失特征、类别型数据和多类别分类等方面的优点；3、随机森林降低了CART树过拟合的缺点。

上面我们介绍了基本的random forest，接着我们进一步看看我们还能在基础版上做什么不一样的事情。我们思考建模过程中得到不同的g的过程，目前主要的方式是bagging方法的bootstrap过程通过抽取不同的资料集进而产生不同的g，另一个能产生不同的g的方式是从特征的角度进行抽样。实际的过程就是从已有的特征中选取部分特征，从而也能产生不一样的g，数学上的解释就是将特征空间映射到一个更低维的空间即使用的是原始空间的一个子空间。通常我们会使用比原始特征少得多的维数，这样能使模型更加有效率。

这样我们得到了延伸版的随机森林，在基础版上我们考虑在CART过程中加入一个random-subspace的动作，一方面可以增加randomness，另一方面可以使CART更加不一样。

实际上作者实际做的事情还有些不一样，作者在做这些投影时并不是简单地投影到原始的特征上，而是投影到某些特征合并之后的反向，这样的投影能使后面的model更加有能力，这样的操作能使整个过程都充满了randomness。

Out-Of-Bag Estimate

我们知道bagging(bootstrap aggregation)是随机森林的一个关键步骤，接下来我们看看其中还有什么关键的信息。我们可以使用表格将bagging过程表示出来，其中蓝色标识的资料为被选到的数据，红色*标识的资料为为被选到的数据，我们将后者称为OOB(out-of-bag example）。

接下来我们思考的问题是有多少资料没有被抽取到，我们看相对简单的情形即bootstrap次数N’=资料数量N的情形，我们容易得到某一笔资料在N次抽样过程中均没有被抽到的概率，然后容易证明当N很大时这个概率趋于某个常数1/e。

然后我们思考OOB的作用，我们可以先回顾一下之前学习的validation的过程，其中资料集被我们分成训练集和验证集，训练集用来学习得到g-,然后在验证集上测试看效果，类比可以发现OOB有点类似验证集的角色，我们也可以使用它来验证g,但在aggregation模型中我们的目的是G，所以我们往往使用OOB来验G而非g。具体的实现逻辑主要是确保用来验证的资料没有被污染，即我们用来验证的资料和待验证的G是相互独立的，所以我们需要做的是定义好G-，然后使用OOB的资料验证看效果最后将整体的表现做一个平均，这样得到OOB error。

也就是说bagging/RF验算法，我们一旦得到一个G，由于它内部的bootstrap过程，很轻易就能做self-validation，从而能看G的表现如何。

结合前面的讨论，我们知道RF的验证过程相对而言会简单一些，首先我们没必要将资料切割成训练集和验证集，此外也没必要做re-training的过程，我们使用OOB error来选择最后的G，实践中是很准确的。

Feature Selection

实际生活中我们获取的资料集的维度可能比较高，其中有很多维度的信息可能是冗余的，此外过多的特征也会加大后续的处理和计算成本，因此接下来我们要讨论的问题是feature selection即从多个特征中选取较少的有效的特征，容易总结得到特征选择的优缺点如下：

从决策树的处理步骤中可以发现它是一个内部进行了特征选择的演算法，接下来我们思考的问题是如何有效地从多个特征中选取有限的特征，

做特征选择的一个大思路就是按特征的重要性进行选择！于是问题就转化为特征的重要性的度量问题，我们首先看linear model，很自然地对应一下可以使用w的绝对值作为度量，于是可以选取前n个w的绝对值较大的特征达到feature selection的目的；但是对于非线性模型，由于特征之间存在交叉关系，所以这个问题相对而言会复杂很多，接下来我们会给出RF这个非线性模型上的特征重要性的度量方式。

主要的思想是random test:如果某个特征很重要，那么在该特征处加入杂讯之后的模型的表现应该会变糟糕。加入杂讯一般可以通过加入一些杂讯的分布，这种方式会改变数据集的分布，于是我们参考bootstrap的思路使用permutation方法即在某个特征上使用类似洗牌的方式打乱该特征数据的顺序，最后计算两者的表现的差值来定义该特征的重要性。

然后我们进一步深入分析，两个performance可以使用OOB error来代替，此外我们将permutation过程放在验证资料的过程而非训练的过程，用于验证的资料也是从OOB的资料中选取而非所有资料集，这样的衡量会比较准确。

总结来说，RF的特征选择主要通过permutation过程和OOB验证，实践上RF的特征选择的效果是很好的。

Random Forest in Action

接下来我们看看RF的实践表现，首先看相对简单的资料集上的表现，左图为单一的CART树做random combination的结果，中间的图为加入一定的bootstrap后的bagging的结果，右图为RF的结果，我们加大树的数量可以观察其表现，可以发现最后多棵树的RF的分类边界是越来越光滑的，并且有做出类似hard-margin的结果。

然后可以看RF在复杂数据集上的表现，可以发现其边界更加光滑且是更具鲁棒性的非线性模型。

最后我们可以在复杂的资料集上加入一定的杂讯，通过增加数的数量，容易发现RF有一定的通过投票消除了一定的杂讯的能能力。

小结

本节课我们主要学习了random forest，首先我们建立了基础的RF演算法，然后介绍了关键的OOB步骤，接着结合RF介绍了feature selection的内容，最后介绍了RF的实践效果。