决策树如何从数据中学出规则

上一节的线性候选用一条直线描述所有样本。如果规律在某个位置突然改变，一条直线就不够贴切。决策树采用另一种办法：先提问，把样本分组，再为每组给出预测。

本页只需要平均数、平方误差和上一节的基线概念。学完应能拿纸笔决定第一次切分，并解释停止条件。递归代码放在下一节。

1. 先看树要处理的对象

固定四个教学样本，不代表真实业务数据：

样本 i	唯一特征 x	标签 y
1	1	1
2	2	1
3	3	3
4	4	3

在代码里，X=[[1],[2],[3],[4]] 是四行一列，每行是一个样本；y=[1,1,3,3] 是对应的四个答案。预测时只提供 X。

最小树只有一个叶子，对所有人回答同一个数字。如果允许切一刀，可以问“x 是否小于等于 2.5”：左边回答 1，右边回答 3。

               x <= 2.5 ?
               /       \
             是         否
          预测 1       预测 3
          样本1、2     样本3、4

内部节点保存问题，叶子保存预测。模型训练要决定：问哪个特征、阈值是多少、还要不要继续问、最后回答什么。

2. 为什么叶子预测均值

设某个节点包含样本集合 $S$，暂时都预测常数 $c$。本页用平方误差和：

$$E(S,c)=\sum _{i\in S}(y_i-c{)}^2.$$

对 $c$ 求导并令其为零：

$$\frac{\partial E}{\partial c}=2\sum _{i\in S}(c-y_i)=0⟹c={\overline{y}}_S.$$

二阶导数是 $2|S|>0$，所以这是最小值。根节点预测均值 2，误差是 $1+1+1+1=4$。记最优常数下的误差为 $\mathrm{SSE}(S)$。

“叶子取均值”依赖平方损失。如果改用绝对误差，最优常数是中位数。不能换了目标仍不加思考地使用均值。

3. 阈值怎样成为可以搜索的对象

连续数值有无穷多个阈值，但有限样本的分组只有有限种。先排序并去重，在相邻不同数值之间取中点，得到 1.5、2.5、3.5。

例如 2.1 和 2.9 对训练样本的分组相同，取 2.5 是一种确定的代表。相等的特征值不能被同一个数值阈值拆到两边。

对特征 $j$ 和阈值 $t$，定义：

$$S_L=\{i:x_{ij}\le t\},S_R=\{i:x_{ij}>t\}.$$

比较切分后的总误差，选择下降最多的一刀：

$$\mathrm{\Delta }=\mathrm{SSE}(S)-\mathrm{SSE}(S_L)-\mathrm{SSE}(S_R).$$

阈值	左叶均值	右叶均值	子节点 SSE 总和	下降 Δ
1.5	1	7/3	8/3	4/3
2.5	1	3	0	4
3.5	5/3	3	8/3	4/3

手算第一行：右侧标签是 [1,3,3]，均值 $7/3$，误差为 $16/9+4/9+4/9=8/3$。因此第二行最优。

如果用均方误差 MSE，比的是按样本数加权的子节点 MSE：

$$\frac{|S_L|}{|S|}\mathrm{MSE}(S_L)+\frac{|S_R|}{|S|}\mathrm{MSE}(S_R).$$

直接把左右 MSE 相加会让一个样本和一百个样本的节点拥有相同权重，改变优化问题。

4. 多特征和递归只是在重复同一件事

多个特征时，对每一列生成候选阈值，再从所有候选中挑最优的一刀。确定分组后，左右节点各自继续搜索。每个节点看到的是落入自己的样本子集。

这是一种贪心搜索：当前选最好的切分，不枚举未来整棵树的所有结构。它并不保证得到全局最优树。

有一个容易漏掉的反例：XOR 数据中，两列都是 0/1，标签只在两列不同时为 1。第一次单列切分可能没有平方误差下降，第二层却可以完全区分。下一节的实现要求严格正增益，因此会在根部停止；这正是该停止规则的能力边界。

通常在以下情况停下来：达到深度限制、样本不足、没有合法阈值，或误差下降没有超过要求。停止时输出当前节点的标签均值。

5. 分类树换的是什么

树仍然在提问和分组，但叶子输出类别或类别频率，切分评价改成分类不纯度。设节点中类别 $k$ 的比例为 $p_k$：

$$\mathrm{Gini}=1-\sum _k{p}_k^2,H=-\sum _k{p}_k{\log }_2{p}_k.$$

约定 $0\log 0=0$。把本页标签 1、3 当作两种类别，根节点各占一半，Gini 为 0.5，熵为 1 bit。阈值 2.5 让两个子节点都只剩一种类别，两种不纯度都降到零。

分类同样按子节点样本数加权。节点越纯，只表示训练标签越一致；一片只有一个样本的叶子也很纯，却可能无法代表新样本。分类树定义和 CART 数值切分可对照 scikit-learn 决策树说明。

6. 验证与反事实

在仓库根目录运行下一节使用的同一实现：

python3 examples/python/tree_boosting.py

首行应包含 split=2.5 和 gain(SSE)=4.0。先预测再检查以下变化：

• 标签都加 5：切分不变，叶子值都加 5，因为与均值的偏差不变。
• 标签都乘 2：叶子值乘 2，SSE 与增益乘 4。
• 特征全变为 1：没有合法阈值，只能预测标签均值。
• 新输入 x=100：仍落入右叶，预测 3；普通常数叶树不会沿某条斜率向外推。

小结、自测与下一步

树学习的是“分区规则 + 区域内预测”。训练误差降低不能替代泛化评估，深度和叶子样本数需要结合验证集判断。

1. 根节点为什么预测 2 而不是 1？
2. 阈值恰好等于输入时往哪边走？
3. 训练误差为零是否证明规律正确？

参考答案

1. 平方误差下均值使误差最小；预测 1 的 SSE 是 8，预测 2 是 4。
2. 本页统一采用 <= 走左侧，训练和预测必须保持相同约定。
3. 没有。四个教学样本可以被记住，需要另外的未见数据与基线判断泛化。

下一步：从零实现 CART 回归树。