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

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

计算机工程与设计

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

Ｄｅｃ．２０１３

Ｖｏｌ．３４　Ｎｏ．１２



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

李孝伟，陈福才，李邵梅

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

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

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

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

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

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

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

０　引　言

［１］

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

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

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

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

２］

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

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

［］

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

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

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

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

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

·４　３２２·

计算机工程与设计

２０１３年

样本策略，如：支持向量机的决策只与决策边界的支持向量有关，重点选择此类样本；Ｃ４．５决策树建树的重点是最优特征值样本的选取，在缩减样本提取分类规则时，则以样本是否能很好的反映类内特征取值的情况来进行取舍。缩减样本可以起到降低分类算法的计算代价，加快训练速

４］

，还能有效地精简训练集，度，避免出现“过拟合”现象［

去除相似、冗余、重复的信息以及噪声样本。此外，对于数据集不大的情况，由于Ｃ４．５对于初始训练样本的依赖性比较大，若初始训练样本不能很好地表征各特征的取值，可能使得训练结果不理想，此时若采用选择样本提取分类规则的策略，提取尽量最优的分类规则以提高训练精度对于Ｃ４．５决策树而言也具有重要意义。

５］

刘鹏等［根据决策树易产生碎片问题，提出了一种合

图１　简单的决策树模型

１．１　Ｃ４．５决策树的形成

假定训练数据集中包含ｍ类别，分别为Ｔ＝｛ｔ１，，。训练数据集中某属性Ａ可能有（，ｔ．．．ｔａａ．．ａ２，ｍ｝１，２，ｋ），，共ｋ种取值，根据属性Ａ的划分为Ｔ′＝｛ｔ′ｔ′．．．ｔ′１，２，ｒ｝其他属性类似于属性Ａ。根据训练集可得其理想划分的信息熵为

ｍ

并分类效果差分枝的Ｒ－Ｃ４．５模型。该模型未设置连续属性

［］

一对多”处理和缺失值处理。ＫｅｍａｌＰｏｌａｔ等６将Ｃ４．５和“　

分类模型相结合应用于多类分类问题，取得了很好的效果。

［］

ＨａｎＪｉｎｔｉ等７将Ｃ４．５和模糊数学相结合，提出了一种处　－ｇ８］理范围输入的方法。姚亚夫等［根据Ｆａｄ连续值取值的ｙｙ

最佳分割点总在边界点处得原理，只在连续属性分界点处的少数几个分割点中选择最佳分割阈值，构造了Ｃ４．５分类器，一定程度上提升了Ｃ４．５处理连续属性的性能。周剑锋

９］等［提出了一种改进的信息熵的计算方法，通过减少计算１０］

根据函数的复杂度，提高就决策树的构建速度。杨哲等［

Ｈ（Ｔ）＝－∑ｐ（ｔｌｏｔｇｉ）２ｉ）ｐ（

ｉ＝１

ｍ

）（１

（。其中ｐ（ｔ＝ｉ）ｉ／ｉ）∑ｉ＝１

以属性Ａ对训练集划分获得的信息熵为

ｒ

Ｔ′）＝　ＨＡ（

＝

信息增益率的不确定性，采用Ｍａｎｔａｒａｓ范式距离来度量属性划分与真实划分的距离，有效避免了增益率的不确定性。现有的改进算法在减少决策树的计算复杂度、特征的优化处理、增益率问题上都有很多的优化。但是对Ｃ４．５决策树的局部最优解、大数据处理的依赖主存问题和效率问题一直没有得到很好的解决。

基于上述问题，本文利用多次抽样选择最优分类规则并对Ｃ４．５决策树算法进行优化和改进，提出了基于分类规则的Ｃ４．５决策树改进算法。实验结果表明，利用改进后的算法处理小样本数据时正确率与Ｃ４．５算法相当；而在处理大样本数据的识别分类时，运算效率和精度的提高比较显著。

ｉ＝１ｒ

ｔ′）Ｈ（ｔ′）∑ｐ（

ｉ

ｉｍ

ｉ

