跳转至

随机森林｜森林模型们⚓︎

约 2541 个字 1 张图片 预计阅读时间 8 分钟 总阅读量 次

前置章节：决策树与树模型。

随机森林⚓︎

虽然单个决策树简单直观，但它有如下问题：

  1. 高方差 (High Variance) / 容易过拟合 (Overfitting)：单个决策树对训练数据的微小变化非常敏感。如果训练数据有轻微的变动，可能会生成一棵结构完全不同的树。这导致模型的泛化能力差，在新的测试数据上表现不稳定。

  2. 不稳定性 (Instability)：正是因为高方差，单个决策树的预测结果不够稳定可靠。

Bagging方法 (e.g., 随机森林 Random Forest)：并行地构建多棵决策树。每棵树在不同的数据子集（通过自助采样法获得）和特征子集上训练。通过“投票”或“平均”来综合所有树的预测结果，能有效降低方差，防止过拟合。

Bootstrap 采样⚓︎

一种采样方式，每次选取原始训练数据集中的一个子集合进行训练，这里的每个子集合里的数据，可能选中某条数据多次，也可能遗漏某些数据。

随机森林的核心思想是“群体智慧”。它通过构建大量的、各不相同的决策树，并将它们的结果进行汇总，来获得一个比任何单个决策树都更准确、更稳定的模型。这个过程极大地降低了模型的方差，从而有效缓解了过拟合问题，提升了模型的泛化能力。

一句话总结：随机森林通过集成大量决策树，以牺牲部分可解释性为代价，换取了模型稳定性和预测精度的显著提升。

算法流程⚓︎

随机森林的构建包含两个关键思想：Bootstrap Aggregating (Bagging) 和 特征随机性。

训练流程⚓︎

假设我们有训练集 \(D\)，包含 \(n\) 个样本，\(M\) 个特征。我们要构建一个包含 \(B\) 棵树的随机森林。

  1. 循环构建决策树：for b = 1 to B do:

    • 步骤 A: 有放回采样 (Bootstrap Sampling)

      • 从原始训练集 \(D\) 中，进行有放回的随机采样，构建一个大小同样为 \(n\) 的新训练集 \(D_b\)。
      • 由于是有放回采样， \(D_b\) 中会有一些重复的样本，也有些原始样本从未被抽中。

    • 步骤 B: 构建决策树 \(T_b\)

      • 使用数据集 \(D_b\) 来训练一棵决策树 \(T_b\)。
      • 关键点：在树的每个节点进行分裂时，不是从全部 \(M\) 个特征中寻找最优分裂点，而是随机选择一个包含 \(m\) 个特征的子集（其中 \(m \ll M\)），然后从这个子集中选择最优分裂特征。
      • 这棵决策树会一直生长，不进行剪枝 (No Pruning)，让每个单独的树都尽可能地去拟合它所看到的数据（即允许单棵树过拟合）。

  2. 完成：重复上述过程 \(B\) 次，最终得到由 \(B\) 棵决策树 \(\{T_1, T_2, ..., T_B\}\) 组成的随机森林。

预测流程⚓︎

