林轩田机器学习技法第十讲-Random Forest

上一讲学习了决策树算法，这一讲来学习讲bagging和Decision Tree结合起来的一种集成算法：随机森林(Random Forest)

在这里插入图片描述
Bagging是使用booststrap从现有的数据集D中产生多个不同的新数据集D’，然后在这些数据集上运行基演算法得到相应的gt，最后将所有的gt采用投票（类别型）或是取平均值（数值型）的方式集成为最后的模型G。

Decision Tree是根据分割的条件，递归的将数据集进行划分，最后形成一棵完全生长的树的结构，它主要由分支条件b(x)和分支子树Gc(x)组成。
在这里插入图片描述

我们知道Bagging是一种减小方差的集成方法，而决策树在分割时要求分割节点的数据越纯越好，这就相当于增大了方差。那么将其结合起来，即使用Bagging的方式把众多的Decision Tree进行uniform结合起来。这种算法就叫做随机森林（Random Forest），它将完全长成的C&RT决策树通过bagging的形式结合起来，最终得到一个庞大的决策模型。

两者结合的随机森林的算法思想如下所示
在这里插入图片描述
它有如下的优点：
• 可以采用并行训练的方法，效率高
• 继承了C&RT的优点
• 缓和了C&RT可能会过拟合的缺点

在这里插入图片描述
因为是集成算法，我们希望森林中的决策树的机构更加具有多样性，所以具体可以怎么做呢？在理论上我们增强学习器多样性的方法是引入随机性，常见的做法有如下的几种：
1. 数据样本扰动
通过从初始数据集中产生不同的子集，利用不同的数据子集来训练不同的个体学习器，这种做法对于不稳定的学习器，例如决策树、神经网络等效果较好，但是对于KNN、线性学习器等的稳定学习器的效果不明显
2. 输入属性扰动
从初始的属性集中抽取不同的子集，在不同的子集上训练基学习器，比如著名的随机子空间(Random subspace)算法。这样的做法类似与一种从高维的属性空间到低维的属性空间的转换
3. 输出表示扰动
对于训练样本的类标记稍作变动，如翻转法、输出调制法等
4. 算法参数扰动
通过随机设置不同的参数，往往可以得到差别较大的个体学习器

具体到随机森林中，可以通过booststrap抽取不同的数据子集来训练得到不同的gt，或是从属性集中随机的抽取一部分属性用来训练，比如生成决策树的数据集含有100个属性，我们可以每次训练时随机抽取30个，这样每一次训练就可以得到不同的决策树。

Random Forest算法的作者建议在构建C&RT每个分支b(x)的时候，都可以重新选择子特征来训练，从而得到更具有多样性的决策树。
在这里插入图片描述

除了随机抽取特征，还可以将现有的特征x通过p进行线性组合，来保持多样性。这种方法使每次分支得到的不再是单一的子特征集合，而是子特征的线性组合（权重不为1）。好比在二维平面上不止得到水平线和垂直线，也能得到各种斜线。这种做法使子特征选择更加多样性。值得注意的是，不同分支i下的pi是不同的，而且向量pi中大部分元素为零，因为我们选择的只是一部分特征，这是一种低维映射
在这里插入图片描述
在Bagging中我们需要使用BoostStrap来产生不同的新的数据集，在新的数据集中只包含初始数据集总的一部分数据，如右下图所示，Di’表示在新的数据集中存在的数据，而红色五角星表示没有被抽到的数据，这里将其称之为out-of-bag(OOB) example
在这里插入图片描述

那么每一次抽取有多少数据不会被抽到呢？使用简答的概率知识我们就可以得到大概有36.8%的数据不会被抽到
在这里插入图片描述

这种做法很像之前的Validation，拿出一部分数据训练，一部分用来验证。通过两个表格的比较，我们发现OOB样本类似于Dval，那么是否能使用OOB样本来验证的好坏呢？可以但是没有必要，因为在bagging中我们关心的是最后的集成模型G的效果，中间的gt即使效果差一点也没有关系。那么如何使用OOB来验证G的好坏？先看每一个样本(xn,yn)是哪些gt的OOB资料，然后计算其在这些gt上的表现，最后将所有样本的表现求平均即可。例如下图红框所示，(xn,yn)样本是g1,g3,gT的OOB，则可以计算在GN(x)上的表现.

