基于分类规则的C4-5决策树改进算法-李孝伟

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

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

计算机工程与设计

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

Ｄｅｃ．２０１３

Ｖｏｌ．３４Ｎｏ．１２

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

李孝伟，陈福才，李邵梅

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

４３２２

计算机工程与设计

２０１３年

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

４］

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

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

５］

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

图１简单的决策树模型

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

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

ｍ

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

［］

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

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

［］

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

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

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

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

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

ｉ＝１

ｍ

）（１

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

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

ｒ

Ｔ′）＝ＨＡ（

＝

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

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

ｉ＝１ｒ

ｔ′）Ｈ（ｔ′）∑ｐ（

ｉ

ｉｍ

ｉ

ｊ

ｉ

２

ｉ＝１

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

ｊ

ｉ

ｊ＝１

ｒ

ｍ

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

ｉ＝１ｊ＝１

Ｔ｜Ｔ′）＝Ｈ（

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

ｉ＝１ｒ

）（２

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

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

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

属性Ａ的分割信息熵为

ｒ

）（３

１Ｃ４．５决策树介绍

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

。

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

ｉ＝１

）（４

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

＝

（））（

Ｈ（Ｔ′）

（）５

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

第３４卷第１２期

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

４３２３

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

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

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

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

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

Ｒａｔｉｏ（Ｔ′）＝

＝

（））（

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

ＨＴ′（）１０

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

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

ｑ

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

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

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

ｑ

ｉ＝１ｑ

ｏｇｙ∑ｐｌ

ｉ

ｉ

≤

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

ｉ＝１

ｉ＝１

ｑ

ｑ

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

ｉ＝１

ｉ＝１

ｑ

近似代替

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

ｍ

ｒ

ｉ＝１

ｏｇｙ∑ｐｌ

ｉ

ｉ

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

（））（

ｄ（Ｔ′，Ｔ）＝

Ｈ（Ｔ′，Ｔ）

ｍ

２

ｒ

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

≈－

ＨＴ′Ｔｍ

２

ｒ

２

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

（，）ｄＴ′Ｔ≈－

ＨＴ′Ｔ（）１１

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

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

ｊ＝１ｉ＝１

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

ｍ

ｒ

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

）（７

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

具体步骤如下：

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

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

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

ｊ＝１ｉ＝１

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

（））（

Ｄ（Ｔ′，Ｔ）＝

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

（）８

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

（，）），））（（（

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

＝２－

令

（））（

ＨＴ′Ｔ（））（

ｄ（Ｔ′，Ｔ）＝

ＨＴ′Ｔ（）９

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

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

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

４３２４

计算机工程与设计

２０１３年

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

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

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

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

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

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

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

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

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

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

特征８１１１７１４８

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

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

３．２实验结果及分析

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

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

。

ｉｍＮ）＝ｐ（

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

ｉ

ｊ

ｉｊ≠

ｊ

２

）（１２ｗｊ）（

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

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

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

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

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

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

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

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

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

３实验及分析

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

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

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

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

第３４卷第１２期

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

４３２５

表２不同数据集抽样次数

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

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

抽样次数

８８１０１２２

０

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

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

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

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

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

４结束语

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

（下转第４３３０页）

４３３０

计算机工程与设计

２０１３年

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

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

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

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

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