基于分类规则的C4_5决策树改进算法_李孝伟

２０１３年１２月第３４卷　第１２期

计算机工程与设计

ＣＯＭＰＵＴＥＲＥＮＧＩＮＥＥＲＩＮＧ　ＡＮＤＤＥＳＩＧＮ　　

Ｄｅｃ．２０１３

Ｖｏｌ．３４　Ｎｏ．１２

??????????????????????????????????????????????????

基于分类规则的Ｃ４．５决策树改进算法

李孝伟，陈福才，李邵梅

（）国家数字交换系统工程技术研究中心，河南郑州４５０００２

摘　要：为解决大样本数据条件下Ｃ４．５决策树算法需要训练集常驻内存、分类精度达不到需求以及如何选取最优分类规则等问题，提出了一种基于分类规则选取的Ｃ４．５决策树改进算法。通过数次有放回的随机抽取训练集形成多个分类规则，在多次分类规则内寻找特征的最优取值以建立最优分类规则，以划分相似度为标准进行Ｃ４．５决策树最优特征选取，在此基础上利用选定的最优分类规则和最优特征对Ｃ４．５决策树算法进行改进。实验结果表明，改进后的算法可有效解决Ｃ４．５决策树与初始训练集相关性较大的问题，对大样本数据集的分类识别在识别率上有显著提高，训练时间明显减少。关键词：Ｃ４．５决策树；分类规则；属性度量；划分相似度；特征选取

）１中图法分类号：ＴＰ３９１．４　文献标识号：Ａ　文章编号：１０００７０２４（２０１３２４３２１０５－－－

ＩｍｒｏｖｅｄＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅａｌｏｒｉｔｈｍｂａｓｅｄｏｎｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓ　　　　　　　ｐｇ

，，ＬＩＸｉａｏｅｉＣＨＥＮＦｕｃａｉＬＩＳｈａｏｅｉ　－ｗ　－　－ｍ

（，）ＣｈｉｎａＮａｔｉｏｎａｌＤｉｉｔａｌＳｗｉｔｃｈｉｎＳｓｔｅｍＥｎｉｎｅｅｒｉｎａｎｄＴｅｃｈｎｏｌｏｉｃａｌＲａｎｄＤＣｅｎｔｅｒＺｈｅｎｚｈｏｕ４５０００２，Ｃｈｉｎａ　　　　　　　　　　ｇｇｙｇｇｇｇ　　：Ｕ，，Ａｂｓｔｒａｃｔｎｄｅｒｔｈｅｃｏｎｄｉｔｉｏｎｏｆｌａｒｅｓａｍｌｅｄａｔａｓｅｔｏｆｍｅｍｏｒｒｅｓｉｄｅｎｔｃｌａｓｓｉｆｉｃａｔｉｏｎａｃｃｕｒａｃｎｅｅｄｔｏｍｅｅｔｔｈｅｄｅｍａｎｄａｎｄ　　　　　　　　　－　　　　　ｇｐｙｙ，ｔｏｓｅｌｅｃｔｔｈｅｏｔｉｍａｌｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓｔｈｅｉｍｒｏｖｅｄＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅａｌｏｒｉｔｈｍｂａｓｅｄｏｎｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓｓｅｌｅｃｔｉｎｉｓｈｏｗ　　　　　　　　　　　　　　　ｐｐｇｇ　ｆｏｒｗａｒｄ．Ｔｈｅａｌｏｒｉｔｈｍｆｏｒｍｓａｌｕｒａｌｉｔｏｆｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓｔｈｒｏｕｈｓｅｖｅｒａｌｔｉｍｅｓｂａｃｋｉｎｔｈｅｒａｎｄｏｍｔｒａｉｎｉｎｓｅｔ．Ｂｕｔ　　　　　　　　　　　　　　　ｐｇｐｙｇｇｙ　　，，ｓｅｖｅｒａｌａｒｔｉｔｉｏｎｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓｔｈｅｏｔｉｍａｌｖａｌｕｅｉｓｆｏｕｎｄｉｎｏｒｄｅｒｔｏｅｓｔａｂｌｉｓｈｔｈｅｏｔｉｍａｌｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓａｎｄｕｓｅｓｉｍｉ　　　　　　　　　　　　　　　　　－ｐｐｐｌａｒｉｔａｓｓｔａｎｄａｒｄｔｏｓｅｌｅｃｔＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅｏｔｉｍａｌｆｅａｔｕｒｅ．Ｂａｓｅｄｏｎｔｈｅｕｓｅｏｆｏｔｉｍａｌｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓａｎｄｓｅｌｅｃｔｅｄｏｔｉｍａｌ　　　　　　　　　　　　　　　　　ｙｐｐｐ　，ｆｅａｔｕｒｅＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅａｌｏｒｉｔｈｍｉｓｉｍｒｏｖｅｄ．Ｔｈｅｅｘｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｒｏｖｅｄａｌｏｒｉｔｈｍｃａｎｅｆｆｅｃｔｉｖｅｌｓｏｌｖｅｔｈｅ　　　　　　　　　　　　　ｇｐｐｐｇｙ　，ｒｏｂｌｅｍｔｈａｔＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅｉｓｌａｒｅｃｏｒｒｅｌａｔｅｄｗｉｔｈｉｎｉｔｉａｌｔｒａｉｎｉｎｓｅｔｃｌａｓｓｉｆｉｃａｔｉｏｎｒａｔｅｏｆｌａｒｅｓａｍｌｅｄａｔａｓｅｔｓｉｓｓｉｎｉｆｉ　　　　　　　　　　　　　　　　　－ｐｇｇｇｐｇ　ｃａｎｔｌｉｎｃｒｅａｓｅｄ．Ｔｈｅｔｒａｉｎｉｎｔｉｍｅｉｓｓｉｎｉｆｉｃａｎｔｌｒｅｄｕｃｅｄ．　　　ｙｇｇｙ　　　

