决策树、划分准则与剪枝

树是对特征空间的递归分区

决策树从包含全部训练样本的根节点开始。每个内部节点选择一个特征和划分规则，把当前区域分成互不重叠的子区域；随后在每个子区域重复。到达停止条件后形成叶节点，分类叶输出类别分布或决策，回归叶通常输出目标均值。一次预测只沿根到叶的一条路径前进。

二叉连续划分常写成 $x_j\le t$ 与 $x_j>t$。节点路径上的条件取交集，因此叶对应一个轴对齐区域。算法在当前节点寻找即时损失下降最大的划分，再分别处理子节点；这是贪心优化，不保证得到给定叶数下全局最优树。根部一次选择会改变后续所有候选，局部最优不能当作全局最优证明。

树的可读规则只对所用特征表示和训练分布成立。若特征是复杂编码、代理变量或处理后信息，短路径也不等于可行动解释，更不等于因果机制。规则审阅应同时显示节点样本量、类别比例、缺失走向和验证性能。

分类不纯度衡量标签混合

设节点 $A$ 中第 $k$ 类比例为 $p_k$。常用基尼不纯度与熵为

纯节点两者都为零；类别更均匀时更大。候选划分把 $A$ 分为 $L,R$，加权不纯度下降为

用子节点样本数加权可防止把极小纯节点与大而混杂的剩余节点视为同等贡献。信息增益就是以熵为不纯度的下降。不同准则常给相似树，却不保证一致；实现还要规定平局、最小叶样本和样本权重。

误分类率 $1-\max_k p_k$ 可描述叶节点多数类错误，却对比例变化不够敏感，通常不如基尼或熵适合生长阶段。训练不纯度也不是最终报告指标；类别不平衡或错误代价不同的任务仍需在验证数据报告概率损失、召回、精确率和目标阈值代价。

回归树让叶均值最小化平方误差

平方损失回归树在节点 $A$ 以均值 $\bar y_A$ 预测，节点残差平方和为

划分得分是父节点平方和减去两个子节点平方和。均值是平方损失下的最优常数；若训练目标为绝对损失，最优叶常数是中位数，划分准则也应相应改变。不能用平方误差长树后，把叶中位数替换进去就声称优化了绝对损失全过程。

连续特征需要排序，类别特征需要限制搜索

连续特征在当前节点排序后，只需考虑相邻不同取值之间的阈值；若相邻样本标签和加权统计相同，部分候选还可跳过。高效实现通过一次扫描维护左右类别计数或目标和与平方和，避免为每个阈值重新遍历全部节点。

类别特征若有 $K$ 个水平，任意二分子集有指数数量，直接穷举只适合很小 $K$。二分类或回归可按类别目标率或均值排序后搜索相邻切分，但这个排序必须仅用当前训练节点，并配合平滑和最小样本约束。高基数类别拥有更多候选，容易因机会产生较大训练增益；直接使用身份标识尤其危险。

预测时出现训练未见类别，必须有冻结策略，例如走训练样本较多的分支、统一未知类别或先在管道中编码。不能在测试标签出现后决定走向。类别编码、稀有水平合并和目标统计都属于模型选择，应在训练折内部完成。

停止规则是预剪枝

树可在节点纯、没有正增益、达到最大深度、叶数上限、节点样本过少或增益低于阈值时停止。最大深度限制路径交互阶数，最小叶样本限制局部估计方差，最小不纯度下降阻止微小训练改善。它们共同定义假设类，需在训练和验证协议内选择。

过强停止使真实异质性被合并，产生高偏差；过弱停止可让每个叶几乎记忆训练样本，训练误差低而概率极端。分类叶的原始频率在小叶中方差很高，可做训练内平滑或独立校准，但校准不能复用最终测试标签。

预剪枝的搜索空间受早期选择限制：一个暂时增益小的划分可能为后续强划分打开路径，却被过早阻断。后剪枝先长较大树，再从其子树序列中选择规模，提供另一种控制方式。

代价复杂度剪枝从大树选择子树

对回归树可定义

其中 $R(T)$ 是训练叶损失之和，$|\mathcal L(T)|$ 是叶数，$\alpha\ge0$ 控制每增加一叶的代价。分类也可用相称的叶损失。由大树反复剪去“单位减少叶数所换来的损失改善最小”的内部枝，可得到一列嵌套子树；再用交叉验证选择 $\alpha$ 或子树大小。

缺失值不是数值零

缺失可能代表传感器故障、未测量、不适用或选择性记录，语义不同。简单策略是在训练折内做插补并增加缺失指示；类别特征可把“未知”作为明确水平；某些树学习缺失默认方向，或用与主划分结果一致的替代特征作为代理划分。任何策略都要在预测时可执行。

若缺失机制与标签相关，缺失指示可能有预测力，但部署采集流程改变后会失效。用全数据按标签决定插补或默认方向会泄漏。训练中从无缺失而线上出现缺失时，算法的隐式分支规则必须显式测试，不能把库的默认行为当业务定义。

单树容易不稳定

树的候选增益常很接近。替换少量样本可能改变根划分，继而改变整棵结构；这种离散选择使单树方差较高。深树对局部交互很灵活，却容易产生小叶；浅树更稳定但可能欠拟合。用一条路径解释单个预测时，应检查重采样树中路径和特征是否稳定。

轴对齐划分对旋转坐标敏感：一条斜直线边界可能需要许多矩形叶逼近。特征缩放不改变单个阈值的样本排序，却会影响某些预处理、缺失和距离派生特征。树可自然表示非线性与交互，但“无需任何预处理”仍是过度概括。

复杂度取决于实现与树形

若每个连续特征预排序并在节点维护统计，一棵近似平衡树常可在约 $O(pn\log n)$ 量级生长；朴素地在每个节点重新排序或形成极不平衡链，成本可更高，甚至接近平方级扫描。类别子集搜索、高维稀疏输入和样本权重也会改变常数与上界，报告应注明实现。

单次预测访问深度 $d$ 个节点，时间 $O(d)$；平衡树深度近似对数，退化树可达叶数同阶。存储与节点数及每节点统计有关。剪枝既可能改善泛化，也直接降低延迟和内存。复杂度比较必须在相同特征管道、批量方式与硬件上测量。

练习

关系与资源

• 训练、验证、测试与数据泄漏 约束类别统计、剪枝与校准选择。
• 熵、互信息与散度 提供信息增益的概率基础。
• 分类、回归指标与基线 区分训练准则和部署证据。
• 随机森林与袋装集成 用聚合降低深树方差。
• AdaBoost、梯度提升与残差拟合 对比逐步降低偏差的树集成。
• 核方法、树模型与集成学习综合复习 比较模型归纳偏置和部署成本。