Skip to content

Chapter 6 决策树

我们要讲的故事

疾旋鼬经过一段时间的学习，总结出了一套挑瓜流程：先看纹理——清晰的好，模糊的坏；纹理稍糊的，再看触感——硬滑的好，软粘的坏。画出来就是一棵树。

纹理?
├── 清晰 → 好瓜
├── 稍糊
│   └── 触感?
│       ├── 硬滑 → 好瓜
│       └── 软粘 → 坏瓜
└── 模糊 → 坏瓜

决策树 (Decision Tree) 的核心思想：通过一系列"判断"逐步缩小范围，最终得到结论。

一、基本结构

  • 内部结点：对应某个属性上的"测试"
  • 分支：对应测试的一种可能结果
  • 叶结点：对应一个预测结果

策略："分而治之" (divide-and-conquer)，自根至叶的递归过程。

三种停止条件： 1. 当前结点样本全属同一类别 2. 属性集为空，或所有样本在所有属性上取值相同 3. 当前结点样本集合为空

二、划分选择

信息增益 (Information Gain)

信息熵 (entropy)：度量样本集合"纯度"的指标。设样本集 \(D\) 中第 \(k\) 类的比例为 \(p_k\)：

\[\text{Ent}(D) = -\sum_{k=1}^{|\mathcal{Y}|} p_k \log_2 p_k\]
  • \(\text{Ent}(D)\) 越小，纯度越高
  • 所有样本同类 → \(\text{Ent}(D) = 0\)
  • 二分类且 \(p_1 = p_2 = 0.5\) → \(\text{Ent}(D) = 1\)

以属性 \(a\)（\(V\) 个取值）划分，第 \(v\) 个分支含 \(D^v\) 个样本：

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

ID3 算法使用信息增益。

问题：信息增益对可取值数目较多的属性有偏好。极端：把"编号"作为属性，信息增益最大。

一个例子（17 个西瓜样本，2 类）：

根结点熵：\(\text{Ent}(D) = -\frac{8}{17}\log_2\frac{8}{17} - \frac{9}{17}\log_2\frac{9}{17} = 0.998\)

以"色泽"（3 取值：青绿 6、乌黑 6、浅白 5）划分：

\[\text{Gain}(D, \text{色泽}) = 0.998 - \frac{6}{17}\text{Ent}(D^{\text{青绿}}) - \frac{6}{17}\text{Ent}(D^{\text{乌黑}}) - \frac{5}{17}\text{Ent}(D^{\text{浅白}}) = 0.109\]

类似计算所有属性，选信息增益最大的"纹理"作为根结点划分属性。

增益率 (Gain Ratio)

C4.5 算法使用增益率。

\[\text{GainRatio}(D, a) = \frac{\text{Gain}(D, a)}{\text{IV}(a)}\]

其中 \(\text{IV}(a) = -\sum_{v=1}^V \frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}\) 是属性 \(a\) 的固有值。取值数目越多，IV 越大。

增益率对可取值数目少的属性有偏好。C4.5 的启发式：先找信息增益高于平均水平的属性，再从中选增益率最高的。

基尼指数 (Gini Index)

CART 算法使用基尼指数。

\[\text{Gini}(D) = \sum_{k=1}^{|\mathcal{Y}|}\sum_{k' \neq k} p_k p_{k'} = 1 - \sum_{k=1}^{|\mathcal{Y}|} p_k^2\]

反映从 \(D\) 中随机抽取两个样本，其类别不一致的概率。\(\text{Gini}(D)\) 越小，纯度越高。

\[\text{GiniIndex}(D, a) = \sum_{v=1}^V \frac{|D^v|}{|D|}\text{Gini}(D^v)\]

选使划分后基尼指数最小的属性。

研究表明：划分选择准则对泛化性能影响有限（信息增益与基尼指数仅约 2% 情况不同），但剪枝方法对泛化性能影响很大（可提升 25%）。

三、剪枝

预剪枝 (Pre-pruning)

在生成过程中，提前终止某些分支的生长。每个结点划分前，先评估划分后验证集精度是否提升： - 提升 → 允许划分 - 不提升 → 禁止划分

优点：训练时间降低，过拟合风险降低。 缺点：可能欠拟合——有些划分单次看无用，组合起来却有用。

后剪枝 (Post-pruning)

先生成完整决策树，再自底向上逐一考察：将子树替换为叶结点，验证集精度是否提升？ - 提升 → 剪枝 - 不提升 → 保留

优点：泛化性能通常优于预剪枝。 缺点：训练时间增加。

后剪枝通常优于预剪枝。

四、连续值与缺失值

连续值处理

二分法：将 \(n\) 个属性值排序，取相邻值的中点为候选划分点（共 \(n-1\) 个），选信息增益最大的：

\[\text{Gain}(D, a) = \max_t \text{Gain}(D, a, t)\]

缺失值处理

仅用无缺失值样本计算信息增益，再乘以无缺失样本比例 \(\rho\) 修正：

\[\text{Gain}(D, a) = \rho \cdot \text{Gain}(\tilde{D}, a)\]

划分时，缺失值样本同时进入所有分支，但带权重（权重按各分支无缺失样本比例分配）。

五、从树到规则

每条从根到叶的路径对应一条 IF-THEN 规则： - IF (纹理=清晰) AND (密度>0.381) THEN 好瓜 - IF (纹理=模糊) THEN 坏瓜

好处：改善可理解性；规则合并、泛化后泛化能力可能优于决策树。

六、多变量决策树

标准决策树产生轴平行分类边界。当真实边界是斜线时，需要很多段才能近似。

多变量决策树：在每个非叶结点建立线性分类器，产生倾斜甚至曲线的分类边界。

决策树简史

年代 算法 作者 特点
1966 CLS Hunt et al. 第一个决策树算法
1979 ID3 Quinlan 信息增益
1993 C4.5 Quinlan 增益率，连续值/缺失值
1984 CART Breiman et al. 基尼指数，可做回归
2001 Random Forest Breiman 集成学习

2026.06