集成学习随机森林算法

目录

1. 引言：什么是随机森林？
2. 第一部分：集成学习基础
3. 第二部分：Bagging算法原理
4. 第三部分：随机森林的核心思想
5. 第四部分：随机森林算法详解
6. 第五部分：完整实例演示
7. 第六部分：多棵树的构建过程
8. 第七部分：预测与投票机制
9. 第八部分：随机森林的优缺点
10. 总结与回顾

引言：什么是随机森林？

从单一决策树到随机森林

单一决策树的问题：

• 容易过拟合：对训练数据过度拟合，泛化能力差
• 对数据变化敏感：数据的小幅变化可能导致树结构的显著变化
• 预测精度有限：单一模型的预测能力有限

随机森林的解决方案：

• 集成多个决策树：构建多棵不同的决策树
• 通过投票或平均得到最终预测：分类问题使用多数投票，回归问题使用平均值
• 提高预测精度和稳定性：多个模型的组合可以显著提高性能

什么是随机森林？

**随机森林（Random Forest）**是一种集成学习算法，由Leo Breiman在2001年提出。它通过构建多个决策树，并对它们的预测结果进行投票（分类）或平均（回归）来得到最终预测。

随机森林的特点：

1. 集成多个决策树：通常构建几十到几百棵决策树
2. Bootstrap采样：每棵树使用不同的训练样本子集
3. 特征随机选择：每棵树在分裂时只考虑部分特征
4. 投票机制：分类问题使用多数投票，回归问题使用平均值

为什么随机森林有效？

"三个臭皮匠，顶个诸葛亮"

• 减少方差：多个模型的平均可以减少预测的方差
• 提高稳定性：即使某些树预测错误，其他树可以纠正
• 降低过拟合：通过随机采样和特征选择，每棵树都略有不同

数学原理：

假设有 $T$ 个独立的模型，每个模型的方差为 $\sigma^2$，则 $T$ 个模型的平均方差为：

$$
Var\left(\frac{1}{T}\sum_{i=1}^{T} h_i(x)\right) = \frac{\sigma^2}{T}
$$

虽然随机森林中的树不是完全独立的，但通过随机采样和特征选择，可以显著降低相关性，从而减少方差。

第一部分：集成学习基础

1.1 什么是集成学习？

集成学习（Ensemble Learning）：通过组合多个弱学习器（Weak Learner）来构建一个强学习器（Strong Learner）的方法。

弱学习器 vs 强学习器：

• 弱学习器：预测精度略好于随机猜测的模型（如：准确率略高于50%的分类器）
• 强学习器：预测精度很高的模型（如：准确率90%以上的分类器）

集成学习的基本思想：

• 训练多个不同的模型
• 组合它们的预测结果
• 得到更好的预测性能

1.2 集成学习的主要方法

1. Bagging（Bootstrap Aggregating）

• 训练方式：并行训练多个模型
• 样本选择：每个模型使用不同的训练样本子集（Bootstrap采样）
• 预测方式：投票（分类）或平均（回归）
• 目标：减少方差
• 代表算法：随机森林

2. Boosting

• 训练方式：串行训练多个模型
• 样本选择：每个模型关注前一个模型的错误
• 预测方式：加权投票或加权平均
• 目标：减少偏差
• 代表算法：AdaBoost、GBDT、XGBoost

3. Stacking

• 训练方式：训练多个基础模型，然后训练元模型
• 样本选择：使用交叉验证
• 预测方式：元模型学习如何组合基础模型的预测
• 目标：结合多种模型的优势
• 代表算法：Stacking

1.3 Bagging vs Boosting

第二部分：Bagging算法原理

2.1 Bootstrap采样

Bootstrap采样（Bootstrap Sampling）：从原始数据集中有放回地随机抽取样本，形成新的训练集。

Bootstrap采样的特点：

1. 有放回采样：每个样本可能被选中多次
2. 样本数量相同：新训练集的大小等于原始数据集
3. 约63.2%的样本被选中：每个样本不被选中的概率为 $(1-\frac{1}{n})^n \approx e^{-1} \approx 0.368$

Bootstrap采样示例：

假设原始数据集有5个样本：{A, B, C, D, E}

第1次Bootstrap采样：

• 随机抽取：A, B, B, D, E
• 新训练集：{A, B, B, D, E}（B出现2次，C未被选中）

第2次Bootstrap采样：

• 随机抽取：A, C, C, D, E
• 新训练集：{A, C, C, D, E}（C出现2次，B未被选中）

数学推导：

对于包含 $n$ 个样本的数据集，进行Bootstrap采样：

• 每个样本被选中的概率：$p = \frac{1}{n}$
• 每个样本不被选中的概率：$q = 1 - \frac{1}{n}$
• $n$ 次采样后，某个样本不被选中的概率：$q^n = (1-\frac{1}{n})^n$

当 $n$ 很大时：
$$
\lim_{n \to \infty} (1-\frac{1}{n})^n = e^{-1} \approx 0.368
$$

因此，约63.2%的样本会被选中至少一次。

2.2 Bagging算法流程

Bagging算法步骤：

1. Bootstrap采样：从原始数据集 $D$ 中有放回地抽取 $n$ 个样本，形成训练集 $D_i$
2. 训练模型：使用训练集 $D_i$ 训练一个模型 $h_i$
3. 重复步骤1-2：重复 $T$ 次，得到 $T$ 个模型
4. 组合预测：
   • 分类：多数投票
   • 回归：平均值

