十大经典算法之C4.5算法综述

七彩极 · 发表于 2022-3-16 09:43

摘要：数据挖掘技术是当前数据库和人工智能领域研究的热点课题，C4.5算法是数据挖掘十大经典算法之一，本文首先对C4.5算法的总体研究情况进行了概略介绍，包括C4.5算法的产生背景、算法内容、优缺点；然后阐述了C4.5算法的发展历程，并对C4.5算法的改进做了相关介绍。
关键词：数据挖掘；决策树；C4.5算法
1、引言
近年来决策树方法在机器学习、知识发现等领域得到了广泛应用。数据挖掘作为一种发现大量数据中潜在信息的数据分析方法和技术已经成为各界关注的热点。其中，决策树以其出色的数据分析效率、直观易懂等特点倍受青睐。构造决策树有多种算法，国际上最早的、具有影响力的决策树是由Quinlan于1986年提出的ID3算法，是基于信息熵的决策树分类算法。ID3算法采用信息熵作为属性选择标准，可这个标准易偏向于取值较多的候选属性。Quinlan于1993年又提出了ID3的改进版本C4.5算法，C4.5算法用信息增益率来选择决策属性，它继承了ID3算法的全部优点，在ID3的基础上还增加了对连续属性的离散化、对未知属性的处理和产生规则等功能。
2、决策树
2.1
决策树是一种由节点和有向边组成的树状结构。节点分为根节点、内部节点和叶子节点，其中根节点和内部节点表示属性测试条件，叶子节点表示类标号。从树的根节点经有向边连接直到某个叶子节点的一条路径表示一条分类规则。
决策树分类是一种从无次序、无规则的训练样本集中推理出决策树表示形式的分类规则的方法。它采用自顶向下的方法，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从根结点到任一个叶结点所形成的一条路径就构成了一条分类规则，其中路径中的属性值偶对就构成了分类规则条件部分（IF部分）中的一个合取项，叶结点所标记的类别就构成了规则的结论内容（THEN部分）。如图1所示，决策树的生成过程包括两个阶段：树构造和树剪枝。

图1 决策树的生成过程

2.2 树构造
决策树采用自顶向下的递归方式：从根节点开始在每个节点上按照给定标准选择测试属性，然后按照相应属性的所有可能取值向下建立分枝、划分训练样本。直到一个节点上的所有样本都被划分到同一个类，或者某一节点中的样本数量低于给定值时为止。这一阶段最关键的操作是在树的节点上选择最佳测试属性，该属性可以将训练样本进行最好的划分。最佳测试属性的选择标准有信息增益、基尼指数以及基于距离的划分等。
2.3 树剪枝
构造过程得到的并不是最简单、紧凑的决策树，因为许多分枝反映的可能是训练数据中的噪声或孤立点。树剪枝过程试图检测和去掉这种分枝，以提高对未知数据集进行分类时的准确性。树剪枝方法主要有先剪枝和后剪枝。树剪枝方法的剪枝标准有最小描述长度（MDL）和最小期望错误率等。前者对决策树进行二进位编码，最佳剪枝树就是编码所需二进位最少的树；后者计算某节点上的子树被剪枝后出现的期望错误率，由此判断是否剪枝。
3、ID3算法
当前最有影响的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5算法。ID3算法是较早出现也是最著名的决策树归纳算法。C4.5是ID3的改进算法不仅可以处理离散值属性，还能处理连续值属性。
ID3算法存在着属性偏向、对噪声敏感等问题。
1983年,T. Niblett和 A.Patterson在 ID3算法的基础上提出了ACLS Algorithm。该算法可以使属性取任意三、C4.5算法的整数值,这扩大了决策树算法的应用范围。
1984年,I.Kononenko、E.Roskar和 I.Bratko 在 ID3算法的基础上提出了ASSISTANT Algorithm,它允许类别的取值之间有交集。
1984年,A. Hart提出了Chi——Square统计算法,该算法采用了一种基于属性与类别关联程度的统计量。
L.Breiman、C.Ttone、R. Olshen和 J. Freidman在1984年提出了决策树剪枝概念,极大地改善了决策树的性能。
1986年,T.Niblett提出了Minimum— Error PruningAlgorithm。1987年,J.R.Quinlan提出了Reduced Error Pruning Algorithm。1987年，J. Mingers提出了Critical Value Pruning Algorithm。1992年,K.Kira和L. Rendell提出了RELIEF Algorithm,该算法是决策树算法发展史上一座里程碑。
4、C4.5算法
4.1 相关概念
4.1.1 熵
熵是信息论中的概念，假设数据集合 D，熵的计算公式为:

