决策树剪枝

目录

1. 引言：为什么需要剪枝？
2. 第一部分：过拟合问题
3. 第二部分：剪枝的基本概念
4. 第三部分：预剪枝方法
5. 第四部分：后剪枝方法概述
6. 第五部分：代价复杂度剪枝详解
7. 第六部分：完整实例演示
8. 第七部分：剪枝过程详解
9. 第八部分：剪枝后的树结构
10. 第九部分：其他剪枝方法
11. 总结与回顾

引言：为什么需要剪枝？

决策树的过拟合问题

决策树的特点：

• 可以完美拟合训练数据
• 如果不对深度进行限制，会一直分裂直到每个叶节点只有一个样本
• 对训练数据的准确率可能达到100%，但泛化能力很差

过拟合的表现：

• 训练集准确率很高，但测试集准确率很低
• 树的结构过于复杂，包含很多不必要的分裂
• 对噪声和异常值过度敏感

什么是剪枝？

剪枝（Pruning）：通过移除决策树的部分分支来简化树结构，提高泛化能力的方法。

剪枝的目标：

• 减少树的复杂度
• 提高泛化能力
• 在准确率和复杂度之间找到平衡

剪枝的两种主要方法：

1. 预剪枝（Pre-pruning）：在构建树的过程中提前停止分裂
2. 后剪枝（Post-pruning）：先构建完整的树，然后从下往上移除分支

第一部分：过拟合问题

1.1 过拟合的直观理解

例子：学生考试

假设有一个学生，他记住了所有练习题和答案：

• 训练集（练习题）：准确率100%
• 测试集（新题目）：准确率60%

这个学生就是"过拟合"了——他记住了题目的细节，但没有理解背后的规律。

决策树也是如此：

• 如果树太深，它会记住训练数据的每个细节
• 包括噪声和异常值
• 无法泛化到新数据

1.2 过拟合的数学表达

模型的复杂度：

假设决策树有 $L$ 个叶节点，每个叶节点对应一个预测规则。树的复杂度可以用叶节点数量来衡量。

过拟合的代价：

$$
\text{总代价} = \text{训练误差} + \alpha \times \text{复杂度惩罚}
$$

其中：

• 训练误差：模型在训练集上的错误率
• 复杂度惩罚：树的复杂度（如叶节点数量）
• $\alpha$：复杂度参数，控制对复杂度的惩罚程度

目标： 最小化总代价

1.3 偏差-方差权衡

偏差（Bias）：模型的预测值与真实值的差异

• 欠拟合：偏差大
• 过拟合：偏差小

方差（Variance）：模型对数据变化的敏感程度

• 欠拟合：方差小
• 过拟合：方差大

剪枝的作用：

• 减少方差（提高稳定性）
• 可能略微增加偏差（降低训练准确率）
• 总体提高泛化能力

第二部分：剪枝的基本概念

2.1 预剪枝 vs 后剪枝

预剪枝（Pre-pruning）：

在构建树的过程中，如果满足某个条件就停止分裂：

• 达到最大深度
• 样本数量小于阈值
• 信息增益/基尼增益小于阈值
• 所有特征都已使用

优点：

• 训练速度快
• 不需要构建完整树

缺点：

• 可能过早停止，导致欠拟合
• 难以确定合适的停止条件

后剪枝（Post-pruning）：

先构建完整的树，然后从下往上移除分支：

• 构建完整树（可能过拟合）
• 评估每个节点的剪枝效果
• 移除对泛化能力没有帮助的分支

优点：

• 通常效果更好
• 可以找到最优的树结构

缺点：

• 训练时间较长
• 需要额外的验证集

2.2 剪枝的评估标准

需要评估：

• 剪枝前后的性能变化
• 树的复杂度变化
• 泛化能力的提升

评估方法：

• 使用验证集评估
• 使用交叉验证
• 使用统计方法（如代价复杂度剪枝）

第三部分：预剪枝方法

3.1 最大深度限制

方法： 限制树的最大深度

参数： max_depth

示例：

• max_depth=3：树最多3层
• max_depth=None：不限制深度

优点： 简单直接

缺点： 难以确定合适的深度

3.2 最小样本数限制

方法： 节点分裂所需的最小样本数

参数： min_samples_split

示例：

