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

导言。 决策树模拟的是人做决定的方式：问一个问题、按答案分支、再问下一个问题。这种朴素的直觉背后藏着不少数学：信息论中的熵告诉我们应该先问哪个问题；基尼指数提供了一种几乎等价但更便宜的代替；代价复杂度剪枝则给出了一套有原则的方式来阻止树去记噪声。今天最强的一类表格学习器——XGBoost、LightGBM、CatBoost——本质上都是这套对象的巧妙组合，所以把基础打扎实，回报会反复显现。

你将学到什么

• 决策树为什么在数学上是特征空间递归划分上的分段常数函数。
• 熵、条件熵、信息增益的信息论动机，以及为什么后来又发明了信息增益率。
• 一条 Taylor 展开就能解释为什么基尼和熵几乎总是选出同一个分裂。
• CART 如何用同一套贪心框架自然地处理连续特征、缺失值和类别特征。
• 预剪枝 vs 后剪枝，以及代价复杂度阈值 $\alpha$ 的完整推导。
• 特征重要性是如何被定义出来的（不仅仅是 sklearn 打印的数字），以及它在哪些场景会误导人。

决策树基础

模型表示

决策树把特征空间 $\mathcal{X} \subseteq \mathbb{R}^d$ 划分为 $M$ 个互不相交的区域 $R_1, \dots, R_M$，并在每个区域上指定一个常数预测 $c_m$：

分类任务里 $c_m \in \{1, \dots, K\}$ 取该区域的多数类，回归任务里 $c_m \in \mathbb{R}$ 取该区域目标值的均值。这些区域是与坐标轴平行的超矩形——因为每个内部节点只对单个特征做阈值判断：

树本身的层次结构是：

• 根节点：包含全部训练样本。
• 内部节点：每个测试一个特征对一个阈值（或一个类别取值）。
• 分支：测试结果。
• 叶节点：终端区域，存放预测。

上图是在 Iris 上训练的深度为 2 的 CART：仅靠两个关于花瓣尺寸的问题就把三个物种分开。每条根到叶的路径，对应特征空间中的一个矩形。

决策树为什么有用——又在哪里失败

方差大正是 bagging（随机森林）和 boosting（GBDT、XGBoost）要解决的问题。

信息论基础

熵：分布的不确定性

对取值在 $\{1, \dots, K\}$、概率为 $p_1, \dots, p_K$ 的离散随机变量 $Y$，Shannon 熵为

以比特为单位，$H$ 等于平均要问多少个 yes/no 问题才能识别出 $Y$。

反复要用的三条性质。

1. 非负性。 $H(Y) \geq 0$，等号当且仅当某个 $p_k = 1$（无不确定性）成立。
2. 均匀分布最大。 在 $\sum_k p_k = 1$ 约束下，用 Lagrange 乘子最大化 $-\sum_k p_k \log p_k$ 得 $p_k = 1/K$，最大值 $H_{\max} = \log_2 K$。
3. 凹性。 $H$ 在概率单纯形上严格凹，所以混合分布只会让熵不降。

条件熵与信息增益

设特征 $X$ 取值 $\{v_1, \dots, v_V\}$。条件熵

是已知 $X$ 后 $Y$ 的平均剩余不确定性。信息增益就是这部分不确定性的减少量：

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

ID3 算法在每个节点选 $IG$ 最大的特征。

信息增益率：惩罚多值特征

信息增益有个臭名昭著的毛病：把"样本 ID"这种每个样本一个唯一值的特征拿来分裂，每个子节点恰好只剩一个样本，子节点熵全为 0，于是这个特征赢下任何分裂——但它毫无泛化价值。

C4.5 通过除以特征自身的固有值来纠正这一点：

它本身是分裂规模的熵。增益率为

多值特征 $IV$ 大，自然被惩罚。C4.5 实际的启发式是：先筛出 $IG$ 高于平均的特征，再在其中挑 $GR$ 最大的——这样可以避免把那些 $IV$ 极小但本身没什么信息量的特征也捧上去。

分裂准则

基尼指数

CART 使用基尼指数：

其中 $p_k$ 是 $S$ 中第 $k$ 类的比例。它等价于"从 $S$ 中独立取两个样本，类别不同的概率"。和熵一样，纯节点为 0、均匀分布最大。

把 $S$ 按某特征分为 $S_1, \dots, S_V$ 的基尼增益与信息增益形式一致：

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

基尼和熵为什么几乎等价

二分类下，正类概率为 $p$ 时

把熵在 $p = \tfrac{1}{2}$ 处用自然对数二阶 Taylor 展开：

而基尼

经过 $H_\mathrm{nat}/(2 \ln 2)$ 这样一个常数缩放，两者在 $p = \tfrac{1}{2}$ 附近的主导项就是同一个。实际跑 CART 时，用基尼和用熵几乎总是切到同一个分裂。

左图同时画了基尼、熵和分类错误率 $1 - \max(p, 1-p)$。右图把 $H/2$ 叠在 $G$ 上——它们在 $p = 1/2$ 附近二阶吻合，仅在两端略有偏差。分类错误率是分段线性的、不严格凹，所以做分裂准则很糟糕：一个让两个子节点都更纯的分裂可能根本不动加权错误率，搜索就停在原地。

