6.1 决策树、分裂准则与剪枝：每个叶子都是一块局部常数区域

若设备故障风险在载荷越过某个阈值后陡增，恶劣天气又会改变这个阈值，线性模型就需要合适的非线性项与交互项。决策树可以直接从数据中搜索这些条件。

树通过递归分区形成规则。成品看起来像几行 if，选择这些条件却仍要逐个比较分裂收益；数学没有缺席，只是换了工位。

本课目标

把树理解为对特征空间的递归分区；
正确计算分类不纯度、回归误差与加权分裂收益；
理解决策树怎样选择数值切分点并在叶子中预测；
区分提前停止与 cost-complexity pruning；
识别树在稳定性、外推、概率估计和解释上的边界。

1. 树把空间切成若干区域

以二叉 CART 风格的树为例，一个数值节点选择特征 $j$ 和阈值 $t$ ：

R_{L} = {x : x_{j} \leq t}, R_{R} = {x : x_{j} > t} .

后续节点继续切分左右区域。到达叶子后：

回归树通常输出该叶训练目标的均值；
分类树可输出类别计数形成的概率，再按决策规则选类别。

因此，普通回归树在每个叶子区域内给出常数预测。边界由一连串轴对齐切分组成；树可以自然表示阈值和特征交互，但斜边界可能需要很多小矩形近似。

2. 分类节点怎样衡量“不纯”

节点中第 $k$ 类的权重占比为 $p_{k}$ 。常见准则包括：

G i n i = 1 - \sum_{k} p_{k}^{2},

E n t r o p y = - \sum_{k} p_{k} \log p_{k} .

约定 $0 \log 0 = 0$ 。纯节点的两种不纯度都为 0。Gini 是从节点的加权类别分布中独立抽两次、标签不同的概率；若改成不放回抽取两行，概率就不同了。

回归树常以节点内 squared-error/variance 为准则。若业务损失更接近 absolute error、Poisson deviance 等，应使用相应实现并检查其叶值定义。

3. 分裂收益必须按子节点大小加权

父节点 $P$ 切成 $L, R$ ，以样本权重和 $W$ 表示节点大小：

Δ I = I (P) - \frac{W_{L}}{W_{P}} I (L) - \frac{W_{R}}{W_{P}} I (R) .

算术平均会让两个子节点各占一半影响，即使其中一个只占极小权重，也可能高估这个纯叶的收益。使用 sample_weight 时，类别比例和分裂收益都要按权重计算；最少叶样本数与最少叶权重仍是不同约束。

训练器在所有合法候选中寻找收益最大的分裂。这个贪心步骤只保证当前节点最好，不保证得到全局最优整棵树。

4. 数值阈值来自相邻不同取值之间

对相邻不同取值 $a < b$ ，在 $x \leq t$ 的规则下，任意 $t \in [a, b)$ 都产生相同的训练样本分区。中点是常见约定，取 $a$ 也合法；对重复值反复计算不会增加候选分区。

下面是 Python 3 / NumPy 的单节点、单特征扫描片段。需提供一维数值特征、可比较的类别标签，以及可选的非负样本权重。缺失值另设路由策略；是否接受返回的收益继续生长，由调用方决定。

python

import numpy as np

def weighted_gini(y, weight):
    _, inverse = np.unique(y, return_inverse=True)
    class_weight = np.bincount(inverse, weights=weight)
    probability = class_weight / class_weight.sum()
    return 1.0 - np.sum(probability ** 2)

def best_numeric_split(x, y, sample_weight=None, min_samples_leaf=1):
    x = np.asarray(x, dtype=float)
    y = np.asarray(y)
    if x.ndim != 1 or y.ndim != 1:
        raise ValueError("x and y must be one-dimensional")
    if not isinstance(min_samples_leaf, (int, np.integer)) or min_samples_leaf < 1:
        raise ValueError("min_samples_leaf must be a positive integer")
    weight = (
        np.ones(len(y), dtype=float)
        if sample_weight is None
        else np.asarray(sample_weight, dtype=float)
    )
    if weight.ndim != 1 or len(x) != len(y) or len(y) != len(weight):
        raise ValueError("x, y and sample_weight must have equal length")
    if not np.all(np.isfinite(x)):
        raise ValueError("x must contain finite values")
    if not np.all(np.isfinite(weight)) or np.any(weight < 0):
        raise ValueError("weights must be finite and nonnegative")
    if len(y) == 0:
        return None
    total_weight = weight.sum()
    if not np.isfinite(total_weight) or total_weight <= 0:
        raise ValueError("total weight must be finite and positive")
    if len(y) < 2 * min_samples_leaf:
        return None

    order = np.argsort(x, kind="mergesort")
    xs, ys, ws = x[order], y[order], weight[order]
    parent = weighted_gini(ys, ws)
    best = None

    for cut in np.flatnonzero(xs[:-1] < xs[1:]):
        left_size = cut + 1
        right_size = len(xs) - left_size
        if left_size < min_samples_leaf or right_size < min_samples_leaf:
            continue

        left_weight = ws[:left_size].sum()
        right_weight = ws[left_size:].sum()
        if left_weight <= 0 or right_weight <= 0:
            continue

        child_impurity = (
            left_weight / total_weight * weighted_gini(ys[:left_size], ws[:left_size])
            + right_weight / total_weight * weighted_gini(ys[left_size:], ws[left_size:])
        )
        gain = parent - child_impurity
        lo, hi = xs[cut], xs[cut + 1]
        threshold = lo / 2.0 + hi / 2.0
        if not lo <= threshold < hi:
            threshold = lo
        if best is None or gain > best["gain"]:
            best = {"threshold": threshold, "gain": gain}

    return best

