决策树分类算法中C4.5算法的研究与改进

Computer Systems & Applications,2019,28(6):198−202 [doi: 10.15888/j.cnki.csa.006954]©中国科学院软件研究所版权所有.

E-mail: csa@iscas.ac.cnhttp://www.c-s-a.org.cnTel: +86-10-62661041

决策树分类算法中C4.5算法的研究与改进①

韩存鸽1,2,  叶球孙1

(武夷学院 数学与计算机学院, 武夷山 354300)

(认知计算与智能信息处理福建省高校重点实验室, 武夷山 354300)通讯作者: 韩存鸽, E-mail: gezi0401@163.com

21

摘　要: C4.5算法是用于生成决策树的一种经典算法, 虽然其有很强的噪声处理能力, 但当属性值缺失率高时, 分类准确率会明显下降, 而且该算法在构建决策树时, 需要多次扫描、排序数据集、以及频繁调用对数, 针对以上缺点, 本文提出一种改进的分类算法. 采用一种基于朴素贝叶斯定理方法, 来处理空缺属性值, 提高分类准确率. 通过优化精简计算公式, 在计算过程中, 改进后的计算公式使用四则混合运算代替原来的对数运算, 减少构建决策树的运行时间. 为了验证该算法的性能, 通过对UCI数据库中5个数据集进行实验, 实验结果表明, 改进后的算法极大的提高了运行效率.

关键词: 决策树; C4.5算法; 朴素贝叶斯分类; UCI

引用格式:  韩存鸽,叶球孙.决策树分类算法中C4.5算法的研究与改进.计算机系统应用,2019,28(6):198–202. http://www.c-s-a.org.cn/1003-3254/6954.html

Research and Improvement of C4.5 Algorithm in Decision Tree Classification Algorithm

HAN Cun-Ge1,2, YE Qiu-Sun1

12

(School of Mathematics and Computer Science, Wuyi University, Wuyishan 354300, China)

(Fujian Provincial Key Laboratory of Cognitive Computing and Intelligent Information Processing, Wuyishan 354300, China)

Abstract: C4.5 algorithm is a classical algorithm used to generate decision tree. Although it has strong noise processingability, the classification accuracy of C4.5 algorithm decreases obviously when the missing rate of attribute value is high,and the algorithm needs to scan many times when constructing decision tree. This paper presents an improvedclassification algorithm for sorting data sets and calling logarithms frequently. A method based on naive Bayesiantheorem is used to deal with the vacant attribute value and improve the classification accuracy. By optimizing andreducing the calculation formula, the improved formula uses four mixed operations to replace the original logarithmicoperation, thus reducing the running time of constructing the decision tree. In order to verify the performance of thealgorithm, five data sets in UCI database are tested. The experimental results show that the improved algorithm greatlyimproves the running efficiency.

Key words: decision tree; C4.5 algorithm; Naive Bayesian classifier; UCI 

决策树分类算法是分类挖掘算法中较为常用的算法, 是一种自顶向下的递归算法, 常用于分类器和预测模型. 1966年Hunt等人开发研制的CLS[1]系统, 为许

① 基金项目: 福建省科技厅自然科学基金(2017J01406)

Foundation item: Natural Science Foundation of Science and Technology Bureau, Fujian Province (2017J01406)收稿时间: 2018-12-23; 修改时间: 2019-01-18; 采用时间: 2019-01-22; csa在线出版时间: 2019-05-25

多决策树算法奠定了基础. 1979 年Quinlan 提出ID3[2]算法, 其核心思想以最大的信息增益属性作为分裂属性. 之后的许多决策树算法都是在ID3算法的基

198 软件技术•算法 Software Technique•Algorithm

2019 年 第 28 卷 第 6 期

http://www.c-s-a.org.cn

计算机系统应用

础上衍生改进的. 其中C4.5[3] 算法就是在 ID3 算法的基础上发展的, 采用信息增益率作为属性选择的度量依据, 在处理连续性属性的时, C4.5算法将这些连续属性“离散化”, 解决了ID3算法多值偏向性的缺点, 有效避免了取值较多的属性容易被选作分裂属性的趋势,增强了决策树模型的有效性. 但是当测试集属性值缺失率高时, C4.5算法的分类准确率会明显下降, 而且在构造树的过程中, 该算法需要多次对数据集进行顺序扫描及排序, 在进行计算时又频繁地调用对数, 增加了算法的时间开销, 从而导致算法低效[4].