$entropy(D)=-\sum_{j=1}^{|C|}{Pr(c_{j})}log_{2}Pr(c_{j})$                                           (1)
式中 $Pr(c_{j})$ 表示 $c_{j}$ 类在数据集 $D$ 中的概率，当熵越小，数据越纯净，所以，熵可作为数据混杂度或混乱度的衡量指标。
4.1.2 信息增益
信息增益可以衡量混杂度或混乱度的减少量。假设  是 D 的属性，可取 v 个值，则 D 可划分成 v个不相交的子集 $D_{1}$ , $D_{2}$ ,…， $D_{v}$ 划分后 D 的熵为:

$entropy(A_{i},D)=\sum_{j=1}^{v}{\frac{\left| D_{j}\right|}{\left| D \right|}}\ast entropy(D_{j})$                                  (2)
则属性  的信息增益计算为:

$gain(D,A_{i})=entropy(D)-entropyA_{i}(D)$                                  (3)
4.1.3 信息增益率
信息增益偏向选择取值较多的属性，为了修正这种偏袒性，利用数据集的相对于属性值分布的熵归一化信息增益，使得熵都是相对于累属性的，称为信息增益率，计算为

$gainRatio(D,A_{i})=\frac{gain(D,A_{i})}{-\sum_{s}^{j-1}{(\frac{|D_{j}|}{|D|}\ast log_{2}\frac{|D_{j}|}{|D|}})}$                                  (4)
式中:s表示属性  的可能取值数目，  表示D中具  属性第j个值的子集。
4.2 C4.5算法描述
算法继承 ID3 的基础，是 ID3 的改进和优化，它用信息增益率代替信息增益来选择测试属性，支持离散属性和连续属性，还对决策树进行了必要的剪枝。
算法: Generate_ decision_ tree 由给定的训练数据集产生一棵决策树
输入: 数据集D，候选属性集A
输出: 一棵决策树T
Generate_ decision_ tree ( D，A)
创建节点 T;
if D都在同一个类C then
返回T作为叶节点，以类C标记;
else if          A为空or没有剩余属性进一步划分样本then
         返回T为叶节点，标记为 D 中最普通的类;             //多数表决
for each  D中的属性
         计算信息增益率 gainRatio
选择A中具有最高信息增益率的属性test_ A为测试属性;
标记节点T为 test_ A;
if 测试属性为连续型then
找到该属性的分割阈值;
for each test_ A 中的已知值                                              // 划分 D
由节点T生出一个条件为 test_ A =  的分枝;
设  是中 test_ A =  的样本集合;                                  //一个划分
if  为then
            加上一个树叶，标记为D中最普通的类;
else
            加上一个由Generate_ decision_ tree(  ，D－test_ A) 返回的节点;
