从零学习随机森林算法并手推示例

1. 概述

随机森林是一种经典的集成学习算法，属于Bagging类型，由多棵决策树构成，其核心思想是 “三个臭皮匠，顶个诸葛亮” 。

通过构建多个弱学习器（决策树），并将它们的结果综合起来（分类问题用投票法，回归问题用平均法），从而获得一个更强大、更稳定、更精确的模型。

• 随机：指数据样本的随机选择和特征变量的随机选择。
• 森林：指由多棵决策树构成的集合。

概念1.1：决策树

决策树是一种基于树形结构的机器学习算法，可用于分类和回归任务，模拟人类在面临决策时的思考过程：通过提出一系列是/否问题，逐步对数据进行细分，最终得到一个结论，这个学习过程就是通过分析训练数据，自动构建出一系列这样的“if-then”规则。

类比：就像玩“20个问题”游戏：“是动物吗？” -> “是哺乳动物吗？” -> “是猫科动物吗？” -> “是猫吗？”，每个问题都将可能性范围缩小，直到找到答案。

概念1.2：熵

熵源自信息论，表示随机变量的不确定性或混乱程度，熵越大，不确定性越高。 公式：对于一个数据集 D 中的第 k 类样本所占比例为 p_k，则数据集 D 的熵定义为：

概念1.3：信息增益

表示使用某个特征 A 对数据集 D 进行分割后，熵减少的程度（即不确定性降低的程度），信息增益越大，意味着用这个特征分裂后，纯度提升得越多，公式：

决策：在选择分裂特征时，选择能带来最大信息增益的那个特征（即纯度提升最大的特征）。

概念1.4：基尼系数

另一种衡量数据不纯度的指标，直观上，表示从数据集中随机抽取两个样本，其类别标签不一致的概率，基尼系数越小，纯度越高，公式：

决策：与信息增益类似，计算用每个特征分裂后的基尼系数加权和，选择那个能使加权基尼系数最小的特征（即纯度提升最大的特征）。

2. 核心原理：两大随机性

随机森林为了确保构建的每棵树都有差异性，从而提升模型的泛化能力，引入了两大随机性，通过引入这两种随机性，随机森林成功地创造了多棵多样且略有不同的决策树，虽然单棵树可能因为剪枝不够而过拟合，但多棵树通过“平均”或“投票”机制，可以相互抵消掉各自的过拟合部分，从而得到一个更加稳健和通用的模型。

2.1 数据随机性

从原始训练集中使用有放回抽样随机抽取n个样本，形成一个子训练集，由于是有放回抽样，原始训练集中有些样本可能被多次抽取，而有些样本可能从未被抽到。大约有 1 - 1/e ≈ 36.8% 的样本不会被抽到，这部分数据被称为 袋外数据（Out-of-Bag, OOB），OOB数据可以用来评估模型性能，无需单独划分验证集。

2.2 特征随机性

在构建决策树的每个分裂节点时，不是从全部特征中选择最优特征，而是先随机从所有特征中选取一个特征子集，然后从这个更小的特征子集中选择最优特征进行分裂。这种做法进一步增强了树与树之间的独立性，打破了特征间的关联，使得模型更能抵抗过拟合。

3. 算法步骤

决策树构建的核心在于，如何选择每个节点上要问的“最佳问题”（即用哪个特征进行分裂）， 这个“最佳”的衡量标准就是信息增益和基尼系数，目标都是让分裂后的子集尽可能“纯”，即同一类别的样本尽可能地分到同一个分支里。以分类问题为例，随机森林的构建过程如下：

1. 准备阶段： 设定森林中树的数量、每个节点考虑的特征数等超参数。
2. 有放回抽样： 对于森林中的第 i (i=1,2,…,n) 棵树，从原始训练集（大小为N）中有放回地随机抽取N个样本，形成该树的训练集。
3. 构建决策树： 使用上一步生成的训练集来构建一棵决策树，在构建树的每个节点时：
   • a. 随机从所有 m 个特征中选择 k 个特征（k ≤ m，例如 k = √m）。
   • b. 从这 k 个特征中，通过基尼系数或信息增益等指标选择最佳分裂特征和分裂点。
   • c. 按照标准决策树算法生成子节点。
   • d. 重复步骤a-c，直到达到终止条件，如节点中的样本全部属于同一类别（纯度已为100%）、没有更多特征可用于分裂（所有特征已用完）、树达到最大深度、节点样本数少于阈值（再分裂下去无统计意义）等（随机森林中的树通常不进行剪枝，让其充分生长）。
