决策树怎样选出第一条规则？从基尼不纯度到剪枝

上一篇的 K 近邻（K-Nearest Neighbors，KNN）能用局部样本拼出弯曲边界，但每次预测都要保存并搜索训练数据。如果希望把训练数据压缩成一组快速执行、可以逐步解释的规则，可以换一种思路：反复询问“某个特征是否不大于某个阈值”。

这就是决策树（Decision Tree）。它不要求线性边界，也不依赖特征之间的欧氏距离；真正困难的部分是：候选特征和阈值那么多，树怎样选出第一条规则，又怎样避免一路分到只记住训练样本？

本文只讲透三个紧密环节：不纯度如何衡量节点混杂程度、一次分裂如何比较候选规则，以及树如何通过限制生长和剪枝控制过拟合。

01 一棵树怎样把输入变成预测？#

二分类树的内部节点保存一个判断：

x_j\le t

$x\in\mathbb{R}^{D}$ ：一个含 $D$ 个特征的样本；
$j\in\{1,\ldots,D\}$ ：当前检查的特征编号；
$t\in\mathbb{R}$ ：阈值（Threshold）；
条件成立进入左子树，否则进入右子树。

训练数据形状和预测数据流是：

训练：X [N,D] + y [N]
          │ 搜索 (feature j, threshold t)
          ▼
     二叉规则树（节点保存 j、t、样本统计）

推理：X_query [Q,D]
          │ 每个样本从根节点向下
          ▼
     leaf_id [Q] ──► 叶节点类别比例 [Q,C]
                         │ argmax
                         ▼
                    prediction [Q]

text

$N$ ：训练样本数；
$Q$ ：查询样本数；
$C$ ：类别数；
每个叶节点保存到达该处的训练样本类别计数，分类概率由计数比例得到。

例如：

                 x₁ <= 2.5 ?
                 /          \
              是/            \否
               /              \
          预测类别 0       x₁ <= 7.5 ?
                           /          \
                        类别 1       类别 0

text

新样本只需执行根到叶的一串 if-then，不再扫描全部训练样本。若树深为 $h$ ，单样本预测通常只访问约 $h$ 个节点。

02 节点“不纯”到底是什么意思？#

若一个节点中的样本全属同一类，它已经足够纯，不必继续分裂；若各类混在一起，则需要寻找规则将它们分开。

对含 $C$ 类的节点 $S$ ，第 $c$ 类比例为：

p_c=\frac{n_c}{|S|}

基尼不纯度（Gini Impurity）定义为：

G(S)=1-\sum_{c=1}^{C}p_c^2

$n_c$ ：节点中第 $c$ 类样本数；
$|S|$ ：节点样本总数；
$G(S)$ ：一个非负标量，越小表示越纯。

二分类中若正类比例为 $p$ ：

G(S)=1-p^2-(1-p)^2=2p(1-p)

正负样本数	正类比例 $p$	基尼不纯度
6 正、0 负	1	0
3 正、3 负	0.5	0.5
1 正、5 负	$1/6$	$10/36\approx0.278$

它可以理解为：按节点类别比例随机给一个样本贴标签时，标签与真实类别不一致的概率。这里用它来比较分裂，不要把它与基尼系数或训练后的业务指标混为一谈。

03 一条候选规则怎样打分？#

候选规则 $(j,t)$ 把父节点 $S$ 分成：

S_L=\{(x_i,y_i)\in S\mid x_{ij}\le t\}

S_R=S\setminus S_L

不能直接相加左右不纯度，因为含 100 个样本的子节点应比含 1 个样本的子节点影响更大。分裂后的加权不纯度为：

G_{split}=\frac{|S_L|}{|S|}G(S_L)+\frac{|S_R|}{|S|}G(S_R)

不纯度下降（Impurity Decrease）为：

\Delta G=G(S)-G_{split}

训练算法选择让 $\Delta G$ 最大的候选分裂。

父节点样本 S
   │ 枚举每个特征 j
   │ 枚举相邻取值之间的候选阈值 t
   ▼
计算左、右类别计数
   │
   ▼
加权子节点不纯度 G_split
   │
   ▼
选取最大 ΔG 的 (j,t)

text

只需要考察排序后相邻不同取值之间的阈值。相同特征值之间放阈值不会产生新的数据划分。

04 用六个样本手算根节点#

