决策树:CART、不纯度准则与剪枝 — 树模型与核方法

周一早盘九点二十,你接手了离职同事留下的 alpha 模型——一棵深度 15 的 CART(Classification and Regression Tree, CART)树,在三年沪深300 成分股日度面板上训练,特征是动量、价值、质量、低波、5 日收益、20 日波动率、换手率等 12 个变量,目标是预测下一日超额收益方向(涨/跌)。样本内训练精度 100%,样本外只剩 51%——几乎等同于抛硬币。PM 推过笔记本:「这棵树为什么这样?直接扔?」本课不扔——你会先弄清一棵树是什么对象、它的偏差—方差曲线为什么这么陡(参 2.6.1-2),再用剪枝把它压回 56%–58% 的可用区间。下一课才轮到「把很多棵这种树平均起来」的随机森林。

一、树作为一个假设类:分段常数预测器

一棵决策树 $T$ 把特征空间 $\mathcal X$ 切成 $M$ 块互不重叠的矩形 $\{R_1, \dots, R_M\}$ ——每一次内部分裂都是一条轴对齐(axis-aligned)阈值 $x_j \leq s$ ,沿着特征 $j$ 把当前区块劈成左右两半。在叶节点 $R_m$ 内,模型输出一个常数 $c_m$ ,合起来就是

h_T(x) = \sum_{m=1}^{M} c_m \, \mathbf{1}\{x \in R_m\}

这是一个分段常数(piecewise-constant)的非参数预测器:没有全局函数形式,模型复杂度完全由「树多深、叶子多少」决定。

叶子常数 $c_m$ 取什么?直接由 2.6.1 监督学习基础里的贝叶斯最优预测器(Bayes-optimal predictor)给出。在区块 $R_m$ 内,贝叶斯最优预测器就是条件期望或条件众数:在平方误差损失下, $c_m^\star = \mathbb E[Y \mid X \in R_m]$ ,经验对应物即 $R_m$ 内 $y_i$ 的样本均值;在 0-1 损失下, $c_m^\star = \arg\max_k \mathbb P(Y = k \mid X \in R_m)$ ,经验对应物即 $R_m$ 内的多数类。所以叶子常数不是另一个需要调的超参数,它由「分到这片叶子上的样本 + 你选的损失」一锤定音,真正的自由度全在「怎么切」上。

二、不纯度准则:基尼、熵、误分类

要量化「这片叶子有多干净」,需要一个不纯度函数 $I(p)$ ,其中 $p = (p_1, \dots, p_K)$ 是叶内各类的样本比例。CART 系列常用三种。前两种是基尼指数(Gini impurity)与 Shannon 熵:

I_G(p) = \sum_{k=1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K} p_k^2

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

第三种是误分类误差 $I_E(p) = 1 - \max_k p_k$ 。回归任务里则直接用方差 $I(R) = \tfrac{1}{|R|} \sum_{i \in R} (y_i - \bar y_R)^2$ ,对应叶子常数即均值。

把这张图记在心里:基尼与熵奖励「把叶子推向纯」——任何让 $p$ 离 0 或 1 更近的分裂都会被记一笔可见的减分;误分类误差对中间区域钝感,常常给出「分裂前后误分类率不变」的虚假平局。这就是为什么 sklearn 的 DecisionTreeClassifier 默认 criterion='gini' 而不是 criterion='misclassification'——前者的梯度信息密度更大,贪心搜索更不容易卡死。周志华西瓜书第 4 章把熵差称作「信息增益」,与这里的 $H$ (parent) − 子节点加权 $H$ 完全是同一对象。

三、贪心分裂:CART 的核心循环

在每个内部节点,CART 遍历所有(特征 $j$ ,阈值 $s$ )候选,挑使不纯度减少(impurity reduction)最大的那一对:

\Delta I(j, s) = I(\text{parent}) - \frac{n_L}{n} I(\text{left}) - \frac{n_R}{n} I(\text{right})

其中 $n_L, n_R$ 是分裂后两侧样本数。这是一次局部最优:它只看当前这一步,不为「往下三层之后能不能切得更好」做让步。已知「全局最优树」问题是 NP-hard,贪心是工程上唯一可承受的妥协,因此 CART 树是局部最优而非全局最优。

Formula Explorer

2*p*(1-p)

