Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 9: Decision Trees

目录 · ← l8 · l10 →

Lecture 9: Decision Trees

概述

本讲介绍决策树 (Decision Trees)——一种直观、可解释、无需特征缩放的分类/回归模型。核心问题：如何自动选择“先问哪个特征、按什么阈值切分”来构建树？答案是信息论准则：每次分裂选择使“混乱度”下降最多的特征（信息增益 / Gini 不纯度）。本讲还讨论树的过拟合控制（预剪枝/后剪枝）与集成（随机森林）。

核心概念与数学直觉

  • 决策树结构：一棵树由内部节点（特征测试，如“年龄 < 30？”）与叶节点（预测标签）组成。预测 = 沿根到叶的路径走一遍。
    • 直观解释：像“二十问”游戏——每次问一个最能区分答案的问题，逐步缩小范围，直到确定答案。
    • 优点：可解释（人类可读的规则集）、天然处理混合类型特征、不需特征缩放、对非线性关系友好。
    • 缺点：单棵树易过拟合、不稳定（数据小扰动→树结构大变）；对特征交互的表达依赖深树。
  • 熵与信息增益 (Entropy & Information Gain)：
    • 熵 (Entropy)：衡量集合的“混乱度/不确定性”： $H(S) = -\sum_{c=1}^{C} p_c \log_2 p_c$
      • $p_c$：集合 $S$ 中类别 $c$ 的比例。
      • 直觉：全部同一类 ⇒ $p=1$ ⇒ $H=0$（最“纯”）；均匀分布 ⇒ $H = \log_2 C$（最混乱）。熵 = 编码一个样本的类别所需的平均比特数。
    • 信息增益 (Information Gain)：按特征 $A$ 分裂后熵的减少量： $\text{Gain}(S, A) = H(S) - \sum_{v \in \text{values}(A)} \frac{\|S_v\|}{\|S\|} H(S_v)$
      • $S_v$：特征 $A$ 取值 $v$ 的样本子集。
      • 直觉：分裂后子集的加权熵越小（越纯），信息增益越大——每次选信息增益最大的特征分裂（贪心）。
    • Gini 不纯度（CART 用）：$\text{Gini}(S) = 1 - \sum_c p_c^2$——随机抽取两个样本类别不同的概率。Gini 与熵行为类似，计算更便宜。
    • 回归树：分裂目标改为最小化子集内方差（MSE 下降量），叶节点输出均值。
  • 过拟合控制：
    • 预剪枝 (Pre-pruning)：限制最大深度、最小叶节点样本数、最小分裂增益。
    • 后剪枝 (Post-pruning)：先长满树，再从底向上评估“剪掉子树换成叶”是否提升验证集性能。
    • 随机森林 (Random Forest)：Bagging + 随机特征子集——训练多棵（在自助采样子集上、每层只用随机子集特征）的树，投票集成。随机性降低树间相关性 ⇒ 大幅降方差。

算法伪代码与逻辑解说：ID3/CART 式决策树构建

伪代码

输入:
    - 训练集 S（样本+标签），特征集 F，超参数（max_depth, min_samples_split, min_gain）

输出:
    - 决策树 T

函数 BuildTree(S, F, depth):
1. 若满足停止条件（depth >= max_depth 或 |S| < min_samples_split 或
    S 中所有样本同类别 或 F 为空）:
    1.1 返回叶节点，标签 = S 中多数类（回归为均值）
2. 对每个特征 f ∈ F（及每个候选分裂点/阈值）:
    2.1 计算分裂后的信息增益 Gain(S, f)（或 Gini 下降 / MSE 下降）
3. 选择增益最大的特征 f*（及最优阈值）
4. 若 Gain(S, f*) < min_gain: 返回叶节点（多数类）
5. 用 f* 把 S 划分为子集 S_1, ..., S_v
6. 对每个子集 S_v: child_v = BuildTree(S_v, F \ {f*}, depth+1)
7. 返回内部节点 (f*, children)

预测: 沿根到叶的路径，返回叶节点标签

【算法逻辑解说】

  1. Step 1 停止条件：防止无限生长与过拟合。叶节点输出多数类（分类）或均值（回归）——叶是“局部常数模型”。
  2. Step 2–3 贪心分裂：在每个节点独立地选“当前最有区分力的特征”——这是贪心策略（不回溯、不考虑未来分裂），计算高效但可能错过全局最优树（NP-hard 问题的实用近似）。
  3. 连续特征：按值排序后尝试相邻点中点为阈值，选增益最大的阈值。
  4. Step 6 递归：分治——每个子问题与父问题同构，天然递归实现。特征不重复使用（ID3 风格）或可重复使用（CART 风格，对连续特征常重复）。
  5. 预测复杂度：$O(\text{深度})$——极快，适合低延迟推理。
  6. 与偏差-方差的关系：单棵树高方差（换数据大变）；剪枝/限制深度=正则化（升偏差降方差）；随机森林=集成降方差。

关键要点

  1. 决策树 = 递归划分特征空间；分裂准则（熵/Gini/MSE）衡量“纯化程度”。
  2. 熵是信息论的“混乱度”度量：信息增益 = 分裂带来的不确定性减少。
  3. 树的主要敌人是过拟合：深度、叶大小、min_gain 是正则化旋钮；后剪枝用验证集。
  4. 随机森林通过 Bagging + 随机特征子集大幅降低方差，是树的实用形态。
  5. 树的可解释性（规则集）是相对神经网络的核心优势。

常见误区与注意事项

  • 不设停止条件导致过拟合：满树在训练集误差 0，但泛化差。务必限制深度/叶大小或剪枝。
  • 用信息增益做多值特征时偏好取值多的特征：ID3 的 Gain 偏向取值数多的特征（如 ID 列）；可用增益率 (Gain Ratio) 或 CART 的 Gini 缓解。
  • 忽视类别不平衡：多数类主导叶标签；可用加权分裂或过采样。
  • 在需要概率输出的场景直接用树：单树输出是硬标签；概率需要叶内比例（校准差）或改用梯度提升树（GBDT 可输出分数）。
  • 树的“不稳定”不等于“不好”：单树方差大是特性；集成（RF/GBDT）才是树的完整形态，实践中几乎总是用集成。

思考题

  1. 问题：为什么熵的公式是 $-\sum p_c \log p_c$？它如何度量“编码成本”？
    • 答案：信息论中，编码概率 $p$ 的事件最优需 $\log_2(1/p) = -\log_2 p$ 比特（香农）。熵 = 各事件编码长度的期望。类别越不确定（分布越均匀），平均编码越长——熵高 = 混乱。
  2. 问题：一个数据集的标签全为“猫”，另一个猫狗各半，哪个熵大？分裂后信息增益可能为负吗？
    • 答案：前者 $H = -1\log 1 = 0$，后者 $H = -2 \times 0.5\log 0.5 = 1$。信息增益理论上 $\ge 0$（$H$ 是凹函数，加权平均子集熵 $\le$ 原熵，Jensen 不等式）；但若用验证集评估或分裂准则不一致，观测值可能“虚增”不提升真实泛化——这也是需要剪枝校验的原因。
  3. 问题：为什么随机森林要随机选特征子集，而不只是 Bagging？
    • 答案：若所有树都用全部特征，Bagging 后树间仍高度相关（强特征被所有树首选），集成方差下降有限。随机特征子集迫使树“各看各的角度”，降低相关性——集成效果随树间不相关性提升。这是“多样性是集成之本”的体现。