：Ｃ；；；；ａｒｔｉｔｉｏｎＫｅｗｏｒｄｓ４．５ｄｅｃｉｓｉｏｎｔｒｅｅｃｌａｓｓｉｆｉｃａｔｉｏｎｒｕｌｅｓａｔｔｒｉｂｕｔｅｍｅａｓｕｒｅｓｓｉｍｉｌａｒｉｔｆｅａｔｕｒｅｓｅｌｅｃｔｉｏｎ　　　　　ｐｙｙ　

０　引　言

［１］

）决策树（是数据挖掘中一个关于分类和ｄｅｃｉｓｉｏｎｔｒｅｅ　

它在以往决策树算法的基础上，增加了对特征为连续值的处理；利用信息增益率来选择特征解决了信息增益偏向于选择特征取值较多的缺点，同时也可以处理缺少特征值的训练样本；通过使用不同的剪枝技术以避免树的不平衡；以及Ｋ次迭代交叉验证来选取尽可能优的局部最优解。但是Ｃ４．５关于决策树的局部最优解问题、大数据处理的依赖主存问题和效率问题并没有过多的改进。

提高算法运算效率的一个有效途径就是利用尽可能少的训练样本，提取出尽可能优的分类规则。但是盲目的减少训练样本不可能提高运算效率。在不影响分类算法泛化性能的前提下减少训练样本，实现算法的存储需求和时间消耗的减少。为此，针对不同的分类器可以有不同的缩减

预测的快速、有效的算法。它首先选取最优特征作为根节点，然后根据不同特征判断从根节点向下的分支，在决策树的叶节点得到结论。传统的决策树算法大都要求训练集

２］

，这使得算法在可伸缩性、精度和效率方面受常驻内存［

到很大的制约。在面对数据量超过运行主存的情况时，构造决策树需要将数据在主存和缓存中导人或者导出，大大降低了运算效率。

［］

Ｃ４．５算法３是决策树中一个经典的算法。Ｑｕｉｎｌａｎ针

对以往决策树算法的不足，在１９９３年提出了Ｃ４．５算法。

；修订日期：２收稿日期：２０１３０４２２０１３０６２５－－－－

）基金项目：国家８６３高技术研究发展计划基金项目（２０１１ＡＡ０１０６０３、２０１１ＡＡ０１０６０５

，男，安徽阜阳人，硕士研究生，研究方向为通信与信息系统；陈福才（，男，江西高安人，硕士生导作者简介：李孝伟（１９８７１９７４－）－），女，湖北钟祥人，博士，讲师，研究方向为通信与信息系统。师，研究方向为通信与信息系统；李邵梅（１９８２－）：Ｅ－ｍａｉｌｌｘｗｅｉ＿１９８７＠１２６．ｃｏｍ

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新经管营销基于分类规则的C4_5决策树改进算法_李孝伟全文阅读和word下载服务。