决策树C4.5算法的改进与分析

决策树C4.5算法的改进与分析

安葳鹏，尚家泽

河南理工大学计算机科学与技术学院，河南焦作454000

摘

要：C4.5算法在选择分裂属性时只考虑了每个条件属性和决策属性之间的关系，而没有考虑到条件属性间的相

关性，直接影响构建树的准确率。提出一种基于Kendall和谐系数的C4.5决策树优化算法，用于解决条件属性之间相关性的问题，提高算法属性选择的准确性。在引入系数的基础上运用等价无穷小原理对计算公式进行简化，提高了算法的效率。对改进后的C4.5算法和传统的算法进行仿真实验，结果表明，改进的C4.5算法在准确度和效率上都有较大提高。

关键词：C4.5算法；Kendall和谐系数；决策树文献标志码：A

中图分类号：TP391.4

doi：10.3778/j.issn.1002-8331.1805-0482

安葳鹏，尚家泽.决策树C4.5算法的改进与分析.计算机工程与应用，2019，55（12）：169-173.

ANWeipeng,SHANGJiaze.ImprovementandanalysisofC4.5decisiontreealgorithm.ComputerEngineeringandAppli-cations,2019,55（12）：169-173.

ImprovementandAnalysisofC4.5DecisionTreeAlgorithm

ANWeipeng,SHANGJiaze

CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo,Henan454000,China

Abstract：Whenchoosingsplittingattributes,C4.5algorithmonlytakestheattributerelationshipbetweeneveryprerequi-siteanddecisioninsteadofcorrelationamongconditionattributes,whichinfluencestheaccuracyoftheconstructiontreedirectly.Anoptimizedalgorithm,C4.5decisionmakingtree,basedonKendallharmonycoefficient,isproposedtosolvethecorrelationamongconditionattributesandimprovetheselectionaccuracyofalgorithmattribute.Theequivalentinfini-tesimalisusedtosimplifythecalculationformulaonthebasisofintroducingthecoefficient,whichimprovesefficiencyofthealgorithm.SimulationontheimprovedC4.5andthetraditionalalgorithmshowsthattheformeronehasmoreaccu-racyandefficiency.

Keywords：C4.5algorithm;Kendall’scoefficientofconcordance;decisiontree

1引言

树的算法。该算法是从ID3算法发展演变而来，但C4.5决策树[1]由于其高效性、误差小的优点，在分类问题

算法的缺点有：（1）在构造树的过程中，需要对算法进行中得到了很广泛的应用。决策树是一个贪心算法，即在递归调用，因而增加算法的复杂度；（2）对连续性的数值特性空间上执行递归的二元分割。在决策树中，内部分处理效率低；（3）算法在选择分裂属性时没有考虑到条支节点[2]表示一个条件属性，而叶子节点表示一种决策件属性间的相关性，只考虑条件属性和决策属性之间的属性或分类结果，算法通常是根据计算熵的大小递归选关系，会降低构建树的准确率。

择树的分支节点，根据分支节点的情况对训练数据进行针对C4.5算法的上述缺点，诸多研究人员对其进划分，凭借其简单，高效性可以对大型数据进行有效的行了改进，文献[4]将皮尔森相关系数引入决策树算法处理。就目前而言，最为流行的就是C4.5算法。

中，可以准确地选择决策树的分割属性和分裂点，但未C4.5[3]算法是由J.RossQuinlan开发并且用于决策

能考虑条件属性之间的关系。文献[5]在C4.5算法中引

基金项目：河南省教育厅应用研究计划（No.16A520052）。

作者简介：安葳鹏（1969—），男，教授，研究领域为计算机测控技术，虚拟现实技术；尚家泽（1994—），男，硕士，研究领域为数据挖

掘，大数据，E-mail：971945362@qq.com。

收稿日期：2018-05-30

修回日期：2018-07-20

文章编号：1002-8331（2019）12-0169-05

CNKI网络出版：2018-10-29,http://kns.cnki.net/kcms/detail/11.2127.TP.20181025.1716.033.html

1702019，55（12）ComputerEngineeringandApplications计算机工程与应用