ｊ

ｉ

２

ｉ＝１

ｔ′）ｔ｜ｔ′）ｌｏｔ｜ｔ′）－∑ｐ（ｇｐ（（）∑ｐ（

ｊ

ｉ

ｊ＝１

ｒ

ｍ

Ｔ′）＝－∑∑ｐ（ｔ′ｔｔ′ｌｏｔｔ′　ＨＡ（ｇｉ）ｉ）２ｉ）ｐ（ｐ（ｊ｜ｊ｜

ｉ＝１ｊ＝１

Ｔ｜Ｔ′）＝Ｈ（

其中ｐ（ｔ′′′∑ｉ）＝ｉ／（ｉ

ｉ＝１ｒ

）（２

），ｐ（ｔ′ｉ）＝ｊ｜ｔ

′ｔ′ｉ∩ｉ。ｊ／表示划分Ｔｔｔ′′中属于ｔ′ｉ）ｉ的样本，在理想划分ｐ（ｊ｜中属于子集ｔｊ的概率。由此可得属性Ａ对于训练集划分的信息增益为

ＨＧＴ′）＝Ｈ（Ｔ）Ｔ′）－ＨＡ（ａｉｎ（

属性Ａ的分割信息熵为

ｒ

）（３

１　Ｃ４．５决策树介绍

决策树作为传统的机器学习算法，其用于分类识别的主要步骤同其他分类算法一致，主要是：一是利用训练数据构建分类模型，二是利用建立的分类模型对待识别样本数据集进行分类。其中主要工作是第一步，对于决策树分类算法而言是建立用于分类的决策树模型。图１所示是一个简单的决策树分类模型，其主要功能是实现根据天气情况来决定是否去户外活动

。

Ｈ（Ｔ′）＝－∑ｐ（ｔ′ｌｏｔ′ｇｉ）２ｉ）ｐ（

ｉ＝１

）（４

）、式（）可得属性Ａ的信息增益率为由式（３４／ａｔｉｏ（Ｔ′）＝ＨＧＴ′）Ｈ（Ｔ′）　　Ｒａｉｎ（

＝

（））（

Ｈ（Ｔ′）

（）５

同理可计算其他属性的信息增益率。通过计算所有属性的信息增益率，选出具有最大信息增益率值的属性作为决策树的根节点。然后，以同样的方法确定决策树各层的

第３４卷　第１２期

李孝伟，陈福才，李邵梅：基于分类规则的Ｃ４．５决策树改进算法

·４３２３·

节点，计算方法同以上步骤。１．２　Ｃ４．５决策树的剪枝

征对应的划分与理想划分之间的相似度。

Ｃ４．５采用的信息增益率如下

Ｃ４．５决策树的剪枝策略采用的是后剪枝的方法。后剪枝策略首先需要构造完整的决策树，允许决策树过度拟合训练数据，然后对那些置信度不够的子树节点用叶节点来替代。

Ｃ４．５决策树对ＩＤ３算法做了改进，取得了不错的效——局部最果。但是Ｃ４．５自身仍存在着决策树的共性问题—）可以看出，当分母为零时，分子必优解。此外，从式（５然为零，这时增益率的计算就出现了问题，这就是增益率带来的不确定性问题。大样本数据条件下，减小Ｃ４．５决策树的运算复杂度也是一个问题。

Ｒａｔｉｏ（Ｔ′）＝

＝

（））（

ＨＴ′）Ｈ（Ｔ）Ｈ（Ｔ，Ｔ′）Ｔ′）（Ｈ（

ＨＴ′（）１０

）与式（比较式（９１０）可得：Ｈ（Ｔ′）＝０时，Ｈ（Ｔ′，）不会出现式（９１０）的０∶０的情况，此时Ｔ）≠０，式（

可以解决增益率带来的不确定性问题。式（９）是由Ｍａｎｔ－ａｒａｓ范式距离而得来的，故其能很好的表征两个划分之间的相似度。划分相似度方法能有效克服信息增益率方法的缺陷，算法的稳定性好，其构建的决策树规模更小，分类速度更快。

