随机森林/RF（Random Forest）

随机森林通过将 Bagging 和 决策树 相结合，使其结果不仅具有决策树一样强大的拟合能力，而且泛化能力相比决策树大大提升。

算法释义

随机森林算法是以决策树为基函数，并引入了随机特征选择的 Bagging 集成方法。要理解随机森林算法，首先介绍 Bagging 集成方法相关的知识。

---

自助采样法（bootstrap sampling）

自助采样法是做 模型选择和评估 方法中的重要方法。其基本思路是对数据集 D 做随机采样(每一个样本每次被抽样的概率相同，且每次抽完之后放回)。假设数据集 D 中有 m 个样本，则对数据集 D 随机采样 m 次，得到训练集 D'。显然，D 中有一部分样本会在 D' 中出现多次，而有一部分样本不会在 D' 中出现。可以对样本不在 D' 中出现的概率做一个估计，为 (1 - 1/m)^m，取极限得到：

---

Bagging

Bagging 基于自助采样法，通过多次自助采样得到不同的训练集，并基于训练集得到基学习器，最后再将这些基学习器的预测结果结合，得到最终的学习器的预测。一般在分类问题中，采用简单投票法结合预测结果，在回归问题中则采用简单平均法。

算法步骤

输入：数据集 D，训练轮数 T
输出：最终预测模型 G
(1) 迭代训练基学习器：
a. 从数据集 D 中自助采样得到训练集 D'
b. 通过训练集 D' 训练得到基学习器 g
(2) 组合预测结果：

---

包外估计

因为用自助采样法训练学习器时每次大概有 36.8% 的数据没有用于训练，因此这一部分数据可以当成验证机，用于估计学习器的泛化误差，这种方法称为“包外估计”。将 Bagging 方法结合包外估计，在做模型选择或者参数选择时，直接可以使用包外估计做验证，而且在确定最终参数后，还无需对整个训练集做一次再训练，这是其相比交叉验证和留出验证的优点之一。

---

随机森林

随机森林算法是以决策树为基函数，并引入了随机特征选择的 Bagging 集成方法。具体来说，传统决策树在结点上作特征选择时采用的是当前特征集中选择最优的划分特征，而在随机森林中，对决策树的每个结点，先从该结点的特征集合中随机选择一个包含 k 个特征的子集，然后再从这个子集中选择一个最优特征用于特征划分。一般情况下，推荐 k = log₂ m。因为随机森林的这种特点，它每次训练基决策树时计算量大大降低，而且使用随机特征子集还缩小了假设空间，相当于降低了过拟合风险，使其作为一种强大的集成算法。

随机森林用作特征选择

很多开源框架都集成了“随机森林特征选择器”，即使用随机森林来做特征选择，其通过在包外估计集中加入随机性扰动，从而判断特征的重要性，进而实现特征选择。

---

参考资料

《机器学习技法》，林轩田
《机器学习》，周志华