入了一个不精确的概率，对决策树进行剪枝操作，可以步骤2，得到子树Ti，返回Ti。

在较复杂的训练数据集中得到较小的决策树，但在较大2.2肯德尔和谐系数

的数据集中准确率就下降了。文献[6]将特征选择的方肯德尔和谐系数[15]可以对多个等级变量之间进行

法引入到C4.5算法中，可以对不完整的训练数据集进比较，计算它们之间的相关程度。设T为类标记数据行有效的分类，但算法复杂度较高，影响决策树生成效集，由N个条件属性X和K个决策属性Y组成，设率。文献[7-9]都对决策树算法引入了相关系数，提高了Bk(k=1,2,⋯,N)为属性X的值，则Ri(i=1,2,⋯,K)表

决策树分类的准确率，但都未考虑到条件属性之间的关示每一行Bk的和。

联。文献[10-11]通过优化算法公式中的对数运算，极大若每个条件属性Ci中的值都不同，则肯德尔和谐地提高了算法的执行效率。

系数计算公式为：

本文提出了一种改进的C4.5算法，利用Kendall（肯德尔）和谐系数对算法进行优化。斯皮尔曼系数讨论的K

(是两个等级变量的相关程度，而肯德尔和谐系数是计算R2∑K

R=1i)2

i多个等级变量之间的相关程度。改进后的算法在一定W=

∑=1

i-iN（6）

程度上解决了条件属性之间相关性的问题，提高了算法121K2(N3-N)的准确率。同时对计算信息增益率的公式进行化简，消若每个条件属性中有m组Ci相同的值，其中每组

除对数的复杂运算，整个计算效率明显得到提高。

相同值的个数为n，则计算公式为：

K

(R2∑K

Ri)2

2C4.5算法和肯德尔和谐系数

i=12.11

i-NC4.5算法

W=

∑i=（7）

C4.5算法[12]在计算信息熵的基础上增加了信息增121K2(N3-N)-K∑NT

i=1

i

益率，用信息增益率作为选择条件属性的依据，极大提其中：

高了决策树构建的准确率。

C4.5算法主要过程可以分为以下几个步骤：Tm

i=∑n3i

-ni

（8）

i=1

12步骤1设训练数据集为D，数据集容量为N，设

肯德尔和谐系数的取值范围在-1~1之间，当W=1有K个类别依次为Bk,k=1,2,⋯,K。设|Bk|为属于

时，表示等级变量之间拥有一致的相关性，当W=-1类Bk的样本个数。设A有n个不同的值：

{a1,a2,⋯,an},时，表示等级变量之间拥有完全相反的相关性，当W=0若A是连续型的则需要进行离散化[13]处理，根据特征A时，表示等级变量之间是相互独立的。

的取值将数据集D划分为n个子集：D1,D2,⋯,Dn，Ni2.3等级数评定法

为对应的Di中的样本个数。设集合Di中属于类ck的在数据集中，有些数据是离散的、非数字化数据，会

样本集合为Dik，其容量为Nik。主要计算：

造成肯德尔和谐系数计算的不便，因此要对这些非数字数据集D的信息熵：化的数据用等级数评定法[4]对其进行数字化处理。

H(D)=-∑

K

|Bk|lb|Bk=Nk|N（1）

设数据集为S，根据特征A取值将数据集S划分1为n个子集S1,S2,⋯,Sn,Ni为对应Si的样本个数。假特征A对于数据集D条件信息熵：

设决策属性中有K个类别依次为Ck,k=1,2,⋯,K,集

H(D/A)=-∑n

N

i×H(Dik)

（2）

合Si中属于类CK的样本集合为Sik，样本个数为i=1NNik。首先设定Ck中的等级数，例如，设定C1的等级

属性A的信息增益：数最高，等级数为1。设定k=2,n=3，统计Di中属于

Gain(D,A)=H(D)-H(D/A)

（3）

类C1的样本集合个数为Ni1，得到概率分布为：P1=

属性A对训练集D分裂信息：

N11

，同理得到PH(D)=-∑n

（4）

N11+N12+N132、P3。等级数评定分为以