ｑ

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

本文针对的主要是大样本条件下的分类识别和Ｃ４．５决策树与初始训练集相关性较大等问题。运用多次抽样选出最优分类规则，以缩减算法的运算复杂度，提高训练精度。在Ｃ４．５最优特征选择上以划分相似度作为选择标准。２．１　最优特征选择

由熵函数的上凸性及詹森不等式有：

ｑ

ｉ＝１ｑ

ｏｇｙ∑ｐｌ

ｉ

ｉ

≤

ｌｏｏｇｇｉｉ，在计算信息熵的时候，由于ｌｉｉ计算ｙｙ∑ｐ∑ｐ

ｉ＝１

ｉ＝１

ｑ

ｑ

结果与ｌｏｏｇｇｉｉ的计算结果相差不大，用ｌｉｉ来ｙｙ∑ｐ∑ｐ

ｉ＝１

ｉ＝１

ｑ

近似代替

本文对Ｍａｎｔａｒａｓ范式距离进行相应的简化，以减少算法的复杂度和时间消耗。Ｍａｎｔａｒａｓ范式距离是在各特征中选择与类别划分距离最近的特征作为当前节点的测试条件，用最短距离划分的办法来构建决策树。根据样本集Ｔ的理，想划分Ｔ＝｛和以属性Ａ作为测试条件所得ｔｔ．．．ｔ１，２，ｍ｝，，则划分Ｔ的划分Ｔ′＝｛ｔ′ｔ′．．．ｔ′′对于理想划分Ｔ１，２，ｒ｝的条件熵可以由式（２）得到。而理想划分Ｔ对于划分Ｔ′的条件熵为

ｍ

ｒ

ｉ＝１

ｏｇｙ∑ｐｌ

ｉ

ｉ

。这样式（）可以简化为９

（））（

ｄ（Ｔ′，Ｔ）＝

Ｈ（Ｔ′，Ｔ）

ｍ

２

ｒ

２ｌｏｔｏｔ′＋ｌｇｇ２ｉ）２ｉ）ｐ（ｐ（∑∑ｉ＝１ｉ＝１

≈－

ＨＴ′Ｔｍ

２

ｒ

２

·ｌｏｔｔ′ｇ２ｉ）ｉ）ｐ（ｐ（（）∑∑ｉ＝１ｉ＝１

（，）ｄＴ′Ｔ≈－

ＨＴ′Ｔ（）１１

）将多次对数运算简化为一次，在一定程度上式（１１减小Ｃ４．５决策树建树的复杂度。２．２　分类规则的选取

）／）（６Ｈ（Ｔ′｜Ｔ）＝－∑∑ｐ（ｔ′ｔｌｏｔ′ｔｔｇｉ，２（ｉ，ｐ（ｐ（ｊ）ｊ）ｊ）

ｊ＝１ｉ＝１

划分Ｔ′与理想划分Ｔ的联合熵为

ｍ

ｒ

本文采用的样本选择方法主要是多次提取样本进行决

）（７

策树的拟合，生成相对较优的决策树，将较大量的样本通过随机有放回的抽样，生成多个训练集，利用这些训练集的训练结果回溯生成最优的分类规则。

具体步骤如下：

第一步，对给定的数据集选择合适的训练样本数据，选择的标准是综合考虑训练时间和迭代次数。如果选择的的数据较小，会造成较多的迭代次数，否则会造成较多的训练时间。

第二步，针对选定的训练样本，通过实验确定抽样迭代次数Ｌ，理论上Ｌ越大越好，但Ｌ越大，处理时间也会

Ｈ（Ｔ′，Ｔ）＝－∑∑ｐ（ｔ′ｔｌｏｔ′ｔｇｉ，２ｉ，ｐ（ｊ）ｊ）

ｊ＝１ｉ＝１

因此，划分Ｔａｎｔａｒａｓ范式距离为′与理想划分Ｔ的Ｍ

（））（

Ｄ（Ｔ′，Ｔ）＝

