决策树模型组合之随机森林（Random Forest）

在机器学习中，随机森林由许多的决策树组成，因为这些决策树的形成采用了随机的方法，所以叫做随机森林。随机森林中的决策树之间是没有关联的，当测试数据进入随机森林时，其实就是让每一颗决策树进行分类看看这个样本应该属于哪一类，最后取所有决策树中分类结果最多的那类为最终的结果（每棵树的权重要考虑进来）。所有的树训练都是使用同样的参数，但是训练集是不同的，分类器的错误估计采用的是oob（out of bag）的办法。因此随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。随机森林可以既可以处理属性为离散值的量，如ID3算法，也可以处理属性为连续值的量，比如C4.5算法。另外，随机森林还可以用来进行无监督学习聚类和异常点检测。

随机森林的建立

基本就是两个步骤：随机采样与完全分裂。

（1）随机采样

首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。

对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个，这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本，同时使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。

对于列采样，从M个feature中，选择m个(m << M)，即：当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。

（2）完全分裂

对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。分裂的办法是：采用上面说的列采样的过程从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。

决策树形成过程中每个节点都要按完全分裂的方式来分裂，一直到不能够再分裂为止（如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。

我们用LearnUnprunedTree(X,Y)表示生成一棵未剪枝的决策树的过程，以下简写LUT (X,Y)：

随机森林的优点

总结如下：

（1）比较适合做多分类问题，训练和预测速度快，在数据集上表现良好；

（2）对训练数据的容错能力强，是一种有效地估计缺失数据的一种方法，当数据集中有大比例的数据缺失时仍然可以保持精度不变和能够有效地处理大的数据集；

（3）能够处理很高维度的数据，并且不用做特征选择，即：可以处理没有删减的成千上万的变量；

（4）能够在分类的过程中可以生成一个泛化误差的内部无偏估计；

（5）能够在训练过程中检测到特征之间的相互影响以及特征的重要性程度；

（6）不会出现过度拟合；

（7）实现简单并且容易实现并行化。

C/C++基本语法学习

STL

C++ primer