Decision Tree —— 决策树

引言

回顾第一阶段：基础监督学习的全部六篇文章——从线性回归的解析解出发，历经逻辑回归的概率建模、KNN 的非参数距离、朴素贝叶斯的生成式假设、SVM 的几何间隔最大化，到核技巧的非线性扩展。这些算法虽然方法论各异，但共享一个底层逻辑：它们都在一个预先定义的假设空间中寻找“最优”的数学函数——无论这个函数是线性超平面、概率分布还是距离度量。

决策树彻底颠覆了这套范式。它放弃了所有关于“函数形式”的预设，转而采用一种与人类决策方式高度契合的机制 —— 通过一系列“是/否”的判断，将特征空间递归地划分为矩形区域，每个区域对应一个预测值。这种“分而治之”的策略让决策树拥有了两个无可替代的优势：极致的可解释性（决策路径可以被直接转化为 if-then 规则）和对特征尺度的天然免疫（分裂仅依赖排序关系，无需任何缩放）。

本文将从决策树家族的三位核心成员出发 —— ID3、C4.5 与 CART —— 系统梳理它们在分裂准则上的根本差异：信息增益、信息增益率、基尼指数与 MSE 各自对应的数学原理与适用场景。随后我们深入剪枝策略，对比预剪枝的“防患于未然”与后剪枝（特别是 CART 的 CCP 成本复杂度剪枝）的“亡羊补牢”，揭示二者在欠拟合与过拟合之间的权衡。最后，我们将从数学上解释决策树为何对特征缩放完全不敏感 —— 这一性质使其在处理异构特征时远比 KNN 或 SVM 从容。

Note
决策树是第二阶段：树模型与集成学习的基石。理解单棵树的生长与剪枝，是后续理解 Bagging（通过抽样降低方差）、随机森林（在 Bagging 基础上引入特征随机选择）以及 AdaBoost、GBM、XGBoost（通过串行拟合残差降低偏差）的必要前提。
下一篇文章，我们将从“一棵树”走向“一片森林”——Bagging 与随机森林将展示如何通过集成学习让决策树从“易过拟合的弱学习器”蜕变为“强泛化的组合模型”。

一、ID3、C4.5与CART

决策树家族中有三大基础算法 —— ID3、C4.5和CART。它们之间的核心区别可以概括为一句话：特征选择的标准不同。

算法	提出年份	树类型	分裂准则	适用任务
ID3	1986	多叉树	信息增益	分类
C4.5	1993	多叉树	信息增益率	分类
CART	1984	二叉树	基尼指数（分类）/ MSE（回归）	分类 + 回归

1.1 ID3：信息增益的开创者

ID3（Iterative Dichotomiser 3）由Ross Quinlan于1986年提出，是决策树算法的开山之作。它的核心思想是以信息增益作为特征选择的准则，选择信息增益最大的特征进行分裂。

ID3的局限性：

只能处理离散特征，无法处理连续值，也不能处理缺失值
没有剪枝策略，容易过拟合
偏好取值多的特征 —— 比如“编号”这样的特征，信息增益会接近1，但毫无意义

1.2 C4.5：ID3的全面升级

C4.5是Quinlan对ID3的改进版本，主要解决了ID3的三大痛点：

用信息增益率代替信息增益，克服了对取值多特征的偏好
引入了连续特征离散化：将连续特征排序后，取相邻两样本值的平均数作为候选切分点
引入悲观剪枝策略进行后剪枝，能够处理缺失值

C4.5的局限性：需要多次扫描和排序数据，效率较低；只能处理分类任务，不能做回归。

1.3 CART：二叉树的全能选手

CART（Classification And Regression Tree）由Breiman等人在1984年提出，是决策树家族中最强大的成员。

CART 与 ID3 / C4.5 的关键区别：

二叉树 vs 多叉树：CART每次只将数据分成两份，生成的是二叉树，而ID3和C4.5是多叉树
分类 + 回归：CART既可以做分类（用基尼指数），也可以做回归（用MSE）
基尼指数代替熵：基尼指数只涉及平方运算，避免了熵模型中的大量对数运算，计算效率更高