ＨＴ′Ｔ）＋Ｈ（），得到＝Ｈ（Ｔ｜Ｔ′Ｔ′

（）８

由熵的强可加性，即Ｈ（Ｔ′，Ｔ）＝Ｈ（Ｔ′｜Ｔ）＋Ｈ（Ｔ）

（，）），））（（（

Ｄ（Ｔ′，Ｔ）＝ＨＴ′Ｔ

＝２－

令

（））（

ＨＴ′Ｔ（））（

ｄ（Ｔ′，Ｔ）＝

ＨＴ′Ｔ（）９

随之增加，Ｌ值的确定依据是当Ｌ增加时，对训练样本的精度提升不再产生影响或是影响很小。

第三步，针对Ｌ次训练结果产生的Ｌ个决策树形成的

定义１　划分相似度ｄ（Ｔ′，Ｔ）。划分相似度表示为特

·４　３２４·

计算机工程与设计

２０１３年

分类规则进行离散取值特征和连续取值特征的处理。具体方法如下：

对于离散数值特征：统计Ｌ个规则内，各个取值出现的次数，选取出现次数多的作为新规则内该类别此特征的取值，以此方法建立此类特征的特征取值空间。

对于连续取值特征：每一类的连续取值特征都有相应的区间上限和下限，选取Ｌ次规则内的全部上限和下限的算术平均作为新规则内该类别特征的取值上限和下限。

通过上述过程，每迭代一次，形成一个决策树的分类规则，相应的每一类别都对应其具体的特征取值，最优的分类规则则是通过多次建树形成的分类规则回溯得到，通过最优的分类规则可以建立最优的决策树。２．３　剪枝策略

回归、聚类、关联规则等多种机器学习算法，并能够实现交互式界面上的可视化。

本文选用ＵＣＩ机器学习数据库（ｍａｃｈｉｎｅｌｅａｒｎｉｎｒｅ　－ｇ　）中的Ｎ、Ｍ、ＢｏｓｉｔｏｒｕｒｓｅｒＤａｔａｂａｓｅａｉｃ０４、Ｌｅｔｔｅｒａｎｋｐｙｙｇ　、ＰＭａｒｋｅｔｉｎｏｓｔｕｒｅＲｅｃｏｎｓｔｒｕｃｔｉｏｎ等５个数据集来进行实　ｇ验。选择的数据集特征维数都不高，便于运用Ｃ４．５算法。各个数据集的大小和特征情况见表１。

表１　数据集样本个数和特征个数

数据集ＮｕｒｓｅｒＤａｔａｂａｓｅ　ｙ　

Ｍａｉｃ０４　ｇＬｅｔｔｅｒ　ＢａｎｋＭａｒｋｅｔｉｎ　ｇ　ＰｏｓｔｕｒｅＲｅｃｏｎｓｔｒｕｃｔｉｏｎ　　

样本１２，９６０　１９，０２０　２０，０００　４８，８４２　１６４，８６０　

特征８　１１　１７　１４　８　

训练集６，４８０９，５１０１０，０００２０，０００５０，０００

本文拟采取的剪枝策略与ＣＡＲＴ算法类似。首先让决策树充分的生长，使得叶节点有最小的不纯度为止，然后，对所有相邻的成对叶节点，考虑是否消去他们。标准是如果消去他们使得不纯度增加的很小，就执行消去。这里的不纯度采用Ｇｉｎｉ不纯度，多类分类问题的不纯度定义为

３．２　实验结果及分析

本文实验采用的硬件环境是：ＣＰＵＣｏｒｅ２Ｐ９６００，　内存４２．６６Ｇ．Ｇ，硬盘５００Ｇ，Ｗｉｎｄｏｗ７操作系统。实验首先采用不同的抽样次数来确定最终的抽样次数。然后在选定抽样次数下于Ｃ４．５算法进行比较。

