资源描述：
《C4.5算法的两点改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第20卷第4期江苏工业学院学报Vol.20No.42008年12月JOURNALOFJIANGSUPOLYTECHNICUNIVERSITYDec.2008文章编号:1673-9620(2008)04-0056-04＊C4.5算法的两点改进12乔增伟,孙卫祥(1.江苏工业学院信息科学与工程学院,江苏常州213164;2.上海交通大学振动、冲击、噪声国家重点实验室,上海200240)摘要:C4.5作为一种重要的决策树算法尚存一些不足之处。针对C4.5对于连续属性最优分割阈值选择比较耗时的缺点,基于F
2、ayyad边界点判定定理,提出一种改进最优阈值选择方法。针对C4.5不具备增量式学习能力的缺点,在改造树结构体的基础上,提出C4.5增量学习的改进方法。关键词:决策树;C4.5;最优阈值;增量式学习中图分类号:TP301.6文献标识码:ATwoImprovementstoC4.5Algorithm12QIAOZeng-wei,SUNWei-xiang(1.SchoolofInformationScienceandEngineering,JiangsuPolytechnicUniversity,Ch
3、angzhou213164,China;2.StateKeyLaboratoryofVibration,Shock&Noise,ShanghaiJiaotongUniversity,Shanghai200240,China)Abstract:Asanimportantdecisiontreealgorithm,C4.5stillhastwodisadvantages.Oneisthatitisverytime-consumingtofindtheoptimalthresholdofcontinuo
4、usattribute.TheotheristhatC4.5hasnoabili-tyofincrementallearning.BasedontheboundarypointtheoremgivenbyFayyad,animprovementmethodofselectingtheoptimalthresholdisproposedtoovercomethefirstdisadvantage.Also,afterthemodifica-tionoftreestructureofC4.5,anin
5、crementalC4.5algorithmisputforwardtosolvethesecondproblem.Keywords:decisiontree;C4.5;optimalthreshold;incrementallearning决策树的先驱是概念学习系统(Concept提出了C4.5算法。LearningSystem,CLS),它由Hunt等人提出,该算法使用一组训练实例,构造出等价于析取规则1C4.5算法简介形式的决策树表示概念描述,然后运用这些概念对C4.5算法是ID3算法的改进
6、,增加了对连续[3]新的实例进行分类。1986年,Quinlan修改了CLS型属性、属性值空缺情况的处理。算法主体由决[1]并提出的ID3算法,ID3以树的形式表示已经获策树生成算法C4.5tree、剪枝算法C4.5pruning、取的知识,树的内部节点表示测试属性,叶节点是规则生成算法C4.5rules3部分组成。C4.5tree算类标识,从根到叶形成一条分类规则。1993年,法依据信息熵理论,选择当前样本集中具有最大信Quinlan在文献[2]中对ID3算法进行了完善,息增益率的属性作为测试属
7、性不断对样本集进行划＊收稿日期:2008-04-11作者简介:乔增伟(1978-),男,河南驻马店人,硕士,讲师,研究方向:数据挖掘、软件工程。乔增伟等.C4.5算法的两点改进·57·分,最终构造出一棵完全决策树。对于连续型的属的T,总是处于实例序列中两个相邻异类实例之性先进行离散化,即把连续型属性的值划分成不同间。的区间,便于处理。C4.5pruning采用基于错误的2.3改进分割阈值选择方法剪枝方法对完全决策树进行修剪,得到简化决策树。C4.5rules把完全决策树转化成一组if.then由F
8、ayyad边界点判定定理可知,无需检查每规则集并进行化简。经剪枝或规则生成过程得到的一个阈值点,只要检查相邻不同类别的边界点即[4]简化决策树和规则集都可用于分类。可。为了保持与C4.5的一致性,这里边界点选为C4.5作为ID3的升级版本,虽然已经得到很相邻不同类别的属性值中较小的一个。例如,当排[5]好的应用,但是还存在一些不足。其一是,对连序后的实例属性值为{v1,v2,…,v10},其中前续属性离散化时,C4.5算法计算每个分割点的信3个属于类别C1,中间4个属于类别C2,最