回归树的均方误差准则

回归任务下，叶 $R_m$ 的预测取目标值的均值

它最小化叶内平方损失。分裂准则选 $(j, \tau)$ 使分裂后平方误差和最小：

等价地，分裂准则就是加权方差缩减：

决策树算法

ID3、C4.5、CART 一图看懂

下面的描述基于 CART，因为这是 scikit-learn 的实现。

贪心递归构建

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 都不需要先填缺失值。

训练阶段。 评估特征 $j$ 时，只用观测到 $x_j$ 的样本。信息增益再乘以观测样本占比

于是缺失多的特征自动被打折。

样本路由。 当一个 $x_j$ 缺失的样本走到一个按 $j$ 分裂的节点时，按观测样本的左右比例同时分到两个子节点：

CART 还在每个节点存替代分裂——能在主分裂特征缺失时近似主分裂结果的备用特征——预测时主特征缺失就启用最佳替代。

类别特征

无序类别有 $K$ 个取值时，穷举二分要试 $2^{K-1} - 1$ 种子集划分。但二分类（或平方损失下的回归）有一个漂亮的捷径（Fisher 1958，Breiman 1984）：按"该类别下的目标均值"排序，最优二分一定沿这个序去切。这把搜索从指数级降到线性级。

把分裂当信息看

上图在同一个父节点（$H = 1$ 比特）上展示了两次合成分裂。左边是信息量大的特征：两个子节点都接近纯，几乎把父节点的不确定性吃掉。右边是几乎没用的特征：加权子熵几乎等于父熵，$IG$ 接近 0。CART 选的是这种"柱子"最高的特征/阈值组合。

二维空间中的决策边界

这组图把树的分段常数本质画得非常直观。深度 1 就是一刀，树退化成一维阈值。深度 3 大致勾勒出双月。深度 6 边界就开始变得锯齿——每个小矩形都在追一两个训练点，这是噪声数据上典型的过拟合特征。

剪枝：控制方差

不剪枝为什么会过拟合

完全长成的树训练误差为 0：每个叶要么只剩一个类，要么只剩一个样本。模型把训练集（包括其中的噪声）背了下来。两个结构性原因：

• 深度。 树越深表达的特征交互越细，最终把噪声也学进去。
• 微小的叶。 一个样本数为 3 的叶里类别比例毫无统计意义。

这就是决策树过拟合的标准曲线，数据是带噪声的双月，深度从 1 扫到 20。训练精度单调爬向 1.0，而测试精度在中等深度处达到峰值后下滑。次轴上的灰点线是叶节点数——它在最佳点之后近乎指数增长，这就是测试曲线为之付出代价的方差。

预剪枝

提前停。常用旋钮：

• max_depth
• min_samples_split（样本太少就不分裂）
• min_samples_leaf（每片叶必须至少这么多样本）
• min_impurity_decrease（要求最小增益）
• max_leaf_nodes（按"最佳增益"贪心地控制叶数上限）

预剪枝快——根本不会去构建完整的树——但短视：现在看似无用的分裂可能在它下面孕育出两个极佳的分裂，预剪枝直接把这种可能性堵死了。

后剪枝：代价复杂度

CART 经典的解法是代价复杂度剪枝（也叫最小代价复杂度剪枝或最弱链剪枝）。对一棵树 $T$，定义

其中 $R(T)$ 是训练风险（叶不纯度按叶内样本数加权之和），$|T|$ 是叶数。$\alpha$ 越大越偏好简单树。

关键推导。 考虑非叶节点 $t$ 及以它为根的子树 $T_t$。把 $T_t$ 折成 $t$ 这一片叶后代价是 $R(t) + \alpha$，保留子树时代价是 $R(T_t) + \alpha |T_t|$。两者相等的临界 alpha 为

当 $\alpha$ 超过这个阈值，折叠该子树会严格降低 $R_\alpha$。从 $\alpha = 0$ 起逐步抬高 $\alpha$，每次折叠最弱链（$\alpha_\text{eff}$ 最小的节点），就能得到一个有限的、嵌套的树序列 $T_0 \supset T_1 \supset \dots \supset T_\text{root}$。这些 $\alpha$ 值正好就是 sklearn cost_complexity_pruning_path 返回的内容。

最终的 $\alpha$ 在训练集上用交叉验证选出。

左图与中图分别展示两种策略最终的决策区域：预剪枝（max_depth=4）切出整齐的大块；后剪枝先长完再折叠最弱链，在这份数据上叶数往往更少但泛化更好。右图是剪枝路径：随着 $\alpha$ 增大，训练精度平滑下滑，测试精度先升后降——树被剪太狠就崩了。

决策树的理论性质

VC 维

对 $d$ 个连续特征上的二叉树，当叶数为 $L$ 时

经典的 PAC 风格泛化界说，以至少 $1 - \delta$ 的概率有

复杂度项就是叶数 $L$——这恰好是代价复杂度剪枝在正则化的对象。

决策树为什么不稳定