• min_samples_split=10：节点至少需要10个样本才能分裂
• min_samples_split=2：节点至少需要2个样本才能分裂

优点： 防止对少数样本过度分裂

缺点： 可能错过重要的分裂

3.3 最小叶节点样本数

方法： 叶节点所需的最小样本数

参数： min_samples_leaf

示例：

• min_samples_leaf=5：叶节点至少需要5个样本
• min_samples_leaf=1：叶节点至少需要1个样本

优点： 确保叶节点有足够的样本支持

缺点： 可能增加树的深度

3.4 信息增益/基尼增益阈值

方法： 如果信息增益/基尼增益小于阈值，停止分裂

参数： min_impurity_decrease

示例：

• min_impurity_decrease=0.01：如果信息增益小于0.01，停止分裂

优点： 只保留有意义的分裂

缺点： 阈值难以确定

第四部分：后剪枝方法概述

4.1 后剪枝的主要方法

1. 错误率降低剪枝（REP - Reduced Error Pruning）

• 使用验证集评估剪枝效果
• 如果剪枝后验证集错误率降低，则剪枝

2. 悲观错误剪枝（PEP - Pessimistic Error Pruning）

• 使用统计方法估计错误率
• 不需要单独的验证集

3. 代价复杂度剪枝（CCP - Cost Complexity Pruning）

• CART算法使用的方法
• 平衡准确率和复杂度

4. 最小错误剪枝（MEP - Minimum Error Pruning）

• 基于贝叶斯理论
• 最小化期望错误率

4.2 后剪枝的一般流程

1. 构建完整树：使用训练集构建完整的决策树
2. 自底向上评估：从叶节点开始，评估每个节点的剪枝效果
3. 选择剪枝节点：选择剪枝后能提高泛化能力的节点
4. 执行剪枝：移除选定的节点及其子树
5. 重复步骤2-4：直到无法进一步改善

第五部分：代价复杂度剪枝详解

5.1 代价复杂度剪枝的基本思想

**代价复杂度剪枝（Cost Complexity Pruning）**是CART算法使用的剪枝方法。

核心思想：

在准确率和复杂度之间找到平衡：

$$
C_\alpha(T) = C(T) + \alpha |T|
$$

其中：

• $C(T)$：树 $T$ 在训练集上的错误率（代价）
• $|T|$：树 $T$ 的叶节点数量（复杂度）
• $\alpha$：复杂度参数（$\alpha \geq 0$）

目标： 对于给定的 $\alpha$，找到使 $C_\alpha(T)$ 最小的树

5.2 复杂度参数 $\alpha$ 的作用

$\alpha = 0$：

• 只考虑准确率，不考虑复杂度
• 选择最复杂的树（完整树）

$\alpha \to \infty$：

• 只考虑复杂度，不考虑准确率
• 选择最简单的树（根节点）

$\alpha$ 的中间值：

• 在准确率和复杂度之间平衡
• 选择最优的树结构

5.3 剪枝过程

步骤1：计算每个节点的 $\alpha$ 值

对于树中的每个非叶节点 $t$，计算：

$$
\alpha(t) = \frac{C(t) - C(T_t)}{|T_t| - 1}
$$

其中：

• $C(t)$：将节点 $t$ 剪枝为叶节点后的错误率
• $C(T_t)$：保留节点 $t$ 的子树 $T_t$ 的错误率
• $|T_t|$：子树 $T_t$ 的叶节点数量

步骤2：选择最小 $\alpha$ 值

选择 $\alpha(t)$ 最小的节点进行剪枝。

步骤3：剪枝

将选定的节点剪枝为叶节点，使用该节点的多数类（分类）或平均值（回归）。

步骤4：重复

重复步骤1-3，直到只剩下根节点。

5.4 最优子树序列

剪枝过程会产生一系列子树：

$$
T_0 \supset T_1 \supset T_2 \supset ... \supset T_k
$$

其中：

• $T_0$：完整树
• $T_k$：根节点
• 每个 $T_i$ 对应一个 $\alpha$ 区间

对于给定的 $\alpha$，选择对应的最优子树。

第六部分：完整实例演示

6.1 数据集描述

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

数据集统计：

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

训练集和验证集划分：

• 训练集：样本1-10（10个样本）
• 验证集：样本11-14（4个样本）

