决策树适用性的扩展探讨

19.3.5 决策树适用性的扩展探讨

阅读准备

决策树要从理论迈向实际应用，必须克服以下四类扩展难题。这里整理了相应的解决思路以供参考。

在真实数据集中，属性值缺失的情况极为常见，决策树主要在训练分裂与样本预测这两个环节进行处理：

训练阶段如何确定分裂属性

加权缩减法（C4.5 策略）：在计算信息增益时，仅利用该属性无缺失值的样本。随后依据无缺失样本的比例，对信息增益进行折扣处理，从而减少了“因样本数量减少而意外获得高信息量”的可能性。

替代分裂（CART 策略）：为每个节点搜寻多个“替代分裂点”，这些点与主分裂点的分类结果高度相关。一旦主属性数据缺失，便启用替代属性来执行划分。

训练时如何将缺失样本分配至子节点

概率分配（C4.5）：依据各子节点中已知样本的比例，将缺失样本以概率权重的方式分配到各个子节点中。在后续计算里，该样本将以分数权重的形态存在。

作为独立类别：将“缺失”视为属性的一种具体取值，直接参与到分裂过程中。

默认分支：为缺失样本设定一个默认的流向（例如样本数量最多的子节点）。

预测阶段遭遇缺失值

同样沿用训练阶段的替代分裂或默认分支规则，引导样本沿着相应的路径向下延伸，最终输出预测结果。

此类扩展主要旨在解决“属性如何使用”的问题。

连续型属性

二元离散化：最为经典的方法。将连续属性的所有取值进行排序，逐一评估相邻值的中位点作为候选划分点。挑选能使不纯度降幅最大的点，例如 C4.5 使用信息增益率，CART 则采用基尼系数或方差缩减。

效率优化：无需计算所有点，可在按目标值排序后，仅在目标值发生变化的区间内寻找分割点（诸如 CART 直方图算法、LightGBM 的 GOSS 等）。

多值输入属性（例如省份、邮编等基数极高的分类型属性）

合并类别：CART 会对分类属性执行“二值合并”操作，将多分类塌缩为两个超类，从而寻找到最优的二元分组。

引入增益率（Gain Ratio）：C4.5 通过信息增益除以属性的“分裂信息”，来惩罚那些取值繁多、近乎按样本编号进行分裂的属性，以此防止过拟合。

目标编码：利用目标均值等统计量替换原始类别，将其转化为连续值进行处理。但这需要严格的交叉验证来规避标签泄漏风险。

当目标变量属于连续数值时，决策树的本质便转化为“分段常数拟合”。

分裂准则的变更

最小化均方误差：即挑选能使分裂后两个子节点内样本目标值的方差之和达到最小的属性和切点。这等同于总平方误差的减小量最大。

最小化绝对偏差：采用最小绝对偏差（LAD）替代 MSE，构建出分段中位数树，对异常值具有更强的鲁棒性。

叶子节点的输出值

通常为该节点内所有样本的目标均值（基于 MSE 准则）或者中位数（基于 LAD 准则）。

剪枝相关策略

代价复杂度剪枝：这是 CART 回归树的经典手段，旨在树的大小与误差之间寻求平衡，借助复杂度参数来调控剪枝的强度。

单棵决策树非常容易发生过拟合，所以模型选择与超参数调优成为了关键步骤。

预剪枝（提前终止）

利用超参数来约束树的生长：包括最大深度、内部节点再次划分所需的最小样本数、叶子节点的最小样本数、不纯度下降的最小阈值等。一旦分裂无法满足这些条件，便直接将其标记为叶节点。

后剪枝（生成后精简）

REP（错误率降低剪枝）：借助验证集，若将某子树替换为叶节点后，验证集的错误率未出现上升，则执行剪枝。

CCP（代价复杂度剪枝）：引入惩罚项 $R_\alpha(T) = R(T) + \alpha |T|$，树越复杂、叶子越多，惩罚就越重。通过调节 $\alpha$，生成一条“子树序列”，再利用交叉验证筛选出最优 $\alpha$ 对应的子树。这是 CART 的经典方法。

