机器学习数学推导（七）：决策树

导言： 决策树模仿了人类做决定的过程：先问一个问题，根据答案分叉，再问下一个问题。这种直观做法背后的数学却出人意料地丰富——信息论中的熵告诉我们该先问哪个问题；基尼指数提供了一个计算更高效、效果几乎相同的替代方案；而代价复杂度剪枝则给出了一种有理论依据的方法，防止模型记住噪声。如今几乎所有主流的提升集成方法（如 XGBoost、LightGBM 和 CatBoost）本质上都是这些决策树的巧妙组合，因此扎实掌握基础将带来丰厚回报。

你将学到什么#

• 为什么决策树在数学上是特征空间递归划分上的分段常数函数。
• 熵、条件熵和信息增益背后的信息论动机，以及增益率为何被提出。
• 仅用一行泰勒展开就能说明基尼指数与熵为何几乎总选择相同的分裂点。
• CART 如何在不破坏其贪心框架的前提下处理连续特征、缺失值和类别特征。
• 预剪枝与后剪枝的区别，以及代价复杂度阈值 $\alpha$ 的精确推导。
• 特征重要性是如何定义的（而不仅仅是 sklearn 打印出来的结果），以及它可能在哪些情况下产生误导。

决策树基础#

模型表示#

整棵树是一个层次结构，包含：

• 根节点：包含全部训练样本。
• 内部节点：对某个特征与阈值（或某个类别值）进行测试。
• 分支：测试结果对应的路径。
• 叶节点：存储预测值的终端区域。

上图展示了一个在 Iris 数据集上训练的深度为 2 的 CART 树。仅凭两个关于花瓣尺寸的问题，就足以区分三种鸢尾花——每条从根到叶的路径对应特征空间中的一个矩形区域。

决策树的优势与局限#

方差问题正是 bagging（随机森林）和 boosting（GBDT、XGBoost）被设计出来要解决的核心痛点。

信息论基础#

熵：作为分布不确定性的度量#

以比特为单位时，$H$ 衡量的是平均需要多少个是非问题才能确定 $Y$ 的取值。

我们将反复用到以下三个性质：

1. 非负性：$H(Y) \geq 0$ ，当且仅当某个 $p_k = 1$ （即无不确定性）时取等号。
2. 均匀分布时熵最大：在约束 $\sum_k p_k = 1$ 下，通过拉格朗日乘子法最大化 $-\sum_k p_k \log p_k$ ，可得 $p_k = 1/K$ ，此时 $H_{\max} = \log_2 K$ 。
3. 凹性：$H$ 在概率单纯形上严格凹，因此混合分布不会降低熵。

条件熵与信息增益#

非负性由 $H$ 的凹性（Jensen 不等式）保证，且 $IG = 0$ 当且仅当 $X$ 与 $Y$ 独立。

ID3 算法在每个节点选择信息增益最大的特征进行分裂。

信息增益 $IG \approx 0.048$ 比特——分裂带来的信息很少。换一个完美特征 $X'$ ：$X'=0$ 全负、$X'=1$ 全正，两子节点熵全为 0，$IG = 0.940$ 比特，把父节点的不确定性一次性消尽。CART 每次分裂就是在比这两种特征的 $IG$ ，挑大的。

增益率：对多值特征的惩罚#

信息增益存在一个广为人知的缺陷：若某特征对每个样本都有唯一值（例如 ID 列），则分裂后每个子节点仅含一个样本，子节点熵全为零，该特征将在每次分裂中胜出——但它毫无泛化能力。

多值特征具有较大的 $IV$ ，因而受到惩罚。C4.5 的实际策略是：先筛选出信息增益高于平均水平的特征，再从中选择增益率最高的——这样可避免因 $IV$ 过小而人为放大 $GR$ ，从而误选信息量不足的特征。

分裂准则#

基尼指数#

其中 $p_k$ 是节点 $S$ 中第 $k$ 类的比例。它表示从 $S$ 中随机抽取两个样本，其类别不同的概率。与熵类似，纯节点时为零，均匀分布时达到最大。