先只看一个特征 $x_1$ ：

样本	$x_1$	标签 $y$
A	1	0
B	2	0
C	3	1
D	6	1
E	7	1
F	8	0

父节点有 3 个正类、3 个负类：

G(S)=1-(3/6)^2-(3/6)^2=0.5

候选阈值取相邻值中点： $1.5,2.5,4.5,6.5,7.5$ 。

比较阈值 $t=2.5$ #

左侧标签为 $[0,0]$ ，完全纯：

G(S_L)=0

右侧标签为 $[1,1,1,0]$ ，正类比例为 $3/4$ ：

G(S_R)=1-(3/4)^2-(1/4)^2=0.375

因此：

G_{split}=\frac{2}{6}\times0+\frac{4}{6}\times0.375=0.25

\Delta G=0.5-0.25=0.25

比较阈值 $t=4.5$ #

左右标签分别为 $[0,0,1]$ 和 $[1,1,0]$ ，两边不纯度都是 $4/9$ ：

G_{split}=\frac36\times\frac49+\frac36\times\frac49=\frac49

\Delta G=0.5-\frac49\approx0.056

完整比较为：

阈值 $t$	分裂后加权不纯度	不纯度下降 $\Delta G$
1.5	0.400	0.100
2.5	0.250	0.250
4.5	0.444	0.056
6.5	0.500	0.000
7.5	0.400	0.100

所以根节点选择 $x_1\le2.5$ 。对右侧四个样本继续搜索，阈值 7.5 能把三个正类与一个负类完全分开，最终得到前面的三叶规则。

交互检查：为什么不直接选让某一个子节点最纯的规则？

阈值 1.5 能让只含 A 的左节点完全纯，但右节点仍混杂；若忽略样本数和另一个子节点，会偏爱不断剥离单个样本的规则。加权不纯度同时评价两个子节点。

05 递归生长的伪代码#

grow(node_samples, depth):
    if labels are pure:
        return leaf(class proportions)

    if depth or sample constraints forbid splitting:
        return leaf(class proportions)

    best_gain = -infinity
    for feature j in candidate_features:
        sort node samples by X[:, j]
        for threshold t between adjacent distinct values:
            split samples into left and right
            gain = parent_impurity - weighted_child_impurity
            keep (j, t) if gain is larger

    if best_gain is below required minimum:
        return leaf(class proportions)

    return node(
        rule=(best_feature, best_threshold),
        left=grow(left_samples, depth + 1),
        right=grow(right_samples, depth + 1),
    )

text

这是贪心算法（Greedy Algorithm）：每个节点只选择当前下降最多的规则，不会穷举所有可能的整棵树。局部最优分裂未必组成全局最小的树，但完整搜索的组合数量过大，贪心递归提供了实用折中。

对连续特征，训练阶段通常需要排序和扫描候选阈值；预测阶段只做比较。树不需要像 KNN 那样先做标准化，因为单调缩放不会改变单个特征的排序与可实现划分。

06 为什么完全生长会过拟合？#

若没有限制，树可以继续分裂到叶节点只剩一个或很少样本。此时训练误差可能为 0，但一个异常点就会生成很深、很窄的规则区域。

浅树：                         过深的树：

        x₂ <= 4                    x₂ <= 4
       /       \                  /       \
    类别 0     类别 1         类别 0      x₁ <= 7.01
                                           /       \
                                      x₂ <= 4.03   类别 1
                                      /       \
                                  类别 1    单个噪声点

text

常见的预剪枝（Pre-pruning）控制包括：

参数	阻止什么	增大限制后的效果
`max_depth`	路径无限加深	规则更短、偏差可能升高
`min_samples_split`	太小的内部节点继续分	减少脆弱分裂
`min_samples_leaf`	产生只含极少样本的叶子	概率更平滑
`max_leaf_nodes`	叶子总数过多	直接限制模型大小
`min_impurity_decrease`	收益太小仍分裂	忽略微弱局部改进

这些值必须用开发数据选择，不能根据封存测试集反复调整。

07 代价复杂度剪枝怎样删掉枝条？#

另一种办法是先生成较大的树，再做后剪枝（Post-pruning）。最小代价复杂度剪枝（Minimal Cost-Complexity Pruning）比较：

R_\alpha(T)=R(T)+\alpha|\widetilde T|