ANN

i=1

NilbNi

下几种情况：

属性A对训练集D的信息增益比[14]：

（1）若P1>P2>P3，则取得D1、

D2、D3的等级数为GainRatio(D,A)=

Gain(D,A)

HA(D)（5）

1、2、3。

（2）若P1=P2>P3，则取得D1、D2、D3的等级数为步骤2根据信息增益比，将数据集D划分为若干1.5、1.5、3（1.5为1和2的平均数）。

个非空子集，构建子节点，由子节点构成树T，返回T。

（3）若P1>P2=P3，则取得D1、

D2、D3的等级数为步骤3对于树中新节点的产生，递归调用步骤1、

1、2.5、2.5（2.5为2和3的平均数）。

安葳鹏，等：决策树C4.5算法的改进与分析2019，55（12）

171

3C4.5算法的优化表1

训练样本数据表

3.1算法优化过程

No.OutlookTemperature

HumidityWindyPlay在C4.5算法中引入肯德尔和谐系数(W)，并对公式1sunnyhothighfalseno进行简化，基本过程如下：

2sunnyhothightrueno（1）根据等级数评定法对各个属性进行等级划分。3overcasthotnormalfalseyes4rainymildnormalfalseyes（2）依照划分后的结果，运用公式（7）或（8）计算出5rainycoolnormalfalseyes相关系数W。

6rainycoolnormaltrueno（3）在公式（3）的基础上引入系数W，公式如下：7overcastcoolnormaltrueyesGain(D,A)=H(D)-H(D/A)×W

（9）

8sunnymildhighfalsenoln9sunnycoolnormalfalseyes（4）根据数学中的换底公式[16]

lbx=lnx2和等价无

10rainymildnormalfalseyes穷小原理ln(1+x)≈x，对涉及对数的公式（1）、（2）、（4）11sunnymildnormaltrueyes进行简化的结果如式（10）~（12），最后得到的结果为12overcastmildhightrueyes式（13）。

13overcasthotnormalfalseyes14

rainy

mild

normal

true

no

H(D)=-∑K

|Bk||Bk|K

|Bk|ln|BNk|（1）计算肯德尔和谐系数

k=1NlbN=-∑k=1

Nln2=

首先按照等级数评定法，对各个属性进行评定。假

K|BN1k|×(N-|Bln2∑k|)（10）

设决策属性Play中yes的等级高于no，可以得出Outlook

k=1N中三个属性值的概率分别为：P(sunny)=2,P(overcast)=

H(D/A)=-∑

nN49i=1

Ni

×H(Dik)=9,P(rainy)=39。可以看出P(overcast)>P(rainy)>P(sunny),同理可以得出属性Temperature中P(mild)>P(cool)>-W×∑nNi×(-K

ln

Dik

P(hot)，在属性Humidity中P(normal)>P(high)，属性

i=1N∑Dik×Ni

)=

K=1Niln2P(false)。等级评定的结果如表2所示。

W×n

K

DWindy中P(ture)>N1ln2∑ik×(Ni-Dik)

（11）

i=1∑k=1Ni

表2

对应等级数据表

OutlookHumidityWindyPlayHn

n

ln

Temperature

12.012.512.54.5A(D)=-∑NNi

ilbNi=NN12.0i=1NN-∑i×=

i=1

Nln212.012.512.511.512.01n

N2.512.55.54.55.0Nln2∑i×(N-Ni)i=1N（12）

7.03.55.54.55.07.08.55.54.55.0GainRatio(D,A)=Gain(D,A)H(D)-H(D/A)

H7.08.55.511.512.0A(D)=HA(D)=

∑K

B2.58.55.511.55.0k×(n12.03.512.54.512.0k=1NN-Bk)-W×∑i=1∑KDik×(Nk=1

Ni-Dik)

i

12.08.55.54.55.0∑nNi×(N-Ni)（13）7.03.55.54.55.0i=1

N12.03.55.511.55.03.2算法优化实现

2.53.512.511.55.0以一组天气信息数据为例，详细介绍改进后C4.5

2.512.55.54.55.0算法优化的实现过程。这里从文献[9]中抽取条件属性7.0