代码实现：

1
from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor
2
from sklearn.datasets import make_classification, make_regression
3

4
# CART分类树（默认使用基尼指数）
5
X_clf, y_clf = make_classification(n_samples=300, n_features=4, random_state=42)
6
clf = DecisionTreeClassifier(criterion='gini', max_depth=5)
7
clf.fit(X_clf, y_clf)
8

9
# CART回归树（使用MSE）
10
X_reg, y_reg = make_regression(n_samples=300, n_features=4, noise=10, random_state=42)
11
reg = DecisionTreeRegressor(criterion='squared_error', max_depth=5)
12
reg.fit(X_reg, y_reg)

二、分裂准则的数学原理

决策树的核心问题只有一个：每次分裂时，应该选择哪个特征？在哪个阈值上分裂？ 不同的算法给出了不同的答案。下面我们逐一推导。

2.1 信息熵与信息增益（ID3）

信息熵（Entropy） —— 信息论中衡量不确定性的指标。不确定性越大，熵越大。

对于样本集合 $D$ ，假设共有 $K$ 个类别，第 $k$ 类样本所占比例为 $p_k$ ，则信息熵定义为：

H(D) = -\sum_{k=1}^{K} p_k \log_2 p_k

熵的性质：当所有样本都属于同一类别时， $H(D) = 0$ （纯度最高）；当各类别样本均匀分布时， $H(D)$ 最大（纯度最低）

条件熵 $H(D|A)$ —— 表示在已知特征 $A$ 的条件下，数据集 $D$ 的不确定性：

H(D|A) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} H(D^v)

其中 $V$ 是特征 $A$ 的取值个数， $D^v$ 是特征 $A$ 取第 $v$ 个值的样本子集。

信息增益 —— 分裂前后熵的减少量：

\boxed{\text{Gain}(D, A) = H(D) - H(D|A)}

ID3选择信息增益最大的特征进行分裂。

代码实现：

1
import numpy as np
2

3
def entropy(y):
4
    """计算信息熵"""
5
    classes = np.unique(y)
6
    probs = [np.sum(y == c) / len(y) for c in classes]
7
    return -np.sum([p * np.log2(p) for p in probs if p > 0])
8

9
def information_gain(X, y, feature_idx):
10
    """计算某个特征的信息增益"""
11
    total_entropy = entropy(y)
12
    values = np.unique(X[:, feature_idx])
13
    weighted_entropy = 0
14
    for v in values:
15
        mask = X[:, feature_idx] == v
16
        subset_y = y[mask]
17
        weighted_entropy += len(subset_y) / len(y) * entropy(subset_y)
18
    return total_entropy - weighted_entropy
19

20
# 示例：计算信息增益
21
X = np.array([[1, 0], [1, 1], [0, 0], [0, 1]])
22
y = np.array([0, 0, 1, 1])
23
print(f"特征0的信息增益: {information_gain(X, y, 0):.4f}")
24
print(f"特征1的信息增益: {information_gain(X, y, 1):.4f}")

2.2 信息增益率（C4.5）

信息增益有一个致命缺陷：偏好取值数量多的特征。比如“ID”这样的特征，每个样本取值都不同，条件熵为0，信息增益最大，但这样的分裂毫无意义。

C4.5引入了信息增益率（Gain Ratio） 来修正这一问题：

\boxed{\text{GainRatio}(D, A) = \frac{\text{Gain}(D, A)}{\text{IV}(A)}}

其中 $\text{IV}(A)$ 称为分裂信息（Intrinsic Value） ，衡量特征 $A$ 自身的信息量：

\text{IV}(A) = -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}

直观理解：特征取值越多， $\text{IV}(A)$ 越大，信息增益率就被惩罚得越狠。

C4.5选择信息增益率最大的特征进行分裂。

2.3 基尼指数（CART分类）

CART分类树使用基尼指数（Gini Index） 作为分裂准则。

基尼指数衡量的是从数据集中随机抽取两个样本，其类别不一致的概率。基尼指数越小，纯度越高。

对于样本集合 $D$ ，基尼指数定义为：