这种做法类似于之前Validation中的Leave-One-Out Cross Validation，每次只对一个样本进行g-的验证。只不过这里选择的是每个样本是哪些gt的OOB，然后再分别进行Gn-(x)的验证。每个样本都当成验证资料一次（与留一法相同），最后计算所有样本的平均表现，如下图蓝框所示。

Eoob(G)估算的就是G的表现好坏，把Eoob称为bagging或者Random Forest的selfvalidation
在这里插入图片描述

在之前使用Eval作为误差衡量的算法中，我们需要选择Eval最小的h，然后再在D上训练的到最后的g。而上面的这种做法不需要这样的重复训练，selfvalidation在调整随机森林算法相关系数并得到最小的Eoob之后，就完成了整个模型的建立，无需重新训练模型，表现上通常相当准确
在这里插入图片描述

如果样本中的冗余太多或是不相关的特征太多，我们就需要舍弃掉一部分，完成属性空间的降维转换
在这里插入图片描述
这种特征选择的优点是：
• 通过减少特征的数量，提高效率
• 较少了有噪声的属性，提高了泛化能力
• 可解释性强
缺点是：
• 筛选特征的计算量较大
• 不同特征组合，也容易发生过拟合
• 可能选到无关特征，导致解释性差
在这里插入图片描述
那么如何进行特征的筛选呢？一种做法是对于每一个特征赋予一个重要性，将其排序后按照重要性的大小进行选择

在这里插入图片描述
上面的做法在线性模型中易使用，因为非线性模型中不同的特征是相互交叉的，很难说哪个更重要。其中|Wi|表示了特征Xi在整个特征空间中的重要性，值越大越重要，反之越不重要。我们可以使用已有的数据来学习到一系列的Wi

在这里插入图片描述
RF中，特征选择的核心思想是random test，即对于某个特征，如果用另外一个随机值替代它之后的表现比之前更差，则表明该特征比较重要，所占的权重应该较大，不能用一个随机值替代反之说明不是很重要。所以通过比较某特征被随机值替代前后的表现，就能推断出该特征的权重和重要性。

那么random test中的随机值如何选择呢？通常有如下的两种方法：
• 使用uniform、gaussian等抽取随机值替换原特征
• 通过permutation的方式将原来的所有N个样本的第i个特征值重新打乱分布（相当于重新洗牌）

比较而言，第二种方法更加科学，它保证了特征替代值与原特征的分布是近似的。这种方法叫做permutation test（随机排序测试），即在计算第i个特征的重要性的时候，将N个样本的第i个特征重新洗牌，然后比较D和D§表现的差异性。如果差异很大，则表明第i个特征是重要的。

在这里插入图片描述

那么如何衡量performance？简单的我们可以使用Eoob来衡量，但是对于N个样本的第i个特征值重新洗牌重置的D§，要对它进行重新训练，而且每个特征都要重复训练，然后再与原D的表现进行比较，过程非常繁琐。

为了简化运算，RF的作者提出了一种方法，就是把permutation的操作从原来的training上移到了OOB validation上去，使用如下红框所示的方法，在训练的时候仍然使用D，但是在OOB验证的时候，将所有的OOB样本的第i个特征重新洗牌，验证G的表现
在这里插入图片描述

下面看一下随机森林在使用中的表现，左下图是一个C&RT树没有使用bootstrap得到的模型分类效果，其中不同特征之间进行了随机组合，所以有斜线作为分类线；中间是由bootstrap（N’=N/2）后生成的一棵决策树组成的随机森林，图中加粗的点表示被bootstrap选中的点；右边是将一棵决策树进行bagging后的分类模型，效果与中间图是一样的，都是一棵树。可以看出，树的数量越多，分类边界就会越光滑
在这里插入图片描述