图２为数据集ＢａｎｋＭａｒｋｅｔｉｎ　ｇ不同抽样次数的正确率对比。由图中可以看出在抽样次数比较少的情况下，本文算法不如Ｃ４．５算法。随着抽样次数的增加，本文算法的优势逐渐体现出来，当抽样次数增加到一定数值时，算法的性能也趋于平稳。由图中可以看出，当抽样次数为１２和１５时，算法性能差别很小，故选择１２为最终抽样次数

。

ｉｍＮ）＝ｐ（

ｗ）Ｐ（ｗ）＝１－∑Ｐ∑Ｐ（

ｉ

ｊ

ｉｊ≠

ｊ

２

）（１２ｗｊ）（

其中Ｐ（是节点Ｎ处属于ｗｗｊ）ｊ类样本数占总样本数的比例。显然如果所有样本都属于一类，则不纯度为０，否则就是一个大于０的正值。

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

本文提出的基于分类规则选取的Ｃ４．５决策树改进算法（ｉｍｒｏｖｅｄＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅａｌｏｒｉｔｈｍｂａｓｅｄｏｎｃｌａｓｓｉｆｉｃａ　　　　　　－ｐｇ，），在训练阶段以第一节提出分ｔｉｏｎｒｕｌｅｓｓｅｌｅｃｔｉｏｎＣＲＣ４．５　　类规则选取策略，在构建决策树选取最优特征上以第二节提出的划分相似度为基础建立Ｃ４．５决策树。具体算法流程如下：

（）运用划分相似度对训练样本各特征进行排序，选１

择有最大划分相似度的特征作为根节点，以后节点以此类推；

（）选定训练样本数目，并对对样本进行有放回的多２

次抽样，运用划分相似度训练分类规则，取多次抽样下分类规则中最优的特征值回溯作为最终分类规则；

）根据最优的分类规则建立最优的决策树，并对测（３

试集进行测试，最后输出分类模型。

３　实验及分析

３．１　实验平台和数据集介绍

图２　不同抽样次数下算法性能比较

经过实验，各数据集下训练集样本迭代次数见表２。Ｃ４．５算法和本文算法的模型建立时间和分类正确率对比如图３、图４所示。其中，Ｃ４．５采用多次次迭代交叉验证的方法。

本文采用Ｗｅｋａ平台对改进的算法和Ｃ４．５算法进行对比测试。Ｗｅｋａ是由新西兰大学Ｗｉｔｔｅｎ教授等人基于Ｊａｖａ编程开发的开源工作平台，它集合了包括对数据进行分类、

第３４卷　第１２期

李孝伟，陈福才，李邵梅：基于分类规则的Ｃ４．５决策树改进算法

·４３２５·

表２　不同数据集抽样次数

数据集ＮｕｒｓｅｒＤａｔａｂａｓｅ　ｙ　

Ｍａｉｃ０４　ｇＬｅｔｔｅｒ　ＢａｎｋＭａｒｋｅｔｉｎ　ｇ　ＰｏｓｔｕｒｅＲｅｃｏｎｓｔｒｕｃｔｉｏｎ　　

抽样次数

８８１０１２２

０

练集相关性大以及信息增益率带来的不确定问题，提出了基于分类规则选取的Ｃ４．５决策树改进算法。分类规则选取上以多次抽样训练的分类规则为基础形成最优分类规则，实验表明在选取的最优分类规则下测试的精度同未进行分类规则选择的训练集测试精度有明显提升。对于大样本而言，训练时间也有明显的缩短。在Ｃ４．５决策树的特征选择上以提出的划分相似度为基准，克服了信息增益率的不稳定性，并且依据熵函数的上凸性，简化了熵的运算，也带来了运算量的减少。目前，本文提出的分类规则选取策略针对分类规则较复杂的情况还没有进一步的论证实验；此外划分相似度的优越性还缺乏有效的理论证明，这些都需要进一步的研究。

参考文献：

［］Ｆ１ＥＮＧＳｈａｏｒｏｎ．Ｒｅｓｅａｒｃｈａｎｄｉｍｒｏｖｅｍｅｎｔｏｆｄｅｃｉｓｉｏｎｔｒｅｅａｌ　　　　　　　－ｇｐ