Bagging的数学表达：

对于分类问题：
$$
\hat{y} = \text{mode}{h_1(x), h_2(x), ..., h_T(x)}
$$

对于回归问题：
$$
\hat{y} = \frac{1}{T} \sum_{i=1}^{T} h_i(x)
$$

其中：

• $T$：模型数量
• $h_i(x)$：第 $i$ 个模型的预测
• $\hat{y}$：最终预测
• $\text{mode}{\cdot}$：众数（多数投票）

2.3 Bagging的优势

1. 减少方差

假设每个模型的预测为 $h_i(x) = f(x) + \epsilon_i$，其中 $f(x)$ 是真实值，$\epsilon_i$ 是误差（方差为 $\sigma^2$）。

单个模型的方差：$Var(h_i(x)) = \sigma^2$

$T$ 个模型的平均方差（假设独立）：
$$
Var\left(\frac{1}{T}\sum_{i=1}^{T} h_i(x)\right) = \frac{1}{T^2} \sum_{i=1}^{T} Var(h_i(x)) = \frac{\sigma^2}{T}
$$

2. 提高稳定性

即使某些模型预测错误，其他模型可以纠正。对于分类问题，如果大多数模型预测正确，最终预测就是正确的。

3. 并行训练

多个模型可以并行训练，提高训练效率。

第三部分：随机森林的核心思想

3.1 随机森林的两个随机性

随机森林在Bagging的基础上增加了特征随机选择：

1. 样本随机性（Bootstrap采样）

• 每棵树使用不同的训练样本子集
• 通过Bootstrap采样实现
• 增加树的多样性

2. 特征随机性（特征子集选择）

• 每棵树在分裂时只考虑部分特征
• 从所有特征中随机选择 $m$ 个特征（$m < M$，$M$ 是总特征数）
• 进一步增加树的多样性，降低树之间的相关性

3.2 特征随机选择的作用

为什么需要特征随机选择？

1. 增加树的多样性：不同的特征选择导致不同的树结构
2. 降低相关性：减少树之间的相关性，提高集成效果
3. 提高泛化能力：避免所有树都关注相同的特征，减少过拟合

特征数量的选择：

• 分类问题：$m = \sqrt{M}$ 或 $m = \log_2(M)$
• 回归问题：$m = M/3$ 或 $m = \sqrt{M}$

数学原理：

假设有 $M$ 个特征，每次随机选择 $m$ 个特征。如果 $m = \sqrt{M}$，则：

• 不同树选择相同特征的概率降低
• 树之间的相关性降低
• 集成效果更好

3.3 随机森林的完整流程

训练阶段：

1. Bootstrap采样：从原始数据集中有放回地抽取样本
2. 特征随机选择：从所有特征中随机选择 $m$ 个特征
3. 构建决策树：使用选定的样本和特征构建决策树（通常使用CART算法）
4. 重复步骤1-3：重复 $T$ 次，得到 $T$ 棵决策树

预测阶段：

1. 单树预测：每棵树对输入样本进行预测
2. 投票/平均：
   • 分类：多数投票
   • 回归：平均值

第四部分：随机森林算法详解

4.1 随机森林算法伪代码

训练阶段：

函数 RandomForest_Train(数据集D, 树数量T, 特征数m):
    森林 = []
    
    对于 i = 1 到 T:
        # Bootstrap采样
        D_i = Bootstrap_Sample(D)
        
        # 构建决策树
        树_i = Build_Tree(D_i, m)
        
        森林.append(树_i)
    
    返回 森林

函数 Bootstrap_Sample(数据集D):
    n = |D|  # 数据集大小
    D_new = []
    
    对于 i = 1 到 n:
        # 有放回地随机抽取
        index = 随机整数(1, n)
        D_new.append(D[index])
    
    返回 D_new

函数 Build_Tree(数据集D_i, 特征数m):
    # 在每次分裂时，从所有特征中随机选择m个特征
    # 然后在这m个特征中选择最优分裂特征
    
    树 = CART_Tree(D_i, 特征选择策略=随机选择m个特征)
    
    返回 树

预测阶段：

函数 RandomForest_Predict(森林, 样本x, 问题类型):
    预测列表 = []
    
    对于每棵树 in 森林:
        预测 = 树.predict(x)
        预测列表.append(预测)
    
    如果 问题类型 == "分类":
        返回 多数投票(预测列表)
    否则:
        返回 平均值(预测列表)

4.2 随机森林的关键参数

1. 树的数量（n_estimators）

• 默认值：100
• 影响：树越多，性能越好，但计算时间越长
• 建议：100-500

2. 特征数量（max_features）

• 分类：$\sqrt{M}$ 或 $\log_2(M)$
• 回归：$M/3$ 或 $\sqrt{M}$
• 影响：特征越少，树之间差异越大，但单树性能可能下降

3. 树的最大深度（max_depth）

• 默认值：None（不限制）
• 影响：控制树的复杂度，防止过拟合

4. 最小样本数（min_samples_split）

• 默认值：2
• 影响：节点分裂所需的最小样本数

5. 最小叶节点样本数（min_samples_leaf）

• 默认值：1
• 影响：叶节点所需的最小样本数

4.3 随机森林的时间复杂度

训练阶段：