\boxed{\text{Gini}(D) = 1 - \sum_{k=1}^{K} p_k^2}

对于二分类问题，如果正类概率为 $p$ ，则：

\text{Gini}(D) = 1 - p^2 - (1-p)^2 = 2p(1-p)

对于特征 $A$ 的某个划分（CART是二叉树，每次只二分）：

\text{Gini}(D, A) = \frac{|D_1|}{|D|}\text{Gini}(D_1) + \frac{|D_2|}{|D|}\text{Gini}(D_2)

CART分类树选择基尼指数最小的特征和阈值进行分裂。

CART用基尼指数代替熵的原因
基尼指数与熵在数学上非常接近。
对于二分类问题，基尼指数 $2p(1-p)$ 与熵之半 $-p\log_2 p - (1-p)\log_2(1-p)$ 的曲线几乎重合。
但基尼指数只涉及平方运算，避免了大量的对数运算，计算效率更高。

代码实现：

1
def gini(y):
2
    """计算基尼指数"""
3
    classes = np.unique(y)
4
    probs = [np.sum(y == c) / len(y) for c in classes]
5
    return 1 - np.sum([p**2 for p in probs])
6

7
def gini_split(X, y, feature_idx, threshold):
8
    """计算在某个阈值上二分的基尼指数"""
9
    mask = X[:, feature_idx] <= threshold
10
    left_y, right_y = y[mask], y[~mask]
11
    left_weight = len(left_y) / len(y)
12
    right_weight = len(right_y) / len(y)
13
    return left_weight * gini(left_y) + right_weight * gini(right_y)

2.4 均方误差（CART回归）

当目标变量是连续值时，CART回归树使用均方误差（Mean Squared Error, MSE） 作为分裂准则。

对于节点 $m$ ，其预测值 $\hat{y}_m$ 为该节点所有样本目标值的均值，MSE为：

\text{MSE}(D) = \frac{1}{|D|}\sum_{i \in D} (y_i - \hat{y}_D)^2

其中 $\hat{y}_D = \frac{1}{|D|}\sum_{i \in D} y_i$ 。

对于某个分裂，分裂后的MSE为左右子节点MSE的加权和：

\text{MSE}_{\text{split}} = \frac{|D_1|}{|D|}\text{MSE}(D_1) + \frac{|D_2|}{|D|}\text{MSE}(D_2)

CART回归树选择使分裂后MSE最小的特征和阈值。

三、剪枝策略

决策树有一个著名的“缺点”：如果不加限制，它可以生长到完美拟合每一个训练样本 —— 直到每个叶子节点都只包含一个样本。这样的树在训练集上准确率100%，但在测试集上表现极差 —— 这就是过拟合。

剪枝（Pruning） 就是为了解决这个问题而生的。剪枝策略分为两大类：预剪枝和后剪枝。

3.1 预剪枝（Pre-Pruning）

预剪枝是在决策树生成过程中就提前停止树的生长。

常见的预剪枝条件：

参数	含义
`max_depth`	树的最大深度
`min_samples_split`	节点分裂所需的最小样本数
`min_samples_leaf`	叶子节点所需的最小样本数
`max_leaf_nodes`	最大叶子节点数
`min_impurity_decrease`	分裂所需的最小不纯度下降

优点：计算效率高，简单直接。
缺点：基于“贪心”本质，过早停止可能导致欠拟合。比如某个节点当前分裂看起来“不划算”，但再往下分裂一层后可能会有更好的效果 —— 预剪枝无法看到这种“长远收益”。

代码实现：

1
from sklearn.tree import DecisionTreeClassifier
2

3
# 预剪枝：通过参数限制树的生长
4
clf = DecisionTreeClassifier(
5
    max_depth=5,              # 最大深度
6
    min_samples_split=10,     # 最少分裂样本数
7
    min_samples_leaf=5,       # 最少叶子样本数
8
    max_leaf_nodes=20,        # 最大叶子节点数
9
    random_state=42
10
)
11
clf.fit(X_train, y_train)

3.2 后剪枝（Post-Pruning）

后剪枝是先让树充分生长，然后再从底部向上修剪。

常见的后剪枝方法