6.2 构建完整树

使用训练集（样本1-10）构建完整树：

训练集统计：

• "是"：6个（样本3,4,5,7,9,10）
• "否"：4个（样本1,2,6,8）

根节点基尼不纯度：

$$
p(是) = \frac{6}{10} = 0.6, \quad p(否) = \frac{4}{10} = 0.4
$$

$$
Gini(D) = 1 - [0.6^2 + 0.4^2] = 1 - [0.36 + 0.16] = 0.48
$$

构建完整树（使用CART算法）：

假设构建的完整树如下：

完整树T0：
                    [根节点：D(10个样本)]
                    Gini(D) = 0.48
                           |
                    [特征：天气=阴?]
                    /            \
            [是:3]            [否:7]
         Gini=0.000        Gini=0.408
            |                  |
    [叶节点:是]        [特征：湿度=高?]
                    /            \
                [是:3]        [否:4]
            Gini=0.000    Gini=0.375
                |              |
        [叶节点:是]    [特征：风力=弱?]
                    /            \
                [是:3]        [否:1]
            Gini=0.000    Gini=0.000
                |              |
        [叶节点:是]    [叶节点:否]

完整树的文本表示：

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

完整树结构：

• 叶节点数量：$|T_0| = 4$
• 训练集错误率：需要计算

计算训练集错误率：

使用训练集（样本1-10）验证：

• 样本1（天气=晴, 湿度=高, 风力=弱）：预测=是，实际=否，错误
• 样本2（天气=晴, 湿度=高, 风力=强）：预测=是，实际=否，错误
• 样本3（天气=阴）：预测=是，实际=是，正确
• 样本4（天气=雨, 湿度=高, 风力=弱）：预测=是，实际=是，正确
• 样本5（天气=雨, 湿度=正常, 风力=弱）：预测=是，实际=是，正确
• 样本6（天气=雨, 湿度=正常, 风力=强）：预测=否，实际=否，正确
• 样本7（天气=阴）：预测=是，实际=是，正确
• 样本8（天气=晴, 湿度=高, 风力=弱）：预测=是，实际=否，错误
• 样本9（天气=晴, 湿度=正常, 风力=弱）：预测=是，实际=是，正确
• 样本10（天气=雨, 湿度=正常, 风力=弱）：预测=是，实际=是，正确

训练集错误数： 3个（样本1,2,8）
训练集错误率： $C(T_0) = \frac{3}{10} = 0.3$

第七部分：剪枝过程详解

7.1 计算每个节点的 $\alpha$ 值

节点标记：

• 节点1：根节点（天气=阴?）
• 节点2：左子节点（天气=阴，叶节点：是）
• 节点3：右子节点（天气≠阴，湿度=高?）
• 节点4：节点3的左子节点（湿度=高，叶节点：是）
• 节点5：节点3的右子节点（湿度=正常，风力=弱?）
• 节点6：节点5的左子节点（风力=弱，叶节点：是）
• 节点7：节点5的右子节点（风力=强，叶节点：否）

需要计算 $\alpha$ 值的节点： 节点1, 3, 5（非叶节点）

7.1.1 节点5的 $\alpha$ 值

节点5： 湿度=正常，风力=弱?

子树 $T_5$：

• 节点6：风力=弱，叶节点：是（样本5,9,10，3个"是"）
• 节点7：风力=强，叶节点：否（样本6，1个"否"）

计算 $C(T_5)$：

使用训练集中属于节点5的样本（样本5,6,9,10）：

• 样本5：预测=是，实际=是，正确
• 样本6：预测=否，实际=否，正确
• 样本9：预测=是，实际=是，正确
• 样本10：预测=是，实际=是，正确

错误数： 0
错误率： $C(T_5) = \frac{0}{4} = 0$

计算 $C(5)$（将节点5剪枝为叶节点）：

节点5的样本：样本5,6,9,10

• "是"：3个（样本5,9,10）
• "否"：1个（样本6）
• 多数类：是

如果剪枝为叶节点"是"：

• 样本5：预测=是，实际=是，正确
• 样本6：预测=是，实际=否，错误
• 样本9：预测=是，实际=是，正确
• 样本10：预测=是，实际=是，正确

