1. 随机森林相关知识
随机森林就是通过集成学习的思想将多棵决策树集成的一种算法，它的基本单元是决策树，而它的本质属于机器学习的集成学习方法。
1.1. 集成学习
集成学习是指使用某种规则把多个学习器进行整合来完成学习任务的方法。
举个例子：
假设有三根决策树，它在三个测试样本上的表现如下，正确用 对 表示，错误用 错 表示：
| 测试样本 1 | 测试样本 2 | 测试样本 3 | |
|---|---|---|---|
| 决策树 1 | 错 | 对 | 对 |
| 决策树 2 | 对 | 错 | 对 |
| 决策树 3 | 对 | 对 | 错 |
采用投票法规则将三个决策树整合起来，投票法即少数服从多数。集成学习之后的表现为：
| 测试样本 1 | 测试样本 2 | 测试样本 3 | |
|---|---|---|---|
| 集成 | 对 | 对 | 对 |
上面就是集成学习的一个例子。
1.2. Bagging
为了完成集成学习，需先学习个体学习器，然后按照某种规则将个体学习器整合。对于随机森林来说，其个体学习器为决策树。
为了得到好的集成结果，需要个体学习器尽可能满足两个条件：
- 个体学习器准确；
- 个体学习器之间相互独立。
假设个体学习器为 10 个，对于给定的训练集，分为 10 个互斥的数据子集。根据数据子集训练出 10 个个体学习器，这样得到的个体学习器满足独立的条件。但是，由于数据子集的数据量占比 (10%) 较少，得到的个体学习器很可能不够准确。反之，如果数据子集中包含了训练集中的大量样本，每个个体学习器的训练数据高度相似，得到的个体学习器之间相关性很大。为了解决这个问题，需采样 Bagging 方法。
Bagging 是基于 bootstrap sampling。bootstrap 采样是有放回抽样，如果训练集的大小为 $N$，随机且有放回的从训练集中抽样 $N$ 次，得到一个新的训练集。重复上述过程 $T$ 次，可以得到 $T$ 个训练集，每个训练集的大小为 $N$。然后根据 $T$ 个训练集训练出 $T$ 个个体学习器，再将这些个体学习器整合起来，这就是 Bagging 的基本思想。
2. 随机森林
随机森林是 Bagging 的扩展。除了 bootstarp sampling 抽样过程有随机外，在决策树的生成过程中也存在“随机”。
假设数据训练集的大小为 $N$，随机森林算法中，每颗决策树的生成过程如下：
- 随机且有放回的从训练集中抽取 $N$ 个样本，形成一个新的训练集，作为该树的训练集；
- 传统决策树在最优特征选择时，是在当前结点的特征集中选择一个最优特征；而随机森林中，随机地从特征集中选取 $m$ 个特征，每次树进行分裂时，从这 $m$ 个特征中选取最优特征；
- 每颗树尽量生长且没有剪枝。
通过上述方法生成组成随机森林的每颗决策树，然后采用某规则将这组决策树整合起来，在随机森林中，某规则一般指投票法。
参考资料
[1] 《机器学习》, 周志华