成本复杂度剪枝（Cost-Complexity Pruning, CCP） —— CART采用的方法

悲观剪枝（Pessimistic Error Pruning, PEP） —— C4.5采用的方法

错误率降低剪枝（Reduced Error Pruning, REP）

成本复杂度剪枝（Cost-Complexity Pruning, CCP）

CCP是CART算法采用的剪枝方法，其核心思想是定义一个损失函数，在预测误差和树复杂度之间做权衡。

对于一棵树 $T$ ，定义其成本复杂度为：

\boxed{C_\alpha(T) = R(T) + \alpha \cdot |T|}

其中：

$R(T)$ ：树的误差（如分类错误率或MSE）
$|T|$ ：树的叶子节点数量（衡量复杂度）
$\alpha \geq 0$ $α \geq 0$ ：惩罚参数，控制复杂度在损失函数中的权重
- $\alpha = 0$ ：只关心误差，不关心复杂度 → 树最大
- $\alpha \to \infty$ ：只关心复杂度 → 树退化为根节点

CCP的剪枝过程：

从完整树 $T_0$ 开始
计算每个内部节点被剪枝后的损失函数变化
每次剪掉使损失函数增加最小的节点
得到一系列嵌套的子树 $T_0 \supset T_1 \supset T_2 \supset ... \supset \{\text{根节点}\}$
用交叉验证选择最优的 $\alpha$ 值，从而选择最优子树

代码实现：

1
from sklearn.tree import DecisionTreeClassifier
2
from sklearn.model_selection import train_test_split
3

4
# 1. 先让树充分生长（不设限制或设很松的限制）
5
clf = DecisionTreeClassifier(
6
    min_samples_split=2,
7
    min_samples_leaf=1,
8
    random_state=42
9
)
10
clf.fit(X_train, y_train)
11

12
# 2. 使用ccp_alpha进行后剪枝
13
# 可以尝试不同的ccp_alpha值，用验证集选择最优的
14
for alpha in [0.0, 0.001, 0.005, 0.01, 0.05]:
15
    clf_pruned = DecisionTreeClassifier(
16
        ccp_alpha=alpha,
17
        random_state=42
18
    )
19
    clf_pruned.fit(X_train, y_train)
20
    acc = clf_pruned.score(X_val, y_val)
21
    print(f"ccp_alpha={alpha:.3f}, 验证集准确率={acc:.4f}, 叶子数={clf_pruned.tree_.n_leaves}")

3.3 预剪枝 vs 后剪枝

对比维度	预剪枝	后剪枝
时机	树生长过程中	树生长完成后
计算开销	小	大（需要先生成完整树）
风险	欠拟合	过拟合（如果剪枝不充分）
效果	通常较差	通常更好
常用程度	常用（因为简单高效）	更常用（因为效果更好）

实际建议：先用预剪枝参数（如 max_depth、min_samples_split）快速得到一个“差不多”的模型，如果效果不理想，再考虑使用 ccp_alpha 做后剪枝。

四、决策树对特征尺度不敏感的原因

对于KNN或逻辑回归，特征标准化（Standardization） 或归一化（Normalization） 是必不可少的预处理步骤。但对于决策树，完全不需要做特征缩放。

4.1 核心原因：决策树基于“排序”而非“距离”

决策树的分裂机制决定了它对特征尺度不敏感 —— 决策树寻找最佳分裂点时，仅依赖特征值的排序关系，而非原始数值大小。

特征选择：信息增益、信息增益率、基尼指数都基于概率分布计算，与特征的具体数值无关。无论特征值是从0到1还是从0到1000，只要排序关系不变，这些指标的计算结果就不变。
分裂点选择：对于连续特征，决策树将特征值排序后，在相邻值之间尝试切分。归一化只是把所有值按比例缩放，排序关系完全不变，因此最佳分裂点的位置（在排序中的位置）也完全不变。

4.2 数学证明

假设连续特征 $A$ 的取值范围为 $[a_{\min}, a_{\max}]$ ，对其进行归一化：

A_{\text{norm}} = \frac{A - a_{\min}}{a_{\max} - a_{\min}}

