鲁达 上一篇文章为大家介绍了ID3决策树分类算法，本文为大家介绍C4.5决策树分类算法，并附有详细的案例帮助大家理解。
C4.5分类算法介绍
C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。
C4.5算法在决策树的生成过程中，用信息增益比来选择特征
C4.5算法考虑了对连续型的属性处理
C4.5算法考虑了对样本的缺失数据处理
信息增益比（Information Gain Ratio）
信息增益是一种衡量最优分支属性的有效函数，但是它倾向于选择具有大量不同取值的属性，从而产生许多小而纯的子集，为了改进这种状况，提出使用信息增益比例来代替信息增益。
分裂信息
分裂信息用来衡量属性F分裂数据样本S的广度和均匀性，这个信息量是与样本的类别无关的，它由如下公式所示：
分裂信息的计算公式
Sv表示属性F划分的第v个样本子集。
信息增益比
属性F对样本S进行划分的信息增益比如下公式所示：
信息增益比计算
一个属性分割样本的的广度越大，均匀性越强，该属性的split_info越大，增益比例就越小，因此使用信息增益比例降低了选择那些值较多且均匀分布的属性的可能性。
对连续型属性的处理
离散化处理：将连续型的属性变量进行离散化处理，形成决策树的训练集
把需要处理的样本（对应根节点）或样本子集（对应子树）按照连续变量的大小从小到大进行排序
假设该属性对应的不同的属性值一共有N个，那么总共有N-1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点
用信息增益比选择最佳划分
对样本缺失值的处理
缺失值：在某些情况下，可供使用的数据可能缺少某些属性的值。例如(X, y)是样本集S中的一个训练实例，X=(F1_v, F2_v, …Fn_v)。但是其属性Fi的值Fi_v未知。
处理策略：
处理缺少属性值的一种策略是赋给它结点t所对应的训练实例中该属性的最常见值
另外一种更复杂的策略是为Fi的每个可能值赋予一个概率
例如，给定一个布尔属性Fi，如果结点t包含6个已知Fi_v=1和4个Fi_v=0的实例，那么Fi_v=1的概率是0.6，而Fi_v=0的概率是0.4。于是，实例x的60%被分配到Fi_v=1的分支（也就是分配到这边的样本总数+0.6），40%被分配到另一个分支（也就是分配到这边的样本总数+0.4）
简单处理策略就是丢弃这些样本
C4.5算法步骤
C4.5的算法步骤与ID3算法的步骤类似，最主要的区别就是，C4.5算法采用信息增益比来选择特征。
创建根节点R
如果当前DataSet中的数据都属于同一类，则标记R的类别为该类
如果当前featureList集合为空，则标记R的类别为当前 DataSet中样本最多的类别
递归情况：
从featureList中选择属性F（选择GainRatio(DataSet, F)最大的属性，连续属性参见上面的离散化过程）
根据F的每一个值v，将DataSet划分为不同的子集DS，对于每一个DS：
创建节点C
如果DS为空，节点C标记为DataSet中样本最多的类别
如果DS不为空，节点C=C4.5(DS, featureList - F)
将节点C添加为R的子节点
C4.5算法实例分析
对毕业生的就业信息进行分析，寻找可能影响毕业生就业的因素。
毕业生就业信息表
第1步，计算决策属性的经验熵（训练集的全部信息量）
entropy(就业情况)=entropy(14，8)
= -14/22*log2(14/22) - 8/22*log2(8/22)
=0.945660
第2步，计算每个属性的信息增益，以属性“性别”为例
entropy(男)=entropy(10，7)
= -10/17*log2(10/17)- 7/17*log2(7/17)
=0.977417
entropy(女)=entropy(4，1)
= -4/5*log2(4/5)- 1/5*log2(1/5)
=0.721928
因此，“性别”的条件熵为：entropy(性别)
=17/22*entropy(男)+5/22*entropy(女)
=0.919351
因此，“性别”的信息增益为：Gain(性别)
=entropy(就业情况) - entropy(性别)
= 0.026308
第3步，计算样本在“性别”属性上的分裂信息
split_info(性别)
= -17/22*log2(17/22) - 5/22*log2(5/22)
=0.773226
第4步，计算样本在“性别”属性上的信息增益比
gain_ratio(性别)= Gain(性别)/split_info(性别)
=0.026308
运用同样的方法计算样本在其他属性上的信息增益比
gain_ratio(性别)=0.034023；
gain_ratio(学生干部)= 0.411714；
gain_ratio(综合成绩)=0.088391；
gain_ratio(毕业论文)= 0.101671
第5步，选择分类属性
由上述计算结果可知，“学生干部”属性具有最大的信息增益比，取“学生干部”为根属性，引出一个分支，样本按此划分。对引出的每一个分支再用此分类方法进行分类，再引出分支，最后所构造出的决策树如下图所示。
最终构造出的决策树