• 单棵树：$O(n \cdot m \cdot \log(n))$
• $T$ 棵树：$O(T \cdot n \cdot m \cdot \log(n))$

预测阶段：

• 单棵树：$O(\log(n))$
• $T$ 棵树：$O(T \cdot \log(n))$

其中：

• $n$：训练样本数
• $m$：特征数
• $T$：树的数量

第五部分：完整实例演示

5.1 数据集描述

我们使用一个天气预测是否打网球的数据集：

数据集统计：

• 总样本数：14
• 特征：天气、温度、湿度、风力（4个特征）
• 类别：是否打网球（2个类别：是、否）
• "是"的数量：9
• "否"的数量：5

随机森林参数设置：

• 树的数量：$T = 3$（为了演示，使用3棵树）
• 特征数量：$m = 2$（每次分裂时随机选择2个特征）
• 使用CART算法构建决策树（基尼不纯度）

5.2 Bootstrap采样

第1次Bootstrap采样（树1）：

从14个样本中有放回地随机抽取14个样本：

假设抽取结果：{1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}

训练集1（$D_1$）：

统计：

• "是"：11个（样本3出现2次）
• "否"：3个
• 总样本数：14
• 未选中的样本：14

第2次Bootstrap采样（树2）：

假设抽取结果：{1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14}

训练集2（$D_2$）：

统计：

• "是"：9个
• "否"：5个（样本14出现2次）
• 总样本数：14
• 未选中的样本：3

第3次Bootstrap采样（树3）：

假设抽取结果：{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 1}

训练集3（$D_3$）：

统计：

• "是"：9个
• "否"：5个
• 总样本数：14
• 所有样本都被选中（无重复）

第六部分：多棵树的构建过程

6.1 树1的构建过程

训练集1（$D_1$）： 14个样本，"是"：11个，"否"：3个

6.1.1 根节点分裂

计算根节点基尼不纯度：

$$
p(是) = \frac{11}{14} = 0.786, \quad p(否) = \frac{3}{14} = 0.214
$$

$$
Gini(D_1) = 1 - [p(是)^2 + p(否)^2] = 1 - [0.786^2 + 0.214^2]
$$

$$
= 1 - [0.618 + 0.046] = 1 - 0.664 = 0.336
$$

特征随机选择： 从4个特征中随机选择2个，假设选择：{天气, 湿度}

计算特征"天气"的基尼增益：

天气取值：{晴, 阴, 雨}

分组1：{晴} vs {阴, 雨}

• $D_{晴}$：样本1,2,8,9,11（5个样本，"是"：2，"否"：3）
• $D_{阴,雨}$：样本3,3,4,5,6,7,10,12,13（9个样本，"是"：9，"否"：0）

$$
Gini(D_{晴}) = 1 - \left[\left(\frac{2}{5}\right)^2 + \left(\frac{3}{5}\right)^2\right] = 1 - [0.16 + 0.36] = 0.480
$$

$$
Gini(D_{阴,雨}) = 1 - \left[\left(\frac{9}{9}\right)^2 + \left(\frac{0}{9}\right)^2\right] = 1 - 1 = 0
$$

$$
Gini(D_1|天气={晴} vs {阴,雨}) = \frac{5}{14} \times 0.480 + \frac{9}{14} \times 0 = 0.171
$$

$$
GiniGain(D_1, 天气={晴} vs {阴,雨}) = 0.336 - 0.171 = 0.165
$$

分组2：{阴} vs {晴, 雨}

• $D_{阴}$：样本3,3,7,12,13（5个样本，"是"：5，"否"：0）
• $D_{晴,雨}$：样本1,2,4,5,6,8,9,10,11（9个样本，"是"：6，"否"：3）

$$
Gini(D_{阴}) = 1 - \left[\left(\frac{5}{5}\right)^2 + \left(\frac{0}{5}\right)^2\right] = 0
$$

$$
Gini(D_{晴,雨}) = 1 - \left[\left(\frac{6}{9}\right)^2 + \left(\frac{3}{9}\right)^2\right] = 1 - [0.444 + 0.111] = 0.445
$$

$$
Gini(D_1|天气={阴} vs {晴,雨}) = \frac{5}{14} \times 0 + \frac{9}{14} \times 0.445 = 0.286
$$

$$
GiniGain(D_1, 天气={阴} vs {晴,雨}) = 0.336 - 0.286 = 0.050
$$

分组3：{雨} vs {晴, 阴}

• $D_{雨}$：样本4,5,6,10（4个样本，"是"：3，"否"：1）
• $D_{晴,阴}$：样本1,2,3,3,7,8,9,11,12,13（10个样本，"是"：8，"否"：2）

$$
Gini(D_{雨}) = 1 - \left[\left(\frac{3}{4}\right)^2 + \left(\frac{1}{4}\right)^2\right] = 1 - [0.5625 + 0.0625] = 0.375
$$

$$
Gini(D_{晴,阴}) = 1 - \left[\left(\frac{8}{10}\right)^2 + \left(\frac{2}{10}\right)^2\right] = 1 - [0.64 + 0.04] = 0.320
$$

$$
Gini(D_1|天气={雨} vs {晴,阴}) = \frac{4}{14} \times 0.375 + \frac{10}{14} \times 0.320 = 0.107 + 0.229 = 0.336
$$

$$
GiniGain(D_1, 天气={雨} vs {晴,阴}) = 0.336 - 0.336 = 0
$$

