第4章决策树

🎯 学习目标

理解决策树的基本原理和递归构建过程
掌握信息增益、信息增益率、基尼指数等划分标准
理解剪枝技术如何防止过拟合
学会处理连续属性和缺失值
认识决策树的优缺点及适用场景

4.1 基本流程

🌳 什么是决策树？

决策树是一种基于树结构的分类与回归方法。它通过一系列的判断规则，将样本从根节点逐步划分到叶节点，每个叶节点对应一个类别或数值。

决策树的组成：

🔴 根节点：包含所有训练样本，树的起点
🔵 内部节点：对应一个属性测试，将样本分流
🟢 叶节点：表示决策结果（类别标签）

🔄 递归构建过程

决策树的构建是一个自顶向下的递归过程，基于分而治之策略：

选择最优划分属性：从当前节点的属性集合中，选择最能降低不确定性的属性
生成分支：根据选定属性的取值，将样本集划分到对应的子节点
递归处理子节点：对每个非空子集，递归执行上述步骤，直至满足停止条件

🛑 停止条件

当满足以下任一条件时，停止分裂并将当前节点标记为叶节点：

✓ 当前节点的所有样本属于同一类别
✓ 属性集为空，或所有样本在所有属性上取值相同
✓ 当前节点包含的样本数少于预设阈值
✓ 树的深度达到预设的最大值

4.2 划分选择

🎯 如何选择最优划分属性？

决策树学习的关键是如何选择最优划分属性。我们希望选择的属性能够最大程度地降低数据的不纯度，使得划分后的子节点尽可能"纯"（即包含单一类别的样本）。

不同的决策树算法使用不同的划分标准：ID3 使用信息增益，C4.5 使用信息增益率，CART 使用基尼指数。

信息熵 (Entropy)

📊 信息熵

信息熵是度量样本集合纯度的常用指标。假设样本集合 D 中第 k 类样本所占比例为 $p_{k}$ ，则 D 的信息熵定义为：

Ent (D) = - \sum_{k = 1}^{| Y |} p_{k} \log_{2} p_{k}

Ent(D) = 0：完全纯，所有样本同类
Ent(D) = 1：最不纯，类别均匀分布（二分类时）
Ent(D) 越大：混乱度越高

调整不同类别的样本数量，观察信息熵如何变化。熵值越小，数据集越纯；熵值越大，数据集越混乱。

当前信息熵

1.000

中等 - 数据混合

0 (完全纯)1.00 (最混乱)

Ent(D) = -Σ p_k log₂ p_k

计算过程：

p₁ = 50/100 = 0.500→-0.500 × log₂(0.500) = 0.500

p₂ = 50/100 = 0.500→-0.500 × log₂(0.500) = 0.500

总和 =1.000

调整类别分布

总样本数: 100

样本数: 50(50.0%)

类别分布

💡

观察要点：

当所有样本属于一个类别时，熵为 0（完全纯）
当各类别样本数量相等时，熵达到最大值（最混乱）
信息熵衡量的是数据集的不确定性或混乱程度
决策树的目标是通过划分降低熵，使子节点更"纯"

信息增益 (Information Gain) - ID3

信息增益表示使用属性 $a$ 进行划分所获得的"纯度提升"。信息增益越大，说明使用属性 $a$ 划分后纯度提升越大。

Gain (D, a) = Ent (D) - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} Ent (D^{v})

其中 $D^{v}$ 表示属性 $a$ 取值为 $v$ 的样本子集。

⚠️ 信息增益的偏好

信息增益倾向于选择取值数目较多的属性（如"编号"属性），这可能导致过拟合。C4.5 算法通过信息增益率来缓解这个问题。

信息增益率 (Gain Ratio) - C4.5

📊 信息增益率

信息增益率通过引入"固有值"来对信息增益进行归一化，缓解信息增益对取值数目多的属性的偏好：

Gain_ratio (D, a) = \frac{Gain (D, a)}{IV (a)}

