此文是本人学习林轩田老师教授的机器学习技法第十——Decision Tree——的笔记。
Random Forest 模型概括讲，就是以 Decision Tree 为基础模型，这里选择未经剪枝的完全树，用 Bagging 进行集合训练。完全决策树在训练集上的零误差，对样本选择十分敏感，有较大的 varaince，但有着训练高效等优点。而 Bagging 能够降低模型预测的 varaince 误差，特别适用于对样本敏感的波动比较大的模型。所以，结合两者应该可以取得好效果。
参考
增强随机性
在 Random Forest 中，为了进一步降低算法 variance 误差，不仅抽取样本时做到随机抽取，还在选择特征时保证一定的随机性。普遍使用方式是 随机选取子空间。
随机选取子空间（random subspace）
在训练 Decision Tree 的每一个节点时，需要按照某种准则（如基尼值）选取一个特征用于数据划分。未经处理的特征选择数目是所有特征的数目 $M$， 为了增大随机性，随机抽取其中的 $m$ （往往 $M,m$ 差距比较大）个特征供选择。一项数据 $(\mathbf{x}, y)$， 将 $\mathbf{x}$ 视作一个空间向量，每个特征对应一个维度，所以，这个过程可以理解成随机抽取一个子空间用做训练。
随机结合子空间（random combination）
与随机选取子空间不同，随机结合子空间将数据向量 $\mathbf{x}$ 投影到另一个空间成为 $\mathbf{x’}$。 $\mathbf{x’}$ 的每一维都是从原 $\mathbf{x}$ 的 $M$ 维中随机选择 $m$ 维结合（相加）而得。
Out Of Bag 验证
Bagging 采用 Bootstrapping 的方式取样，有些样本没有被抽到不能用作训练数据，称其为 Out Of Bag（简称 OOB） 数据，但它们也可以被利用起来，作为验证使用。
具体做法是，在为每个 Decision Tree 抽取训练数据时就标记那些未被抽取的 OOB 数据，在整个 Random Forest 训练结束后用 OOB 做验证。在用某项 OOB 数据做验证时，该数据可能被一些 Decision Tree 用作训练数据，所以必须排除这些 Decision Tree。
特征选择——置换重要性
特征选择 指从所有特征中选取对结果有影响（有用）的特征，剔除无关特征。Random Forest 能很容易实现这个功能。
如果一个特征 $x_i$ 对结果 $y$ 无影响，那么 $x_i$ 与 $y$ 是否正确对应也就无关紧要。基于这个思想，研究者提出一个通过置换特征计算其重要程度的方法：
$$ importance(i) = E{oob}(G) - E{oob}^{(p)}(G) $$
其中，G 指已经训练完成的 Random Forest 模型， $E{oob}$ 指 OOB 验证误差，未经任何处理，而 $E{oob}^{(p)}$ 指在进行 OOB 验证前，所有 OOB 数据的第 $i$ 个特征（第 $i$ 维数值 $x_i$）相互间进行随机置换（互换）。
这个思想类似 permutation test 置换检验。
树越多越好？
老师指出，理论上讲，树越多，Random Forest 的越强，建议在预测效果不好时，适当增加树的个数。