特征"天气"的最佳基尼增益：0.165（分组1：{晴} vs {阴, 雨}）

计算特征"湿度"的基尼增益：

湿度取值：{高, 正常}

分组：{高} vs {正常}

• $D_{高}$：样本1,2,3,3,4,8,12（7个样本，"是"：4，"否"：3）
• $D_{正常}$：样本5,6,7,9,10,11,13（7个样本，"是"：7，"否"：0）

$$
Gini(D_{高}) = 1 - \left[\left(\frac{4}{7}\right)^2 + \left(\frac{3}{7}\right)^2\right] = 1 - [0.327 + 0.184] = 0.490
$$

$$
Gini(D_{正常}) = 1 - \left[\left(\frac{7}{7}\right)^2 + \left(\frac{0}{7}\right)^2\right] = 0
$$

$$
Gini(D_1|湿度={高} vs {正常}) = \frac{7}{14} \times 0.490 + \frac{7}{14} \times 0 = 0.245
$$

$$
GiniGain(D_1, 湿度={高} vs {正常}) = 0.336 - 0.245 = 0.091
$$

特征选择结果：

选择"天气"作为根节点分裂特征，分裂条件：天气 = 晴？

6.1.2 左分支分裂（天气=晴）

当前数据集： $D_{晴}$（5个样本，"是"：2，"否"：3）

$$
Gini(D_{晴}) = 0.480
$$

特征随机选择： 从剩余特征中随机选择2个，假设选择：{湿度, 风力}

计算特征"湿度"的基尼增益：

• $D_{晴,高}$：样本1,2,8（3个样本，"是"：0，"否"：3）
• $D_{晴,正常}$：样本9,11（2个样本，"是"：2，"否"：0）

$$
Gini(D_{晴,高}) = 1 - \left[\left(\frac{0}{3}\right)^2 + \left(\frac{3}{3}\right)^2\right] = 0
$$

$$
Gini(D_{晴,正常}) = 1 - \left[\left(\frac{2}{2}\right)^2 + \left(\frac{0}{2}\right)^2\right] = 0
$$

$$
Gini(D_{晴}|湿度={高} vs {正常}) = \frac{3}{5} \times 0 + \frac{2}{5} \times 0 = 0
$$

$$
GiniGain(D_{晴}, 湿度={高} vs {正常}) = 0.480 - 0 = 0.480
$$

计算特征"风力"的基尼增益：

• $D_{晴,弱}$：样本1,8,9（3个样本，"是"：1，"否"：2）
• $D_{晴,强}$：样本2,11（2个样本，"是"：1，"否"：1）

$$
Gini(D_{晴,弱}) = 1 - \left[\left(\frac{1}{3}\right)^2 + \left(\frac{2}{3}\right)^2\right] = 1 - [0.111 + 0.444] = 0.445
$$

$$
Gini(D_{晴,强}) = 1 - \left[\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2\right] = 0.500
$$

$$
Gini(D_{晴}|风力={弱} vs {强}) = \frac{3}{5} \times 0.445 + \frac{2}{5} \times 0.500 = 0.267 + 0.200 = 0.467
$$

$$
GiniGain(D_{晴}, 风力={弱} vs {强}) = 0.480 - 0.467 = 0.013
$$

选择"湿度"作为分裂特征，分裂条件：湿度 = 高？

6.1.3 树1的完整结构

树1：
                    [根节点：D1(14个样本)]
                    Gini(D1) = 0.336
                           |
                    [特征：天气=晴?]
                    GiniGain = 0.165
                    /            \
            [是:5]            [否:9]
         Gini=0.480        Gini=0.000
            |                  |
    [特征：湿度=高?]      [叶节点:是]
    GiniGain=0.480
    /            \
[是:3]        [否:2]
Gini=0.000  Gini=0.000
    |            |
[叶:否]      [叶:是]

树1的文本表示：

如果 天气 = 晴：
    如果 湿度 = 高：
        返回 否
    否则（湿度 = 正常）：
        返回 是
否则（天气 ≠ 晴）：
    返回 是

6.2 树2的构建过程

训练集2（$D_2$）： 14个样本，"是"：9个，"否"：5个

6.2.1 根节点分裂

计算根节点基尼不纯度：

$$
p(是) = \frac{9}{14} = 0.643, \quad p(否) = \frac{5}{14} = 0.357
$$

$$
Gini(D_2) = 1 - [0.643^2 + 0.357^2] = 1 - [0.414 + 0.127] = 0.459
$$

特征随机选择： 从4个特征中随机选择2个，假设选择：{温度, 风力}

计算特征"温度"的基尼增益：

温度取值：{高, 中, 低}

分组1：{高} vs {中, 低}

• $D_{高}$：样本1,2,13（3个样本，"是"：1，"否"：2）
• $D_{中,低}$：样本4,5,6,7,8,9,10,11,12,14,14（11个样本，"是"：8，"否"：3）

$$
Gini(D_{高}) = 1 - \left[\left(\frac{1}{3}\right)^2 + \left(\frac{2}{3}\right)^2\right] = 1 - [0.111 + 0.444] = 0.445
$$

$$
Gini(D_{中,低}) = 1 - \left[\left(\frac{8}{11}\right)^2 + \left(\frac{3}{11}\right)^2\right] = 1 - [0.529 + 0.074] = 0.397
$$