进行剪枝;
4.3 决策树的剪枝
剪枝即是删除一些最不可靠的分枝，用多个类的叶节点代替，以加快分类的速度和提高决策树正确分类新数据的能力。常用的剪枝方法有预剪枝和后剪枝: 预剪枝就是提早结束决策树的构造过程，通过选取一个阈值判断树的构造是否停止，因为适当的阈值很难界定，所以预剪枝存在危险，不能保证树的可靠性; 后剪枝是在决策树构造完毕后得到一棵完整的树再进行剪枝，通常的思想是对每个树节点进行错误估计，通过与其子树的错误估计的比较，来判断子树的裁剪，如果子树的错误估计较大，则被剪枝，最后用一个独立的测试集去评估剪枝后的准确率，以此得到估计错误率最小的决策树。
C4.5剪枝技术是基于悲观错误的后剪枝方法，首先把构造的决策树转换成规则集合，然后通过删去某些条件来使得规则变短或变少。
5、分析和改进
5.1 C4.5算法问题分析
C4.5算法是在ID3算法的基础上改进而来，它不但分类速度快，精度高，分类规则易于理解，而且能够处理连续属性，此外C4.5算法用信息增益率代替信息增益来选择属性，克服了ID3算法在使用信息增益选择分枝属性时偏向取值较多的属性的缺陷。
但C4.5算法仍然存在一些不足，具体表现在以下两个方面：
（1）C4.5算法计算效率不高。设数据集  有R个记录，第h个属性为连续属性，  表示第i个记录的第h个属性的值。传统的C4.5算法，要将R个记录的第h个属性的所有属性值都作为候选划分点，对每个候选  都要遍历一遍数据集，计算出大于  和小于  的记录数，然后计算每个候选划分点的信息增益。选择信息增益最大的值作为最佳划分点。可以预见，当训练集中存在大量的连续属性时，对数据集的频繁遍历将会大大地降低算法的效率。
（2）C4.5算法容易导致过度拟合。Lim等对32种决策树的分类准确度、训练时间和模型复杂度等指标进行了对比研究。结果表明:C4.5算法虽然在训练时间与预测准确度等方面占有优势，但模型复杂度较高。这主要是因为：C4.5在进行分枝时，如果选取的属性是离散型属性，分枝产生的节点个数与该离散型属性的取值个数相同。如果选取的属性是连续型属性，分枝产生的节点个数 N 理论上在2与(R-1) 之间（R表示为记录个数）。在最坏的情况下，当数据集较大并且分枝的节点个数取(R-1)时，决策树的模型复杂度将是巨大的。巨大的模型复杂度必然导致决策树的过度拟合。
5.2 C4.5决策树算法的改进
5.2.1算法效率的改进
针对 C4.5算法计算效率不高的问题，本文首先利用边界定理，寻找候选分界点，之后用Gini指标代替信息熵来求得最佳分界点。算法改进思想具体描述如下：
定理1 Fayyad和Irani边界定理：不管用于训练的数据集有多大，维度有多高，也不管数据集中有多少类，其类别的分布如何，连续型属性的最佳划分点总是在边界点处。
边界定理表明，连续属性离散化的最佳分界点必定出现在边界处。基于这一思想可以降低连续属性离化的时间复杂度。以对  数据集排序为例，首先按照其连续属性数值的大小对数据集进行排序，然后找出记录中类标号发生变化的点，最后计算这些点两边的连续属性平均值，把这些平均值作为边界点。在最好的情况下，按照连续属性排序后，各个记录按照其类标号刚好集中在一起，此时只有一个分界点；在最差的情况下，按照连续属性排序后，各个类标号都不同，此时分界点的个数为预测集数据总数减 1。因此用边界定理可以减少计算次数，提高计算效率。
此外，用Gini指标代替信息熵来求得最佳分界点，能够简化计算过程，进一步的提高计算效率。
5.2.2解决过度拟合问题
针对 C4.5容易产生过度拟合的问题，本文基于“Occam’s razor”，采用再带入估计，对算法进行了改进。算法改进思想具体描述如下：
定理2 奥卡姆剃刀（Occam’s razor）定理：给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型更可取。
设：训练集D有R个记录,s个类。用此训练集形成的决策树有t个叶子节点，叶子节点的集合表示为{ $L_{1}$ , $L_{2}$ ,…, $L_{t}$ } ，第k个叶子节点中的类分别表示为{ $L_{k1}$ , $L_{k2}$ ,…, $L_{ks}$ } ，| $N_{k}$ |表示第 k 个节点中类的总个数，相应的第 k 个节点中每个类的个数表示为 |  |(1  i  s) ，max(|  |)(1  i  s)表示 |  | 中最大的值。则表示泛化误差的公式为：