传入 x=[1, 2, 3, 4]、y=[0, 0, 1, 1]，返回阈值 2.5、收益 0.5。中点写法避免 hi - lo 溢出；若两个浮点数之间没有可表示的中点，则退回 lo，仍保持同一训练分区。

成熟实现会用累计类别权重或累计和避免对每个候选重复切片，并同时扫描多个特征。近似/histogram 算法则先把连续值装入有限 bins，以少量精度换取训练速度和内存。

5. 叶子也有统计问题

分类叶中若 9 个训练样本有 8 个正例，未平滑概率是 $8 / 9$ 。叶子很小或类别稀少时，这个估计方差很大，容易输出 0 或 1。可通过以下方式控制：

增大 min_samples_leaf 或等价权重约束；
限制叶子数/深度；
在独立校准数据上做概率校准；
报告按叶大小、群体和时间切片的 log loss/Brier score。

类别标签由概率和阈值产生。即使树的类别准确率不错，也不能推断概率已经校准。

6. 提前停止不是唯一的剪枝方法

Pre-pruning 在生长过程中限制复杂度：

max_depth；
min_samples_split 与 min_samples_leaf；
max_leaf_nodes；
最小不纯度下降；
样本/叶权重约束。

这些值没有适用于所有数据的固定范围，应在不泄漏的 validation/CV 协议中选择。

Cost-complexity pruning 先考虑较大的树，再最小化：

R_{α} (T) = R (T) + α | \tilde{T} |,

其中 $R (T)$ 是叶节点风险之和， $| \tilde{T} |$ 是叶子数。增大 $α$ 会沿 weakest-link pruning 路径得到更小的子树。应在训练折内生成候选 pruning path，再由 validation 选择 $α$ ；不能看 test 后挑树。

7. 缺失值与类别特征取决于实现

“树天然支持缺失值”不是通用结论。不同库可能：

拒绝 NaN，要求 pipeline 先填补；
为每个切分学习默认缺失方向；
使用 surrogate split；
把缺失作为单独类别或额外指示特征。

部署时还要区分“确实未知”和“采集链路故障”。缺失模式变化本身可能造成漂移。

类别变量也不能随意映射为整数。编码为 red=1, blue=2, green=3 会引入虚构顺序；one-hot、目标编码和原生 categorical split 各有统计与实现条件，目标编码尤其必须在折内拟合。

8. 单棵树的优势与边界

优势：

不要求数值特征标准化；
可表示阈值和高阶交互；
小树能转写为明确规则；
精确候选分区依赖排序，严格递增变换在精确算术下保持分区；分箱和浮点舍入可能改变结果。

边界：

数据轻微变化可能改变上层分裂，结构不稳定；
叶内局部常数预测通常不能可靠外推；
深树会把噪声切成小叶；
轴对齐分区对平滑/斜边界可能低效；
“被树用于分裂”不等于因果重要。

可解释性也不是模型类型自动赠送的。几百个叶子的树很难人工理解；规则还依赖前处理、缺失路由和训练分布。

常见误区

树不需要数学：它在每个节点优化不纯度/损失。
每个观测值都要单独试一次阈值：相邻不同值定义候选分区，重复值不会增加分区。
树对缺失值天然鲁棒：是否支持及如何路由由实现决定。
深度取 3–6 最合适：容量必须由数据量、噪声、损失和验证协议决定。
小树一定可解释：还要审计特征语义、前处理和稳定性。

练习

手算一个三分类节点的 Gini、entropy 和两个候选分裂收益。
给 best_numeric_split 加上累计类别权重，避免每个候选重复统计。
在同一 CV 下比较 pre-pruning 与 cost-complexity pruning。
制造斜边界数据，观察树深度与叶子数怎样增长。

小结

决策树通过贪心分裂把特征空间划成局部区域。正确理解它，需要同时看到分裂准则、候选搜索、叶值估计和复杂度控制，而不是把它简化成一串直觉问题。

单棵树的主要困难是高方差。下一课让许多彼此不完全相同的树共同预测，研究平均为什么有效，以及它不能消除哪些误差。

第1章逻辑

第2章集合论

第3章证明方法

第4章递归、归纳与递推

第5章关系与函数

第6章组合数学

第7章图论

第8章概率与统计

第9章数论

第10章线性代数

第11章微积分与优化

第12章信息论与数值计算