第4章 决策树

为什么从问题合同开始

、、、、、共同构成本页的学习坐标。把决策树学习还原为递归划分、停止、叶节点决策和剪枝的完整程序，并逐项核对信息增益、增益率与基尼指数。

机器学习不是先选流行算法再寻找数据，而是先写清任务对象、可观测属性、目标变量或反馈、数据生成过程、允许使用的信息和错误代价。训练集用于估计模型，验证集用于选择结构与超参数，测试集只在所有决定冻结后评价一次。聚类、半监督和强化学习虽然反馈形式不同，也必须给出对应的独立证据，不能把训练目标本身当作泛化结论。

每次实验记录样本标识、折分策略、预处理拟合范围、特征顺序、随机种子、数值精度、依赖版本和停止规则。模型训练保存每步目标分解、关键状态与更新；模型选择保存所有候选而不是只留最好一次；失败样本与成功样本使用同一管线。这样才能区分概念假设错误、数据泄漏、数值错误、优化未收敛和抽样波动。

阅读时先预测：若只改变一个条件，第一处应该变化的是输入表示、模型状态、目标项、参数更新、预测分布还是评价轨迹？随后运行最小样本并在第一条不一致处停止。继续观察下游准确率通常只会增加噪声。任何修复都清空派生产物并从原始数据重放，防止错误状态污染后续结论。

数学骨架与可核查量

经验风险把冻结训练样本上的逐例损失聚合：

$$\widehat R(f)=\frac{1}{m}\sum_{i=1}^{m}\ell\bigl(f(x_i),y_i\bigr).$$

结构约束或先验通过正则项进入训练目标：

$$\mathcal J(\theta)=\widehat R(f_\theta)+\lambda\Omega(\theta).$$

模型选择在验证数据上完成，测试风险不得参与选择：

$$\hat\lambda=\arg\min_{\lambda\in\Lambda}\widehat R_{\mathrm{valid}}(f_\lambda),\qquad \widehat R_{\mathrm{test}}(f_{\hat\lambda})\text{ once}.$$

本页专属可核查关系为：

$$\operatorname{Gain}(D,a)=\operatorname{Ent}(D)-\sum_{v}\frac{|D^{v}|}{|D|}\operatorname{Ent}(D^{v}).$$

信息增益衡量按属性划分后熵的下降，取值多的属性可能天然占优，因此还需理解增益率的校正及其偏好。 实现时同时检查输入输出形状、有限值、约束残差、目标变化方向、概率归一或守恒关系，并用可枚举小样本或有限差分建立独立基线。

机制辨析

1. 决策树以根到叶路径表达一组可读规则。训练过程不仅是选属性，还包括纯叶、属性耗尽、空分支、连续值、缺失值和剪枝的决策。
2. 基本流程递归选择划分属性并为每个取值创建分支。若节点样本同类则停止；属性耗尽时用多数类；空分支使用父节点分布而非虚构样本。
3. 划分选择比较信息增益、增益率和基尼指数。三者的偏好不同，候选集合、权重和并列规则必须固定，才能复现树结构。
4. 预剪枝在展开前用验证集判断，计算便宜但可能阻止有益组合；后剪枝先长满再回退，通常更稳但成本更高。验证集不可兼作最终测试。
5. 连续属性对排序后相邻值中点枚举阈值，同一属性可在后续节点再次使用。缺失值可按无缺失样本估计属性质量，并按分支概率分配权重。
6. 多变量决策树用若干属性的线性组合形成斜划分，能用较浅树表示斜边界，但节点优化更复杂、解释也从单属性规则变为局部超平面。
7. 阅读材料连接ID3、C4.5、CART与可微分树。比较算法时要区分划分准则、剪枝策略和缺失值处理，而不是只比较名称。

本章机制必须与替代解释分开。例如训练风险下降可能来自容量增加、泄漏、更多计算或随机好运，而不一定来自目标机制；概率输出可能已归一却未校准；凸目标可全局求解却仍受错误特征和分布偏移影响。对照实验只改变一个因素，并让简单基线获得相同数据、调参机会和资源预算。

权威目录逐项讲解

第4章 决策树

决策树以根到叶路径表达一组可读规则。训练过程不仅是选属性，还包括纯叶、属性耗尽、空分支、连续值、缺失值和剪枝的决策。

学习“第4章 决策树”时先在“冻结数据合同”冻结输入、样本身份、特征形状、随机状态和适用假设，再进入“计算模型状态”只改变一个条件。至少保存目标值、关键中间量、更新前后状态和独立评价；若最终指标改善但机制预期的第一处变化没有发生，应先排查泄漏、索引、尺度、优化容差和随机性，不能用末端分数覆盖首错。

通过标准包含四层：能够准确解释定义与适用前提；能够在极小样本上手算公式或枚举状态；能够用固定种子复现算法一步；能够构造一个破坏前提的反例并指出停止位置。修复后清空派生特征、缓存、伪标签、模型状态和评价结果，从冻结原始样本完整重放。

4.1 基本流程

基本流程递归选择划分属性并为每个取值创建分支。若节点样本同类则停止；属性耗尽时用多数类；空分支使用父节点分布而非虚构样本。

学习“4.1 基本流程”时先在“计算模型状态”冻结输入、样本身份、特征形状、随机状态和适用假设，再进入“核对目标与约束”只改变一个条件。至少保存目标值、关键中间量、更新前后状态和独立评价；若最终指标改善但机制预期的第一处变化没有发生，应先排查泄漏、索引、尺度、优化容差和随机性，不能用末端分数覆盖首错。

