随机森林详解

随机森林（Random Forest）是属于集成学习的一种组合分类算法，集成学习的核心思想就是将若干个弱（基）分类器组合起来，得到一个分类性能显著优越的强分类器。如果各弱分类器之前没有强依赖关系、可并行生成，就可以使用随机森林算法。
随机森林利用自主抽样法（bootstrap）从原数据集中有放回地抽取多个样本，对抽取的样本先用弱分类器—决策树进行训练，然后把这些决策树组合在一起，通过投票得出最终的分类或预测结果。

（一）决策树

决策树是一种树形结构，其中有三种几点：根结点、中间结点和叶子结点。树中的每个结点都表示对象的特征，根结点为训练对象的集合，边为父节点对于某一特征的某种可能的取值规则，中间结点为父结点根据某一特征的某种可能的取值筛选后形成的训练对象的集合，叶子结点为分类结果。决策树的结构如图1所示。

图1 决策树结构示意图

运用决策树进行分类的算法称为决策树分类算法，其基本原理是：把被分类的对象从根结点开始，测试该结点对应的特征，然后按照给定的特征的取值按照对应的边往下遍历，直到到达叶子结点获得被分类对象的类别。
决策树作为一种弱分类器，采取的是单一的分类决策模式，所以存在很多缺点，比如过度拟合、分类规则复杂、只能得到局部最优解等。

（二）随机森林

为了解决决策树模型存在的问题，在决策树的基础上，结合多个分类器组合的思想，由多个决策树生成随机森林。随机森林的核心思想就是，对训练集进行重采样，组成多个训练子集，每个子集生成一个决策树，所有决策树通过投票的方式进行决策，组成随机森林。
为了描述方便，我们设训练极为T，由N个样本，即T={t₁,t₂,…,t_N}，设特征集为F，有M维特征，即F={f₁,f₂,…,f_M}，类别集合为C，有L种类别，即C={c₁,c₂,…,c_L}，测试集为D，有λ个测试样本，即D={d₁,d₂,…,d_λ}。
随机森林的算法流程如下所示：

1. 从容量为N的训练集T中，采用自助抽样法（bootstrap），即有放回地抽取N个样本，作为一个训练子集T_k；
2. 对于训练子集T_k，从特征集F中无放回地随机抽取m个特征，其中m=log₂M（向上取整），作为决策树上的每个节点分裂的依据，从根结点开始，自上而下生成一个完整的决策树S_k，不需要剪枝；
3. 重复n次步骤1和2，得到n个训练子集T₁,T₂,…,T_n，并生成决策树S₁,S₂,…,S_n，将n个决策树组合起来，形成随机森林；
4. 将测试集D的样本d_μ输入随机森林中，让每个决策树对d_μ进行决策，然后采用多数投票法（Majority Voting Algorithm）对决策结果投票，最终决定d_μ的分类；
5. 重复λ次步骤4，直到测试集D分类完成。

随机森林建立过程如图2所示。

图2 随机森林生成过程示意图

（三）测试结果评估

若已知每个测试样本的正确分类（标签），随机森林还可以对测试结果的正确性进行评估，从而说明特征维选择的合理性。
对于测试集为D={d₁,d₂,…,d_λ}，设为C’={c₁’,c₂’,…,c_L’；}，则将某个测试样本d_μ的测试结果c_μ和正确分类c_μ’进行比对，相同则记为1，不同则记为0，得到测试集D的分类正确率为