决策树C4.5算法详解
更新时间：2017年12月20日14:15:08 作者：
本文主要详细介绍了决策树的C4.5算法的相关信息，具有一定的参考价值。 有兴趣的朋友可以参考一下
本文分享决策树的C4.5算法，供大家参考。 具体内容如下
1.C4.5算法简介
C4.5算法是用于生成决策树的经典算法，它是ID3算法的扩展和优化。 C4.5算法对ID3算法进行了多项改进：
（1）通过信息增益率选择分裂属性，克服了ID3算法倾向于通过信息增益选择属性值多个属性作为分裂属性的缺点；
（2）能够处理离散和连续属性类型，即将连续属性离散化；
(3)构建决策树后进行剪枝；
(4)能够处理缺失属性值的训练数据。
2. 分裂属性的选择——信息增益率
分裂属性选择的标准是决策树算法之间的根本区别。 与ID3算法通过信息增益选择分裂属性不同，C4.5算法通过信息增益率选择分裂属性。
属性A（split）的“分割信息”：
其中，训练数据集S按属性A的属性值|Sj|分为m个子数据集表示第j个子数据集中的样本数，|S| 表示划分前数据集中的样本总数。
按属性A划分后样本集的信息增益：
信息增益的详细计算方法可以参考博客《决策树的ID3算法及其实现》中信息增益的计算。
按属性A划分后样本集的信息增益率：
通过C4.5算法构建决策树时，信息增益率最大的属性就是当前节点的分裂属性。 随着递归计算，计算出的属性的信息增益率会越来越小，后期会使用相对信息增益率比较大的属性作为分裂属性。
3.连续属性的离散化
当属性类型为离散时，无需对数据进行离散化； 当属性类型为连续时，需要对数据进行离散化。 C4.5算法针对的是连续属性的离散化。 核心思想是：将属性A的N个属性值按升序排列； 将属性A的所有属性值通过二分法分为两部分（一共有N-1种划分方法，二分法的阈值为两个相邻属性值的中间值）； 计算每种划分方法对应的信息增益，选择信息增益最大的划分方法的阈值作为属性A二值划分的阈值。 详细流程如下：
(1) 将节点Node上的所有数据样本按照连续属性A的具体值从小到大排列，得到属性A的属性值序列(xA1,…,xAN)。
(2)序列(xA1,...,xAN)中有N-1个二分法，即总共生成N-1个分离阈值。 对于第i个二值方法，其二值阈值θi=xAi+xAi+12。 它将该节点上的数据集分为2个子数据集(xA1,...,xAi)(xAi+1,...,xAN)。 计算这种二分结果下的信息增益。
(3)分别计算N-1个二值结果下的信息增益，选择信息增益最大的二值结果作为属性A的除法结果，记录此时的二值阈值。
4. 剪枝——PEP（Error）剪枝方法
由于决策树的建立完全依赖于训练样本，因此决策树可以对训练样本产生完美的拟合效果。 但这样的决策树对于测试样本来说过于庞大和复杂，可能会产生较高的分类错误率。 这种现象称为过度拟合。 因此，需要对复杂的决策树进行简化，即去除一些节点来解决过拟合问题。 这个过程称为修剪。
剪枝方法有两种：预剪枝和后剪枝。 预剪枝是在构建决策树的过程中提前终止决策树的生长，以避免生成过多的节点。 预剪枝方法虽然简单，但实用性不是很强，因为很难准确判断何时终止树的生长。 后剪枝就是在决策树构建完成后，将那些置信度不符合标准的节点子树替换为叶子节点，并将叶子节点的类标号标记为节点子树中出现频率最高的类。 后剪枝方法有两种，一种是将训练数据集分为树生长集和剪枝集； 另一种是使用相同的数据集进行决策树的生长和剪枝。 常见的后剪枝方法有CCP（Cost）、REP（Error）、PEP（Error）、MEP（Error）等。
C4.5算法采用PEP（Error）剪枝方法。 PEP剪枝方法是PEP提出的，是一种自上而下的剪枝方法，根据剪枝前后的错误率来决定是否剪枝子树，因此不需要单独的剪枝数据集。 接下来我们将详细介绍PEP（Error）剪枝方法。
对于覆盖n个样本、有e个错误的叶子节点，则该叶子节点的错误率为(e+0.5)/n，其中0.5为惩罚因子（惩罚因子一般为0.5）。
对于一棵子树，它有L个叶子节点，那么该子树的误判率为：
其中，ei表示子树第i个叶子节点的误分类样本数，ni表示子树第i个叶子节点的样本总数。
假设一棵子树误判了一个值为1的样本，正确分类了一个值为0的样本，那么该子树的误判数可以认为是伯努利分布，所以误判数的均值和总和可以得到子树的标准差：
将子树替换为叶子节点后，叶子节点的误报率为：
其中，e′=ΣLi=1ei，n′=ΣLi=1ni。
同时，叶子节点的误判次数也是伯努利分布，因此叶子节点的平均误判次数为：
修剪条件为：
当满足剪枝条件时，将得到的叶子节点替换为子树，这就是剪枝操作。
5. 缺失属性值的处理
有些样本可能会缺失训练样本集中的某些属性值，这种情况也会出现在待分类的样本中。 如何处理这样的样本集？ 缺失属性的样本集通常会导致三个问题：
(1)构建决策树时，每个分裂属性的选择由训练样本集中所有属性的信息增益率决定。 现阶段，如果训练样本集中的某些样本缺少某些属性，此时如何计算该属性的信息增益率；
(2)当选择某个属性作为分裂属性时，样本集应该根据该属性的值进行分支，但对于那些属性值未知的样本，应该分支到哪一棵子树；
(3)决策树构建完成后，如果待分类样本中某些属性值缺失，如何进行样本的分类过程。
针对上述三个属性值缺失导致的问题，C4.5算法有多种解决方案。
面对问题1，在计算各个属性的信息增益率时，如果某些样本的属性值未知，那么可以这样处理：在计算某个属性的信息增益率时，忽略缺失的样本这个属性； 或者将这个属性的样本中出现频率最高的属性值赋给缺失这个属性的样本。
面对第二个问题，假设已经选择了属性A作为决策树中的分支节点，那么在对样本集进行分支时，对于那些属性A的值未知的样本，可以将样本送去处理：不处理那些样本其属性A为未知样本，即直接忽略； 或者根据属性A的其他样本的取值给未知样本赋值； 或者为缺失属性A的样本创建单独的分支，但这种方式得到的决策树模型的节点数明显增加，使得模型更加复杂。
面对第三个问题，根据生成的决策树模型，在对待分类样本进行分类时，如果该样本的属性A的值未知，可以进行如下处理：当待分类样本到达分支节点时属性A的分类过程可以结束，该样本的类别属于属性A的子树中概率最大的类别； 或者将待分类样本的属性A赋予一个最常见的值，然后继续分类过程。
6. C4.5算法流程
7.C4.5算法优缺点分析
优势：
（1）通过信息增益率选择分裂属性，克服了ID3算法倾向于通过信息增益选择属性值多个属性作为分裂属性的缺点；
（2）能够处理离散和连续属性类型，即将连续属性离散化；
(3)构建决策树后进行剪枝；
(4)能够处理缺失属性值的训练数据。
缺点：
(1)算法计算效率较低，特别是对于包含连续属性值的训练样本。
(2)算法在选择分裂属性时没有考虑条件属性之间的相关性，仅计算数据集中各条件属性与决策属性之间的期望信息，这可能会影响属性选择的正确性。
以上就是本文的全部内容。 希望对您的学习有所帮助，也希望您多多支持脚本之家。