文献[5]调整了连续阈值惩罚项, 但是并没有解决决策树过度拟合问题. 文献[6]提出双重熵平均决策树算法,采用熵值拟合的方法, 提高算法运行速度, 但是没有解决空缺属性问题. 文献[7]在连续属性离散化方面进行了改进, 但并没有很好的解决过度拟合问题. 文献[8]适用范围为变精度粗糙集, 不适合一般数据分析.

本文在研究C4.5 算法的基础上提出一种优化算法, 通过对UCI数据库中 5个数据集进行实验, 实验结果表明, 改进后的算法极大的提高了运行效率.

1   C4.5算法理论

C4.5算法是在ID3的基础上加进了对连续型属性、属性值空缺情况的处理, 通过生成树和树剪枝两个阶段来建立决策树. C4.5算法通过计算每个属性的信息增益率(information GainRatio), 最后选出具有最高信息增益率的属性给定集合S的测试属性, 再根据测试属性值建立分支, 采用递归算法, 得到初步决策树.C4.5算法的相关计算公式如下[9]:

(1)期望信息(也称信息熵) 设S是Si个数据样本的集合, 假定类标号属性有m个不同值, 定义m个不同类Ti (i=1, …, m). 设Si是类Ti中的样本数. 对一个给定的样本分类所需的期望值为:

Info(S)=∑m−siSii=1slog2S(1)(2)信息增益 由属性A划分成子集的信息量为:

E(A)=Info∑vA(S)=SiSij)(2)j=1SInfo(信息增益为原来的信息需求与新的需求之间的差.

即Gain(A)=Info(S)−E(A)(3)(3)信息增益率C4.5算法中引入了信息增益率,属性A的信息增益率的计算公式为:

GainRatio(A)=Gain(A)SplitE(A)(4)SpliE(A)=−∑k|Si|log2|Si|i=1|S||S|(5)C4.5算法采用后剪枝技术对生成的决策树进行剪枝操作, 形成决策树模型, 根据建立好的模型, 生成一系列IF-THEN 规则, 实现对训练集的分类.

2   改进的C4.5算法

2.1 决策分类过程中空缺属性值处理研究

(1) 延伸贝叶斯分类算法

决策树进行分类时, 测试样本数据中可能存在缺失某些属性值. 传统的决策树算法在处理缺失属性值时, 一般采用抛弃缺失属性值的样本, 或重新赋予训练样本该属性的常见值[10]. C4.5算法采用概率分布的填充法来处理缺失属性值, 具体执行过程: 首先为某个未知属性的每个可能值赋予一个概率, 根据某节点上属性不同值的出现频率, 这些概率可以再次估计[11]. 虽然C4.5算法有很强的处理噪声数据的能力, 但当训练集合属性值的缺失率很高时, 使用该算法构建的决策树模型的结点数更多, 模型更为复杂, 而且分类准确率也会下降[12]. 鉴于朴素贝叶斯分类具有坚实的理论基础、较小的出错率. 本文提出一种基于朴素贝叶斯定理方法[13], 来处理空缺属性值.

假设数据样本为n维向量空间, V={V1, V2, V3, …,Vi} 若该数据样本有C1, C2, C3, …, Cm个类别属性取值, 那么基本贝叶斯将未知类别的样本V归到类别Ci,当且仅当:

p(ci)p(v|ci)p(cj)p(v|cp(v)>j)p(v)等价p(ci)p(v|ci)>p(cj)p(v|cj).

若V的m个属性互相独立, 那么

p(v|ci)=∏np(vk|ci)k=1继而推出:

∏np(ci)p(vk|ci)>p(c∏nj)p(vk|cj)k=1k=1所以, 

si∏nsp(vsj∏nsk=1k|ci)>i

sp(vk=1k|cj)(因为p(ci)=s).故将未知类别的样本X归到类别Ci,当且仅当

Software Technique•Algorithm 软件技术•算法 199

计算机系统应用

http://www.c-s-a.org.cn

2019 年 第 28 卷 第 6 期

si∏nsp(vsj∏nk|ci)>sp(vk|cj),1<=j<=m且j󰀁ik=1k=1根据上述原理可以实现对多维空缺属性的处理:

si′∏nsp(v′′s′j∏nk|c′i)>sp(v′′k|c′j)k=1k=11<=j<=m且j󰀁i(2) 空缺属性值处理过程

本文采用上述算法处理空缺属性, 大致流程如下:① 读入测试数据.

② 若数据集中没有空缺属性值, 则把数据压入Di集合; 如果测试数据集中含有空缺属性值, 采用“样本空缺属性个数排序, 越少越排前, 反之则排后. ”的原则插入到D2集合.

③ 返回第一步, 直到测试数据集中所有数据都检测结束. 最后形成Di、D2两个集合. 其中Di中存放没有空缺属性值, D2中存放包含空缺属性的信息.

④ 取出D2中的记录数据, 为缺失属性赋值计入Di.⑤ 递归调用上述第④步, 直到D2中记录为0.2.2 改进思想及改进计算方式

虽然C4.5算法具有建模速度快、准确率高、易于理解、灵活简单等优点, 但是该算法在构造树的过程中, 需要多次对数据集进行顺序扫描及排序,在进行计算时又频繁地调用对数, 增加了算法的时间开销, 从而导致算法低效. 针对以上缺点, 本文对C4.5算法的计算公式进行精简优化, 从减小计算时间上提出一种改进算法命名为N-C4.5算法. 公式简化如下:

假设S是n维有穷离散数据集, S中只有正反两种情形, 分别表示为YS 、NS, 其中正例YS的记录数为m, 反例NS的记录数为n, 根据式(1)数据集S分类所需的期望值为:

Info(S)=−mm+nlogmm+n−nm+nlogmn+n22假设决策树的根为A属性, A属性的取值为{A1,A2, …, Ai}, 利用属性A将数据集S分为{S1,S2, …,Si}个子集, 其中Si为S中属性A取Ai值的样本实例数据, 那么由属性A划分成子集的信息量为

mininiI(Smi)=−imi+nilogmi+nimi+n2−mi+nilogi2在数据集D中计算属性X的信息熵公式为

200 软件技术•算法 Software Technique•Algorithm

Info)=∑vmA(Si+nii=1m+nI(Si)=1∑vmin(m+n)ln2−miln−nilnii=1mi+nimi+niInfoA(S)=∑vmi+nii=1m+nI(Si)=1∑v(m+n)ln2(−mmilninimi+ni−nilnmi+ni)i=1InfoA(S)=∑v(−mmilninii=1mi+ni−nilnmi+ni)(由于

1

(m+n)ln2

为常数, 故可以简化).

根据无穷小原理ln(1+x)≈x, 那么:

lnmimi+ni=ln(1−nimi+ni)=−nimi+ni同理,lnni

mimi+ni==−mi+ni.

v()Info∑mA(S)=−milninii=1mi+ni−nilnmi+ni=∑v(minimini)∑v2minii=1mi+ni+mi+ni=i=1mi+niInfo)=∑vminA(Sii=1mi+ni(常数2省略)信息增益: Gain(A)=Info(S)−InfoA(S).

nmSplitE(A)=−nimii+nimimiimi+nilog2−mi+nilog+ni2=∑v2miniln2(mi+ni)2i=1SplitE(∑vA)=mini((m因为2)i=1i+ni)2ln2为常数可简化信息增益率: GainRatio(A)=

Info(S)−InfoA(S)

SplitE(A)

.改进后的计算公式使用四则混合运算代替原来的

对数运算, 可以使计算效率得到提升. 原C4.5算法的时间复杂度为O(n2logn2), 改进后的算法时间复杂度为O(n2), 新算法去掉了对数运算, 优化了时间复杂度.2.3 N-C4.5算法实际应用

为了验证算法正确性, 这里以顾客购买计算机的样本信息S为例, 具体样本记录如表1所示. 使用改进

2019 年 第 28 卷 第 6 期

http://www.c-s-a.org.cn

计算机系统应用

后的算法构建决策树, 命名为N-C4.5算法. 该数据集S有age、income、student、credit_rating、buy 5个属性, 其中buy为类标号属性, 有两个取值{yes,no}, S数据集的前4个属性为分裂属性, 并且每个属性都是离散化的. 这里根据每个人的age、income、student、credit_rating  

来进行分类, 判断顾客是否购买计算机.

表1     顾客购买计算机的样本信息S

RIDageincomestudentcredit_rating

buy1youthhighnobadno2youthhighnogoodno3middlehighnobadyes4seniormediumnobadyes5seniorlowyesbadyes6seniorlowyesgoodno7middlelowyesgoodyes8youthmediumnobadno9youthlowyesbadyes10seniormediumyesbadyes11youthmediumyesgoodyes12middlemediumnogoodyes13middlehighyesbadyes14

senior

medium

no

good

no

对客户购买计算机的样本信息按照改进以后的算法构建决策树, 利用改进后的公式计算信息熵、信息增益、分裂信息量、以及信息增益率, 同时选择最大信息增益率作为分裂结点, 采用递归算法构建决策树.在数据集S中属于类别“yes”的有9个, 属于类别“no”的有5个, 根据改进后的公式计算过程分如下五步.

Step1. 计算分类所需的期望信息

Info(S)=mn9×5(m+n)2=(9+5)2=0.230Step2. 计算每个属性的信息熵

Info(age)=2×32+3+4×04+0+3×23+2=2.4Info(income)=3.083Info(student)=2.571Info(credit_rating)=3.0Step3. 计算每个属性的信息增益

Gain(age)=Info(S)−Info(age)=0.230−2.4=−2.170Gain(income)=0.230−3.083=−2.783Gain(student)=0.230−2.571=−2.341Gain(credit_rating)=0.230−3.0=−2.8Step4. 计算每个属性的分裂信息度量

SplitE(age)=5×4×5(5+4+5)2=0.510SplitE(income)=0.490SplitE(student)=0.250SplitE(credit_rating)=0.245Step5. 信息增益率

GainRatio(age)=−2.1700.510=−4.255GainRatio(income)=−5.680GainRatio(student)=−9.346GainRatio(credit_rating)=−11.430由计算结果可知, age 属性的信息增益率最大, 所以选择age 作为分裂属性, 将原数据集分为youth、middle、senior三个子集, 采用递归算法计算每个属性的信息熵、信息增益、分裂信息量、信息增益率, 对于youth子集, 经计算得出student信息增益率最大, 选择student作为测试属性; 对于middle子集全部归为yes 类, 所以不需要进行分类; 而对于senior子集, 通过计算得知, credit_rating信息增益率最大, 因此选择credit_rating作为测试属性, 根据所有结点, 可以得出

购买计算机数据集采用N-C4.5算法构造的决策树如图1.

ageyouthmiddle seniorstudentyescreditnoyesbadgoodnoyesyesno 图1    N-C4.5算法构造的决策树

由图1可以看出采用N-C4.5算法构造的决策树与使用原C4.5算法得到的决策树结构完全相同, 但C4.5算在计算的过程中调用了大量的对数, 而N-C4.5算法却只需要采用简单的混合运算即可, 因此运算效率大幅度提高.

3   实验结果比较分析

为了验证N-C4.5算法的性能, 本实验选择UCI数据库中 5个数据集进行仿真实验, 实验数据的基本信息见表2 , 实验硬件配置: 内存 4 GB, CPU 2.50 GHz ,使用Window7 操作系统, 采用Java 语言在WEKA 平

Software Technique•Algorithm 软件技术•算法 201

计算机系统应用

http://www.c-s-a.org.cn

2019 年 第 28 卷 第 6 期

台中进行仿真实验. 仿真实验时, 首先利用延伸的贝叶斯分类算法填充多维空缺属性, 该方法会生成空缺属性的各种可能取值组合, 接着遍历各种组合, 按公式计算值并记录最大值即可; 然后利用改进后的公式计算信息熵、信息增益、分裂信息量、以及信息增益率,最后选择最大信息增益率作为分裂结点, 采用递归算法构建决策树.

表2     测试数据集基本信息

DatasetExampleMissingFeatruesclassesIris150Sepalwidth(30)43Glass214Silicon(45)106Vote435Crime(50)162Diagnostic569Area(45)322Breast

699

Ino-nodes(75)

9

2

Iris数据集是构建决策树挖掘中最典型的一组数据, 共有150条记录, 有4个分裂属性, 类标记属性为3种, 人为添加部分缺失信息, 缺失属性为sepal width,共有30条缺失记录, 使用Iris数据集对改进前后的算法进行 

5次仿真实验, 实验结果如图2所示.

0.0350.03C4.5N-C4.5)s0.025(间0.02时行0.015运0.010.005012345 实验次数图2    Iris数据建模时间

由图2可以看出, 对于Iris 数据, N-C4.5算法的运行时间短, 优化效果明显. 为了验证N-C4.5算法算法的效率, 对于其他4组数据集, 同样都分别使用改进后的N-C4.5算法与C4.5算法进行仿真实验, 测试时每个数据集都运行5次, 建模时间取5次的平均值, 建模时间如表3所示.

表3     建模信息表

DatasetC4.5N-C4.5比率提升(%)Iris0.0260.0122.170.3Glass0.850.711.120.1Vote0.0180.0121.50.15Diagnostic0.950.781.220.1Breast

3.43

1.62

2.12

0.03

由表中可以看出, 数据样本的大小会影响算法的运行时间, 一般情况下, 测试数据样本数据量越大, 需

202 软件技术•算法 Software Technique•Algorithm

要运行的时间越长. 算法改进前后的比率都大于1, 正确率的提升都是正值, 可以得出结论: N-C4.5算法的建模时间明显优于C4.5算法, 分类准确率也高于原C4.5算法.

4   总结

虽然C4.5算法具有建模速度快、准确率高、易于理解、灵活简单、以及处理噪声数据的能力强等优

点, 但当属性值缺失率高时, 分类准确率会明显下降;在构建决策树时, 需要多次扫描、排序数据集、以及频繁调用对数等缺点. 本文提出一种改进的决策树分类算法. 采用一种基于朴素贝叶斯定理方法, 来处理空缺属性值, 提高分类准确率. 通过优化计算公式, 改进后的N-C4.5算法使用四则混合运算代替原来的对数运算, 减少构建决策树模型的运行时间, 使计算效率得到提升.

参考文献

1芦思雨. 数据挖掘中分类算法的比较分析[硕士学位论文].

天津: 天津财经大学, 2016.

2唐一. ID3改进算法在高校就业系统中的应用研究[硕士学位论文]. 长沙: 湖南大学, 2012.

3陈杰, 邬春学. 决策树C4.5算法改进与应用. 软件导刊,2018, (10): 88–92.

4

黄秀霞. C4.5决策树算法优化及其应用[硕士学位论文].无锡: 江南大学, 2017.

5徐鹏, 林森. 基于C4.5决策树的流量分类方法. 软件学报,2009, 20(10): 2692–2704.

6蔡星. 决策树算法及其改进. 科技创新导报, 2014, (12): 40,45.

7

姚亚夫, 邢留涛. 决策树C4.5连续属性分割阈值算法改进及其应用. 中南大学学报(自然科学版), 2011, 42(12): 3772–3776.

8

刘兴文, 王典洪, 陈分雄. 一种基于变精度粗糙集的C4.5决策树改进算法宰. 计算机应用研究, 2011, 28(10):3649–3651. [doi: 10.3969/j.issn.1001-3695.2011.10.011]9

Han JW, Kamber M. 数据挖掘: 概念与技术. 范明, 孟小峰,译. 北京: 机械工业出版社, 2007.

10乐明明. 数据挖掘分类算法的研究和应用[硕士学位论文].成都: 电子科技大学, 2017.

11李旭. 五种决策树算法的比较研究[硕士学位论文]. 大连:大连理工大学, 2011.

12缪连芬. 改进的C4.5算法在大学生情感素质分析中的研究与应用[硕士学位论文]. 上海: 上海师范大学, 2018.

13

李锦善. 基于Volume Test的贝叶斯分类器研究[硕士学位论文]. 北京: 北京交通大学, 2008.