错误数： 1
错误率： $C(5) = \frac{1}{4} = 0.25$

计算 $\alpha(5)$：

$$
\alpha(5) = \frac{C(5) - C(T_5)}{|T_5| - 1} = \frac{0.25 - 0}{2 - 1} = \frac{0.25}{1} = 0.25
$$

7.1.2 节点3的 $\alpha$ 值

节点3： 天气≠阴，湿度=高?

子树 $T_3$：

• 节点4：湿度=高，叶节点：是（样本1,2,4,8，4个样本）
• 节点5：湿度=正常，风力=弱?（子树，2个叶节点）

计算 $C(T_3)$：

使用训练集中属于节点3的样本（样本1,2,4,5,6,8,9,10）：

• 样本1：预测=是，实际=否，错误
• 样本2：预测=是，实际=否，错误
• 样本4：预测=是，实际=是，正确
• 样本5：预测=是，实际=是，正确
• 样本6：预测=否，实际=否，正确
• 样本8：预测=是，实际=否，错误
• 样本9：预测=是，实际=是，正确
• 样本10：预测=是，实际=是，正确

错误数： 3（样本1,2,8）
错误率： $C(T_3) = \frac{3}{8} = 0.375$

计算 $C(3)$（将节点3剪枝为叶节点）：

节点3的样本：样本1,2,4,5,6,8,9,10

• "是"：5个（样本4,5,9,10，以及样本7不在节点3中）
• "否"：3个（样本1,2,6,8）
• 多数类：是

如果剪枝为叶节点"是"：

• 样本1：预测=是，实际=否，错误
• 样本2：预测=是，实际=否，错误
• 样本4：预测=是，实际=是，正确
• 样本5：预测=是，实际=是，正确
• 样本6：预测=是，实际=否，错误
• 样本8：预测=是，实际=否，错误
• 样本9：预测=是，实际=是，正确
• 样本10：预测=是，实际=是，正确

错误数： 4（样本1,2,6,8）
错误率： $C(3) = \frac{4}{8} = 0.5$

计算 $\alpha(3)$：

$$
\alpha(3) = \frac{C(3) - C(T_3)}{|T_3| - 1} = \frac{0.5 - 0.375}{3 - 1} = \frac{0.125}{2} = 0.0625
$$

7.1.3 节点1的 $\alpha$ 值

节点1： 根节点（天气=阴?）

子树 $T_1$： 完整树 $T_0$（4个叶节点）

计算 $C(T_1)$：

$C(T_1) = C(T_0) = 0.3$

计算 $C(1)$（将节点1剪枝为叶节点）：

节点1的样本：所有训练样本（样本1-10）

• "是"：6个
• "否"：4个
• 多数类：是

如果剪枝为叶节点"是"：

• 错误数：4（样本1,2,6,8）
• 错误率：$C(1) = \frac{4}{10} = 0.4$

计算 $\alpha(1)$：

$$
\alpha(1) = \frac{C(1) - C(T_1)}{|T_1| - 1} = \frac{0.4 - 0.3}{4 - 1} = \frac{0.1}{3} = 0.0333...
$$

7.2 第一次剪枝

$\alpha$ 值汇总：

选择最小 $\alpha$ 值： 节点1（$\alpha = 0.0333...$）

但是，通常从叶节点开始剪枝，所以先选择节点5（$\alpha = 0.25$）

剪枝节点5：

将节点5剪枝为叶节点，使用多数类"是"。

剪枝后的树 $T_1$：

树T1（剪枝节点5后）：
                    [根节点：D(10个样本)]
                    Gini(D) = 0.48
                           |
                    [特征：天气=阴?]
                    /            \
            [是:3]            [否:7]
         Gini=0.000        Gini=0.408
            |                  |
    [叶节点:是]        [特征：湿度=高?]
                    /            \
                [是:3]        [否:4]
            Gini=0.000    Gini=0.000
                |              |
        [叶节点:是]    [叶节点:是]

树 $T_1$ 的统计：

• 叶节点数量：$|T_1| = 3$

计算 $C(T_1)$：

使用训练集验证：

