三、生成算法

1. 决策树有两种常用的生成算法：

   • ID3 生成算法。
   • C4.5 生成算法。
2. ID3 生成算法和 C4.5 生成算法只有树的生成算法，生成的树容易产生过拟合：对训练集拟合得很好，但是预测测试集效果较差。

3.1 ID3 生成算法

1. ID3 生成算法核心是在决策树的每个结点上应用信息增益准则选择特征，递归地构建决策树。

   • 从根结点开始，计算结点所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征划分出子结点。

   • 再对子结点递归地调用以上方法，构建决策树。

   • 直到所有特征的信息增益均很小或者没有特征可以选择为止，最后得到一个决策树 。

     如果不设置特征信息增益的下限，则可能会使得每个叶子都只有一个样本点，从而划分得太细。

2. ID3 生成算法：

   • 输入：

     • 训练数据集
     • 特征集合
     • 特征信息增益阈值

   • 输出：决策树

   • 算法步骤：

     • 若 中所有样本均属于同一类 ，则 为单结点树，并将 作为该结点的类标记，算法终止。

     • 若 ，则 为单结点树，将 中样本数最大的类 作为该结点的类标记，算法终止。

     • 否则计算 ，选择信息增益最大的特征 ：

       • 若 ，则置 为单结点树，将 中样本数最大的类 作为该结点的类标记，算法终止 。

       • 若 ，则对 特征的每个可能取值 ，根据 将 划分为若干个非空子集 。

         将 中样本数最大的类作为该子集的标记，构建子结点。

     • 对第 个子结点， 以 为训练集， 以 为特征集，递归地调用前面的步骤来构建子树。

3.2 C4.5 生成算法

1. C4.5 生成算法与 ID3 算法相似，但是 C4.5 算法在生成过程中用信息增益比来选择特征。