第4章：决策树 — 西瓜书学习笔记

本文是周志华《机器学习》（西瓜书）第4章 决策树（Decision Trees）的学习笔记，涵盖本章所有核心知识点，配有通俗类比与公式推导。

决策树是一棵用于分类的树形结构：内部节点对应属性测试，分支对应该属性的可能取值，叶子节点给出分类结果。

算法：TreeGenerate(D)

生成节点 node
if D 中样本全属于同一类别 C：
将 node 标记为 C 类叶节点；return
if A = ∅ OR D 中样本在 A 上取值相同：
将 node 标记为 D 中样本数最多的类；return
从 A 中选最优划分属性 a*
for a* 的每个取值 a_v：
为 node 生成一个分支；令 D_v 为在 a* 上取值为 a_v 的样本子集
if D_v = ∅：将分支节点标记为 D 中样本数最多的类
else：以 TreeGenerate(D_v, A \ {a*}) 为分支节点

🍉 通俗类比

决策树就像你玩**”是谁杀了小明”**的推理游戏。每个问题（节点）都是一个关于嫌疑人的属性测试：ta是男是女？有没有不在场证明？案发时在不在现场？每答一个问题就排除一批人，最后剩下唯一嫌疑人（叶子节点）。

💡 技巧提示

核心问题：第4步中如何选择”最优划分属性”？ —— 这就引出了信息增益、增益率、基尼指数三种度量。

信息熵度量样本集合的纯度，熵越小纯度越高：

📐 公式

\text{Ent}(D) = -\sum_{k=1}^{|Y|} p_k \log_2 p_k

属性 $a$ 对 $D$ 划分的信息增益：

📐 公式

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

选择最大化 $\text{Gain}$ 的属性。ID3 算法完全基于信息增益。

⚠️ 注意事项

信息增益的偏好问题：信息增益对可取值数目较多的属性有偏好（如”编号”这个属性，每个样本取值都不同，信息增益最大但不具备泛化能力）。

引入**固有值（IV）**来惩罚取值过多的属性：

📐 公式

\text{Gain\_ratio}(D,a) = \frac{\text{Gain}(D,a)}{\text{IV}(a)},\quad \text{IV}(a) = -\sum_{v=1}^V \frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}

C4.5 的启发式策略：先从候选属性中找 信息增益高于平均水平 的属性，再从中选增益率最高的。

基尼值度量从 $D$ 中随机抽两个样本属于不同类的概率（越小越纯）：

📐 公式

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

属性 $a$ 的基尼指数（加权和）：

📐 公式

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

选基尼指数最小的属性。CART 只生成二叉树。

决策树容易过拟合——树枝太多，把训练集的噪声也学到了。剪枝是对抗过拟合的核心武器。

类型	时机	做法	特点
预剪枝	生成过程中	划分前评估划分能否提升验证集精度，不能则停止	省时间，但可能欠拟合（贪心，当前不提升不代表孩子不提升）
后剪枝	生成完整树后	自底向上，若剪掉子树（替换为叶节点）能提升验证集精度，则剪	泛化更好，但训练开销大

🍉 通俗类比

预剪枝 = 小孩学走路时，父母觉得走两步要摔了就说”别走了”。后剪枝 = 先让他自由走，等都走完了，再回头把那些摔倒的动作裁剪掉。后剪枝保留的可能性更大，泛化也更好。

💡 技巧提示

实际中后剪枝比预剪枝更常用。C4.5 使用 PEP（悲观错误剪枝），CART 使用 CCP（代价复杂度剪枝）。

基本思路：二分法（bi-partition）。将连续属性 $a$ 的所有取值排序，取相邻值的中点作为候选划分点：

📐 公式

T_a = \left\{\frac{a^i + a^{i+1} }{2} \;\middle|\; 1 \le i \le n-1\right\}

对每个候选划分点，像离散属性一样计算信息增益，选最好的。注意：连续属性在后代节点中仍可继续使用（不像离散属性被移除）。

C4.5 方案（两阶段）：

🍉 通俗类比

连续值二分法就像切西瓜——一刀下去（某个阈值），左边是甜的，右边是淡的。CART 用二叉树天然适配这个思路，所以 CART 处理连续值特别自然。

标准决策树的分类边界是**轴平行（axis-parallel）**的——每个划分只用单个属性，导致边界像楼梯一样锯齿状。

多变量决策树（斜决策树）：每个非叶节点用一个属性的线性组合 $\sum w_i a_i = t$ 来测试，边界变成一条斜线。表达能力更强，但训练也更复杂。

📌 核心定义

一句话总结：决策树 = 最优属性递归划分 + 剪枝防过拟合。可解释性最强、对数据预处理要求最低的模型，同时也是随机森林和 GBDT 等集成方法的基石。