对于任意候选分裂点 $t \in [a_{\min}, a_{\max}]$ ，归一化后的对应分裂点为：

t_{\text{norm}} = \frac{t - a_{\min}}{a_{\max} - a_{\min}}

由于归一化是严格单调递增的线性变换，排序关系完全不变。因此，原始分裂点 $t$ 与归一化分裂点 $t_{\text{norm}}$ 在分裂效果上完全等价。

更一般地，任何严格单调变换（如取对数、平方根等）都不会改变决策树的分裂决策。

4.3 树模型“免疫”特征缩放的原因

决策树由输入特征的阶跃函数组成 —— 每个分裂点就像在特征轴上“切一刀”，左边的归左子树，右边的归右子树。这个“切”的位置只取决于相对顺序，而不取决于绝对数值。

这与其他基于距离的算法形成鲜明对比：

模型类型	对特征缩放是否敏感	原因
KNN、SVM、神经网络	敏感	依赖距离计算，量纲大的特征主导
决策树、随机森林、GBDT	不敏感	依赖排序关系，不依赖距离

代码实现：

1
from sklearn.tree import DecisionTreeClassifier
2
from sklearn.preprocessing import StandardScaler
3
from sklearn.datasets import make_classification
4

5
# 验证：特征缩放不影响决策树的预测结果
6
X, y = make_classification(n_samples=200, n_features=5, random_state=42)
7
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3)
8

9
# 不缩放
10
clf_raw = DecisionTreeClassifier(random_state=42)
11
clf_raw.fit(X_train, y_train)
12
pred_raw = clf_raw.predict(X_test)
13

14
# 标准化
15
scaler = StandardScaler()
16
X_train_scaled = scaler.fit_transform(X_train)
17
X_test_scaled = scaler.transform(X_test)
18
clf_scaled = DecisionTreeClassifier(random_state=42)
19
clf_scaled.fit(X_train_scaled, y_train)
20
pred_scaled = clf_scaled.predict(X_test_scaled)
21

22
# 两次预测应该完全一致
23
print(f"预测结果是否相同: {np.all(pred_raw == pred_scaled)}")  # True

五、完整代码实现

1
import numpy as np
2
import matplotlib.pyplot as plt
3
from sklearn.datasets import load_iris
4
from sklearn.tree import DecisionTreeClassifier, plot_tree
5
from sklearn.model_selection import train_test_split
6
from sklearn.metrics import accuracy_score
7

8
# 1. 加载数据
9
iris = load_iris()
10
X, y = iris.data, iris.target
11
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
12

13
# 2. 训练决策树（带预剪枝）
14
clf = DecisionTreeClassifier(
15
    criterion='gini',      # CART分类树使用基尼指数
16
    max_depth=4,           # 预剪枝：限制深度
17
    min_samples_split=10,  # 预剪枝：限制分裂最小样本数
18
    random_state=42
19
)
20
clf.fit(X_train, y_train)
21

22
# 3. 评估
23
y_pred = clf.predict(X_test)
24
print(f"准确率: {accuracy_score(y_test, y_pred):.4f}")
25
print(f"树的深度: {clf.get_depth()}")
26
print(f"叶子节点数: {clf.get_n_leaves()}")
27

28
# 4. 可视化决策树
29
plt.figure(figsize=(16, 8))
30
plot_tree(clf, feature_names=iris.feature_names, class_names=iris.target_names,
31
          filled=True, rounded=True, fontsize=10)
32
plt.title("决策树可视化（鸢尾花分类）")
33
plt.show()
34

35
# 5. 后剪枝：使用ccp_alpha
36
path = clf.cost_complexity_pruning_path(X_train, y_train)
37
ccp_alphas = path.ccp_alphas
38

39
# 对每个alpha训练一棵树
40
clfs = []
41
for alpha in ccp_alphas:
42
    clf_alpha = DecisionTreeClassifier(ccp_alpha=alpha, random_state=42)
43
    clf_alpha.fit(X_train, y_train)
44
    clfs.append(clf_alpha)
45