通过标准包含四层：能够准确解释定义与适用前提；能够在极小样本上手算公式或枚举状态；能够用固定种子复现算法一步；能够构造一个破坏前提的反例并指出停止位置。修复后清空派生特征、缓存、伪标签、模型状态和评价结果，从冻结原始样本完整重放。

4.2 划分选择

划分选择比较信息增益、增益率和基尼指数。三者的偏好不同，候选集合、权重和并列规则必须固定，才能复现树结构。

学习“4.2 划分选择”时先在“核对目标与约束”冻结输入、样本身份、特征形状、随机状态和适用假设，再进入“执行学习或推断”只改变一个条件。至少保存目标值、关键中间量、更新前后状态和独立评价；若最终指标改善但机制预期的第一处变化没有发生，应先排查泄漏、索引、尺度、优化容差和随机性，不能用末端分数覆盖首错。

通过标准包含四层：能够准确解释定义与适用前提；能够在极小样本上手算公式或枚举状态；能够用固定种子复现算法一步；能够构造一个破坏前提的反例并指出停止位置。修复后清空派生特征、缓存、伪标签、模型状态和评价结果，从冻结原始样本完整重放。

4.3 剪枝处理

预剪枝在展开前用验证集判断，计算便宜但可能阻止有益组合；后剪枝先长满再回退，通常更稳但成本更高。验证集不可兼作最终测试。

学习“4.3 剪枝处理”时先在“执行学习或推断”冻结输入、样本身份、特征形状、随机状态和适用假设，再进入“独立评估泛化”只改变一个条件。至少保存目标值、关键中间量、更新前后状态和独立评价；若最终指标改善但机制预期的第一处变化没有发生，应先排查泄漏、索引、尺度、优化容差和随机性，不能用末端分数覆盖首错。

通过标准包含四层：能够准确解释定义与适用前提；能够在极小样本上手算公式或枚举状态；能够用固定种子复现算法一步；能够构造一个破坏前提的反例并指出停止位置。修复后清空派生特征、缓存、伪标签、模型状态和评价结果，从冻结原始样本完整重放。

4.4 连续与缺失值

连续属性对排序后相邻值中点枚举阈值，同一属性可在后续节点再次使用。缺失值可按无缺失样本估计属性质量，并按分支概率分配权重。

学习“4.4 连续与缺失值”时先在“独立评估泛化”冻结输入、样本身份、特征形状、随机状态和适用假设，再进入“定位首个分叉”只改变一个条件。至少保存目标值、关键中间量、更新前后状态和独立评价；若最终指标改善但机制预期的第一处变化没有发生，应先排查泄漏、索引、尺度、优化容差和随机性，不能用末端分数覆盖首错。

通过标准包含四层：能够准确解释定义与适用前提；能够在极小样本上手算公式或枚举状态；能够用固定种子复现算法一步；能够构造一个破坏前提的反例并指出停止位置。修复后清空派生特征、缓存、伪标签、模型状态和评价结果，从冻结原始样本完整重放。

4.5 多变量决策树

多变量决策树用若干属性的线性组合形成斜划分，能用较浅树表示斜边界，但节点优化更复杂、解释也从单属性规则变为局部超平面。

学习“4.5 多变量决策树”时先在“定位首个分叉”冻结输入、样本身份、特征形状、随机状态和适用假设，再进入“冻结数据合同”只改变一个条件。至少保存目标值、关键中间量、更新前后状态和独立评价；若最终指标改善但机制预期的第一处变化没有发生，应先排查泄漏、索引、尺度、优化容差和随机性，不能用末端分数覆盖首错。

通过标准包含四层：能够准确解释定义与适用前提；能够在极小样本上手算公式或枚举状态；能够用固定种子复现算法一步；能够构造一个破坏前提的反例并指出停止位置。修复后清空派生特征、缓存、伪标签、模型状态和评价结果，从冻结原始样本完整重放。

4.6 阅读材料

阅读材料连接ID3、C4.5、CART与可微分树。比较算法时要区分划分准则、剪枝策略和缺失值处理，而不是只比较名称。

学习“4.6 阅读材料”时先在“冻结数据合同”冻结输入、样本身份、特征形状、随机状态和适用假设，再进入“计算模型状态”只改变一个条件。至少保存目标值、关键中间量、更新前后状态和独立评价；若最终指标改善但机制预期的第一处变化没有发生，应先排查泄漏、索引、尺度、优化容差和随机性，不能用末端分数覆盖首错。

通过标准包含四层：能够准确解释定义与适用前提；能够在极小样本上手算公式或枚举状态；能够用固定种子复现算法一步；能够构造一个破坏前提的反例并指出停止位置。修复后清空派生特征、缓存、伪标签、模型状态和评价结果，从冻结原始样本完整重放。

常见失败与边界

本章回顾

把决策树学习还原为递归划分、停止、叶节点决策和剪枝的完整程序，并逐项核对信息增益、增益率与基尼指数。 验收时从冻结数据预测中间状态、目标与更新，解释结构或分布条件为何改变答案，并在失败样本中指出第一处违背前提的位置。最终底线是：每个候选划分必须使用同一节点样本和权重；连续阈值只从训练节点产生；剪枝依据独立验证证据，不能用测试集修树。