$e=\frac{\sum_{k=1}^{t}{\sum_{i=1}^{s}{(|N_{k}|-max(|L_{ki}|))}}}{R}$                                           (5)
由定理2可知，当泛化误差相同时，较简单的模型更可取。因此，在只需要计算效率而不过分追求准确率的情况下，可以用再代入估计法。再代入估计方法的具体描述如下。
决策树每进行一次分裂，计算一次训练误差（训练误差是指训练集的误差，计算公式如式（5）），把训练误差看作泛化误差，当泛化误差小于某一特定值δ时停止决策树增长。δ根据数据集的不同而不同，需要根据实际需求经过多次测试来确定。
6、总结及展望
C4.5算法作为分类规则的经典算法，得到了业界的普遍肯定，不过决策树尽管分类较快和预测精度高，但是构造的树不够小，存在碎片和过度拟合的情况，针对 C4.5决策树算法的不足，如何改进和优化算法，还存在不少问题亟待解决，这正是今后的研究方向，主要有：
1.要找到最优的决策树是ＮＰ问题，必须寻找更好的方法，将决策树技术和其它新兴技术相结合，取长补短，提高决策树的抗噪声能力和准确性。
2.研究属性间的相关性对决策树产生的影响，以及如何利用或者消除这些相关性来构造决策树，值得关注。
3.决策树技术中如何处理时间复杂度和分类准确性之间的矛盾，一直以来都是一个令人感兴趣的问题。怎样在提高准确度的前提下降低时间复杂度，是今后研究的一个重点及难点。
4.决策树技术软件化一直是决策树技术的方向之一。如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决策树技术，是今后需努力实现的目标。
7、参考文献
[1] 刘耀南. C4.5算法的分析及应用[J]. 东莞理工学院学报, 2012(05):47-52.
[2] 姜欣, 徐六通, 张雷. C4.5决策树展示算法的设计[J]. 计算机工程与应用, 2003, 039(004):93-94,97.
[3] 李强. 创建决策树算法的比较研究——ID3,C4.5,C5.0算法的比较[J]. 甘肃科学学报, 2006(04):88-91.
[4] 黄爱辉. 决策树C4.5算法的改进及应用[J]. 科学技术与工程, 2009, 9(1):34-36.
[5] 苗煜飞, 张霄宏. 决策树C4.5算法的优化与应用[J]. 计算机工程与应用, 2015.
[6] 叶萌.决策树学习研究综述[J].黑龙江科技信息,2011(34):22+156.
[7] 李会, 胡笑梅. 决策树中ID3算法与C4.5算法分析与比较[J]. 水电能源科学, 2008(02):129-132.
[8] 谢金梅,王艳妮. 决策树算法综述[J]. 软件导刊(11期):83-85.
[9] 谢妞妞. 决策树算法综述[J]. 软件导刊, 2015, 14(011):63-65.
[10]Quinlan J R . Induction of Decision Trees[J]. Machine Learning, 1986, 1(1):81-106.
[11]Quinlan J R． C4． 5: Programs for Machine Learning［M］． San Mateo，CA: Morgan Kaufman Publisher，1993．
[12]于露，杨亚宁．C4．5 算法的研究与应用［J］．云南大学学报: 自然科学版，2010，32(S2) : 136 － 140．
[13]杨学兵，张俊．决策树算法及其核心技术［J］．计算机技术与发展，2007，17(1) : 43 － 45．
[14]刘小虎，李生.决策树的优化算法［J］．软件学报，1998，9( 10) : 797 － 800．
[15]王小巍，蒋玉明.决策树ID3算法的分析与改进［J］．计算机工程与设计，2011，32(9):3069－3076．
[16]黄爱辉，陈湘涛．决策树ID3算法的改进［J］．计算机工程与科学，2009，31(6) : 109 － 111．
[17]王会青，陈俊杰，侯晓晶，等．决策树分类的属性选择方法的研究［J］．太原理工大学学报，2011，42(4) : 346 － 352．
[18]Bing Liu． Web 数据挖掘［M］．北京: 清华大学出版社，2009．
[19]刘鹏，姚正，尹俊杰．一种有效的 C4． 5 改进模型［J］．清华大学学报: 自然科学版，2006，46( S1) : 996 － 1001．
[20]Hunt E B，Marin J，Stone P T.Experiments in induction[M].San Diego：Academic Press，1966：77-89.
[21]Dunham M.Data mining：Introductory and advanced topics[M].Upper Saddle River，N J：Pearson Education，2003.
[22]刘佳，王新伟.一种改进的 C4.5 算法及实验分析[J].计算机应用与软件，2008，25（12）：260-262
[23]Breiman L，Friedman J H，Olshen R，et al.Classification and regression trees[M].New York：Chapman & Hall，1984.
[24]魏晓云.决策树分类方法研究［J］.计算机系统应用，2007（9）.
[25]王玉珍.基于数据挖掘的决策树方法分析［J］.电脑开发与应用.2007（5）.
[26]王名扬．基于数据挖掘的决策树生成与剪枝方法［J］．计算机工程与科学，2005（11）．
[27]Yuxun L , Niuniu X . Improved ID3 algorithm[C]// IEEE International Conference on Computer Science & Information Technology. 0.
[28]Breiman L I , Friedman J H , Olshen R A , et al. Classification and Regression Trees. Wadsworth.[J]. Biometrics, 1984, 40(3):358.
[29]Gama J . Functional Trees[J]. Machine Learning, 2004, 55(3):219-250.
[30]谢妞妞, 刘於勋. 决策树属性选择标准的改进[J]. 计算机工程与应用, 2010, 46(034):115-118.

		自动登录	找回密码
密码			立即注册

十大经典算法之C4.5算法综述

本帖子中包含更多资源