CART 选择使 $\Delta G$ 最大的分裂。

为何基尼与熵行为几乎一致#

经常数缩放 $H_\mathrm{nat}/(2 \ln 2)$ 后，两者在 $p = \tfrac{1}{2}$ 附近的主导项形状完全相同。实践中，使用基尼或熵训练的 CART 几乎总是做出相同的分裂选择。

左图对比了三种不纯度度量：基尼、熵和分类错误率 $1 - \max(p, 1-p)$ 。右图将 $H/2$ 叠加在 $G$ 上——二者在 $p = 1/2$ 附近二阶吻合，仅在两端略有差异。相比之下，分类错误率是分段线性的且非严格凹，这正是它不适合作为分裂准则的原因：即使分裂使两个子节点都更纯，加权错误率也可能不变，导致搜索陷入停滞。

回归树的均方误差准则#

决策树算法#

ID3、C4.5、CART 一览#

下文主要遵循 CART，因为 scikit-learn 实现的正是 CART。

贪心递归构建#

1
2
3
4
5

def build_tree(S, depth):
    if stop(S, depth): return Leaf(predict(S))
    j*, tau* = argmax_{j, tau} delta_impurity(S, j, tau)
    S_L, S_R = split(S, j*, tau*)
    return Node(j*, tau*, build_tree(S_L, depth+1), build_tree(S_R, depth+1))

stop 通常综合判断：节点是否纯净、是否存在有效分裂、是否达到深度上限，或剩余样本数是否少于 min_samples_split。该贪心选择仅保证局部最优——即使对二值特征，寻找全局最优树也是 NP 难问题。

连续特征与缺失值#

连续特征的阈值搜索#

将特征 $j$ 的值排序为 $x_{(1)} < \dots < x_{(n)}$ ，候选阈值取相邻值的中点 $\tau_i = (x_{(i)} + x_{(i+1)})/2$ 。对每个 $\tau_i$ 评估分裂准则。朴素实现每特征需 $O(n^2)$ 时间；若预先排序一次，并在样本跨越阈值时增量更新不纯度计数，则可降至 $O(n \log n)$ 。

一个著名性质是：最优阈值必位于两个标签不同的相邻样本之间。当标签分布偏斜时，该性质能大幅缩减候选集。

缺失值处理#

C4.5 和 CART 均无需预填充缺失值。

从而自动降低缺失值较多特征的权重。

CART 还会在每个节点存储替代分裂——即能近似主分裂的备用特征——预测时若主特征缺失，则使用最佳替代分裂。

类别特征#

对无序类别特征（含 $K$ 个类别），穷举所有二分需测试 $2^{K-1} - 1$ 个子集。但在二分类（或平方损失回归）中存在巧妙捷径（Fisher 1958, Breiman 1984）：按各类别的目标均值排序后，最优二分必沿此顺序进行。这将搜索复杂度从指数级降至线性级。

分裂中的信息视角#

图示展示了同一父节点（$H = 1$ 比特）的两次合成分裂。左侧特征信息量大，两个子节点接近纯净，几乎完全消除了父节点的不确定性；右侧特征信息量小，加权子节点熵几乎与父节点相同，故 $IG$ 接近零。CART 会选择“柱子”最高的特征-阈值组合。

二维空间中的决策边界#

这些边界直观体现了决策树的分段常数特性。深度为 1 时，仅有一条垂直或水平切割线，树的行为如同一维阈值；深度达 3 时，已能大致勾勒出双月形状；深度增至 6 时，边界变得支离破碎——每个微小矩形都在追逐一两个训练点，这是在噪声数据上过拟合的典型标志。

剪枝：控制方差#

为何未剪枝树会过拟合#

完全生长的树训练误差为零：每个叶节点要么仅含一类样本，要么只剩一个样本。模型实质上记住了训练集（包括噪声），原因有二：

• 深度：深树表达更精细的特征交互，最终拟合噪声。
• 微小叶节点：仅含 3 个样本的叶节点，其类别比例在统计上无意义。