46
# 在验证集上选择最优alpha
47
train_scores = [clf.score(X_train, y_train) for clf in clfs]
48
test_scores = [clf.score(X_test, y_test) for clf in clfs]
49

50
# 可视化alpha的影响
51
plt.figure(figsize=(10, 6))
52
plt.plot(ccp_alphas, train_scores, 'b-o', label='训练集准确率')
53
plt.plot(ccp_alphas, test_scores, 'r-o', label='测试集准确率')
54
plt.xlabel('ccp_alpha')
55
plt.ylabel('准确率')
56
plt.legend()
57
plt.title('ccp_alpha 对模型性能的影响')
58
plt.show()

总结

概念核心内容
ID3 信息增益，多叉树，只能分类，无剪枝
C4.5 信息增益率，多叉树，只能分类，有剪枝
CART 基尼指数（分类）/ MSE（回归），二叉树，分类+回归
信息增益 $H(D) - H(D\|A)$ ，偏好取值多的特征
信息增益率 信息增益 / 分裂信息，修正了对取值多特征的偏好
基尼指数 $1 - \sum p_k^2$ ，越小越纯，CART分类用
MSE $\frac{1}{n}\sum(y_i - \hat{y})^2$ ，CART回归用
预剪枝 生长过程中提前停止，简单但可能欠拟合
后剪枝 生长完成后修剪，效果好但计算量大
CCP $C_\alpha(T) = R(T) + \alpha\|T\|$ ，CART的后剪枝方法
特征尺度 决策树对特征缩放不敏感（依赖排序而非距离）
核心要点回顾

ID3、C4.5、CART 的核心区别在于分裂准则不同。ID3用信息增益，C4.5用信息增益率，CART分类用基尼指数、回归用MSE。

信息增益偏好取值多的特征，信息增益率通过除以分裂信息来修正这一偏差，基尼指数与熵在数学上近似但计算更高效。

预剪枝通过 max_depth、min_samples_split 等参数在树生长过程中限制复杂度；后剪枝（如CART的CCP）先生成完整树再修剪，通常效果更好。

决策树对特征尺度不敏感的根本原因在于：分裂只依赖特征值的排序关系，而非数值大小。任何单调变换都不会改变分裂决策。

实际使用建议：先用预剪枝参数快速得到一个基准模型，再用 ccp_alpha 做精细的后剪枝调优。

ZHY's Blog

Decision Tree —— 决策树

引言

一、ID3、C4.5与CART

1.1 ID3：信息增益的开创者

1.2 C4.5：ID3的全面升级

1.3 CART：二叉树的全能选手

二、分裂准则的数学原理

2.1 信息熵与信息增益（ID3）

2.2 信息增益率（C4.5）

2.3 基尼指数（CART分类）

2.4 均方误差（CART回归）

三、剪枝策略

3.1 预剪枝（Pre-Pruning）

3.2 后剪枝（Post-Pruning）

3.3 预剪枝 vs 后剪枝

四、决策树对特征尺度不敏感的原因

4.1 核心原因：决策树基于“排序”而非“距离”

4.2 数学证明

4.3 树模型“免疫”特征缩放的原因

五、完整代码实现

学习路径

反馈与建议

ZHY's Blog

Decision Tree —— 决策树

引言

一、ID3、C4.5与CART

1.1 ID3：信息增益的开创者

1.2 C4.5：ID3的全面升级

1.3 CART：二叉树的全能选手

二、分裂准则的数学原理

2.1 信息熵与信息增益（ID3）

2.2 信息增益率（C4.5）

2.3 基尼指数（CART分类）

2.4 均方误差（CART回归）

三、剪枝策略

3.1 预剪枝（Pre-Pruning）

3.2 后剪枝（Post-Pruning）

3.3 预剪枝 vs 后剪枝

四、决策树对特征尺度不敏感的原因

4.1 核心原因：决策树基于“排序”而非“距离”

4.2 数学证明

4.3 树模型“免疫”特征缩放的原因

五、完整代码实现

学习路径

反馈与建议

继续探索

Hidden Markov Model (HMM) —— 隐马尔可夫模型

Expectation-Maximization Algorithm —— EM算法

K-Means Clustering —— 聚类算法