• 样本1：预测=是，实际=否，错误
• 样本2：预测=是，实际=否，错误
• 样本3：预测=是，实际=是，正确
• 样本4：预测=是，实际=是，正确
• 样本5：预测=是，实际=是，正确（节点5剪枝后预测为"是"）
• 样本6：预测=是，实际=否，错误（节点5剪枝后预测为"是"，原来是"否"）
• 样本7：预测=是，实际=是，正确
• 样本8：预测=是，实际=否，错误
• 样本9：预测=是，实际=是，正确
• 样本10：预测=是，实际=是，正确

错误数： 4（样本1,2,6,8）
错误率： $C(T_1) = \frac{4}{10} = 0.4$

7.3 第二次剪枝

重新计算剩余节点的 $\alpha$ 值：

节点3： 天气≠阴，湿度=高?

子树 $T_3$（剪枝后）：

• 节点4：湿度=高，叶节点：是
• 节点5（已剪枝）：湿度=正常，叶节点：是

计算 $C(T_3)$：

使用训练集中属于节点3的样本（样本1,2,4,5,6,8,9,10）：

• 样本1：预测=是，实际=否，错误
• 样本2：预测=是，实际=否，错误
• 样本4：预测=是，实际=是，正确
• 样本5：预测=是，实际=是，正确
• 样本6：预测=是，实际=否，错误
• 样本8：预测=是，实际=否，错误
• 样本9：预测=是，实际=是，正确
• 样本10：预测=是，实际=是，正确

错误数： 4
错误率： $C(T_3) = \frac{4}{8} = 0.5$

计算 $C(3)$：

节点3的多数类：是

• 错误数：4（样本1,2,6,8）
• 错误率：$C(3) = 0.5$

计算 $\alpha(3)$：

$$
\alpha(3) = \frac{C(3) - C(T_3)}{|T_3| - 1} = \frac{0.5 - 0.5}{2 - 1} = \frac{0}{1} = 0
$$

节点1： 根节点

计算 $C(T_1)$：

$C(T_1) = 0.4$

计算 $C(1)$：

节点1的多数类：是

• 错误数：4（样本1,2,6,8）
• 错误率：$C(1) = 0.4$

计算 $\alpha(1)$：

$$
\alpha(1) = \frac{C(1) - C(T_1)}{|T_1| - 1} = \frac{0.4 - 0.4}{3 - 1} = \frac{0}{2} = 0
$$

$\alpha$ 值汇总：

选择节点3进行剪枝（$\alpha = 0$，剪枝后错误率不变）

剪枝节点3：

将节点3剪枝为叶节点，使用多数类"是"。

剪枝后的树 $T_2$：

树T2（剪枝节点3后）：
                    [根节点：D(10个样本)]
                    Gini(D) = 0.48
                           |
                    [特征：天气=阴?]
                    /            \
            [是:3]            [否:7]
         Gini=0.000        Gini=0.000
            |                  |
    [叶节点:是]        [叶节点:是]

树 $T_2$ 的统计：

• 叶节点数量：$|T_2| = 2$

计算 $C(T_2)$：

使用训练集验证：

• 所有样本预测为"是"
• 错误数：4（样本1,2,6,8）
• 错误率：$C(T_2) = 0.4$

7.4 第三次剪枝

重新计算节点1的 $\alpha$ 值：

节点1： 根节点

计算 $C(T_1)$：

$C(T_1) = C(T_2) = 0.4$

计算 $C(1)$：

节点1的多数类：是

• 错误数：4
• 错误率：$C(1) = 0.4$

计算 $\alpha(1)$：

$$
\alpha(1) = \frac{C(1) - C(T_1)}{|T_1| - 1} = \frac{0.4 - 0.4}{2 - 1} = \frac{0}{1} = 0
$$

剪枝节点1：

将节点1剪枝为叶节点，使用多数类"是"。

剪枝后的树 $T_3$：

树T3（剪枝节点1后）：
                    [根节点：D(10个样本)]
                           |
                    [叶节点:是]

树 $T_3$ 的统计：

• 叶节点数量：$|T_3| = 1$

计算 $C(T_3)$：

$C(T_3) = 0.4$

7.5 剪枝序列总结

剪枝序列：

注意： 由于节点3和节点1的 $\alpha$ 值都是0，它们会在 $\alpha = 0$ 时被剪枝。

第八部分：剪枝后的树结构

8.1 使用验证集选择最优树

验证集（样本11-14）：

评估各树在验证集上的表现：