这是决策树过拟合的经典曲线，基于带噪声的双月数据集，深度从 1 到 20。训练准确率单调上升至 1.0，而测试准确率在中等深度达峰后下降。次坐标轴上的灰点线表示叶节点数——其在最佳点后近乎指数增长，正是测试性能下降所付出的方差代价。

预剪枝#

提前终止生长。常用参数包括：

• max_depth
• min_samples_split（样本过少则不分裂）
• min_samples_leaf（每叶至少需此多样本）
• min_impurity_decrease（要求最小增益）
• max_leaf_nodes（限制叶节点数，按最佳增益贪心分裂）

预剪枝速度快（避免构建完整树），但目光短浅：当前看似弱的分裂，可能为后续优质分裂铺路，而预剪枝直接扼杀了这种可能。

后剪枝：代价复杂度#

其中 $R(T)$ 为训练风险（叶节点不纯度按样本数加权），$|T|$ 为叶节点数。$\alpha$ 越大，越倾向简单树。

当 $\alpha$ 超过此阈值，折叠子树严格改善 $R_\alpha$ 。从 $\alpha = 0$ 开始逐步增大 $\alpha$ ，反复折叠最弱链（即 $\alpha_\text{eff}$ 最小者），可得有限嵌套树序列 $T_0 \supset T_1 \supset \dots \supset T_\text{root}$ 。这些 $\alpha$ 值正是 scikit-learn 中 cost_complexity_pruning_path 返回的结果。

最终 $\alpha$ 通过训练集交叉验证选定。

左、中图展示决策区域：预剪枝（max_depth=4）生成整齐大块；后剪枝先完全生长再折叠最弱链，所得树叶节点往往更少，且在此数据集上泛化更好。右图为剪枝路径：随 $\alpha$ 增大，训练准确率平滑下降，测试准确率先升后降——树被过度剪枝时性能崩塌。

决策树理论#

VC 维#

叶节点数 $L$ 是自然的复杂度度量——这正是代价复杂度剪枝所正则化的对象。

为何树不稳定#

若根节点上两特征信息增益相近（如 $g_1 - g_2 = \epsilon$ ），任意微小扰动都可能翻转选择，并引发下方树结构的彻底改变。形式化地，只要数据扰动使任一子节点不纯度变化超过 $\epsilon$ ，就可能反转顺序。这种高方差正是随机森林有效的根源：对多个自助采样树取平均，去相关误差使方差大致随树数成比例下降。

特征交互与树深#

因此，深度-$d$ 树最多表达 $d$ 阶交互。这也解释了为何即使浅树，在需特征“协同作用”才有预测力的数据上，也能轻松击败线性模型。

实现：一个最简 CART#

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

import numpy as np
from sklearn.datasets import load_iris, fetch_california_housing
from sklearn.metrics import accuracy_score, mean_squared_error
from sklearn.model_selection import train_test_split

class Node:
    def __init__(self, feature=None, threshold=None,
                 left=None, right=None, value=None):
        self.feature = feature
        self.threshold = threshold
        self.left = left
        self.right = right
        self.value = value  # 如果 value 不为 None，表示是叶子节点