，２：Ｊ］．ＪｏｕｒｎａｌｏｆＸｉａｍｅｎＵｎｉｖｅｒｓｉｔ００７，４６（４）ｏｒｉｔｈｍ［　　　ｙｇ

）冯少荣．决策树算法的研究与改进４９６５００（ｉｎＣｈｉｎｅｓｅ．［－　［］）：］Ｊ．厦门大学学报，２００７，４６（４４９６５００．－

［］Ｆ，Ｘ２ＥＮＧＳｈａｏｒｏｎＩＡＯ　Ｗｅｎｕｎ．Ｉｍｒｏｖｅｄｄｅｃｉｓｉｏｎｔｒｅｅａｌｏ　　　　－ｇｊｐｇ

图３　模型建立时间

对比

ｒｉｔｈｍｂａｓｅｄｏｎｓａｍｌｅｓｓｅｌｅｃｔｉｏｎ［Ｊ］．ＪｏｕｒｎａｌｏｆＳｏｕｔｈｗｅｓｔ　　　　　　ｐ，）：）冯ＪｉａｏｔｏｎＵｎｉｖｅｒｓｉｔ２００９，４４（５６４３６４７（ｉｎＣｈｉｎｅｓｅ．［－　ｇｙ　］少荣，肖文俊．基于样本选择的决策树改进算法［Ｊ．西南交）：］通大学学报，２００９，４４（５６４３６４７．－

］Ｔ［３ｈａｋｕｒＤ，ＭａｒｋａｎｄａｉａｈＮ，ＲａＤＳ．ＲｅｏｔｉｍｉｚａｔｉｏｎｏｆＩＤ３　　　　　　ｊｐ　

／ＩａｎｄＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅ［Ｃ］／ｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎ　　　　，ＣｏｍｕｔｅｒａｎｄＣｏｍｍｕｎｉｃａｔｉｏｎＴｅｃｈｎｏｌｏ２０１０：４４８４５０．　　　－ｐｇｙ［］Ｂ，４ｒａｍｅｒＭ．ＰｒｉｎｃｉｌｅｓｏｆＤａｔａＭｉｎｉｎＭ］．ＬｏｎｄｏｎＳｒｉｎｅｒ　　　　　ｐｇ［ｐｇ

２０１３：１２１１３６．－

［］Ｌ，ＹＡＯ，Ｙ５ＩＵＰｅｎＺｈｅｎＩＮＪｕｎｉｅ．Ｉｍｒｏｖｅｄｄｅｃｉｓｉｏｎｔｒｅｅｏｆ　　　　　　ｇｇｊｐ

］，：Ｃ４．５［Ｊ．ＴｓｉｎｈｕａＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏ２００６，４６（Ｓ１）　　　ｇｇｙ

图４　分类正确率对比

从图３和图４中可以看出，ＣＲＣ４．５与Ｃ４．５算法相比，在较小数据集情况下，模型建立时间和分类正确率基本相当。但是随着数据集的加大，本文算法的优势逐渐体现出来。从模型建立时间来看，本文提出的划分相似度相对于信息增益率在数据集较大情况下，运算速度明显加快。从正确率对比可以看出，经过最优分类规则的选择，在较大数据集下，本文算法性能相对于Ｃ４．５算法提升比较明显。本文算法从分类规则入手，在多次训练的分类规则中，寻找特征的最优取值本，在数次的局部最优解中寻找最优的分类规则。虽然还是局限于局部最优解，但是尽可能的逼近最优解，体现了全局最优解的特点。

）刘鹏，姚正，尹俊杰．一种有效的９９６１００１（ｉｎＣｈｉｎｅｓｅ．［－　：Ｃ４．５改进模型［Ｊ］．清华大学学报，２００６，４６（Ｓ１）］９９６１００１．－

［］Ｋ，Ｓ６ｅｍａｌＰｏｌａｔａｌｉｈＧüｎｅｓ．Ａｎｏｖｅｌｈｂｒｉｄｉｎｔｅｌｌｉｅｎｔｍｅｔｈｏｄ　　　　　　ｙｇ

ｏｎＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅｃｌａｓｓｉｆｉｅｒａｎｄｏｎｅａａｉｎｓｔａｌｌａｂａｓｅｄ　　　　　　－－　－ｇｐ］ｒｏａｃｈｆｏｒｍｕｌｔｉｃｌａｓｓｃｌａｓｓｉｆｉｃａｔｉｏｎｒｏｂｌｅｍｓ［Ｊ．ＥｘｅｒｔＳｓ　　－　　　－ｐｐｐｙ，）：ｔｅｍｓｗｉｔｈＡｌｉｃａｔｉｏｎｓ２００９，３３（２１５８７１５９２．　　－ｐｐ

［］Ｈ，７ａｎＪｉｎｔｉＧｕＹｕｉａ．Ｓｔｕｄｏｎｈａｎｄｉｎｒａｎｉｎｕｔｓｍｅｔｈｏｄｓｏｎ　　　　　ｇｊｙｇｇｐ　　　

／Ｃ４．５ａｌｏｒｉｔｈｍ［Ｃ］／ＣｏｍｕｔｅｒＳｃｉｅｎｃｅｅｃｈｎｏｌｏａｎｄＡ　－Ｔ　－ｇｐｇｙｐ　，ｌｉｃａｔｉｏｎｓ２００９：４７４９．－ｐ

［］ＹＡＯ　８Ｙａｆｕ，ＸＩＮＧＬｉｕｔａｏ．ＩｍｒｏｖｅｍｅｎｔｏｆＣ４．５ｄｅｃｉｓｉｏｎｔｒｅｅ　　　　ｐ

ｃｏｎｔｉｎｕｏｕｓａｔｔｒｉｂｕｔｅｓｓｅｍｅｎｔａｔｉｏｎｔｈｒｅｓｈｏｌｄａｌｏｒｉｔｈｍａｎｄｉｔｓ　　　　　　ｇｇ］ａｌｉｃａｔｉｏｎ［Ｊ．ＪｏｕｒｎａｌｏｆＣｅｎｔｒａｌＳｏｕｔｈＵｎｉｖｅｒｓｉｔｏｆＴｅｃｈ　　　　　－ｐｐｙ　）：）姚亚夫，刑ｎｏｌｏ２０１１，４２（１２３７７２３７７６（ｉｎＣｈｉｎｅｓｅ．［－　ｇｙ，］留涛．决策树Ｃ４．５连续属性分割阈值算法改进及其应用［Ｊ．）：］中南大学学报，２０１１，４２（１２３７７２３７７６．－

４　结束语

本文是基于Ｃ４．５决策树在处理较大样本的不足、与训

（下转第４３３０页）

·４　３３０·

计算机工程与设计

２０１３年

（）万燕，刘伟．基于低质量图片的两级车牌字ｉｎＣｈｉｎｅｓｅ．［　］：符识别算法［Ｊ．计算机应用与软件，２０１２，２９（１１）２８１］２８４．－

［，ＧＡＯ１２］ＹＡＮＧＬｕｎｂｉａｏＹｉｎｉ．Ｐｒｉｎｃｉｌｅａｎｄａｌｉｃａｔｉｏｎｏｆ　　　　　ｇｙｐｐｐ

：ｆｕｚｚｍａｔｈｅｍａｔｉｃｓ［Ｍ］．ＧｕａｎｚｈｏｕＳｏｕｔｈＣｈｉｎａＵｎｉｖｅｒｓｉｔ　　ｙｇｙ　，２）杨纶标，ｏｆＴｅｃｈｎｏｌｏＰｒｅｓｓ００６：３９４０（ｉｎＣｈｉｎｅｓｅ．［　－　ｇｙ　高英仪．模糊数学原理及应用［Ｍ］．广州：华南理工大学出］版社，２００６：３９４０．－

［］ＱＵ，，，１３ＦｕｈｅｎＣＵＩＧｕａｎｃａｉＬＩＹａｎｆａｎｅｔａｌ．Ｆｕｚｚｃｌｕｓｔｅ　　　　－ｇｇｇｙ　