模型选择及集成

单棵树的超参数调优通常依赖于交叉验证，直接筛选出最佳深度、最小样本数等参数。

更为强大的思路是采用集成模型（如随机森林、梯度提升树），它们本身即可作为决策树的模型扩展。在此情况下，树的个体超参数（如深度等）与集成框架超参数（如树的数量、学习率、采样率）需要进行联合调优，这使得决策树的“模型选择”提升到了一个新的维度。

AI 智能导读

在实际应用场景里，决策树往往需要应对比“离散属性、完全数据”更为复杂的状况。本节提出了四类常见的扩展方向，并给出了对应的解决思路：

1. 数据缺失问题

教材详细内容

通过处理以下复杂情形，决策树能够获得更为广泛的应用。

●缺失数据：在众多问题领域中，并非每个样例的所有属性都是已知的。这些数值可能未被记录，也可能因获取成本过高而无法获取。这引发了两个问题：首先，给定一棵完整的决策树，对于缺少某个测试属性的样例，该如何对其进行分类？其次，当部分样例的属性值未知时，该如何调整信息增益公式？

●连续属性与多值输入属性：针对连续属性（例如身高、体重或时间），可能每个样例都拥有不同的属性值。若用信息增益来衡量属性，将导致此类属性获得理论上最高的信息增益，最终生成一棵以该属性为根的浅层树，其中每个可能值都对应一个单样例子树。然而，当我们需要对一个新样例进行分类，且该样例的此属性值未被观测过时，这棵树便失去了作用。

处理连续值的一个更优途径是采用分割点测试——即关于属性值的不等式测试。例如，在树中的某个给定节点上，体重[插图]160 的测试或许能提供最多的信息。寻找优质分割点的有效方法是：首先对属性的值进行排序，然后仅将具有不同分类结果的两个相邻样例之间的值视为可能的分割点，同时将以分割点划分出的正负样例作为新样例继续执行算法。分割的实现是实际决策树学习应用中成本最高的环节。

对于不连续的或排序无意义，但拥有大量可能值的属性（例如邮政编码或信用卡号码），可以采用一种称为信息增益比的度量方法，以防止算法将树分割成众多单样例子树。另一种有效的方法是采用形如 A=vk 的等式进行测试。例如，测试邮政编码=10002，可以在纽约市筛选出该邮政编码下的一大群人，随后将其余所有人归并到“其他”子树中。

●连续值输出属性：若要预测一个数值类型的输出，那么我们需要的是一棵回归树，而非分类树。回归树在每个叶节点上都拥有一个关于数值属性子集的线性函数，而非单一的输出值。举例而言，两居室公寓的价格最终可能以一个关于占地面积和浴室数量的线性函数输出。学习算法必须能够判定何时停止对树进行分割，并开始对属性应用线性回归（见 19.6 节）。CART 这个名字代表分类与回归树，用于涵盖这两个类别的树。

一个面向实际应用的决策树学习系统必须具备处理所有这些问题的能力。处理连续值变量尤为重要，因为物理过程和金融过程所提供的均为数值数据。现实应用中已经涌现出一些符合这些标准的商业软件包，并已用于开发数千个部署系统。在工业和商业的众多领域中，决策树依然是从数据集中探寻分类方法的首选手段。

决策树具备诸多优点：易于理解，可推广至大型数据集，在处理离散输入和连续输入以及分类和回归问题方面具有多功能性。然而，其精确度可能并非最优（主要由贪心搜索所致），并且如果树很深，那么在调用树为新样例进行预测时可能会产生高昂的运行代价。决策树也是不稳定的，因为仅添加一个新的样例，就可能改变根上的测试结果，进而改变整棵树。在 19.8.2 节中，我们将看到随机森林模型可以解决这些问题中的一部分。