3.5

5.5

11.5

12.0

为：Outlook（天气）、Temperature（温度）、Humidity（湿根据表2的数据运用式（7）和式（8）可计算出系数度）、Windy（风强度）、决策属性为：Play（出行）的信息得W，

首先计算出每行条件属性值的和分别为R1=12+到表1的训练样本数据表。

12.5+12.5+4.5=41.5，同理可得其他各行的值分别为从表1可以看到，Outlook中有三个属性值：sunny、R2=48.5，R3=25，R4=20.5，R5=25.5，R6=32.5，overcast、rainy，Temperature中有三个属性值：hot、mild、R7=28，R8=32.5，R9=30.5，R10=20.5，R11=32.5，cool，Humidity中有两个属性值：high、normal，Windy中R12=30，R13=25，R14=27.5。

有两个属性值：true、false，Play中有两个属性值：yes、no。根据式（8）可得：

根据表中的属性值，首先计算出系数W，再根据式（13）计算出每个属性的增益比，根据增益比构造决策树。

Tm

1=∑n3i

=53-5+43-4+53-5=10+5+10=25

i=1

121212121722019，55（12）ComputerEngineeringandApplications计算机工程与应用

表3

Gas数据集

序号放散初速度

坚固性系数

瓦斯压力/MPa

煤体破坏类型

开采深度/10m

是否突出16.000.240.953.004.55Yes214.000.342.164.005.10Yes34.001.401.403.004.28No46.000.421.403.004.26Yes54.000.512.905.004.42Yes614.000.243.953.005.52Yes74.000.531.652.004.38No86.000.543.955.005.43Yes97.400.370.754.007.40Yes103.000.511.403.004.00No1119.000.312.763.006.20Yes…

…

…

…

…

…

…

同理可得T2=27.5，T3=87.5，T4=59.5，则：

如表3，决策属性中只有两种类型分别为Yes和No。分K

Ri)2

别用K_C4.5（改进后的C4.5）算法、文献[7]算法、文献[8]K

