【机器学习】集成学习(四)----随机森林

从前面的提升树，到 $GBDT$ ，再到 $RF$ ，我们可以发现在集成学习中，基分类器选择决策树往往能有很不错的效果，这是因为它们通常具有较低的偏差和较高的方差(分类误差小，但容易过拟合)，这样的特性使其在平均过程中更有利。这一篇我们就来了解一下随机森林这个算法的方法。
随机森林( $Random Forest$ )，是在以决策树为基分类器构建 $Bagging$ 集成的基础上进一步在 $cart$ 决策树的训练过程引入了随机属性选择。关于随机森林这一算法，书上对其的描述都比较少，因此去看了一些论文和文章。

【算法思想】

总的来看，其实就是用 $bootstrap$ 自助采样得到的 $T$ 个数据集，以分类决策树作为基分类器进行学习，得到 $T$ 棵分类决策树，用投票法的方式将它们结合起来变为森林(将测试样本输入，每棵决策树会给出相应的分类，森林的最终分类，选择这些分类中出现最多的类别作为输出)。
随机体现在哪？
那么，随机森林的“随机”是体现在哪呢？其实就是体现在，对自助采样得到的数据集学习分类器这一学习过程中。
回忆前面的决策树生成算法，我们通常会根据每个节点上的所有特征，选择最优划分特征来进行划分节点。而在随机森林的每棵决策树生成中，我们对最优划分特征的选取集合并不是每个节点上的所有特征，而是会通过对所有特征这一集合随机选取一个子集来作为我们的选取范围，然后再在这个子集集合内选择最优划分特征。

算法过程:

输入:原始训练数据集 $D$ ( $m$ 个样本)，特征集 $A$ (有 $K$ 个特征)，参数 $k$
输出:最终分类器(随机森林)

(1)对原始训练数据集 $D$ 采用 $bootstrap$ 方法，得到 $T$ 个样本集(每个样本集有 $m$ 个样本);
$\color{red}{由于自助采样只使用了原始训练数据集的约63.2\%的样本，剩下的36.8\%的未抽}$
$\color{red}{到样本可用于包外错误估计\text{(The out-of-bag(oob) error estimate)}}$
$\color{red}{因此在随机森林中，不需要交叉验证或单独的测试集来做错误估计}$

(2) $t=1,2,...,T$ ，对样本集 $t$ 进行学习，得到基分类器 $t$ (基决策树 $t$ );
$\color{red}{在学习基决策树t的过程中需注意以下两点:}$
$\color{red}{①对基决策树t的每个节点，先从该节点的所有特征集合中随机选择k个特征作为子集，}$
$\color{red}{然后再从这个子集中选择最优属性进行划分。}$
$\color{red}{②对基决策树t进行完全划分，即决策树的某一叶节点要么无法继续划分，要么里}$
$\color{red}{面的所有样本都是同一个分类}$

(3)用这 $T$ 棵基决策树(基分类器)组成随机森林(最终分类器)。
$\color{red}{用随机森林对新输入样本进行分类，选择类别出现最多的作为分类结果(用投票法}$
$\color{red}{作为结合策略，票数最多的为最终结果)}$

$\color{blue}{从上面的算法我们可以看出，随机森林中只有决策树的生成，并没有剪枝，回忆}$
$\color{blue}{决策树剪枝的意义，实际上是为了减小过拟合，由于随机森林生成决策树过程中}$
$\color{blue}{样本集随机，特征集也随机，因此很难出现过拟合现象，但是对于每一棵决策树}$
$\color{blue}{而言，它们的性能其实是很弱的，但通过结合策略集成为森林后，性能得到了很}$
$\color{blue}{大的提升，这可能就是所谓的集思广益、众志成城吧(笑)}$

算法中重要参数:

1.决策树的数量 $T$
树的数量越多，则过拟合越难出现，预测的效果会越好，但是这样会导致模型很大
2.每个节点上特征子集中的特征数 $k$
当 $k=1$ 时，则是随机选择一个特征用于划分，当 $k=$ 当前节点中所有特征值数量 $K'$ 时，则与传统的决策树无异。一般情况下，推荐 $k=log_2K'$

【算法优缺点】

优点：
1、在当前的很多数据集上表现都很不错，相对于其他算法有着很大的优势；
$\color{orange}{比如超参数数量不多，且这些超参数易理解}$
$\color{orange}{比如相较于Boosting系列的AdaBoost和GBDT来说，RF实现比较简单}$

2、训练速度很快，能够高度并行化；
$\color{orange}{Bagging算法的特点，即各个模型之间相互独立，因此对于RF而言同理，}$
$\color{orange}{训练时树与树之间是相互独立的}$

3、它可以估计出每个特征的重要性，并且检测到特征间的关系；
$\color{orange}{\text{---It gives estimates of what variables are important in the classification.}}$
$\color{orange}{\text{---Prototypes are computed that give information about the relation}}$
$\color{orange}{\text{between the variables and the classification.}}$

4、由于随机选择节点的特征子集，因此它能够高效的训练样本特征很多(高维度)的模型；

5、它有一个有效的方法来估计丢失的数据，并在大部分数据丢失时保持准确性；
$\color{orange}{\text{---It has an effective method for estimating missing data and maintains}}$
$\color{orange}{\text{accuracy when a large proportion of the data are missing.}}$

6、对于不平衡的数据集来说，它可以平衡误差；
$\color{orange}{\text{---It has methods for balancing error in class population unbalanced data}}$
$\color{orange}{\text{sets.}}$

7、模型的方差小，抗过拟合能力强，由于对泛化误差使用的是无偏估计模型，因此泛化能力强；

8、不仅可以做分类、回归问题，还可以推广到无标签数据，进而将功能扩展到无监督聚类，数据视图，异常点检测等。还有很多基于 $RF$ 的变种算法，如 $\text{extra trees}$ 、 $\text{Totally Random Trees Embedding}$ 、 $\text{Isolation Forest}$ ，应用相当广泛(这些算法的大概内容，可以去下面贴出的博客中看一看)。
$\color{orange}{\text{---The capabilities of the above can be extended to unlabeled data, }}$
$\color{orange}{\text{leading to unsupervised clustering, data views and outlier detection.}}$

缺点：
1、对于特征较少的样本(低维度)，分类效果可能并不理想；
2、在做回归问题时，它的效果并不如在分类问题上的效果，因为它不能给出一个连续的输出(即预测值不会超出训练数据集的范围)，现在已有证明表示，在某些噪音较大的数据集上，随机森林会出现过拟合现象。
3、和神经网络相同，随机森林也像一个黑盒子一般。我们难以控制与解释其模型内部的运行，只能通过改变参数和随机种子来不断调试。

【总结】

从上述的特点来看，我们可以发现，随机森林对高维数据，不平衡数据，缺失数据有着很好地训练效果。
对于随机森林的学习暂且没有深入下去了，集成学习也准备告一段落，后面要准备开始进行实践和提升代码能力了。有时间会补充学习EM算法、隐马尔科夫和条件随机场，然后再看看K均值和数据挖掘中其他一些聚类算法。

参考文献:
1.《机器学习》　　周志华
2.随机森林　　 Leo Breiman 、Adele Cutler
https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#ooberr
3.Bagging与随机森林算法原理小结　　刘建平Pinard
https://www.cnblogs.com/pinard/p/6156009.html