class CARTBase:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.root = None

    def _impurity(self, y):
        raise NotImplementedError

    def _leaf_value(self, y):
        raise NotImplementedError

    def _best_split(self, X, y):
        n, d = X.shape
        if n < self.min_samples_split:
            return None, None, 0.0
        parent_impurity = self._impurity(y)
        best_gain = 0.0
        best_j = None
        best_t = None
        for j in range(d):
            xs = X[:, j]
            order = np.argsort(xs)
            xs_sorted = xs[order]
            ys_sorted = y[order]
            for i in range(1, n):
                if xs_sorted[i] == xs_sorted[i - 1]:
                    continue
                if i < self.min_samples_leaf or n - i < self.min_samples_leaf:
                    continue
                t = 0.5 * (xs_sorted[i] + xs_sorted[i - 1])
                left = ys_sorted[:i]
                right = ys_sorted[i:]
                gain = parent_impurity - (i * self._impurity(left) +
                                          (n - i) * self._impurity(right)) / n
                if gain > best_gain:
                    best_gain = gain
                    best_j = j
                    best_t = t
        return best_j, best_t, best_gain

    def _build(self, X, y, depth):
        if (self.max_depth is not None and depth >= self.max_depth) or len(y) < self.min_samples_split:
            return Node(value=self._leaf_value(y))
        j, t, gain = self._best_split(X, y)
        if j is None or gain <= 0:
            return Node(value=self._leaf_value(y))
        mask = X[:, j] <= t
        return Node(j, t,
                    self._build(X[mask], y[mask], depth + 1),
                    self._build(X[~mask], y[~mask], depth + 1))

    def fit(self, X, y):
        self.root = self._build(np.asarray(X), np.asarray(y), 0)
        return self

    def _predict_one(self, x, node):
        if node.value is not None:
            return node.value
        nxt = node.left if x[node.feature] <= node.threshold else node.right
        return self._predict_one(x, nxt)

    def predict(self, X):
        return np.array([self._predict_one(x, self.root) for x in X])

class CARTClassifier(CARTBase):
    def _impurity(self, y):  # Gini 系数
        if len(y) == 0:
            return 0.0
        _, c = np.unique(y, return_counts=True)
        p = c / len(y)
        return 1.0 - np.sum(p ** 2)

    def _leaf_value(self, y):
        return int(np.bincount(y).argmax())

class CARTRegressor(CARTBase):
    def _impurity(self, y):  # 方差
        return float(np.var(y)) if len(y) else 0.0

    def _leaf_value(self, y):
        return float(np.mean(y))

if __name__ == "__main__":
    X, y = load_iris(return_X_y=True)
    Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.2,
                                          random_state=42, stratify=y)
    clf = CARTClassifier(max_depth=4).fit(Xtr, ytr)
    print(f"Iris 准确率: {accuracy_score(yte, clf.predict(Xte)):.3f}")

    Xb, yb = fetch_california_housing(return_X_y=True)
    Xtr, Xte, ytr, yte = train_test_split(Xb[:2000], yb[:2000],
                                          test_size=0.2, random_state=42)
    reg = CARTRegressor(max_depth=6).fit(Xtr, ytr)
    print(f"Housing MSE: {mean_squared_error(yte, reg.predict(Xte)):.3f}")

特征重要性#

特征 $j$ 的重要性为所有此类节点 $\Delta I(t)$ 之和，并归一化使总和为 1。

在 Iris 数据集上，花瓣长度和宽度的重要性遥遥领先，与前述深度-2 树一致——仅凭这两特征即可区分三类鸢尾花。该图由 sklearn 的 feature_importances_ 生成，图注公式与定义一一对应。

注意事项：

• MDI 偏向连续型和高基数特征——它们有更多机会被选为分裂候选。
• 单棵树的重要性不稳定。在随机森林上聚合（或使用置换重要性）可得更可靠排序。
• 重要性不等于因果性。特征可能因与真实原因相关而显得重要。

多变量决策树#

即特征空间中的超平面。它可用单节点表示对角边界，而非数十个轴对齐阶梯。但需权衡：

• 每节点找最优 $w$ 通常 NP 难（启发式：线性判别、感知机、软优化）。
• 可解释性下降：每节点变为小型线性模型，而非单一阈值。

精选问答#

Q1：决策树为何能建模非线性关系？ 单次分裂虽线性，但轴对齐分裂的组合构成特征空间递归划分上的分段常数函数。任何有界可积连续函数均可被此类分段常数在 $L^1$ 范数下任意逼近——故树是此类函数的通用逼近器。

Q2：信息增益为何偏好多值特征？ 因更细划分天然更纯：极限情况下每子节点仅一样本，子节点熵为零，增益等于父节点熵。但这与泛化无关。C4.5 的增益率通过除以 $IV(X)$ （本身为熵）来消除此伪影。

