三个臭皮匠顶个诸葛亮的随机森林算法！

1. 随机森林的分组策略

为了保持在随机森林中每个决策树的差异性，选择在生成决策树的时候选择不同特征集在不同的数据集上进行训练，生成最终的决策树。因此，我们需要对数据集和特征集进行分组，在分组的过程中，分别对数据集的分组和对特征集的分组。

在分组的过程中，采用基于BootstrapingAggregation(Bagging)分组策略的改进方法。在Bagging分组策略的方法思路如下：

1. 首先对个数为n的样本集通过重采样（有放回的采样）进行分组，每组大小为n个，分成m组。这样相当于是m个大小为n的样本集。

2. 在所有属性上，分别对m个样本集进行分类模型训练。这样训练完成后就得到m个分类器。

3. 利用m个分类器对数据进行分类。根据m个分类器的投票结果决定数据最终归结为哪一类。

然而，随机森林为了更能体现出其随机性，在Bagging分组策略的基础上进行了一些改进：不仅对样本集进行分类，还对特征集进行分类。具体如下：

1. 首先对个数为n的样本集通过重采样（有放回的采样）进行分组，每组大小为n个，分成m组。这样相当于是m个大小为n的样本集。

2. 对属性进行分组，属性的个数为t，在所有属性上无放回的随机选取k个属性（k<t），重复m次，这样共选取m组，大小为k的特征集。

3. 在m组属性集和m组样本集中，利用一组属性集在一组样本集上训练得到一个决策树分类器。这样训练完成后就得到m个分类器。

4. 利用m个分类器对数据进行分类。根据m个分类器的投票结果决定数据最终归结为哪一类。

首先通过重采样对数据集进行分组，将数据集分为t组。如图1所示：

图1. 对数据集进行分组

在该分组过程中，输入是原始的数据集，输出为分好组的子数据集D_i，其中子数据集的长度是和原始数据集的长度相同，值得注意的是为了保持数据集大小的一致和数据的多样性，这里采用重采样，所以在每一个子数据集中，允许有重复的样本出现。

对数据集进行分组后，对特征集进行分组，如图2所示：

图2. 对特征集的分组

对特征集的分组，如上图所示，输入是原始全部特征集。通过采样得到t组F_i，在对特征集进行分组的时候，是通过直接采样进行的，所以每个子特征集中的特征不会重复。这里特征集的长度应比原始特征集的长度小，如果等于原始特征集的长度，则在子特征集中特征不重复的情况下，每个子特征都一样，缺少了子特征集的多样性，从而限制了随机森林中，决策树的多样性。

2.决策树的建立

决策树的建立，主要分两步：构建完全决策树和决策树剪枝。首先是通过一定的方法选择决策树节点，构建出一个未剪枝的决策树。然后，对该决策树进行剪枝来提高其分类的泛华能力。

随机森林中利用CART算法构建完全决策树，CART算法利用Gini指标进行分裂节点的选择。Gini指标度量数据划分或训练数据集D的不纯度，其中特征A的取值A_i的不纯度定义为；

其中表示取值A_i时样本的类别，j为该取值下的类别，则特征A的不纯度表示为：

其中i表示特征A所取的值，j表示所分的类别。

选择不纯度最小的属性作为节点，进行决策树的构建。

当决策树构建完全之后，由于数据中的噪声点和离群点。许多分枝反应的是训练数据集中的异常。剪枝方法是用来处理构建决策树后的这种过拟合的问题。通常的剪枝方法都是使用统计度量的方法，即剪去最不可靠的分枝。

剪枝一般分为两种方法：先剪枝和后剪枝:

先剪枝的方法是通过提前停止树的构造（比如决定在某个节点不再分裂）而对树剪枝，一旦停止，这个节点就编程树叶，该树叶可能取它持有的子集最频繁的类作为自己的类。先剪枝有很多方法，比如当决策树达到一定的高度就停止决策树的生长；或者到达此节点的实例个数小于某个阈值的时候也可以停止树的生长，不足之处是不能处理那些数据量比较小的特殊情况。先剪枝有个缺点就是视野效果问题，也就是说我们很难确定基于先剪枝生成的决策树是否是最优的决策树。

更常用的是第二种方法后剪枝。它由完全成长的树剪去子树而形成，通过删除节点的分枝并用树叶来替换它。树叶一般用子树中最频繁的类别来标记。这个方法称为基于误判的剪枝。这个思路很直接，因为完全决策树过拟合，所以通过一个测试数据集来纠正它。对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树，然后比较这两个决策树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，并且该子树里面没有包含另外一个具有类似特性的子树（所谓类似的特性，指的就是把子树替换成叶子节点后，其测试数据集误判率降低的特性），那么该子树就可以替换成叶子节点。该算法以bottom-up的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

在我们的随机森林算法构建决策树的时候，就是在在对数据集和特征集分组之后，将子特征集和子数据集分组进行训练分类模型：

在传统的随机森林算法中，决策树的建立是通过CART算法进行训练决策树模型。CART算法的基本原理是通过由测试变量和目标变量构成的训练数据集的循环分析，而构成的二叉树形式的决策树CART算法在最佳测试变量和分割阈值准则上采用经济学中的基尼系数Gini,Gini系数的定义上。通过CART的方法对每组G_i进行构建决策树。这样我们就可以构建t颗决策树。

3.投票机制

投票机制是指根据投票者的选择以选出最终结果的一种常用方法。其中主要分一下几种：

1. 一票否决制（一致表决）：一票否决制是指在投票的过程中，只有在大家都同意A结果的情况下，最终的结果才为A，任何一票不同意，则最后的结果均不为A。

2. 少数服从多数制：是指在投票的过程中，最终的结果是大多数人认可的结果，少数人须服从多数人的意愿。

3. 阈值表决制：在投票的时候，为每个类设置阈值，当投票结果达到某一类的阈值时，即选取该类为最终结果。

4. 加权投票制：即指在投票的过程中，某些人投票分量比较重，在GEP中，可以看做适应值高的个体投票份额较大。

5. 贝叶斯投票机制：简单的投票法假设每个分类器都是平等的，在实际生活中，我们听取一个人的意见，会考虑这个人过去的意见是否有用，从而加大或减少权值。也就是说贝叶斯投票机制是基于每个分类器在过去的分类表现设定一个权值，然后按照这个权值进行投票。

随机森林的决策树的传统方法通过使用CART的方法训练决策树，在根据t组数据和特征获得t棵决策树后，需要利用每一棵决策树对测试集进行决策出一个结果。这样就会对一个测试样本得到t个测试结果。最简单的，这里每颗决策树投一票，根据少数服从多数的原则，得到该测试样本的最终分类结果。如下图3：

图3 随机森林流程图

整个随机森林的流程图如上图所示。首先对数据集和特征集进行分组，然后对每一组数据集和特征集通过CART算法进行决策树的构建，对于一个测试样本，每一个决策树都会得出一个决策结果，最后根据少数服从多数的原则进行投票得出最终是分类结果。

免责声明：本文系网络转载。版权归原作者所有。如涉及版权，请联系删除！