当有一个新的测试样本 \(x'\) 需要预测时：

  1. 分别预测：将样本 \(x'\) 输入到森林中的每一棵决策树 \(T_b\) 中，得到 \(B\) 个预测结果 \(\{p_1, p_2, ..., p_B\}\)。
  2. 汇总结果 (Aggregate)：
    • 分类问题：采用多数投票 (Majority Voting) 的方式。\(B\) 棵树中，哪个类别的票数最多，最终的预测结果就是哪个类别。
    • 回归问题：采用平均值 (Averaging) 的方式。将 \(B\) 棵树的预测结果求算术平均值，作为最终的预测值。

I. 两个“随机性”的来源⚓︎

这是随机森林“随机”二字的精髓，也是它相比于普通 Bagging+决策树 的改进之处。

  1. 行采样随机性 (Sample Randomness)：即 Bagging 中的 Bootstrap 采样。这保证了每棵树训练的数据集是不同的，使得树之间产生差异。
  2. 列采样随机性 (Feature Randomness)：即在每个节点分裂时，随机选择部分特征进行最优分裂点的寻找。这是随机森林的核心创新。

为什么特征随机性如此重要？

它能进一步降低树与树之间的相关性 (Decorrelate the trees)。想象一个场景，数据集中有一个非常强的预测特征。在普通的 Bagging 中，大部分树的根节点可能都会选择这个强特征进行分裂，导致所有树的结构都非常相似，它们会犯同样的错误。引入特征随机性后，某些树在分裂时根本“看不到”这个强特征，它们被迫去学习其他特征的组合规则。这样就产生了结构更多样、相关性更低的树，集成后的模型泛化能力更强。

II. OOB (Out-of-Bag) Error⚓︎

这是随机森林一个非常优雅的特性，可以在不使用交叉验证或独立测试集的情况下，对模型性能进行无偏估计。

  • 什么是 OOB 数据？ 在进行 Bootstrap 采样时，对于每一棵树 \(T_b\)，大约有 \(1 - (1 - 1/n)^n \approx 1 - 1/e \approx 36.8\%\) 的原始数据没有被抽到。这些未被抽中的数据构成了树 \(T_b\) 的袋外数据 (Out-of-Bag Data)。

  • 如何计算 OOB Error?

    1. 对于训练集中的每一个样本 \(x_i\)，找到所有没有用它来训练的树（即 OOB 树）。
    2. 让这些 OOB 树对样本 \(x_i\) 进行预测，并用投票/平均的方式得到一个“OOB 预测结果”。
    3. 用这个 OOB 预测结果与 \(x_i\) 的真实标签进行比较，得出是否预测正确。
    4. 最后，将所有样本的误分类率或均方误差进行平均，就得到了模型的 OOB Error。

作用

OOB Error 是对模型泛化误差的一个很好的无偏估计。在实践中，它通常与 K-折交叉验证的结果非常接近，但计算成本要低得多。这使得我们可以在训练过程中监控模型性能，并用于模型调参 。

一个显而易见的事儿就是，我们一开始并不知道每次随机选特征的时候选几个特征，此时就可以多试几个参数，比如，一般，从 \(\sqrt{M}\) 个参数开始选，正负某些数值，看看不同参数下建出来的树在 OOB Error 的表现如何。选Error更小的，作为最终的参数即可。

III. 特征重要性 (Feature Importance)⚓︎

随机森林可以评估每个特征在预测中的重要性，这也是它的一个重要副产品。主要有两种计算方法：

  1. 基于基尼不纯度下降 (Mean Decrease in Impurity)：一个特征在决策树中每次被用来分裂节点时，都会带来一次基尼不纯度的下降。将这个特征在单棵树中所有分裂点带来的不纯度下降值加起来，就是它对这棵树的贡献。最后，将所有树的贡献值取平均，就得到了该特征的重要性。这种方法计算速度快，但可能偏向于取值更多的特征。

  2. 基于置换的重要性 (Permutation Importance / Mean Decrease in Accuracy)：这是一种更可靠但计算量更大的方法。

    • 首先，计算模型的 OOB Error。
    • 然后，对于特征 \(j\)，将其在所有 OOB 数据中的值随机打乱 (Permute)，保持其他特征和标签不变。这相当于切断了特征 \(j\) 和目标标签之间的联系。
    • 用打乱后的数据重新计算 OOB Error。
    • 两次 OOB Error 的差值，就代表了这个特征 \(j\) 的重要性。如果差值很大，说明模型非常依赖这个特征，它很重要；如果差值很小，说明这个特征不那么重要。

4. 算法复杂度⚓︎

假设有 \(n\) 个样本， \(M\) 个特征，森林中有 \(n_{tree}\) 棵树，每棵树分裂时考虑 \(m\) 个特征。

  • 训练复杂度：

    • 构建一棵不剪枝决策树的复杂度约为 \(O(m \times n \log n)\)。
    • 随机森林需要构建 $n_{tree} 棵树，且这个过程可以完美地并行化（因为每棵树的训练是独立的）。
    • 因此，总的训练复杂度为 \(O(n_{tree} \times m \times n \log n)\)。

  • 预测复杂度：

    • 对于一个新样本，需要经过 \(n_{tree}\) 棵树的预测。
    • 单棵树的预测复杂度为树的深度，约 \(O(\log n)\)。
    • 因此，总的预测复杂度为 \(O(n_{tree} \times \log n)\)。

总而言之，随机森林是一个功能强大、应用广泛且相对容易理解的集成模型，是你面试准备中必须熟练掌握的一环。

Boosting 相关的 Trick⚓︎

  • Boosting (e.g., AdaBoost, GBDT)：串行地构建多棵决策树。每一棵新树都专注于修正前面树犯下的错误。模型整体是一个加法模型，能有效降低偏差。

  • XGBoost (Extreme Gradient Boosting)：GBDT 的一种高效、灵活且可移植的工程实现。它在 GBDT 的基础上做了大量优化：

    1. 在目标函数中加入了正则化项（L1 和 L2 正则），防止过拟合。
    2. 对目标函数进行了二阶泰勒展开，使得优化更精确。
    3. 支持并行化处理（在特征层面）。
    4. 内置了处理缺失值的策略。

  • LightGBM (Light Gradient Boosting Machine)：微软推出的另一个 GBDT 实现，以速度快、内存占用低著称。

    1. 基于梯度的单边采样 (GOSS)：保留梯度大的样本，随机采样梯度小的样本，在保证精度的同时减少了计算量。
    2. 互斥特征捆绑 (EFB)：将一些互斥的稀疏特征捆绑在一起，减少特征维度。
    3. 带深度限制的 Leaf-wise 生长策略：XGBoost 是 Level-wise 生长，LGBM 是 Leaf-wise，每次选择增益最大的叶子节点进行分裂，效率更高，但可能生成更深的树，需要max_depth来防止过拟合。

希望这份详细的梳理能帮助你更好地准备秋招面试！祝你成功！