本文依照《机器学习从原理到应用》（卿来云、黄庆明编著，人民邮电出版社，2020 年第一版）的目录顺序整理，为系列的第五篇，覆盖非线性模型中的决策树部分。决策树是最贴近人类决策过程的模型，也是后续集成学习（随机森林、GBDT）的基学习器，承上启下。

---

〇、本章知识地图

基本结构：根节点 / 内部节点 / 叶节点
  → 学习流程：递归分治（选特征 → 划分 → 停止）
  → 核心问题1：按什么标准选特征？—— 信息增益(ID3) / 增益率(C4.5) / 基尼指数(CART)
  → 核心问题2：如何防止过拟合？—— 预剪枝 / 后剪枝
  → 工程细节：连续值离散化、缺失值处理

决策树学习的本质：在特征空间中递归地进行轴平行划分，使每个子区域尽可能"纯"。

一、基本结构与学习流程

1.1 树的组成

• 根节点：包含全部训练样本；
• 内部节点：对应一个特征测试（如"年龄 ≤ 30？"）；
• 叶节点：对应决策结果（类别或数值）。

从根到叶的一条路径就是一条 if-then 规则，整棵树等价于一组规则的析取——这是决策树可解释性强的根本原因。

1.2 递归学习流程

决策树的生成是一个分治过程，对当前节点执行三步：

1. 选特征：按某种准则选出当前最优的划分特征；
2. 做划分：按特征取值把样本分到各子节点；
3. 判停止：满足停止条件则标记为叶节点，否则对子节点递归。

停止条件（常考）：当前节点样本全部同类；无可用特征（或特征取值全相同）；样本数低于阈值或树达到最大深度。

二、划分选择准则（本章核心考点）

2.1 信息熵

度量样本集合"纯度"的基本工具。集合 D 中第 k 类样本比例为 ，则信息熵为：

性质：熵越小，纯度越高。全部同类时熵为 0；各类均分时熵最大（二分类时为 1）。

2.2 信息增益（ID3 算法）

特征 a 把 D 划分为若干子集 ，信息增益 = 划分前的熵 − 划分后的加权平均熵：

ID3 算法选择信息增益最大的特征。缺陷：偏好取值多的特征（极端例子：以"学号"为特征，每个子集只含一个样本，熵为 0，增益最大，但毫无泛化能力）。这一缺陷是必考点。

2.3 增益率（C4.5 算法）

为矫正上述偏好，C4.5 引入特征自身的固有值（Intrinsic Value）作分母：

取值越多的特征 IV 越大，增益率被压低。注意 C4.5 的实际策略是"先从候选中找出增益高于平均的特征，再从中选增益率最大者"，而非直接最大化增益率。

2.4 基尼指数（CART 算法）

CART 树使用基尼指数度量纯度：

基尼指数越小纯度越高，选择使划分后加权基尼指数最小的特征。CART 生成二叉树，同时支持分类（基尼指数）与回归（平方误差）。

2.5 三个准则对比表

	ID3	C4.5	CART
划分准则	信息增益	增益率	基尼指数（分类）/ 平方误差（回归）
树结构	多叉	多叉	二叉
对取值多特征	偏好	矫正	相对不敏感
支持回归	否	否	是
连续值/缺失值	不支持	支持	支持

三、剪枝：决策树的过拟合对策

决策树生长过深会记住训练集的噪声（过拟合的典型例子，呼应复习(1)）。剪枝是标准对策，分两类：

	预剪枝	后剪枝
时机	划分之前评估，不提升验证集性能则停止	先长成完整树，再自底向上考察是否合并
判断依据	划分前后验证集精度	子树替换为叶节点后验证集精度
优点	训练快、开销小	保留信息充分，通常效果更好
缺点	可能欠拟合（视野效应：当前不划算的划分可能有利的后续划分）	训练开销大

记忆要点：预剪枝"先停"，风险是欠拟合；后剪枝"长完再修"，代价是慢。

四、连续值与缺失值（了解即可）

• 连续值：二分法离散化——把候选切分点排序，逐一尝试，选信息增益最大的切分点（如"年龄 ≤ 30"）；
• 缺失值：C4.5 的做法是让含缺失值的样本以权重方式同时进入各子节点，权重正比于子节点样本占比。

五、决策树优缺点

优点	缺点
可解释性极强（可视化为一组规则）	单棵树极易过拟合（方差大）
无需特征缩放，对量纲不敏感	对数据扰动敏感，小改动可能长出完全不同的树
同时处理数值与类别特征	轴平行划分，表达斜边界能力弱
训练快	类别不均衡时偏向多数类

"单树方差大"这一缺点正是下一篇集成学习的出发点：随机森林与 GBDT 都是围绕"如何组合多棵决策树"展开的。

附：代码实践（动手 10 分钟）

片段 1：决策树深度与过拟合——直观验证剪枝的必要性。

from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0)

for depth in [2, 4, None]:   # None = 不限制深度（不剪枝）
    clf = DecisionTreeClassifier(max_depth=depth, random_state=0)
    clf.fit(X_train, y_train)
    print(f"max_depth={str(depth):>4}  训练准确率={clf.score(X_train, y_train):.3f}  "
          f"测试准确率={clf.score(X_test, y_test):.3f}")

预期现象：不限深度时训练准确率达到 1.000 而测试准确率反而下降——教科书式的过拟合演示。max_depth 就是最常见的预剪枝手段，同类参数还有 min_samples_split、min_samples_leaf。

片段 2：特征重要性——决策树天然给出各特征的贡献。

import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier

X, y = load_breast_cancer(return_X_y=True)
names = load_breast_cancer().feature_names
clf = DecisionTreeClassifier(max_depth=4, random_state=0).fit(X, y)

order = np.argsort(clf.feature_importances_)[::-1][:5]
for i in order:
    print(f"{names[i]:<25} 重要性={clf.feature_importances_[i]:.3f}")

重要性基于各特征在所有划分中带来的纯度提升累计——这正是第 2 节划分准则的直接产物。

六、本章自测题

1. 写出信息熵公式，并说明熵与纯度的关系。
2. 写出信息增益公式，说明 ID3 的缺陷及成因。
3. C4.5 如何矫正 ID3 的缺陷？写出增益率公式。
4. 写出基尼指数公式，说明 CART 与 ID3/C4.5 的两个主要区别。
5. 决策树递归生成的停止条件有哪些？
6. 比较预剪枝与后剪枝的流程、优点与缺点。什么是视野效应？
7. 为什么单棵决策树容易过拟合？这一缺点如何引出集成学习？
8. 决策树为什么不需要特征标准化？（与 SVM、Logistic 回归对比作答）

七、复习建议

1. 三个划分准则的公式 + "ID3 偏好取值多的特征"这一缺陷，是本章出题密度最高的区域；
2. 剪枝部分按"对比表"记忆，注意预剪枝的欠拟合风险是反向考点；
3. 学习本章时顺手把代码片段 1 跑一遍——决策树是验证"过拟合"概念成本最低的模型。