$$
Gini(D_2|温度={高} vs {中,低}) = \frac{3}{14} \times 0.445 + \frac{11}{14} \times 0.397 = 0.095 + 0.312 = 0.407
$$

$$
GiniGain(D_2, 温度={高} vs {中,低}) = 0.459 - 0.407 = 0.052
$$

分组2：{中} vs {高, 低}

• $D_{中}$：样本4,8,10,11,12,14,14（7个样本，"是"：4，"否"：3）
• $D_{高,低}$：样本1,2,5,6,7,9,13（7个样本，"是"：5，"否"：2）

$$
Gini(D_{中}) = 1 - \left[\left(\frac{4}{7}\right)^2 + \left(\frac{3}{7}\right)^2\right] = 1 - [0.327 + 0.184] = 0.490
$$

$$
Gini(D_{高,低}) = 1 - \left[\left(\frac{5}{7}\right)^2 + \left(\frac{2}{7}\right)^2\right] = 1 - [0.510 + 0.082] = 0.408
$$

$$
Gini(D_2|温度={中} vs {高,低}) = \frac{7}{14} \times 0.490 + \frac{7}{14} \times 0.408 = 0.245 + 0.204 = 0.449
$$

$$
GiniGain(D_2, 温度={中} vs {高,低}) = 0.459 - 0.449 = 0.010
$$

分组3：{低} vs {高, 中}

• $D_{低}$：样本5,6,7,9（4个样本，"是"：3，"否"：1）
• $D_{高,中}$：样本1,2,4,8,10,11,12,13,14,14（10个样本，"是"：6，"否"：4）

$$
Gini(D_{低}) = 1 - \left[\left(\frac{3}{4}\right)^2 + \left(\frac{1}{4}\right)^2\right] = 0.375
$$

$$
Gini(D_{高,中}) = 1 - \left[\left(\frac{6}{10}\right)^2 + \left(\frac{4}{10}\right)^2\right] = 1 - [0.36 + 0.16] = 0.480
$$

$$
Gini(D_2|温度={低} vs {高,中}) = \frac{4}{14} \times 0.375 + \frac{10}{14} \times 0.480 = 0.107 + 0.343 = 0.450
$$

$$
GiniGain(D_2, 温度={低} vs {高,中}) = 0.459 - 0.450 = 0.009
$$

特征"温度"的最佳基尼增益：0.052（分组1：{高} vs {中, 低}）

计算特征"风力"的基尼增益：

风力取值：{弱, 强}

分组：{弱} vs {强}

• $D_{弱}$：样本1,4,5,8,9,10,13（7个样本，"是"：5，"否"：2）
• $D_{强}$：样本2,6,7,11,12,14,14（7个样本，"是"：4，"否"：3）

$$
Gini(D_{弱}) = 1 - \left[\left(\frac{5}{7}\right)^2 + \left(\frac{2}{7}\right)^2\right] = 1 - [0.510 + 0.082] = 0.408
$$

$$
Gini(D_{强}) = 1 - \left[\left(\frac{4}{7}\right)^2 + \left(\frac{3}{7}\right)^2\right] = 1 - [0.327 + 0.184] = 0.490
$$

$$
Gini(D_2|风力={弱} vs {强}) = \frac{7}{14} \times 0.408 + \frac{7}{14} \times 0.490 = 0.204 + 0.245 = 0.449
$$

$$
GiniGain(D_2, 风力={弱} vs {强}) = 0.459 - 0.449 = 0.010
$$

特征选择结果：

选择"温度"作为根节点分裂特征，分裂条件：温度 = 高？

6.2.2 右分支分裂（温度≠高）

当前数据集： $D_{中,低}$（11个样本，"是"：8，"否"：3）

$$
Gini(D_{中,低}) = 0.397
$$

特征随机选择： 从剩余特征中随机选择2个，假设选择：{天气, 风力}

计算特征"天气"的基尼增益：

• $D_{中,低,晴}$：样本8,9,11（3个样本，"是"：2，"否"：1）
• $D_{中,低,非晴}$：样本4,5,6,7,10,12,14,14（8个样本，"是"：6，"否"：2）

$$
Gini(D_{中,低,晴}) = 1 - \left[\left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2\right] = 1 - [0.444 + 0.111] = 0.445
$$

$$
Gini(D_{中,低,非晴}) = 1 - \left[\left(\frac{6}{8}\right)^2 + \left(\frac{2}{8}\right)^2\right] = 1 - [0.5625 + 0.0625] = 0.375
$$

$$
Gini(D_{中,低}|天气={晴} vs {非晴}) = \frac{3}{11} \times 0.445 + \frac{8}{11} \times 0.375 = 0.121 + 0.273 = 0.394
$$

$$
GiniGain(D_{中,低}, 天气={晴} vs {非晴}) = 0.397 - 0.394 = 0.003
$$

计算特征"风力"的基尼增益：

• $D_{中,低,弱}$：样本4,5,8,9,10（5个样本，"是"：4，"否"：1）
• $D_{中,低,强}$：样本6,7,11,12,14,14（6个样本，"是"：4，"否"：2）

$$
Gini(D_{中,低,弱}) = 1 - \left[\left(\frac{4}{5}\right)^2 + \left(\frac{1}{5}\right)^2\right] = 1 - [0.64 + 0.04] = 0.320
$$