$T$ ：某棵候选子树；
$R(T)$ ：叶节点不纯度按样本权重汇总后的训练代价；
$|\widetilde T|$ ：叶节点数量；
$\alpha\ge0$ ：每增加一个叶子要支付的复杂度价格。

$\alpha=0$ 时几乎不惩罚树大小； $\alpha$ 增大后，只有能显著降低不纯度的枝条值得保留。scikit-learn 中对应 ccp_alpha。

cost_complexity_pruning_path(X_train, y_train) 会返回一串候选 ccp_alphas 及对应叶节点不纯度。应在训练数据上产生候选，再由交叉验证选择，而不是挑训练准确率最高的值。

08 用当前 scikit-learn API 实现#

截至本文写作时，scikit-learn 1.9 的 DecisionTreeClassifier 默认 criterion='gini'、splitter='best'、ccp_alpha=0.0。默认大小限制会让树一直长到叶子纯净或无法再分，因此实际项目应显式验证复杂度。

import numpy as np
from sklearn.model_selection import GridSearchCV, StratifiedKFold
from sklearn.tree import DecisionTreeClassifier, export_text

# X_train: [N, D]；y_train: [N]
base_tree = DecisionTreeClassifier(
    criterion='gini',
    random_state=42,
)

path = base_tree.cost_complexity_pruning_path(X_train, y_train)
candidate_alphas = np.unique(path.ccp_alphas)  # [num_subtrees]

search = GridSearchCV(
    estimator=base_tree,
    param_grid={
        'ccp_alpha': candidate_alphas,
        'min_samples_leaf': [1, 5, 20],
        'max_depth': [None, 3, 6],
    },
    scoring='balanced_accuracy',
    cv=StratifiedKFold(n_splits=5, shuffle=True, random_state=42),
    n_jobs=-1,
    refit=True,
)
search.fit(X_train, y_train)

tree = search.best_estimator_
predictions = tree.predict(X_val)          # [num_val]
probabilities = tree.predict_proba(X_val)  # [num_val, C]
leaf_ids = tree.apply(X_val)               # [num_val]
paths = tree.decision_path(X_val)           # [num_val, num_nodes] 稀疏矩阵

print(search.best_params_)
print(export_text(tree, feature_names=list(feature_names)))

python

重要 API 的语义：

fit(X,y) 接收 [N,D] 和 [N]，学习树结构与叶节点类别统计；
predict_proba(X) 返回 [Q,C]，列顺序由 classes_ 给出；
apply(X) 返回每个样本到达的叶节点编号 [Q]；
decision_path(X) 返回 [Q,num_nodes] 的稀疏指示矩阵，指出每个样本访问了哪些节点；
tree_.feature 和 tree_.threshold 保存内部节点使用的特征编号与阈值；
feature_importances_ 是基于训练不纯度下降的汇总，不等于因果重要性。

09 怎样解释一条预测，而不是只画整棵树？#

大树的全图很快变得不可读。调试单个样本时，更有效的是打印它经过的规则：

sample = X_val[[0]]                       # [1, D]
node_indicator = tree.decision_path(sample)
leaf_id = tree.apply(sample)[0]

for node_id in node_indicator.indices:
    if node_id == leaf_id:
        print('leaf', node_id, tree.predict_proba(sample)[0])
        continue

    feature_id = tree.tree_.feature[node_id]
    threshold = tree.tree_.threshold[node_id]
    value = sample[0, feature_id]
    operator = '<=' if value <= threshold else '>'
    print(feature_names[feature_id], value, operator, threshold)

python

需要同时记录原始样本 ID、使用的模型版本和特征定义。若线上特征顺序改变，而模型仍按旧列号读取，路径看起来合法却会执行完全错误的规则。

10 常见错误与最短调试路径#

用训练准确率挑深度。 完全生长的树几乎总占优势；应比较交叉验证或独立验证指标。
把标准化当必需步骤。 树按单特征阈值切分，通常不需要缩放；真正要固定的是列顺序、单位和缺失值语义。
类别失衡仍只看普通准确率。 打印每类召回率、混淆矩阵和叶节点类别计数，必要时验证 class_weight。
把高基数 ID 当普通数值。 树可能用设备 ID、订单号切出偶然群组；这通常不具备可推广含义。
把 feature_importances_ 当真相。 基于不纯度的重要性偏爱可切分点多的特征，也会在相关特征间任意分配功劳；用留出集置换重要性补充检查。
忽略概率的样本量。 叶子只有 2 个训练样本且都为正时，predict_proba 会给出 1.0，但证据远弱于含 2000 个正样本的叶子。
结果无法复现。 多个候选分裂收益相同时选择可能变化；固定 random_state 并记录库版本。

