【机器学习】随机森林

本文介绍了结合集成学习思想的随机森林算法。首先介绍了集成学习中两种经典的集成思想Bagging和Boosting。然后介绍了Bagging的两个关键点：1）样本有放回随机采样，2）特征随机选择。最后介绍了Bagging的代表学习算法随机森林，从方差和偏差的角度分析了Bagging为什么能集成以及随机森林为什么能防止过拟合。

作者 | 文杰

编辑 | yuquanle

集成学习

集成学习通过构建多个学习器采用加权的方式来完成学习任务，类似于”三个臭皮匠顶个诸葛亮”的思想。当然多个学习器之间需要满足一定的条件，一般来讲，多个学习器同属于一种模型，比如决策树，线性模型，而不会交叉用多种模型。

为了保证集成学习的有效性，多个弱分类器之间应该满足两个条件：

1. 准确性：个体学习器要有一定的准确性，这样才能有好的效果。
2. 多样性：学习器之间要有一些差异，因为完全相同的几个学习器集成起来后几乎不会有提升。

目前，集成学习主要分为Bagging和Boosting两种方式，前者通过Booststrap Aggregation的重采样得到多组训练集，并行的训练基学习器。而后者是一种提升的思想，基学习器是串行执行的，下一个学习器会基于上一个学习的经验进行调整，学习器前后有依赖关系，多个学习器最终组合得到强学习器。

随机森林

随机森林是集成学习中Bagging方式的代表，其相对于决策树而已，有一个很重要的优点：防止过拟合。

随机森林主要通过以下两点来防止过拟合，这与深度学习中的Dropout（随机的丢失一些样本和特征）技术非常相似：

1. 样本选择随机：Bootstrap Sampling
2. 特征选择随机：基学习器决策树的特征选择

Bootstrap Sampling

Bootstrap Sampling是一种统计学上的抽样方法，该方法是这样执行的：对于有个样本的数据集，进行次有放回采样得到数据集 ，这样与的大小一致。有放回采样使得中有的样本重复出现，有的样本则没有出现，简单估计一下，某个样本在次采样中始终没被采到的概率为，取极限：

即中的样本大概有%几率出现在中，采样出个Bootstrap 样本集 ，对这个样本集分别训练一个基学习器 ，结合这些基学习器共同作出决策。

决策时，在分类任务中通常采用投票法，若两个类别票数一样，最简单的做法是随机选择一个；而回归任务则一般使用平均法。整个流程如下所示：

基学习器

早期的Bagging方法是每个基学习器都是一个决策树，完全按照决策树的规则建树。

随机森林则在Bagging的基础继续采用特征随机，每个基学习器只对在个特征构成的子集下进行建树，一般取。这样构建的决策树相对于完整的决策树是一个“浅决策树”，这样就构成了特征的随机性。

随机森林过程

1. 假设我们设定训练集中的样本个数为，然后通过Bootstrap Sampling来获得个有重复的样本集；
2. 针对每个样本集独立训练，对于有个特征的数据集，随机选择(k<d)个特征构成特征选择集。然后在样本集，特征集上构建决策树。值是保持不变的， 随机选取特征增加树的独立性，每棵决策树都最大可能地进行生长而不进行剪枝；
3. 通过对所有的决策树进行加权来预测新的数据（在分类时采用多数投票，在回归时采用平均）。

到此，随机森林基本介绍完，但是依然存在问题，随机森林为什么能防止过拟合，随机森林适合什么样的场景？

Bias and Variance

从Bias和Variance的角度分析，Bagging对样本的重采样得到个训练集，对于每个训练集训练一个基学习器，因为基学习器相同，因此各个学习器有近似的Bais和Variance（学习器并不一定独立）。

假设每个学习器的权重相同即。每个学习器的损失用表示，那么随机森林的损失可表示为：

所以Bagging后的Bias和单个基学习器的接近，并不能显著降低bias。若各基学习器独立，因为每个学习器的权重是，所以引入的方差为，那么随机森林的Variance可表示为：

可以看出，Bagging通过降低Variance来防止过拟合，严格来说每个学习器之间不严格独立，所以Variance的降低会小于B倍。

随机森林优缺点

优点：

1. 正如上文所述，随机森林在解决分类与回归两种类型的问题有很大的优势；
2. 随机森林抗过拟合能力比较强；
3. 随机森林能处理很高维度的数据（也就是很多特征的数据），并且不用做特征选择，因为建树时会随机选择一些特征作为待选特征子集 ；
4. 训练速度快，容易做成并行化方法(训练时，树与树之间是相互独立的) ；
5. 随机森林可以做类似于GBDT那样的特征组合；
6. 在对缺失数据进行估计时，由于随机丢失特征，随机森林依然十分有效；
7. 当存在分类不平衡的情况时，随机森林能够提供平衡数据集误差的有效方法，比如对于 10:1 的数据，将多数数据分为 10份，做 10个 1:1 的单模型然后 Bagging 起来即可。

缺点：

1. 随机森林在解决回归问题时，并没有像它在分类中表现的那么好。因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够做出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过度拟合。（PS：随机森林已经被证明在某些噪音较大的分类或者回归问题上会过拟合）。
2. 对于许多统计建模者来说，随机森林给人的感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。
3. 可能有很多相似的决策树，掩盖了真实的结果。
4. 对于小数据或者低维数据（特征较少的数据），可能不能产生很好的分类。（处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处）。

代码实战

int createBinTree(bitree_R &t,const Data &data, const int &deep, const int &epsilon) 
{ 
 if(!(t=(bitnode_R *)malloc(sizeof(bitnode_R)))) exit(-1); 
 split_R sp=chooseBestSplit(data,deep,epsilon,10); 
 cout<<"index="<<sp.bestIndex<<endl; 
 t->feature=sp.bestIndex; 
 t->meanValue=sp.value; 
 //t->data=data; 
 if(t->feature==-1) 
 { 
 t->left=NULL; 
 t->right=NULL; 
 //t->data=data; 
 cout<<"feat-1"<<endl; 
 return 0; 
 } 
 else 
 { 
 cout<<"feature="<<t->feature<<" value="<<t->meanValue<<endl; 
 twoSubData_R twosubdata=binSplitDataSet(data,sp.bestIndex,sp.value); 
 createBinTree((t->left),twosubdata.left,deep,epsilon); 
 createBinTree((t->right),twosubdata.right,deep,epsilon); 
 } 
 return 0; 
 }

完整代码见【https://github.com/myazi/myLearn】