C4.5 算法生成决策树的一种经典算法,是 ID3 的优化版本,主要进行了一下几个方面的优化:

  1. 通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足;
  2. 能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理
    • C4.5 处理连续特征是先将特征取值排序,以连续两个值中间值作为划分标准。
    • 尝试每一种划分,并计算修正后的信息增益,选择信息增益比最大的分裂点作为该属性的分裂点。
  3. 构造决策树之后进行剪枝操作;
  4. 能够处理具有缺失属性值的训练数据。

C4.5 剪枝

  C4.5 生成的决策树也有过拟合的倾向,需要进行剪枝,剪枝分为预剪枝和后剪枝两大类,C4.5 采用 PEP 方法的后剪枝策略。

悲观剪枝(Pessimistic Error Pruning,PEP)

  PEP 是一种自上而下的剪枝法,根据剪枝前后的错误率来判定是否进行子树的修剪,因此不需要单独的剪枝数据集。

  对于一个叶子节点,它覆盖了 $n$ 个样本,其中有 $e$ 个错误,那么该叶子节点的错误率为 $\frac{e+0.5}{n}$,这里的 $0.5$ 为惩罚因子 (惩罚因子一般设置为 0.5)。

  对于一个由 $L$ 个叶子节点的子树,其误判率为:

  其中 $e_i$ 表示子树第 $i$ 个叶子节点错误分类的样本数量,$n_i$表示表示子树第 $i$个叶子节点中样本的总数量。

  假设一棵子树错误分类一个样本取值为 $1$,正确分类一个样本取值为 $0$,那么子树的误判次数可以认为服从伯努利分布,因此可以得到该子树误判次数的均值和标准差:

  接着来考虑叶子节点的误判率为:

  其中 $e^{\prime}=\sum_{i=1}^{L} e_{i}$,$e^{\prime}=\sum_{i=1}^{L} e_{i}$。

  同样的,叶子节点的误判次数也服从伯努利分布,则该叶子节点误判次数的均值为:

  最后,剪枝的条件为(有效性如何证明❓):

  满足剪枝条件时,将所得叶子节点替换该子树,即为剪枝操作。

C4.5 总结

C4.5 优点

  1. 通过信息增益率选择分裂属性,克服了 ID3 算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足;
  2. 能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理;
  3. 构造决策树之后进行剪枝操作,减少了过拟合现象;
  4. 能够处理具有缺失属性值的训练数据。

C4.5 缺点

  1. 算法的计算效率较低,特别是针对含有连续属性值的训练样本时表现的尤为突出。
  2. 算法在选择分裂属性时没有考虑到条件属性间的相关性,只计算数据集中每一个条件属性与决策属性之间的期望信息,有可能影响到属性选择的正确性。

C5.0

TODO

References

  1. 决策树之C4.5算法详解