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

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

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

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

2. ID3 生成算法：

   • 输入：

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

   • 算法步骤：

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

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

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

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

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

3.2 C4.5 生成算法