：Ｎｒｉｎａｌｏｒｉｔｈｍａｎｄｉｔｓａｌｉｃａｔｉｏｎ［Ｍ］．ＨｕｎａｎａｔｉｏｎａｌＤｅ　　　　－ｇｇｐｐ　

，２）曲福ｆｅｎｃｅＩｎｄｕｓｔｒＰｒｅｓｓ０１１：１４０１７６（ｉｎＣｈｉｎｅｓｅ．［　－　ｙ　恒，崔广才，李岩芳，等．模糊聚类算法及应用［Ｍ］．湖］南：国防工业出版社，２０１１，１４０１７６．－

［］Ｌ，Ｘ，，１４ＩＦａｎｆａｎＩＡＯＢｅｎｌｉｎＪＩＡ　Ｙｏｎｈｏｎｅｔａｌ．Ｉｍｒｏｖｅｄ　　　ｇｇｇｇｐ

ＳＩＦＴａｌｏｒｉｔｈｍａｎｄｉｔｓａｌｉｃａｔｉｏｎｉｎａｕｔｏｍａｔｉｃｒｅｉｓｔｒａｔｉｏｎｏｆ　　　　　　　　ｇｐｐｇｓｅｎｓｅｄｉｍａｅｒＪ］．ＧｅｏｍａｔｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎｒｅｍｏｔｅｌ－　　　ｇｙ［ｙ，）：１ＳｃｉｅｎｃｅｏｆＷｕｈａｎＵｎｉｖｅｒｓｉｔ２００９，３４（１０２４５１２４９（ｉｎ　　　－ｙ）李芳芳，肖本林，贾永红，等．ＳＣｈｉｎｅｓｅ．［ＩＦＴ算法优化］及其用于遥感影像自动配准［Ｊ．武汉大学学报信息科学版，）：１］２００９，３４（１０２４５１２４９．－

（上接第４３２５页）

［］Ｚ，ＹＡＮＧ　，９ＨＯＵＪｉａｎｆｅｎＡｉｍｉｎＬＩＵＪｉｃａｉ．Ｔｒａｆｆｉｃｃｌａｓｓｉｆｉｃａｔｉｏｎ　　　ｇ

］ａｒｏａｃｈｂａｓｅｄｏｎｉｍｒｏｖｅｄＣ４．５ａｌｏｒｉｔｈｍ［Ｊ．ＣｏｍｕｔｅｒＥｎｉ　　　　　－ｐｐｐｇｐｇ，，）：７）周ｎｅｅｒｉｎａｎｄＡｌｉｃａｔｉｏｎｓ２０１２４８（５１７４（ｉｎＣｈｉｎｅｓｅ．［　－　ｇｐｐ　剑锋，阳爱民，刘吉财．基于改进的Ｃ４．５算法的网络流量分类］，４）：７］算法［Ｊ．计算机工程与应用，２０１２８（５１７４．－

［］Ｙ，，，１０ＡＮＧＺｈｅＬＩＬｉｎｚｈｉＪＩＱｉｉｎｅｔａｌ．Ｎｅｔｗｏｒｋｔｒａｆｆｉｃｃｌａｓｓｉｆｉ　　　　　　－ｇｊｇ

］ｃａｔｉｏｎｕｓｉｎｄｅｃｉｓｉｏｎｔｒｅｅｂａｓｅｄｏｎｍｉｎｉｍｕｍｄｉｓｔａｎｃｅ［Ｊ．ａｒｔｉｔｉｏｎ　　　　　　　ｇｐ　，，）：９）ＪｏｕｒｎａｌｏｆＣｏｍｍｕｎｉｃａｔｉｏｎ２０１２３３（３０１０２（ｉｎＣｈｉｎｅｓｅ．　　－　［杨哲，李领治，纪其进，等．基于最短划分距离的网络流量］，３）：９］决策树分类方法［Ｊ．通信学报，２０１２３（３０１０２．－

本文来源：https://www.bwwdw.com/article/40ej.html