回到开头那棵沪深300 的树:第一刀往往切在动量上——5 日收益的 $\Delta I$ 一骑绝尘,模型先按动量正负把样本劈成两半,后续每一刀在子树里递归。这是树作为因子模型解释器的实用价值:看根附近用了哪些特征,你就知道这棵树「相信」哪几类信号。

四、手算示例:六行数据,一次切分

下表 6 行,两个数值特征 $X_1, X_2$ ,二分类标签 $y \in \{0, 1\}$ ,父节点类比例 $p = (3/6, 3/6)$ :

i	$X_1$	$X_2$	$y$
1	0.1	0.7	0
2	0.2	0.4	0
3	0.3	0.9	0
4	0.7	0.2	1
5	0.8	0.6	1
6	0.9	0.5	1

候选 A:在 $X_1 \leq 0.5$ 切;候选 B:在 $X_2 \leq 0.5$ 切。父节点基尼为 $I_G = 2 \cdot 0.5 \cdot 0.5 = 0.5$ 。任务:用基尼准则算出两条候选的 $\Delta I$ ,选出 CART 赢家。两个渐进式 Hint 留在练习里。

五、代价复杂度剪枝:把过深的树压回去

回看开头:深度 15、训练 100%、样本外 51%——典型的「叶子过多,每片叶子只盖少量训练样本,把噪声当信号记进去」。CART 的解药是代价复杂度剪枝(cost-complexity pruning):对带罚的风险

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

寻找最优子树。 $|T|$ 是叶子数, $\alpha \geq 0$ 是惩罚因子: $\alpha = 0$ 时返回原大树, $\alpha \to \infty$ 时塌成根节点。Breiman 等(1984)证明:存在一条「最弱链接」(weakest-link)剪枝路径,把 $\alpha$ 从 0 单调拉到无穷,会得到一列有限个嵌套子树 $T_0 \supset T_1 \supset \dots \supset T_{\text{root}}$ ,每个 $\alpha$ 区间对应一个固定的最优子树。 $\alpha$ 本身用 k 折交叉验证(k-fold cross-validation,参 2.6.1-4)从验证集风险曲线的最低点反解;那条曲线两端高、中间低,中间那片低谷就是「不过拟合也不欠拟合」的甜蜜区。剪枝完成后,样本外精度从 51% 抬回 56%–58% 是常见量级——还远不够,但已经说明:不是「这棵树不该存在」,而是「这棵树太深」。

六、练习

Exercise

用第四节那张 6 行表,完成下列步骤:

(a) 对候选 A( $X_1 \leq 0.5$ )分别写出左/右两侧的样本编号、类计数 $(n_0, n_1)$ 与基尼 $I_G$ 。

(b) 对候选 B( $X_2 \leq 0.5$ )做同样的事。

提示

先按阈值把 6 行分到左右两堆,再逐堆数

y = 0

与

y = 1

的个数,代二分类基尼

I_G = 2 p (1 - p)

即可。候选 A 把样本

\{1, 2, 3\}

划到左、

\{4, 5, 6\}

划到右;候选 B 把

\{2, 4, 6\}

划到左、

\{1, 3, 5\}

划到右。

提示

候选 A:左

\{1,2,3\}

全为 0,右

\{4,5,6\}

全为 1,

I_L = I_R = 0

\Delta I_A = 0.5

。候选 B:左

\{2,4,6\}

类比

(1/3, 2/3)

,右

\{1,3,5\}

类比

(2/3, 1/3)

I_L = I_R = 4/9

\Delta I_B \approx 0.056

。CART 取

\Delta I

最大者,赢家是候选 A;左右已纯,这一支长成两片叶子止步。

七、通往下一站

到这里你已经能把一棵决策树拆成三件事:递归轴对齐划分给出分段常数预测器、不纯度减少驱动贪心分裂、代价复杂度剪枝把过深的树压回交叉验证甜蜜区。但开头那棵沪深300 树的根本困境没消失——单棵树的偏差—方差曲线天生陡:浅树偏差大,深树方差爆炸,剪枝只能在中间走平衡木,样本外极限封顶在低 60% 一带。下一课换思路:不去优化「一棵树」,而是同时训练成百上千棵高方差的树,再把它们的预测平均——只要这些树彼此弱相关,平均后的方差会按 $1/B$ 的速度衰减。这就是 Bagging 与随机森林的核心想法,也是为什么 CN 私募的多因子选股线上几乎不会单独部署一棵 CART:树作为基础学习器很强,作为终端模型太脆。