Q3：基尼或熵——有区别吗？ 几乎无区别。二者在 $p = 1/2$ 附近的二阶泰勒展开一致，实践中生成的树仅少数分裂不同。基尼稍快（无对数运算），也是 scikit-learn CART 的默认选择。

Q4：如何处理类别特征？ 三种选项：(i) one-hot 编码，让树分裂各指示变量；(ii) 多叉分裂，每类别一枝（ID3/C4.5）；(iii) 最优二分——二分类中按类别目标均值排序后选最佳有序切分，搜索从 $O(2^K)$ 降至 $O(K)$ 。

Q5：支持多输出树吗？ 支持。多输出回归中，叶节点存均值向量，不纯度为叶内协方差矩阵的迹；多标签分类中，叶节点存类别概率向量，不纯度为各标签基尼的平均。sklearn 原生支持二者。

Q6：预剪枝还是后剪枝？ 预剪枝快，适合原型开发；后剪枝（代价复杂度）更准，因它见过完整树再决定剪枝，但更耗时。实践中常直接调 max_depth 和 min_samples_leaf，因树通常嵌于集成中，其余方差由集成吸收。

Q7：为何树尺度不变？ 分裂仅比较 $x_j \leq \tau$ ——仅值序重要。特征的任意单调变换不改变树结构。这也解释了为何类别变量可直接 one-hot 编码而无需预处理。

Q8：如何可视化树？

1
2
3
4
5

from sklearn.tree import plot_tree
import matplotlib.pyplot as plt
plt.figure(figsize=(20, 10))
plot_tree(clf, feature_names=iris.feature_names,
          class_names=iris.target_names, filled=True, rounded=True)

Q9：树能做特征选择吗？ 能——按 feature_importances_ 排序并设阈值。但单棵树排序不稳定。生产环境建议用随机森林或置换重要性。

Q10：树训练可并行化吗？ 单棵树生长按节点顺序，无法并行；但同节点内各特征的分裂搜索可完全并行；随机森林中各树彼此独立，亦可并行。XGBoost 和 LightGBM 还通过特征桶直方图流水线优化分裂搜索。

Q11：max_depth 合理范围？ 对数千样本的表格数据，默认 $3 \leq d \leq 12$ 。交叉验证确定。集成中常用较浅树——boosting 典型深度为 4–8。

Q12：树能处理高维数据吗？ 理论上能，但单节点分裂成本为 $O(d \cdot n \log n)$ ，高维中多数特征为噪声。高 $d$ 时优先选正则化线性模型，或每节点特征子采样的随机森林（由 max_features 控制）。

变体与扩展#

• 代价敏感树：用非对称损失 $L(y, \hat{y})$ 替代分类错误——适用于假阴性代价更高场景（如医疗诊断、欺诈检测）。
• 模糊/软树：每次分裂将样本分数送入左右子树，使训练可微，可用梯度下降优化。
• 增量树：Hoeffding 树（Domingos & Hulten, 2000）用 Hoeffding 界判断何时有足够样本进行高置信分裂，支持流式训练。
• 斜树：使用线性组合分裂（如 CART-LC, OC1）。

练习题#

练习 1：手动计算信息增益。 14 样本数据集含 9 正 5 负。特征 $X$ 有两值：$X=a$ 含 8 样本（6+, 2−），$X=b$ 含 6 样本（3+, 3−）。计算 $H(Y)$ 、$H(Y \mid X)$ 、$IG$ 、$IV(X)$ 和 $GR$ 。

解答： $H(Y) = -\tfrac{9}{14}\log_2 \tfrac{9}{14} - \tfrac{5}{14}\log_2\tfrac{5}{14} \approx 0.940$ 。条件熵：$H(Y \mid X=a) \approx 0.811$ ，$H(Y \mid X=b) = 1.000$ 。故 $H(Y \mid X) = \tfrac{8}{14}(0.811) + \tfrac{6}{14}(1.000) \approx 0.892$ ，$IG \approx 0.048$ 。$IV(X) \approx 0.985$ ，故 $GR \approx 0.049$ 。