IV (a) = - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} \log_{2} \frac{| D^{v} |}{| D |}

IV(a) 称为属性 $a$ 的固有值，属性取值数目越多，IV(a) 通常越大。

💡 C4.5 的启发式策略

先从候选属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。

基尼指数 (Gini Index) - CART

基尼指数反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率。基尼指数越小，数据集的纯度越高。

Gini (D) = 1 - \sum_{k = 1}^{| Y |} p_{k}^{2}

Gini_index (D, a) = \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} Gini (D^{v})

选择使得 Gini_index 最小的属性作为最优划分属性。

选择划分标准（信息增益、信息增益率、基尼指数），观察决策树的构建过程。点击节点查看详细信息和计算过程。

划分标准

当前使用: 信息增益 (Information Gain)

最大深度: 2

1234

特征空间与决策边界

决策树结构

💡

使用说明：

左图显示特征空间，黄色虚线是决策边界
右图显示决策树结构，点击节点查看详细信息
尝试不同的划分标准和深度，观察树结构的变化
信息增益率对取值多的属性惩罚更强，可缓解过拟合

4.3 剪枝处理

✂️ 为什么需要剪枝？

决策树在训练时为了尽可能正确分类训练样本，会不断分裂生长。这可能导致过拟合：树的分支过多过细，把训练集自身的特点当作了所有数据的一般性质。

过拟合的表现：

训练误差很低，但测试误差很高
树的深度过大，叶节点数量过多
对训练数据的噪声过度敏感

剪枝是决策树学习算法对付过拟合的主要手段，通过主动去掉部分分支来降低过拟合风险。

预剪枝 (Pre-Pruning)

在决策树生成过程中，提前停止树的生长。在每个节点划分前，先评估划分是否能提升泛化性能。

策略：

限制树的最大深度
限制节点的最小样本数
限制信息增益的最小阈值
使用验证集评估划分效果

✓ 优点：计算开销小，生成过程直接停止
✗ 缺点：可能过早停止，欠拟合风险

后剪枝 (Post-Pruning)

先生成完整的决策树，然后自底向上地检查非叶节点，若将该节点替换为叶节点能提升泛化性能，则进行剪枝。

过程：

生成完整决策树
从叶节点向上考察每个非叶节点
若剪枝后验证集性能提升，则剪枝
重复直到无法继续剪枝

✓ 优点：保留更多有用分支，泛化性能更好
✗ 缺点：训练时间更长，需要额外验证集

剪枝对比

特性	预剪枝	后剪枝
时机	生成过程中	生成完成后
计算开销	小	大
过拟合风险	低	更低
欠拟合风险	较高	低
泛化性能	较好	更好

4.4 连续值与缺失值

处理连续值属性

📏 连续属性离散化

前面讨论的都是离散属性。但实际任务中常会遇到连续属性（如身高、体重、温度）。最常用的方法是二分法（Binary Split）。

排序：将连续属性的所有取值按从小到大排序： $a^{1}, a^{2}, \dots, a^{n}$
候选划分点：考虑相邻两个值的中点： $t_{i} = (a^{i} + a^{i + 1}) / 2$
选择最优划分点：将样本分为 $\leq t$ 和 $> t$ 两部分，计算信息增益，选择最优的 $t$

💡 关键特性

与离散属性不同，连续属性在生成子树时可以继续使用（多次划分）。例如，可以先判断"年龄 ≤ 30"，在某个分支下再判断"年龄 ≤ 25"。

处理缺失值

❓ 缺失值带来的问题

现实任务中常会遇到属性值缺失的情况。这给决策树学习带来两个问题：

问题1：属性选择 — 如何在某属性值缺失的情况下，进行划分属性的选择？
问题2：样本划分 — 给定划分属性后，若某样本在该属性上的值缺失，如何对该样本进行划分？

方法1：样本权重

为每个样本赋予权重 $w$ ，初始时 $w = 1$ 。在属性选择时，只考虑该属性上无缺失值的样本，根据这些样本的权重比例来调整信息增益的计算。

