Question

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

   • ID3 生成算法。
   • C4.5 生成算法。

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

3.1 ID3 生成算法

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

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

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

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

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

2. ID3 生成算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-420 $
     • 特征集合 $ MathJax-Element-115 $
     • 特征信息增益阈值 $ MathJax-Element-116 $

   • 输出：决策树 $ MathJax-Element-403 $

   • 算法步骤：

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

     • 若 $ MathJax-Element-122 $ ，则 $ MathJax-Element-403 $ 为单结点树，将 $ MathJax-Element-420 $ 中样本数最大的类 $ MathJax-Element-240 $ 作为该结点的类标记，算法终止。

     • 否则计算 $ MathJax-Element-126 $ ，选择信息增益最大的特征 $ MathJax-Element-133 $ ：

       • 若 $ MathJax-Element-128 $ ，则置 $ MathJax-Element-403 $ 为单结点树，将 $ MathJax-Element-420 $ 中样本数最大的类 $ MathJax-Element-240 $ 作为该结点的类标记，算法终止 。

       • 若 $ MathJax-Element-132 $ ，则对 $ MathJax-Element-133 $ 特征的每个可能取值 $ MathJax-Element-134 $ ，根据 $ MathJax-Element-135 $ 将 $ MathJax-Element-136 $ 划分为若干个非空子集 $ MathJax-Element-140 $ 。

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

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

3.2 C4.5 生成算法

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