$$
Gini(D_{中,低,强}) = 1 - \left[\left(\frac{4}{6}\right)^2 + \left(\frac{2}{6}\right)^2\right] = 1 - [0.444 + 0.111] = 0.445
$$

$$
Gini(D_{中,低}|风力={弱} vs {强}) = \frac{5}{11} \times 0.320 + \frac{6}{11} \times 0.445 = 0.145 + 0.243 = 0.388
$$

$$
GiniGain(D_{中,低}, 风力={弱} vs {强}) = 0.397 - 0.388 = 0.009
$$

选择"风力"作为分裂特征，分裂条件：风力 = 弱？

6.2.3 树2的完整结构

树2：
                    [根节点：D2(14个样本)]
                    Gini(D2) = 0.459
                           |
                    [特征：温度=高?]
                    GiniGain = 0.052
                    /            \
            [是:3]            [否:11]
         Gini=0.445        Gini=0.397
            |                  |
    [叶节点:否]        [特征：风力=弱?]
                    GiniGain=0.009
                    /            \
                [是:5]        [否:6]
            Gini=0.320    Gini=0.445
                |              |
        [叶节点:是]    [叶节点:是]

树2的文本表示：

如果 温度 = 高：
    返回 否
否则（温度 ≠ 高）：
    如果 风力 = 弱：
        返回 是
    否则（风力 = 强）：
        返回 是

6.3 树3的构建过程

训练集3（$D_3$）： 14个样本，"是"：9个，"否"：5个

6.3.1 根节点分裂

计算根节点基尼不纯度：

$$
Gini(D_3) = 0.459
$$

特征随机选择： 从4个特征中随机选择2个，假设选择：{天气, 温度}

计算特征"天气"的基尼增益：

分组1：{晴} vs {阴, 雨}

• $D_{晴}$：样本1,2,8,9,11（5个样本，"是"：2，"否"：3）
• $D_{阴,雨}$：样本3,4,5,6,7,10,12,13,14（9个样本，"是"：7，"否"：2）

$$
Gini(D_{晴}) = 0.480
$$

$$
Gini(D_{阴,雨}) = 1 - \left[\left(\frac{7}{9}\right)^2 + \left(\frac{2}{9}\right)^2\right] = 1 - [0.605 + 0.049] = 0.346
$$

$$
Gini(D_3|天气={晴} vs {阴,雨}) = \frac{5}{14} \times 0.480 + \frac{9}{14} \times 0.346 = 0.171 + 0.222 = 0.393
$$

$$
GiniGain(D_3, 天气={晴} vs {阴,雨}) = 0.459 - 0.393 = 0.066
$$

分组2：{阴} vs {晴, 雨}

• $D_{阴}$：样本3,7,12,13（4个样本，"是"：4，"否"：0）
• $D_{晴,雨}$：样本1,2,4,5,6,8,9,10,11,14（10个样本，"是"：5，"否"：5）

$$
Gini(D_{阴}) = 0
$$

$$
Gini(D_{晴,雨}) = 0.500
$$

$$
Gini(D_3|天气={阴} vs {晴,雨}) = \frac{4}{14} \times 0 + \frac{10}{14} \times 0.500 = 0.357
$$

$$
GiniGain(D_3, 天气={阴} vs {晴,雨}) = 0.459 - 0.357 = 0.102
$$

分组3：{雨} vs {晴, 阴}

• $D_{雨}$：样本4,5,6,10,14（5个样本，"是"：3，"否"：2）
• $D_{晴,阴}$：样本1,2,3,7,8,9,11,12,13（9个样本，"是"：6，"否"：3）

$$
Gini(D_{雨}) = 0.480
$$

$$
Gini(D_{晴,阴}) = 0.445
$$

$$
Gini(D_3|天气={雨} vs {晴,阴}) = \frac{5}{14} \times 0.480 + \frac{9}{14} \times 0.445 = 0.171 + 0.286 = 0.457
$$

$$
GiniGain(D_3, 天气={雨} vs {晴,阴}) = 0.459 - 0.457 = 0.002
$$

特征"天气"的最佳基尼增益：0.102（分组2：{阴} vs {晴, 雨}）

计算特征"温度"的基尼增益：

分组1：{高} vs {中, 低}

• $D_{高}$：样本1,2,3,13（4个样本，"是"：2，"否"：2）
• $D_{中,低}$：样本4,5,6,7,8,9,10,11,12,14（10个样本，"是"：7，"否"：3）

$$
Gini(D_{高}) = 0.500
$$

$$
Gini(D_{中,低}) = 1 - \left[\left(\frac{7}{10}\right)^2 + \left(\frac{3}{10}\right)^2\right] = 1 - [0.49 + 0.09] = 0.420
$$

$$
Gini(D_3|温度={高} vs {中,低}) = \frac{4}{14} \times 0.500 + \frac{10}{14} \times 0.420 = 0.143 + 0.300 = 0.443
$$

$$
GiniGain(D_3, 温度={高} vs {中,低}) = 0.459 - 0.443 = 0.016
$$

特征选择结果：

选择"天气"作为根节点分裂特征，分裂条件：天气 = 阴？

6.3.2 右分支分裂（天气≠阴）

当前数据集： $D_{晴,雨}$（10个样本，"是"：5，"否"：5）

$$
Gini(D_{晴,雨}) = 0.500
$$

特征随机选择： 从剩余特征中随机选择2个，假设选择：{温度, 湿度}

计算特征"温度"的基尼增益：