树 $T_0$（完整树）：

• 样本11：预测=是，实际=是，正确
• 样本12：预测=是，实际=是，正确
• 样本13：预测=是，实际=是，正确
• 样本14：预测=是，实际=否，错误
• 验证错误数： 1
• 验证错误率： $\frac{1}{4} = 0.25$

树 $T_1$（剪枝节点5后）：

• 样本11：预测=是，实际=是，正确
• 样本12：预测=是，实际=是，正确
• 样本13：预测=是，实际=是，正确
• 样本14：预测=是，实际=否，错误
• 验证错误数： 1
• 验证错误率： $\frac{1}{4} = 0.25$

树 $T_2$（剪枝节点3后）：

• 所有样本预测=是
• 样本11：预测=是，实际=是，正确
• 样本12：预测=是，实际=是，正确
• 样本13：预测=是，实际=是，正确
• 样本14：预测=是，实际=否，错误
• 验证错误数： 1
• 验证错误率： $\frac{1}{4} = 0.25$

树 $T_3$（根节点）：

• 所有样本预测=是
• 验证错误数： 1
• 验证错误率： $\frac{1}{4} = 0.25$

所有树的验证错误率相同，选择最简单的树： $T_2$ 或 $T_3$

8.2 最优树结构

选择树 $T_2$（平衡复杂度和准确率）：

最优树T2：
                    [根节点：D(10个样本)]
                    Gini(D) = 0.48
                           |
                    [特征：天气=阴?]
                    /            \
            [是:3]            [否:7]
         Gini=0.000        Gini=0.000
            |                  |
    [叶节点:是]        [叶节点:是]

树 $T_2$ 的文本表示：

如果 天气 = 阴：
    返回 是
否则（天气 ≠ 阴）：
    返回 是

简化后：

返回 是

实际上，树 $T_2$ 可以进一步简化为根节点。

8.3 树的图示

完整树 $T_0$：

                    ┌─────────────────┐
                    │  根节点(10样本) │
                    │ Gini(D) = 0.48  │
                    └────────┬────────┘
                             │
                    ┌────────▼────────┐
                    │  特征：天气=阴? │
                    └───┬────────────┘
                        │
            ┌───────────┴───────────┐
            │                       │
    ┌───────▼──────┐       ┌───────▼──────┐
    │ 是 (3样本)   │       │ 否 (7样本)   │
    │ Gini=0.000   │       │ Gini=0.408   │
    └───────┬──────┘       └───────┬──────┘
            │                      │
    ┌───────▼──────┐       ┌───────▼────────┐
    │ 叶节点:是    │       │ 特征：湿度=高? │
    └──────────────┘       │ GiniGain=0.091 │
                           └───┬────────────┘
                               │
                   ┌───────────┴───────────┐
                   │                       │
           ┌───────▼──────┐       ┌───────▼──────┐
           │ 是 (3样本)   │       │ 否 (4样本)   │
           │ Gini=0.000   │       │ Gini=0.375   │
           └───────┬──────┘       └───────┬──────┘
                   │                      │
           ┌───────▼──────┐       ┌───────▼────────┐
           │ 叶节点:是    │       │ 特征：风力=弱? │
           └──────────────┘       │ GiniGain=0.125 │
                                  └───┬────────────┘
                                      │
                          ┌───────────┴───────────┐
                          │                       │
                  ┌───────▼──────┐       ┌───────▼──────┐
                  │ 是 (3样本)   │       │ 否 (1样本)   │
                  │ Gini=0.000   │       │ Gini=0.000   │
                  └───────┬──────┘       └───────┬──────┘
                          │                      │
                  ┌───────▼──────┐       ┌───────▼──────┐
                  │ 叶节点:是    │       │ 叶节点:否    │
                  └──────────────┘       └──────────────┘

剪枝后的树 $T_2$：

                    ┌─────────────────┐
                    │  根节点(10样本) │
                    │ Gini(D) = 0.48  │
                    └────────┬────────┘
                             │
                    ┌────────▼────────┐
                    │  特征：天气=阴? │
                    └───┬────────────┘
                        │
            ┌───────────┴───────────┐
            │                       │
    ┌───────▼──────┐       ┌───────▼──────┐
    │ 是 (3样本)   │       │ 否 (7样本)   │
    │ Gini=0.000   │       │ Gini=0.000   │
    └───────┬──────┘       └───────┬──────┘
            │                      │
    ┌───────▼──────┐       ┌───────▼──────┐
    │ 叶节点:是    │       │ 叶节点:是    │
    └──────────────┘       └──────────────┘