如果根节点上两个特征的信息增益差不多，任意微小的扰动都可能翻转选择，并把这种差异级联放大到下面整棵树。形式化一下：设两个增益为 $g_1, g_2$ 且 $g_1 - g_2 = \epsilon$；任何让某个子节点不纯度变化超过 $\epsilon$ 的扰动都可能反转这个序。这种高方差恰好是 bagging 多棵自助采样树（即随机森林）有效的原因：把多棵误差相对去相关的树取平均，方差大致按树数比例下降。

特征交互与树深

一条长度为 $d$ 的根到叶路径表示一个 $d$ 元交互：

所以深度为 $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

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, self.threshold = feature, threshold
        self.left, self.right = left, 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 = self._impurity(y)
        best_gain, best_j, best_t = 0.0, None, None
        for j in range(d):
            xs = X[:, j]
            order = np.argsort(xs)
            xs_sorted, ys_sorted = xs[order], 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, right = ys_sorted[:i], ys_sorted[i:]
                gain = parent - (i * self._impurity(left)
                                 + (n - i) * self._impurity(right)) / n
                if gain > best_gain:
                    best_gain, best_j, best_t = gain, j, 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))


# --- 与 sklearn 对照 ---
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$ 分裂的内部节点 $t$，归到该节点头上的不纯度平均下降量（MDI）为

特征 $j$ 的重要性即所有按 $j$ 分裂的节点 $\Delta I(t)$ 之和，再做归一化使所有重要性求和为 1。

在 Iris 上，花瓣长度和花瓣宽度遥遥领先——和我们在前面画的深度 2 树一致：仅这两个特征就能区分三个物种。这张图直接调用 sklearn 的 feature_importances_，与图注里的公式一一对应。

几个需要注意的坑。

• MDI 偏向连续和高基数特征——它们更容易被选作候选分裂。
• 单棵树上的重要性不稳定。聚合到随机森林（或者用置换重要性）能给出更可靠的排序。
• 重要性 ≠ 因果。一个特征"很重要"可能只是因为它和真正的因果变量高度相关。

多变量决策树

标准分裂只用一个特征，所以边界与坐标轴对齐。斜分裂（oblique）允许

即特征空间里的一个超平面。一根斜线只需一个节点就能表达，省去几十次轴对齐的"阶梯"。代价是：

• 一般情况下找最优 $w$ 是 NP 难的（启发式：线性判别、感知机、软优化）。
• 可解释性下降：每个节点变成一个小线性模型，而不再是一个阈值。

精选 Q&A

Q1：决策树为什么能建模非线性？ 单次分裂确实是线性的，但组合起来的轴对齐分裂构成的是特征空间递归划分上的分段常数函数。任意有界可积的连续函数都能被这样的分段常数在 $L^1$ 上任意逼近——所以树是有界可积函数的万能逼近器。

Q2：信息增益为什么偏好多值特征？ 机制上：更细的划分天然更纯。极端情况下每个子节点只有一个样本，子节点熵全为 0，增益等于父节点熵。但这与泛化能力毫无关系。C4.5 用增益率除以 $IV(X)$（本身也是个熵）来抵消这个机械效应。

Q3：基尼和熵到底哪个好？ 基本无所谓。两者在 $p = 1/2$ 附近的二阶 Taylor 展开一致，实测里两套树的分裂只在少数节点上不同。基尼略快（无对数），是 sklearn 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 怎么选？ 表格数据、$n$ 在千量级时一个常用范围是 $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) = -\tfrac{6}{8}\log_2\tfrac{6}{8} - \tfrac{2}{8}\log_2\tfrac{2}{8} \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) = -\tfrac{8}{14}\log_2\tfrac{8}{14} - \tfrac{6}{14}\log_2\tfrac{6}{14} \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 \ln p - (1-p)\ln(1-p)$ 在 $p_0 = \tfrac{1}{2}$ 处展开。一阶导在 $p_0$ 处为 0（极大值），二阶导为 $-1/p_0 - 1/(1-p_0) = -4$，所以 $H_\mathrm{nat}(p) \approx \ln 2 - 2(p - \tfrac{1}{2})^2$。同理 $G(p) = 2p(1-p) = \tfrac{1}{2} - 2(p - \tfrac{1}{2})^2$。两者二阶项形状一致，常数项相差恰好就是把 nat 转成 bit 的 $\ln 2$。

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

$\alpha = 0.06 > 0.05$，保留子树的代价已超过收益，应剪枝：$R_\alpha(\text{leaf}) = 0.25 + 0.06 = 0.31$ vs $R_\alpha(T_t) = 0.10 + 4(0.06) = 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$ 的矩形阶梯，单步高度 $1/n$，误差 $\Theta(1/n)$。要 $1/n \leq \epsilon$ 即 $n = \lceil 1/\epsilon \rceil$ 块矩形——$\Theta(1/\epsilon)$ 个叶。而斜树用 $y - x \leq 0$ 这一个分裂就能精确表示，0 误差。这正是轴对齐对角线上的代价。

参考文献

• 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 的前提——后续章节都直接建立在本章打下的这套机器之上。

系列导航