• $D_{晴,雨,高}$：样本1,2（2个样本，"是"：0，"否"：2）
• $D_{晴,雨,非高}$：样本4,5,6,8,9,10,11,14（8个样本，"是"：5，"否"：3）

$$
Gini(D_{晴,雨,高}) = 0
$$

$$
Gini(D_{晴,雨,非高}) = 1 - \left[\left(\frac{5}{8}\right)^2 + \left(\frac{3}{8}\right)^2\right] = 1 - [0.391 + 0.141] = 0.469
$$

$$
Gini(D_{晴,雨}|温度={高} vs {非高}) = \frac{2}{10} \times 0 + \frac{8}{10} \times 0.469 = 0.375
$$

$$
GiniGain(D_{晴,雨}, 温度={高} vs {非高}) = 0.500 - 0.375 = 0.125
$$

计算特征"湿度"的基尼增益：

• $D_{晴,雨,高}$：样本1,2,4,8,14（5个样本，"是"：1，"否"：4）
• $D_{晴,雨,正常}$：样本5,6,9,10,11（5个样本，"是"：4，"否"：1）

$$
Gini(D_{晴,雨,高}) = 1 - \left[\left(\frac{1}{5}\right)^2 + \left(\frac{4}{5}\right)^2\right] = 1 - [0.04 + 0.64] = 0.320
$$

$$
Gini(D_{晴,雨,正常}) = 1 - \left[\left(\frac{4}{5}\right)^2 + \left(\frac{1}{5}\right)^2\right] = 0.320
$$

$$
Gini(D_{晴,雨}|湿度={高} vs {正常}) = \frac{5}{10} \times 0.320 + \frac{5}{10} \times 0.320 = 0.320
$$

$$
GiniGain(D_{晴,雨}, 湿度={高} vs {正常}) = 0.500 - 0.320 = 0.180
$$

选择"湿度"作为分裂特征，分裂条件：湿度 = 高？

6.3.3 树3的完整结构

树3：
                    [根节点：D3(14个样本)]
                    Gini(D3) = 0.459
                           |
                    [特征：天气=阴?]
                    GiniGain = 0.102
                    /            \
            [是:4]            [否:10]
         Gini=0.000        Gini=0.500
            |                  |
    [叶节点:是]        [特征：湿度=高?]
                    GiniGain=0.180
                    /            \
                [是:5]        [否:5]
            Gini=0.320    Gini=0.320
                |              |
        [叶节点:否]    [叶节点:是]

树3的文本表示：

如果 天气 = 阴：
    返回 是
否则（天气 ≠ 阴）：
    如果 湿度 = 高：
        返回 否
    否则（湿度 = 正常）：
        返回 是

第七部分：预测与投票机制

7.1 三棵树的完整结构图示

随机森林（3棵树）：

树1：                          树2：                          树3：
    [天气=晴?]                     [温度=高?]                     [天气=阴?]
    /        \                     /        \                     /        \
[是]        [否]               [是]        [否]               [是]        [否]
  |          |                   |          |                   |          |
[湿度=高?]  [叶:是]            [叶:否]    [风力=弱?]          [叶:是]    [湿度=高?]
  /    \                         /    \                         /    \
[是]  [否]                    [是]  [否]                    [是]  [否]
  |    |                        |    |                        |    |
[叶:否] [叶:是]              [叶:是] [叶:是]              [叶:否] [叶:是]

7.2 预测示例

示例1：预测样本（天气=晴, 温度=高, 湿度=高, 风力=弱）

树1预测：

• 路径：天气=晴？是 → 湿度=高？是 → 否

树2预测：

• 路径：温度=高？是 → 否

树3预测：

• 路径：天气=阴？否 → 湿度=高？是 → 否

投票结果：

• 否：3票
• 是：0票

最终预测：否 ✓（实际：否）

示例2：预测样本（天气=阴, 温度=中, 湿度=正常, 风力=弱）

树1预测：

• 路径：天气=晴？否 → 是

树2预测：

• 路径：温度=高？否 → 风力=弱？是 → 是

树3预测：

• 路径：天气=阴？是 → 是

投票结果：

• 是：3票
• 否：0票

最终预测：是 ✓（实际：是）

示例3：预测样本（天气=雨, 温度=低, 湿度=正常, 风力=强）

树1预测：

• 路径：天气=晴？否 → 是

树2预测：

• 路径：温度=高？否 → 风力=弱？否 → 是

树3预测：

• 路径：天气=阴？否 → 湿度=高？否 → 是

投票结果：

• 是：3票
• 否：0票

最终预测：是 ✓（实际：是）

示例4：预测样本（天气=晴, 温度=中, 湿度=正常, 风力=强）

树1预测：

• 路径：天气=晴？是 → 湿度=高？否 → 是

树2预测：

• 路径：温度=高？否 → 风力=弱？否 → 是

树3预测：

• 路径：天气=阴？否 → 湿度=高？否 → 是

投票结果：

• 是：3票
• 否：0票

最终预测：是 ✓（实际：是）

7.3 投票机制的数学表达

分类问题（多数投票）：

$$
\hat{y} = \arg\max_{c} \sum_{i=1}^{T} \mathbb{1}(h_i(x) = c)
$$

其中：

• $T$：树的数量
• $h_i(x)$：第 $i$ 棵树的预测
• $c$：类别
• $\mathbb{1}(\cdot)$：指示函数（如果条件为真返回1，否则返回0）