第九部分：其他剪枝方法

9.1 错误率降低剪枝（REP）

方法：

1. 使用验证集评估
2. 对于每个节点，如果剪枝后验证集错误率降低或不变，则剪枝
3. 自底向上剪枝

优点：

• 简单直观
• 效果通常较好

缺点：

• 需要单独的验证集
• 可能过度剪枝

9.2 悲观错误剪枝（PEP）

方法：

• 使用统计方法估计错误率
• 不需要单独的验证集
• 基于二项分布

公式：

$$
e'(t) = \frac{e(t) + 0.5}{n(t)}
$$

其中：

• $e(t)$：节点 $t$ 的错误数
• $n(t)$：节点 $t$ 的样本数
• $e'(t)$：调整后的错误率

剪枝条件：

如果剪枝后的错误率估计小于等于子树错误率估计的上界，则剪枝。

9.3 最小错误剪枝（MEP）

方法：

• 基于贝叶斯理论
• 最小化期望错误率
• 考虑先验概率

优点：

• 理论基础扎实
• 不需要验证集

缺点：

• 计算复杂
• 需要先验知识

总结与回顾

核心概念回顾

1. 过拟合问题

   • 树太复杂，对训练数据过度拟合
   • 训练准确率高，但泛化能力差

2. 剪枝的目的

   • 减少树的复杂度
   • 提高泛化能力
   • 在准确率和复杂度之间平衡

3. 预剪枝 vs 后剪枝

   • 预剪枝：构建过程中停止
   • 后剪枝：构建完整树后剪枝（通常效果更好）

4. 代价复杂度剪枝

   • 平衡准确率和复杂度
   • 使用复杂度参数 $\alpha$ 控制剪枝程度
   • 产生一系列最优子树

关键公式汇总

代价复杂度函数：
$$
C_\alpha(T) = C(T) + \alpha |T|
$$

节点的 $\alpha$ 值：
$$
\alpha(t) = \frac{C(t) - C(T_t)}{|T_t| - 1}
$$

其中：

• $C(T)$：树 $T$ 的错误率
• $|T|$：树 $T$ 的叶节点数量
• $\alpha$：复杂度参数
• $C(t)$：节点 $t$ 剪枝后的错误率
• $C(T_t)$：子树 $T_t$ 的错误率
• $|T_t|$：子树 $T_t$ 的叶节点数量

剪枝算法流程

代价复杂度剪枝流程：

1. 构建完整树：使用训练集构建完整的决策树
2. 计算 $\alpha$ 值：对于每个非叶节点，计算 $\alpha(t)$
3. 选择最小 $\alpha$：选择 $\alpha(t)$ 最小的节点
4. 执行剪枝：将选定的节点剪枝为叶节点
5. 重复步骤2-4：直到只剩下根节点
6. 选择最优树：使用验证集选择最优的子树

学习要点

1. 理解过拟合问题：为什么需要剪枝
2. 掌握代价复杂度剪枝：最常用的剪枝方法
3. 理解 $\alpha$ 参数：控制剪枝程度的关键参数
4. 掌握剪枝流程：自底向上，逐步剪枝
5. 理解剪枝效果：在复杂度和准确率之间平衡

实际应用建议

1. 参数选择：

   • 使用交叉验证选择最优的 $\alpha$
   • 或者使用验证集评估不同子树

2. 预剪枝参数：

   • max_depth：限制最大深度
   • min_samples_split：最小分裂样本数
   • min_samples_leaf：最小叶节点样本数

3. 后剪枝：

   • 使用代价复杂度剪枝
   • 使用验证集选择最优子树

4. 模型评估：

   • 使用测试集评估最终模型
   • 比较剪枝前后的性能

延伸学习

• 交叉验证：如何选择最优的剪枝参数
• 其他剪枝方法：REP、PEP、MEP的详细实现
• 集成方法：随机森林如何通过集成减少过拟合
• 正则化：其他防止过拟合的方法