决策树算法（三）：C4.5

这篇文章主要介绍 C4.5 算法，C4.5 算法是对 ID3 算法的改进。C4.5 算法使用信息增益比来选择特征。

信息增益比（增益率）

信息增益比的定义如下：
GainRatio(D,a)=Gain(D,a)IV(a) IV(a)=−V∑v=1|Dv||D|log2|Dv||D|GainRatio(D,a)=Gain(D,a)IV(a)IV(a)=−∑v=1V|Dv||D|log2|Dv||D|
以上定义的符号，大部分在上一篇文章中已经出现过了，GainRatio(D,a)GainRatio(D,a) 就是将数据集 DD 按照特征 aa 进行划分后对应的信息增益比。这里只需要理解一下 IV(a)IV(a)。
通常来说，特征 aa 的可取值数目越大，IV(a)IV(a) 的值也会越大。将 IV(a)IV(a) 放在分母的位置上，在一定程度上减轻了使用信息增益选择特征时，会更加偏好那些可取值数目多的特征带来的不利影响。
但是直接使用信息增益比来选择特征则会更加偏好那些可取值数目较少的特征。因此 C4.5 算法并不是直接选取信息增益比最大的特征。

C4.5 算法如何选择特征

1. 首先 C4.5 算法会从可选特征中找出那些信息增益高于平均水平的特征。
2. 然后再从这些信息增益高于平均水平的特征中选出信息增益率最高的特征。

C4.5 算法对连续特征的处理

ID3 算法没有考虑连续特征，比如质量，密度等。C4.5 算法对此做了改进。C4.5 算法使用的机制是采用二分法对连续特征进行处理。
假设在样本集 DD 中连续特征 aa 的取值有 nn 个，记为 a1,a2,a3,…,ana1,a2,a3,…,an。那么对于特征 aa 一共有 n−1n−1 个候选划分点，首先将这 nn 个点排序，然后通过下式计算出这 n−1n−1 个候选点：
T_a = \Big{t_i = \frac{a^i + a^{i+1}}{2}|1 \leq i \leq n-1 \Big}T_a = \Big{t_i = \frac{a^i + a^{i+1}}{2}|1 \leq i \leq n-1 \Big}
首先要分别计算按 TaTa 中的每个点进行划分后对应的信息增益，记作 G1,G2,…,Gn−1G1,G2,…,Gn−1。
从所有划分点对应的信息增益中选择一个最大的作为按特征 aa 进行划分对应的信息增益。到这里就成功的处理了连续特征的信息增益的计算问题。C4.5 算法可以成功的处理连续特征了~
需要补充的是与离散属性不同，若当前结点划分属性为连续属性，则该属性还可以作为其后代结点的划分属性。

剪枝策略主要有两种，分别为预剪枝和后剪枝，剪枝是主要是为了应对决策树学习算法可能会过拟合的问题。
预剪枝是在决策树的生成过程中，对每个结点在划分前后进行评估。如果当前结点划分后并不能带来泛化能力的提升，就停止划分当前结点，并将当前结点标记为叶结点。
后剪枝是先训练一棵完整的决策树，然后自底向上对每个非叶结点进行考察，若将该结点对应的子树替换为叶子结点能带来决策树泛化能力的提升，则将该子树替换为叶结点。
上面的描述引出一个关键的问题，如何判断决策树的泛化能力是否提升呢？可以用“留出法”，也就是预留一部分数据用作“验证集”进行评估。
剪枝的根本目的都使决策树变得简单，从而避免过拟合的问题。
通常来说，后剪枝比预剪枝保留了更多的分支，所以一般情形下，后剪枝更不容易欠拟合。并且通过后剪枝得到的决策树的泛化能力也往往要比预剪枝好。但是后剪枝要在决策树完全生成以后进行，与预剪枝相比时间开销更大。

C4.5 算法总结

• C4.5 算法是对 ID3 算法的改进
• C4.5 算法避免了 ID3 算法的偏好问题（偏向可取值数目多的特征）
• C4.5 算法可以处理连续值
• C4.5 算法引入了剪枝策略（避免过拟合）
• C4.5 算法考虑了缺失值问题
• C4.5 算法只能用来分类（ID3 算法也只能用来分类）
• c4.5 算法生成的决策树是多叉树
• c4.5 算法处理连续值时需要排序（排序可能会带来比较大的性能开销）

1. 《机器学习》 —— 周志华
2. 《统计学习方法》 —— 李航

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以在文章下方的评论区进行评论，也可以邮件至 [email protected]