回归问题（平均值）：

$$
\hat{y} = \frac{1}{T} \sum_{i=1}^{T} h_i(x)
$$

7.4 随机森林的优势体现

1. 提高预测精度

单棵树可能预测错误，但多棵树的投票可以纠正错误。例如：如果2棵树预测正确，1棵树预测错误，最终预测仍然是正确的。

2. 提高稳定性

即使某些树的结构不同，只要大多数树预测正确，最终预测就是稳定的。对数据的小幅变化不敏感。

3. 降低过拟合

每棵树使用不同的训练样本和特征，单棵树可能过拟合，但多棵树的平均可以减少过拟合。

第八部分：随机森林的优缺点

8.1 优点

1. 预测精度高

• 集成多个模型，通常比单一决策树精度更高
• 在大多数数据集上表现优秀

2. 处理高维数据

• 通过特征随机选择，可以处理大量特征
• 自动进行特征选择

3. 处理非线性关系

• 可以捕捉特征之间的复杂交互
• 不需要假设线性关系

4. 评估特征重要性

• 可以计算每个特征的重要性
• 帮助理解哪些特征对预测最重要

5. 处理缺失值

• 对缺失值有一定的容忍度
• 可以通过其他特征的信息来弥补

6. 并行训练

• 多棵树可以并行训练
• 提高训练效率

7. 不需要特征缩放

• 对特征的尺度不敏感
• 不需要归一化或标准化

8.2 缺点

1. 可解释性差

• 虽然单棵树可解释，但多棵树的组合难以解释
• 不如单一决策树直观

2. 内存占用大

• 需要存储多棵决策树
• 树的数量越多，内存占用越大

3. 训练时间长

• 需要训练多棵决策树
• 虽然可以并行，但总体时间仍然较长

4. 对噪声敏感

• 虽然比单一决策树好，但仍可能受到噪声影响
• 需要足够的数据量

5. 可能过拟合

• 如果树的数量过多或深度过深，仍可能过拟合
• 需要调整超参数

8.3 与其他算法的对比

总结与回顾

核心概念回顾

1. 集成学习

   • 通过组合多个弱学习器构建强学习器
   • 主要方法：Bagging、Boosting、Stacking

2. Bagging（Bootstrap Aggregating）

   • 并行训练多个模型
   • 每个模型使用不同的训练样本子集（Bootstrap采样）
   • 预测时进行投票或平均

3. 随机森林

   • 在Bagging基础上增加特征随机选择
   • 两个随机性：样本随机性（Bootstrap采样）和特征随机性
   • 集成多个决策树，通过投票或平均得到最终预测

4. Bootstrap采样

   • 有放回地随机抽取样本
   • 约63.2%的样本被选中至少一次

5. 特征随机选择

   • 每次分裂时从所有特征中随机选择 $m$ 个特征
   • 分类：$m = \sqrt{M}$ 或 $\log_2(M)$
   • 回归：$m = M/3$ 或 $\sqrt{M}$

关键公式汇总

Bootstrap采样概率：
$$
P(\text{样本不被选中}) = (1-\frac{1}{n})^n \approx e^{-1} \approx 0.368
$$

Bagging预测（分类）：
$$
\hat{y} = \text{mode}{h_1(x), h_2(x), ..., h_T(x)}
$$

Bagging预测（回归）：
$$
\hat{y} = \frac{1}{T} \sum_{i=1}^{T} h_i(x)
$$

方差减少（假设独立）：
$$
Var\left(\frac{1}{T}\sum_{i=1}^{T} h_i(x)\right) = \frac{\sigma^2}{T}
$$

随机森林算法流程

训练阶段：

1. Bootstrap采样：从原始数据集中有放回地抽取样本
2. 特征随机选择：从所有特征中随机选择 $m$ 个特征
3. 构建决策树：使用选定的样本和特征构建决策树
4. 重复步骤1-3：重复 $T$ 次，得到 $T$ 棵决策树

预测阶段：

1. 单树预测：每棵树对输入样本进行预测
2. 投票/平均：分类问题使用多数投票，回归问题使用平均值

学习要点

1. 理解集成学习的思想：多个弱学习器组合成强学习器
2. 掌握Bootstrap采样：有放回采样，约63.2%的样本被选中
3. 理解两个随机性：样本随机性和特征随机性
4. 掌握投票机制：分类问题使用多数投票，回归问题使用平均值
5. 理解随机森林的优势：减少方差、提高稳定性、降低过拟合

实际应用建议

1. 参数调优：

   • 树的数量：100-500
   • 特征数量：分类用 $\sqrt{M}$，回归用 $M/3$
   • 树的深度：根据数据复杂度调整

2. 特征工程：

   • 随机森林对特征缩放不敏感
   • 可以处理高维数据
   • 自动进行特征选择

3. 模型评估：

   • 使用交叉验证评估性能
   • 查看特征重要性
   • 分析OOB（Out-of-Bag）误差

4. 并行训练：

   • 利用多核CPU并行训练
   • 提高训练效率

延伸学习

• 特征重要性：如何计算和解释特征重要性
• OOB误差：使用未选中的样本评估模型性能
• 极端随机树（Extra Trees）：进一步随机化的随机森林
• 梯度提升树（GBDT）：另一种集成学习方法
• XGBoost和LightGBM：基于梯度提升的高效框架