C4.5算法
C4.5算法简介
C4.5算法是用于生成决策树的一种经典算法，是ID3算法的一种延伸和优化。C4.5算法对ID3算法主要做了一下几点改进：
（1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足；
（2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
（3）构造决策树之后进行剪枝操作；
（4）能够处理具有缺失属性值的训练数据。
分裂属性的选择——信息增益率
分裂属性选择的评判标准是决策树算法之间的根本区别。ID3算法由于采用的是信息增益，容易倾向于选择取值较多的属性作为节点。改良后的C4.5算法采用的是信息增益率，信息增益率=信息增益/属性熵，公式：
信息增益的计算公式如下（ID3中https://www.aben.fun/2021/12/04/ID3%E7%AE%97%E6%B3%95/）
其中$S$为全部样本集合，$value(T)$是属性$T$的所有取值的集合，$v$是$T$的其中一个属性值，$S_v$是$S$中属性$T$的值为$v$的样例集合，$|S_v|$为$S_v$中所含样例数。
属性熵
当属性有很多值时，虽然信息增益变大了，但是相应的属性熵也会变大。所以最终计算的信息增益率并不是很大。在一定程度上可以避免ID3倾向于选择取值较多的属性作为节点的问题。
连续型属性的离散化处理
当属性类型为离散型，无须对数据进行离散化处理；当属性类型为连续型，则需要对数据进行离散化处理。C4.5算法针对连续属性的离散化处理，核心思想：将属性A的N个属性值按照升序排列；通过二分法将属性A的所有属性值分成两部分（共有N-1种划分方法，二分的阈值为相邻两个属性值的中间值）；计算每种划分方法对应的信息增益，选取信息增益最大的划分方法的阈值作为属性A二分的阈值。
剪枝——PEP(Pessimistic Error Pruning)剪枝法
由于决策树的建立完全是依赖于训练样本，因此该决策树对训练样本能够产生完美的拟合效果。但这样的决策树对于测试样本来说过于庞大而复杂，可能产生较高的分类错误率。这种现象就称为过拟合。因此需要将复杂的决策树进行简化，即去掉一些节点解决过拟合问题，这个过程称为剪枝。
剪枝方法分为预剪枝和后剪枝两大类。预剪枝是在构建决策树的过程中，提前终止决策树的生长，从而避免过多的节点产生。预剪枝方法虽然简单但实用性不强，因为很难精确的判断何时终止树的生长。后剪枝是在决策树构建完成之后，对那些置信度不达标的节点子树用叶子结点代替，该叶子结点的类标号用该节点子树中频率最高的类标记。后剪枝方法又分为两种，一类是把训练数据集分成树的生长集和剪枝集；另一类算法则是使用同一数据集进行决策树生长和剪枝。常见的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。
C4.5算法采用PEP(Pessimistic Error Pruning)剪枝法。PEP剪枝法由Quinlan提出，是一种自上而下的剪枝法，根据剪枝前后的错误率来判定是否进行子树的修剪，因此不需要单独的剪枝数据集。
缺失属性值的处理
训练样本集中有可能会出现一些样本缺失了一些属性值，待分类样本中也会出现这样的情况。当遇到这样的样本集时该如何处理呢？含有缺失属性的样本集会一般会导致三个问题：
（１）在构建决策树时，每一个分裂属性的选取是由训练样本集中所有属性的信息増益率来决定的。而在此阶段，如果训练样本集中有些样本缺少一部分属性，此时该如何计算该属性的信息増益率；
（２）当已经选择某属性作为分裂属性时，样本集应该根据该属性的值来进行分支，但对于那些该属性的值为未知的样本，应该将它分支到哪一棵子树上；
（３）在决策树已经构建完成后，如果待分类样本中有些属性值缺失，则该样本的分类过程如何进行。
针对上述因缺失属性值引起的三个问题，C4.5算法有多种解决方案。
面对问题一，在计算各属性的信息増益率时，若某些样本的属性值未知，那么可以这样处理：计算某属性的信息増益率时忽略掉缺失了此属性的样本；或者通过此属性的样本中出现频率最高的属性值，賦值给缺失了此属性的样本。
面对问题二，假设属性Ａ已被选择作为决策树中的一个分支节点，在对样本集进行分支的时候，对于那些属性Ａ的值未知的样本，可以送样处理：不处理那些属性Ａ未知的样本，即简单的忽略它们；或者根据属性Ａ的其他样本的取值，来对未知样本进行赋值；或者为缺失属性Ａ的样本单独创建一个分支，不过这种方式得到的决策树模型结点数显然要増加，使模型更加复杂了。
面对问题三，根据己经生成的决策树模型，对一个待分类的样本进行分类时，若此样本的属性Ａ的值未知，可以这样处理：待分类样本在到达属性Ａ的分支结点时即可结束分类过程，此样本所属类别为属性Ａ的子树中概率最大的类别；或者把待分类样本的属性Ａ赋予一个最常见的值，然后继续分类过程。
C4.5算法优缺点分析
优点：
（1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足；
（2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
（3）构造决策树之后进行剪枝操作；
（4）能够处理具有缺失属性值的训练数据。
缺点：
（1）算法的计算效率较低，特别是针对含有连续属性值的训练样本时表现的尤为突出。
（2）算法在选择分裂属性时没有考虑到条件属性间的相关性，只计算数据集中每一个条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性。
参考文章：