4. 重复生成： 重复步骤2和3，直到生成预设数量的树，共同组成森林。
5. 集成输出（预测）：
   • 分类问题：输入一个新样本，让森林中的每棵树都进行预测，最终结果由所有树投票决定（少数服从多数）。
   • 回归问题：输入一个新样本，让森林中的每棵树都给出一个预测值，最终结果是所有树预测值的平均值。

4. 算法简单对比

总结来说，随机森林是一个强大、稳健且易于使用的“开箱即用”算法。它通过构建多棵决策并引入随机性，有效提升了模型的泛化能力和精度，使其成为机器学习领域不可或缺的工具之一。

5. 手推个栗子（判断是否适合跑步）

5.1 问题定义与数据集

使用一个非常经典的微型数据集，根据天气状况决定是否进行户外跑步。

特征 (X):

• 天气预报：晴天，阴天，下雨
• 温度：热、中、冷
• 湿度：高、正常
• 有风：有、无

目标 (y): 是否跑步：是、否

训练数据集 (共14个样本):

任务：训练一个由 3棵决策树 组成的随机森林，来预测在新的天气条件下是否应该去跑步。

随机森林的核心是 有放回抽样 和 随机特征选择，将构建3棵树（Tree1, Tree2, Tree3），本文详细展示构建 Tree1的过程，Tree2 和 Tree3 的构建流程完全相同，只是基于它们自己的训练集。

5.2：为每棵树创建训练集

从原始数据集中有放回地随机抽取14次，形成每个树自己的训练集。

Tree1 的 训练集:

随机抽到的天数序列是：[D1, D3, D4, D5, D6, D6, D7, D8, D9, D10, D11, D12, D13, D14]，其中D6 被抽到了两次，D2 没有被抽到，D2将成为 Tree1 的 OOB（袋外）数据，可用于后续验证。

Tree2 的 训练集: 随机抽到的序列：[D2, D2, D3, D4, D5, D7, D8, D9, D10, D11, D12, D13, D14, D14]，其中D2、D14被抽到两次，D1, D6 是OOB数据。

Tree3 的 训练集:

假设抽到的序列：[D1, D2, D3, D3, D5, D6, D7, D8, D9, D10, D11, D12, D13, D14]，D3被抽两次，D4 是OOB数据。

5.3 构建 Tree1（展示第一个节点的详细计算）

我们使用 CART算法 和 基尼系数作为分裂标准。

Tree1 的根节点包含了它所有样本：D1, D3, D4, D5, D6, D6, D7, D8, D9, D10, D11, D12, D13, D14 (共14个样本)。

目标值的分布:

跑步（是）: D3, D4, D5, D7, D9, D10, D11, D12, D13 (9个) 跑步（否）: D1, D6, D6, D8, D14 (5个)

现在需要尝试所有特征的所有可能分裂方式，找到最佳分裂特征。随机森林在每个节点分裂时，可以随机选择一个特征子集，本次从4个特征中随机选择 √4 = 2 个特征，选到的两个特征是 天气和 湿度，在这两个特征中找最佳分裂点。

A. 计算按天气特征分裂的基尼系数

天气有3个取值：晴天，阴天，下雨

• A1：晴天分支 (天气=晴天)
  • Tree1中样本：D1、D8、D9、D11
  • 权重 = 4/14
  • 跑步（是）: D9、D11 (2个)
  • 跑步（否）: D1,、D8 (2个)
  • Gini晴天=1−((2/4)2+(2/4)2)=1−(0.25+0.25)=0.5

  

• A2：阴天分支 (天气=阴天)
  • 样本：D3, D7, D12, D13
  • 权重 = 4/14
  • 跑步（是）: 全部 (4个) -跑步（否）: 无(0个)
  • Gini阴天=1−((4/4)2+(0/4)2)=0

  

• A3：下雨分支 (天气=下雨)
  • 样本：D4, D5, D6, D6, D10, D14
  • 权重 = 6/14
  • 跑步（是）: D4, D5, D10 (3个)
  • 跑步（否）: D6, D6, D14 (3个)
  • Gini下雨=1−((3/6)2+(3/6)2)=1−(0.25+0.25)=0.5

  

• 计算汇总:

B. 计算按特征湿度分裂的基尼系数

湿度有2个取值：高、正常

• B1：高分支 (湿度=高):
  • 样本：D1, D3, D4, D8, D12, D14
  • 权重 = 6/14
  • 跑步（是）: D3, D4, D12 (3个)
  • 跑步（否）: D1, D8, D14 (3个)
  • Gini高=1−((3/6)2+(3/6)2)=0.5

  

• B2：正常分支 (湿度=正常):
  • 样本：D5, D6, D6, D7, D9, D10, D11, D13
  • 跑步（是）: D5, D7, D9, D10, D11, D13 (6个)
  • 跑步（否）: D6, D6 (2个)
  • Gini正常=1−((6/8)2+(2/8)2)=1−(0.5625+0.0625)=0.375

  

  • 权重 = 8/14
• 计算汇总：

C. 选择根节点的最佳分裂特征

• Gain_天气 = 0.102
• Gain_湿度 = 0.031

天气带来的纯度提升远大于湿度，因此根节点选择 天气作为分裂特征，根节点的分裂结果:

• 天气=晴天 -> 新建一个子节点（包含D1, D8, D9, D11）
• 天气=阴天-> 这是一个纯节点（全部是跑步），直接变为叶节点，预测结果为 跑步（是）。
• 天气=下雨 -> 新建一个子节点（包含D4, D5, D6, D6, D10, D14）

5.4 继续构建 Tree1 的其他节点

上述分裂后，晴天和下雨分支还需要继续分裂，流程与根节点完全相同：

对于晴天节点，随机选择2个特征（比如 温度 和 有风），计算这两个特征分裂后的加权基尼系数，选择增益最大的特征进行分裂，重复此过程，直到满足停止条件（如节点纯度达到100%、节点样本数小于预设值、达到最大深度等）。

假设我们继续这个过程，最终得到一颗完整的 Tree1：

• 天气=阴天 -> 跑步(叶节点)
• 天气=晴天->
  • 如果 湿度=高 -> 不跑步 (叶节点, 如D1, D8)
  • 如果 湿度=正常 -> 跑步 (叶节点, 如D11)
• 天气=下雨 ->
  • 如果 有风=是 -> 不跑步 (叶节点, 如D6, D14)
  • 如果 有风=否 -> 跑步 (叶节点, 如D4, D5, D10)

5.5：构建完整的森林（Tree2 和 Tree3）

完全重复 第1步到第3步 的过程：

使用 Tree2 的 数据集 (D2,D2, D3, D4, D5, D7, D8, D9, D10, D11, D12, D13, D14, D14)，在每个节点随机选择特征子集，使用基尼系数选择最佳分裂点，生成一颗可能完全不同的决策树 Tree2。

同理，生成 Tree3。

最终，我们得到3颗不同的决策树，组成一个“森林”。

5.6 使用森林进行预测

新的样本：天气=晴天，温度=冷，湿度=高，有风=否，要预测是否应该去跑步，让森林里的每棵树都进行投票：

1. Tree1 预测:

• 天气=晴朗 -> 走到 晴朗 分支
• 湿度=高 -> 走到 不跑步 叶节点。
• Tree1 投票: 不跑步

2. Tree2 预测:

• (假设Tree2的结构中) 天气=晴朗 -> … -> 投票: 跑步

3. Tree3 预测:

• (假设Tree3的结构中) 天气=晴朗 -> … -> 投票: 不跑步

最终投票结果：不跑步 (2票) vs 跑步(1票)

• 随机森林的最终预测结果是：不跑步。

5.7 总结与关键点

通过这个手推示例，我们可以清晰地看到随机森林的工作原理：

1. 有放回抽样：为每棵树创建略有差异的训练集，保证树的多样性。
2. 随机特征选择：在每个节点分裂时，只考虑一个随机的特征子集，进一步增加树之间的独立性，防止所有树都一样。
3. 构建决策树：每棵树都使用CART算法，基于基尼系数等指标贪婪地生长。
4. 集成投票：预测时，每棵树的预测结果都算一票，最终通过“少数服从多数”的原则做出决策。

这种“集思广益”的机制，有效降低了单颗决策树容易过拟合的风险，使得随机森林成为一个非常强大且稳定的模型。这个手算过程虽然繁琐，但彻底揭示了其内部机制。在实际应用中，计算机构建拥有几百棵树的森林也只是瞬间之事。