练习 2：基尼 ≈ 熵 / 2。 证二分类中，自然对数下 $H_\mathrm{nat}(p) \approx 2\,G(p) \cdot \ln 2$ 在 $p = \tfrac{1}{2}$ 附近二阶成立。

解答： $H_\mathrm{nat}(p)$ 在 $p_0 = \tfrac{1}{2}$ 处二阶展开为 $\ln 2 - 2(p - \tfrac{1}{2})^2$ ；$G(p) = \tfrac{1}{2} - 2(p - \tfrac{1}{2})^2$ 。二者二次项相同，常数项相差因子 $\ln 2$ （nat 转 bit 的换算因子）。

练习 3：临界 alpha。 子树 $T_t$ 有 4 叶，训练误差 0.10；折叠为叶后误差 0.25。求 $\alpha_\text{eff}(t)$ 并判断 $\alpha = 0.06$ 时是否剪枝。

解答： $\alpha_\text{eff} = \frac{0.25 - 0.10}{4 - 1} = 0.05$ 。因 $\alpha = 0.06 > 0.05$ ，应剪枝：$R_\alpha(\text{leaf}) = 0.31 < R_\alpha(T_t) = 0.34$ 。

练习 4：缺失值惩罚。 100 样本中特征 $X$ 缺失 20 个。80 观测样本上 $H(Y) = 0.94$ ，$H(Y \mid X) = 0.60$ 。求调整后信息增益。

解答： 观测比例 $80/100 = 0.8$ ，故 $IG_\text{adj} = 0.8 \cdot (0.94 - 0.60) = 0.272$ 比特。缺失率翻倍则信用减半。

练习 5：逼近对角线需几步？ 在 $[0, 1]^2$ 上，轴对齐二叉树逼近 $y = x$ 至 $L^\infty$ 误差 $\epsilon$ 内需多少叶？

解答： $n$ 阶阶梯（每宽 $1/n$ ）误差 $\Theta(1/n)$ 。令 $1/n \leq \epsilon$ 得 $n = \lceil 1/\epsilon \rceil$ ，即 $\Theta(1/\epsilon)$ 叶。斜树单次分裂 $y - x \leq 0$ 即零误差——凸显轴对齐逼近对角结构的代价。

下一步#

决策树用"轴对齐切分 + 信息增益"把表格数据切到了极致，但它有两个硬伤：单棵树容易过拟合（方差大），而且边界永远是阶梯状——再深也没法画出一条斜线。要解决这两个问题，要么换一个完全不同的归纳偏置，要么对树本身做集成。下一章我先走"换偏置"那条路——支持向量机。

SVM 的核心思想和决策树几乎相反：它不切空间，而是找一个最大间隔超平面；它不靠贪心，而是解一个二次规划；它不靠深度造表达力，而是靠核技巧把数据映射到更高维空间，让原本非线性可分的问题变成线性可分。这一章我会把硬间隔、软间隔、对偶、核技巧、SMO 一条线推到底——它是凸优化在第八章后第一次真正硬碰硬地用上 KKT 条件。读完之后，你会对"什么时候 SVM 比树好"“什么时候反过来"有一个更具体的判断。

参考文献#

• Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106.
• Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
• Breiman, L., Friedman, J., Stone, C. J., & Olshen, R. A. (1984). Classification and Regression Trees. Wadsworth.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer. Chapter 9.
• Mitchell, T. M. (1997). Machine Learning. McGraw-Hill. Chapter 3.
• Breiman, L. (2001). Random forests. Machine Learning, 45(1), 5–32.
• Loh, W. Y. (2011). Classification and regression trees. WIREs Data Mining and Knowledge Discovery, 1(1), 14–23.
• Domingos, P., & Hulten, G. (2000). Mining high-speed data streams. KDD.

决策树是我们现有最成功表格学习器的基石。理解熵、基尼指数和代价复杂度剪枝，是掌握随机森林、GBDT、XGBoost 和 LightGBM 的前提——后续章节将直接建立在此处发展的机制之上。