ρ = \frac{\sum (无缺失样本权重)}{\sum (全部样本权重)}

方法2：同时划入多个分支

若某样本在划分属性上的值缺失，则将该样本同时划入所有子节点，但权重按子节点样本比例分配。例如：某节点有 60% 样本进入左子树，40% 进入右子树。缺失值样本以 0.6 的权重进入左子树，0.4 的权重进入右子树。

其他缺失值处理方法

删除法：直接删除包含缺失值的样本。简单但可能损失大量信息，仅适用于缺失比例很小的情况。
填充法：用某个值填充缺失值：
- 均值/众数：用该属性的平均值或最常见值填充
- 同类均值：用相同类别样本的均值填充
- 模型预测：用其他算法预测缺失值

4.5 优缺点与应用

优点

✓ 可解释性强 — 决策过程直观，可以转换为规则
✓ 处理能力强 — 可处理连续值、类别型、缺失值
✓ 无需归一化 — 对数据缩放不敏感
✓ 训练快速 — 适合大规模数据集
✓ 特征选择 — 自动进行特征筛选

缺点

✗ 容易过拟合 — 需要剪枝来控制复杂度
✗ 不稳定 — 数据微小变化可能导致树结构大变
✗ 贪心策略 — 局部最优，无法保证全局最优
✗ 类别不平衡 — 倾向于多数类
✗ 轴对齐限制 — 只能沿特征轴划分，难以处理斜向边界

实际应用场景

🏥 医疗诊断 — 根据症状、检查结果等制定诊断规则，医生可以理解决策依据
💳 信用评估 — 根据个人信息、财务状况评估信用风险，结果可解释
📧 垃圾邮件过滤 — 根据邮件特征快速判断是否为垃圾邮件
🎮 游戏AI — NPC决策树，根据玩家行为做出不同反应
🛒 推荐系统 — 根据用户画像和行为推荐商品
🔍 欺诈检测 — 识别异常交易模式，防范金融欺诈

改进与扩展

随机森林 (Random Forest) — 集成多棵决策树，通过"投票"提高稳定性和准确率。是最流行的集成学习方法之一。
梯度提升树 (GBDT) — 通过逐步拟合残差来提升性能。XGBoost、LightGBM 等是其高效实现。
多变量决策树 — 每个内部节点使用多个属性的线性组合进行测试，可以处理斜向边界。
增量学习 — 支持在线学习，新数据到来时无需重新训练整棵树。

📝 本章小结

总结

✅ 决策树通过递归划分构建树结构，每个内部节点对应属性测试，叶节点对应决策结果
✅ 信息增益（ID3）、信息增益率（C4.5）、基尼指数（CART）是三种主流的划分标准
✅ 信息熵衡量样本集合的纯度，熵越小表示纯度越高
✅ 剪枝是对抗过拟合的主要手段，分为预剪枝和后剪枝两种策略
✅ 连续值通过二分法离散化，缺失值通过样本权重和多分支划入处理
✅ 决策树具有可解释性强、训练快速等优点，但容易过拟合、对数据敏感
✅ 集成方法（如随机森林、GBDT）通过组合多棵树显著提升性能

第4章 决策树 ​

🎯 学习目标 ​

4.1 基本流程 ​

4.2 划分选择 ​

信息熵 (Entropy) ​

调整类别分布

类别分布

信息增益 (Information Gain) - ID3 ​

信息增益率 (Gain Ratio) - C4.5 ​

基尼指数 (Gini Index) - CART ​

特征空间与决策边界

决策树结构

4.3 剪枝处理 ​

预剪枝 (Pre-Pruning) ​

后剪枝 (Post-Pruning) ​

剪枝对比 ​

4.4 连续值与缺失值 ​

处理连续值属性 ​

处理缺失值 ​

其他缺失值处理方法 ​

4.5 优缺点与应用 ​

优点 ​

缺点 ​

实际应用场景 ​

改进与扩展 ​

📝 本章小结 ​