最小结构检查：

assert X_train.ndim == 2 and y_train.ndim == 1
assert X_train.shape[0] == y_train.shape[0]
assert np.isfinite(X_train).all()
assert tree.get_depth() <= 6 or search.best_params_['max_depth'] is None
assert tree.get_n_leaves() >= 2
print('depth:', tree.get_depth(), 'leaves:', tree.get_n_leaves())

python

11 失败场景与相近方法边界#

单棵树的最大弱点是高方差（High Variance）：训练数据稍微变化，靠近根部的最佳分裂就可能改变，整棵下游结构随之重排。

方法	边界形状	是否需要缩放	主要优点	主要限制
决策树	轴对齐、分段常数	通常不需要	非线性、规则可追踪、推理快	不稳定、易过拟合
KNN	局部距离形成	通常需要	几乎不训练、局部灵活	推理和存储昂贵、高维退化
逻辑回归	全局线性	通常有益	系数紧凑、概率目标清晰	原始空间只能线性分割
规则系统	人工定义	取决于规则	业务约束明确	维护成本高、难从数据自动适应

决策树还不擅长需要平滑外推的回归：叶节点输出训练目标均值，超出训练特征范围后不会像线性模型那样自然延伸。若数据噪声很高、特征轻微变化不应造成预测跳变，也要特别检查树边界的稳定性。

12 今天真正需要记住什么？#

决策树用一串单特征阈值把特征空间递归切成叶节点，预测时只沿根到叶执行规则。
基尼不纯度衡量类别混杂程度；候选分裂由左右子节点的样本数加权后比较。
训练在每个节点贪心选择不纯度下降最大的 (feature, threshold)，并不保证得到全局最优整棵树。
完全生长容易记住噪声，应在开发数据上选择深度、最小叶样本数或 ccp_alpha。
解释时既要看经过的规则，也要看叶节点样本量；不纯度重要性不能直接解释为因果作用。

13 思考题与小练习#

练习 1：手算一个候选分裂

父节点标签为 [0,0,0,1,1]，某规则分出左侧 [0,0]、右侧 [0,1,1]。父节点基尼不纯度为 $1-(3/5)^2-(2/5)^2=0.48$ ；右侧为 $4/9$ ，加权子节点不纯度为 $(2/5)0+(3/5)(4/9)=4/15\approx0.267$ ，下降约 0.213。

练习 2：为什么增大 min_samples_leaf 会平滑概率？

每个叶子必须由更多样本支持，单个异常点无法独占一个叶子；类别比例的方差通常下降，但太大也会抹去真实的小群体。

练习 3：验证树对缩放不敏感的边界

把一个连续特征从“元”改成“万元”，重新训练并比较预测。严格单调缩放通常只改变阈值数值，不改变划分；若数据预处理发生舍入、截断或缺失值替换，划分仍可能改变。

14 下一篇预告#

剪枝能让一棵树更简单，却没有消除“训练数据稍变，整棵树就可能重排”的高方差。下一篇将让许多棵树分别观察不同的自助样本和特征子集，再把它们的概率平均，解释随机森林为何常比任何一棵成员树稳定。

01 一棵树怎样把输入变成预测？#

02 节点“不纯”到底是什么意思？#

03 一条候选规则怎样打分？#

04 用六个样本手算根节点#

比较阈值 t=2.5t=2.5t=2.5#

比较阈值 t=4.5t=4.5t=4.5#

05 递归生长的伪代码#

06 为什么完全生长会过拟合？#

07 代价复杂度剪枝怎样删掉枝条？#

08 用当前 scikit-learn API 实现#

09 怎样解释一条预测，而不是只画整棵树？#

10 常见错误与最短调试路径#

11 失败场景与相近方法边界#

12 今天真正需要记住什么？#

13 思考题与小练习#

相关工作#

14 下一篇预告#

比较阈值 $t=2.5$ #

比较阈值 $t=4.5$ #