C4.5算法

C4.5算法是由Ross Quinlan（英语：Ross Quinlan）开发的用于产生决策树的算法。该算法是对Ross Quinlan之前开发的ID3算法的一个扩展。C4.5算法产生的决策树可以被用作分类目的，因此该算法也可以用于统计分类。

C4.5算法与ID3算法一样使用了信息熵的概念，并和ID3一样通过学习数据来建立决策树。[1]

在Springer LNCS于2008年发表的优秀论文中，该算法在前10大数据挖掘算法中排名第一，之后使得它变得非常受欢迎。[2]

算法

C4.5跟ID3一样，使用信息熵从训练数据集中构建决策树。训练数据是已经分类的样本集合${\displaystyle S={s_{1},s_{2},...}}$。每个样本${\displaystyle s_{i}}$由p维向量${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$组成，其中${\displaystyle x_{j}}$表示样本的属性值或者叫特征，当然也包括样本 ${\displaystyle s_{i}}$ 的类别。

在树的每个节点上，C4.5选择数据的属性，该属性最有效地将其样本集划分为集中在一个类或另一个类中的子集。划分准则是归一化的信息增益，即熵的差。选择信息增益最大的属性进行决策，然后对划分后的子集进行递归处理。

该算法有几个基本情况：

• 若一个样本集合的样本都属于同一个类别，则直接创建一个叶节点，表示选择该类别；
• 若所有特征都没有提供任何信息增益，C4.5使用类的期望值在树的上层创建一个决策节点；
• 若遇到了以前未见过的样本，C4.5使用期望值在树的上层创建一个决策节点。

伪代码

构建决策树的一般算法是：[3]

1. 检查上述基本情况
2. 对于每个特征a，计算划分a的信息增益
3. 记a_best为最高信息增益的特征
4. 创建一个在a_best上划分的决策节点
5. 使用划分后的样本创建作为当前决策节点的子节点，并在这些子节点上递归地处理

参考

1. Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
2. Umd.edu - Top 10 Algorithms in Data Mining (PDF). [2019-02-16]. （原始内容存档 (PDF)于2018-11-23）. 
3. S.B. Kotsiantis, "Supervised Machine Learning: A Review of Classification Techniques", Informatica 31(2007) 249-268, 2007