(2∑i-i=1

N算法以及原始C4.5算法对该数据集进行分类。最终实

W=

∑Ri=1

1=

验结果的准确率的对比如图1所示。

12K2(N3-N)-K∑NT

i

1.0i=1

(41.52

+48.52

+…+27.52

)-(41.5+48.5+...+27.5)2

0.8率12114×42×(143-14)-4×(25+27.5+87.5+59.5)=0.265

确0.6准（2）计算信息增益率

法算0.4K_C4.5算法通过式（10）计算各个属性的信息增益率如下，其中：文献[7]算法∑K

Ck×(N0.2文献[8]算法N-Ck)=9×(14-9)+5×(14-5)

1414=6.269C4.5算法k=1

0

W×∑n

∑K

Ck×(Ni-Ck)

=0.265×

100

2003004005006007008009001000

样本个数

i=1k=1

Ni

图1四种算法准确率对比图

(2×(5-2)3×(5-5+3)5+3×(5-3)5+2×(5-2)5)=1.272

从图1可知，通过增加样本数对四种算法的准确率∑n

Ni×(N-N)5×(14-5)进行比较，当样本数偏少时四种算法的准确率基本相i=1Ni=14+同，但是当随着样本数的增加可以看出改进后K_C4.54×(14-4)5×(14-5)

14+14=9.286

算法的准确率明显高于其他三种算法。

4.2实验二

Gain(Outlook)=6.4299.286-1.272=0.555

为了进一步验证改进后算法的高效性，实验选取

同理，可计算出其他几个属性的增益率为：UCI中Labor、University、Student、Seed、Adult的数据集，Gain(Temperature)=0.524分别用K_C4.5算法、文献[7]算法、文献[8]算法、原C4.5Gain(Humidity)=0.907算法计算进行对比实验，准确率的对比如图2所示，建Gain(Windy)=0.706

模速率对比如图3所示。

根据Gain(Humidity)>Gain(windy)>Gain(Outlook)>从图2和图3看出，在不同大小的数据集中，在准确Gain(Temperature)，应该选择Humidity为根属性。经

率方面，改进后的算法K_C4.5比其他三种算法有所提过分析可得，与原C4.5算法相比，分类结果更准确，从高。在分类的速率方面，K_C4.5算法和文献[8]算法建模时间基本一致，但两种算法和文献[7]、C4.5算法相比一定程度上解决了属性之间相关性的问题。

建模时间有较大的提高。因此改进后的算法更具有高效性。

4实验及结果分析4.1实验一

5结束语

数据集Gas中有1031个样本数据，部分数据显示

本文引用肯德尔和谐系数的相关概念，提出了基于

安葳鹏，等：决策树C4.5算法的改进与分析

2019，55（12）173

1.0[3]HssinaB，MerbouhaA，EzzikouriH，etal.Acomparative

0.8studyofdecisiontreeID3andC4.5[J].InternationalJour-nalofAdvancedComputerScience&Applications，2014（2）.率确0.6[4]MuY，LiuX，WangL.Apearson’scorrelationcoefficient

准法baseddecisiontreeanditsparallelimplementation[J].Infor-算0.4K_C4.5算法mationSciences，2018，435：40-58.

文献[7]算法0.2文献[8]算法[5]MantasCJ，AbellánJ.Credal-C4.5：decisiontreebased

C4.5算法onimpreciseprobabilitiestoclassifynoisydata[J].Expert0

LaborUniversityStudent

Seed

Adult

SystemswithApplications，2014，41（10）：4625-4637.样本名称

[6]NgocPV，NgocCVT，NgocTVT，etal.AC4.5algo-图2

四种算法准确率对比

rithmforenglishemotionalclassification[J].EvolvingSys-1.4tems，2017（2）：1-27.

1.2[7]CaoTT，ZhangM，AndreaeP，etal.Improvingperfor-manceforclassificationwithincompletedatausingwrapper-s/1.0间basedfeatureselection[J].EvolutionaryIntelligence，2016，时模0.89（3）：1-14.

建法0.6[8]董跃华，刘力.基于相关系数的决策树优化算法[J].计算机

算0.4K_C4.5算法工程与科学，2015，37（9）：1783-1793.

0.2文献[7]算法文献[8]算法[9]吴思博，陈志刚，黄瑞.基于相关系数的ID3优化算法[J].

0

C4.5算法计算机工程与科学，2016，38（11）：2342-2347

LaborUniversityStudentSeed

Adult

样本数据集

[10]王文霞.数据挖掘中改进的C4.5决策树分类算法[J].吉林

图3四种算法建模速率对比

大学学报（理学版），2017，55（5）：1274-1277.

肯德尔相关系数的决策树C4.5优化算法。肯德尔和谐[11]陈英，马仲兵，黄敏.优化的C4.5决策树算法[J].软件，

2013，34（2）：61-64.

系数能准确地反映条件属性之间相关性的问题，并且对[12]LinSW，ChenSC.Parameterdeterminationandfea-算法公式进行简化，在一定程度上提高了算法的准确率tureselectionforC4.5algorithmusingscattersearch和执行效率。实验结果分析表明，优化后的算法分类更approach[J].SoftComputing，2012，16（1）：63-75.高效，准确率更高。

[13]姚亚夫，邢留涛.决策树C4.5连续属性分割阈值算法改

进及其应用[J].中南大学学报（自然科学版），2011，42（12）：参考文献：

3772-3776.

[1]RamageriBM.Dataminingtechniquesandapplications[J].

[14]李孝伟，陈福才，李邵梅.基于分类规则的C4.5决策树改

IndianJournalofComputerScience&Engineering，2010，进算法[J].计算机工程与设计，2013，34（12）：4321-4325.1（4）：25-47.

[15]刘艳锋.肯德尔和谐系数的实际运用[J].河南机电高等专

[2]JiangL，LiC.Scalinguptheaccuracyofdecision-tree

科学校学报，2006，14（1）：41-42.

classifiers：aNaive-Bayescombination[J].JournalofCom-[16]同济大学数学系.高等数学.上册[M].上海：同济大学出

puters，2011，6（7）：1325-1331.

版社，2014.