1.6.3　决策树算法面临的基本问题

若属性值的每种组合都在训练集中出现，而且每种组合都具备唯一的类标号，则Hunt算法是有效的。但对于大多数的实际状况来说，这一假设并不现实，所以，须要额外的条件来处理如下状况：

●在第二步中，算法所建立的子节点可能为空，即不存在与这些节点相关联的记录数据。若是没有一个训练记录包含与这样的节点相关联的属性组合（这种情形就有可能发生），这时，该节点成为叶子节点，类标号为其父节点所关联记录集中类别个数最多的类别。

●在第二步中，若与D相关联的全部记录都具备相同的属性值（类标号除外），则没有属性可用于进一步划分当前记录集，这时可采用投票原则（少数服从多数）将当前节点强制设为叶子节点，其类标号为该节点所关联记录集中类别个数最多的类别。

由Hunt算法的基本思想，我们能够看到，决策树算法必须解决如下问题。

1. 如何分割训练记录数据集？如何选择属性？

记录数据集的分割对决策树的构造有巨大影响。它主要由两个因素决定：一是选择哪个属性；二是如何划分该属性的值并选择分割点，这个方面与属性的数据类型密切相关。

2. 如何处理不同属性的数据类型？如何设定对应的测试条件？如何评估测试条件的优劣？

每次递归都依据属性测试条件将记录划分为更小的子集。为了更好地进行记录分割，算法必须为不一样类型的属性指定不同的测试条件的方法，而且提供评估每一个测试条件优劣的客观标准。

目前属性的数据类型主要有以下几种。

图1.25　二值类型属性的划分示意图

●二值类型。该类型的可取值只有两个，因此，其测试条件可以直接采用二分测试方法。例如，如图1.25所示，将动物根据体温是否恒定分为冷血和温血动物。

●标称值类型（枚举类型）。标称值类型也称为枚举类型，可取值数目是有限的。因此，可以采用每个取值对应一个测试条件的多路测试方法，或者任意分成两组，然后利用二分测试方法。例如，如图1.26所示，可以将婚姻的三种状态（图1.26a）中的任意两个状态分为一组，从而转为两种状态（图1.26b）。

●连续值类型。连续属性的可取值的数目不再有限，因此不能像前面的那些类型一样对节点进行划分。因此需要对连续属性进行离散化处理，常用的离散化方法是二分法或多路划分方法。例如，如图1.27所示，年收入为连续值属性，可以通过单个范围值离散化（图1.27a），也可以使用多个范围值进行离散化（图1.27b）。

图1.26　标称值类型属性的划分示意图

图1.27　连续值类型属性的划分示意图

●有序值类型。有序值类型的可取值的数目有可能是有限的，也可能是无限的。如果是有限数目，则可以类似于标称值类型进行处理；如果是无限数目，则可以类似于连续值类型进行处理。例如，如图1.28所示，衣服的尺码具有有序的特点，可以将多个相邻的尺码进行分组。

图1.28　有序值类型属性的划分示意图

3. 如何中止分裂？如何避免过拟合？

为了终止决策树的成长过程，一个可能的策略是分裂节点直到全部的记录都属于同一类，或者全部的记录都具备相同的属性值。但是这种情况有可能导致过拟合，从而导致决策树模型的泛化能力不足。尽管这两个约束条件对于结束决策树成长是充分的，可是还需要其余的标准来提早中止树的生长过程。

4. 如何提升决策树的预测精度？

决策树基于现有属性特征进行学习和推理，具有很好的可解释性。但随着样本数量的增加，决策树的预测精度问题变得比较突出，特别是与其他机器学习方法比较而言没有明显优势。因此，如何提升决策树的预测精度成为一个重要的研究焦点。