决策树增长

增长将包含训练数据集的表用作输入表，从单个根节点开始。该表包含多个代表属性的列，以及一个代表类属性的列。

期望的输出是基于训练数据集的决策树模型表示。

执行拆分时，所创建的每个后代节点都对应于适用的训练数据集子集。进一步拆分这些节点会产生对应于更小数据集子集的新节点，依此类推。未拆分的节点将会成为叶。

决策树增长就是反复执行以下操作：

1. 停止条件

   此操作确定是否已执行拆分，或者某个节点是否由于不再进行拆分而变为叶。该决策基于与该节点相对应的训练数据集子集。

   满足以下某个条件时，就不会执行拆分：

   • 相应子集中的所有实例均属于同一类
   • 相应子集中的实例数小于指定的最小值
   • 当前节点的层次大于指定的最大值，其中根节点的层次为 1，其后代节点的层次为 2，依此类推
   • 根据可用的最佳拆分可实现的类杂质改善小于指定的最小值
2. 类标签分配

   相应子集中最频繁的类与每个树节点相关联。此操作在以后要修剪树时非常有用，因为后续的修剪会使一些节点变成叶。它还使得读取树结构更容易。对于所有节点都会分配类标签。

3. 拆分选择

   此操作将杂质最小的拆分分配给未满足停止条件的节点。候选拆分集包括适用于所有离散属性的相等二叉拆分，以及适用于所有连续属性的非相等二叉拆分。杂质指标将会应用于与拆分结果对应的子集，以评估候选拆分。