决策树C4.5算法改进与应用

陈杰 邬春学

摘要：针对决策树算法C4.5在处理数据挖掘分类问题中出现的算法低效以及过拟合问题，提出一种改进的TM-C4.5算法。该算法主要改进了C4.5算法的分支和剪枝策略。首先，将升序排序后的属性按照边界定理，得出分割类别可能分布的切点，比较各点的信息增益和通过贝叶斯分类器得到的概率，使用条件判断确定最佳分割阈值；其次，使用简化的CCP（Cost-Complexity Pruning）方法和评价标准，对已生成决策树的子树根节点计算其表面误差率增益值和S值，从而判断是否删除决策树节点和分支。实验结果表明，用该算法生成的决策树进行分类更为精确、合理，表明TM-C4.5算法有效。

关键词：C4.5；TM-C4.5算法；CCP；贝叶斯分类器；剪枝策略；评价标准

DOIDOI：10.11907/rjdk.181302

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）010-0088-05

英文摘要Abstract：Aiming at the inefficiency and over-fitting problem of decision tree algorithm C4.5 in the classification of data mining problems， an improved TM-C4.5 algorithm is proposed. The algorithm mainly improves the branching and pruning strategy of C4.5 algorithm. First， the ascending ordered attribute values are combined with the boundary theorem to get the cut points of the possible segmentation classifications. The information gain rate of each point and the probability obtained by the Bayesian classifier are compared， and the optimal segmentation threshold is determined according to the rules. Secondly， the simplified algorithm of CCP （Cost-Complexity Pruning） and evaluation criteria were used to calculate the surface error rate gain and S value of the subtree root node of the generated decision tree to judge whether to delete the decision tree node and branch. The analysis of the experimental results shows that the classification of the decision tree made by this algorithm is more accurate and reasonable， indicating the validity of TM-C4.5 algorithm.

英文关键词Key Words：C4.5；TM-C4.5 algorithm；CCP；Bayesian classifier；pruning strategy；evaluation standard

0 引言

分类技术是数据挖掘领域中一种非常重要的研究方法[1]。目前解决分类问题应用较广泛的算法有决策树算法、贝叶斯分类、人工神经网络算法、K邻近算法、支持向量机算法等，而决策树学习是以实例为基础的归纳学习算法[2]，在数据挖掘领域属于一种常用、简单有效的快速分类算法[3]。

本文对决策树C4.5算法的分支和剪枝策略进行改进，旨在获得更加高效、明确以及合理的分类效果。为提高算法的计算效率，文献[4]提出利用等价无穷小性质改变C4.5算法中的熵、信息增益和信息增益率[4]，虽然计算过程中减少了对数运算函数的调用次数，但由于忽略了常量值的计算，使得误差值变大，导致分类结果准确率下降。针对缺失属性值导致分类准确率下降的问题，文献[5]提出在决策树生成过程中，当分支的子集中属性值未知时，返回叶子节点，标记为unknown，并在之后的剪枝中将比例超过1/3（unknown节点与叶子节点之比）的unknown节点删除[5]。与传统的C4.5算法相比，该算法的时间复杂度在属性缺失率较高时能提高很多，但在数据集缺失率较低甚至没有缺失率情况下，该算法的时间复杂度相比传统的C4.5算法没有明显提升。另外，该算法对于属性缺失率阈值的设置缺乏合理的计算方法。文献[6]提出在实验中加入风险评估机制，并增添了覆盖率和高风险率作为该机制的评价标准，通过将其与朴素贝叶斯和决策树的分类结果对比，得出决策树的覆盖率优于另外两种分类器的结论[6]。

综合上述学者的研究成果，为了获取更加高效和精确的决策树模型，本文结合边界定理和贝叶斯分类器，获得更为精确的分割切点，使用简化的CCP方法和评价标准对决策树进行修剪以提高分类效率。

1 决策树C4.5算法

ID3算法和C4.5都是由QUINLAN提出的，后者是基于前者的改进算法。ID3算法虽然可以有效处理离散型属性，但对于连续型属性却难以处理。连续型属性的处理是数据挖掘领域热门问题之一，影响着数据挖掘算法的准确性、复杂性和可理解性[7]。同时，ID3算法容易产生过度拟合现象[8]。C4.5算法解决了ID3算法产生过度拟合的缺点，并增加了一些功能，如未知属性的处理、连续属性的离散化和规则的产生等[9]，具体改进如下：①在ID3的基础上，为避免用信息增益Gain选择属性时偏向选择取值多的属性之不足，C4.5选择用信息增益率GainRatio选擇属性作为树的节点；②对构造的树进行剪枝，防止过度拟合；③完成对连续属性的离散化处理；④对不完整数据进行处理。

C4.5算法流程见图1。

3 实验结果

3.1 数据预处理

实验系统环境为：Windows7；编程工具：PyCharm； 编程语言：python。实验数据来自UCI数据集，一共768条记录，数据集划分为11组，将其中10组600条记录用作训练集。采用随机抽取方法抽取训练集；抽取训练集之后，将实验室数据集剩余的168条记录作为测试集数据。实验数据集样本包含9种属性，分别为：①number of time pregnant（怀孕次数）；②Plasma glucose concentration a 2 hours in an oral glucose tolerance test（口服葡萄糖耐量试验中血浆葡萄糖浓度为2小时）；③Diastolic blood pressure （mm Hg）（舒张压）；④Triceps skin fold thickness （mm） 三头肌皮褶皱厚度 ；⑤2-Hour serum insulin （mu U/ml） （2小时血清胰岛素）；⑥Body mass index（BMI）；⑦Diabetes pedigree function（糖尿病谱系功能）；⑧Age （年龄）；⑨类Class（0 or 1）。

其中，将怀孕次数在0～1之间标记为Low，将2～5之间标记为Medium，大于等于6则标记为High[13]；属性BMI（体质指数）=体重（kg）/身高（m）。根据WHO标准划分等级为：BMI数值小于18.5设为偏瘦， 18.5～24.9之间设为正常，大于等于25设为超重。由于实验数据采样范围过于宽泛，并不能代表某一个国家或地区的典型划分依据，因此在本实验数据集基础上，通过计算属性BMI的信息增益率获取一个节点阈值，将小于该值的属性值标记为Light，大于该值的则为Overweight。属性AGE的处理与属性BMI的计算方式相似，其值分别标记为Young、Elderly。为使生成的决策树简明，方便后续算法进行，将数据集属性名分别缩写为NTP、PG、DBP、TSF、HSI、BMI、DPF、AGE。根据统计得出各属性缺失值数据及所占比例，将数据以图表展示，分别如图3和图4所示。

从图3和图4可以看出，属性NTP的缺失值记录数比例虽然达到了14.5%，但由于属性的现实参考意义很大，因此不能作为缺失值处理；属性TSF和HSI的缺失值分别达到了227个和374个，占据了总记录数的29.6%和48.7%，将该属性删除而不是删除包含这些缺失值的记录，以得到更多记录值。

通过以上分析，获得被处理分析的数据集属性取值如表1所示。

从表1可以看出，除了Class之外的6個属性中，有5个都是连续属性。在数据量较大以及连续属性过多时，若不对离散化方法进行改进，则算法效率必受到较大影响。

3.2 实验结果

通过结合边界定理和贝叶斯分类器得到的属性各切点的信息增益和概率值如表2所示。

从表2中选择具有最大信息增益和最大概率值的切点值作为最佳分割阈值，由此得到最佳分割阈值，如表3所示。

从表3可以看出，PG的最佳分割阈值为145.5mg/dl（8.08mmol/l），这与目前医学上口服葡萄糖耐量实验中2小时的正常值水平7.8mmol/l很接近，反映了对连续属性离散化的改进是有效的。其余属性如DBP、BMI、DPF、AGE的最佳分割阈值分别为72mmHg、27.5kg/m2、1.208 5和37。

此外，改进后的方法与原方法的执行时间分别为855ms和937ms，时间缩短了8.75%。由于数据集的数据量有限，因而效率提高不大，但相比原算法已经有了明显提升。

图5是属性AGE和BMI下的各节点表面误差率增益值和S值情况，通过改进方法选择删除两者值都较小的节点。

由图5可以看出，BMI下的子树AGE的表面误差率增益值为0.014 3，为最小值，其S值0.442也最小，表明该节点的分类精度和覆盖率都比较差，因此删除该节点改为用叶子节点替代。若没有引入评价标准S作为CCP方法的补充，在表面误差率增益值相差千分之几的情况下就很难抉择应该删除哪个节点。

表4所示为当测试集Ti （i=1，2，3，4，5）的实例数目分别为100、200、300、400、500时，C4.5算法和改进后的TM-C4.5算法的分类精度比较结果。

从表4可以看出，TM-C4.5算法的分类精度在不同的测试集下普遍高于原C4.5算法的分类精度。测试集实例数目递增时，改进后的算法准确率也逐步上升，证明了TM-C4.5算法的有效性。

4 结语

本文引用边界定理作为基础，进行节点贝叶斯概率计算，在决策树生成过程中提高了对子树根节点为连续属性时的离散化效率；在对决策树后剪枝时，在原来的CCP方法上添加了评价标准，使得在删除子树根节点时，确保该节点相比于其它节点，在分类过程中对整个决策树影响较小。但是在处理数据集的缺失属性值时，对于占比较大的属性直接删除，虽然省去了处理这些缺失值的麻烦，但是对最后生成的决策树会有一定影响。目前对缺失值的处理方法有删除法、插补法（均值插补、回归插补）等。因此，如何处理那些有较大数量缺失值的属性是下一步研究方向。

参考文献：

[1] 徐洪伟.数据挖掘中决策树分类算法的研究与改进[D]. 哈尔滨： 哈尔滨工程大学， 2010.

[2] 王源，王甜甜.改进决策树算法的应用研究[J].电子科技，2010，23（9）：89-91.

[3] 张琳，陈燕，李桃迎，等.决策树分类算法研究[J].计算机工程，2011，37（13）：66-67.

[4] 黄爱辉.决策树C4.5算法的改进及应用[J].科学技术与工程，2009（6）：34-36，42.

[5] 邱磊.基于决策树C4.5算法剪枝策略的改进研究[D].武汉：华中师范大学，2016.

[6] SONGTHUNG D， SRIPANIDKULHAI K. Improving type 2 diabetes mellitus risk prediction[C].International Joint Conferenceon Computer Science and Software Engineering （JCSSE），2016.

[7] DEWAN MD，FARID. Improve the quality of supervised discretization of continuous valued attributes in dataMining[C]. Proceedings of 14th International Conference on Computer and Information Technology （ICCIT 2011）， 2011.

[8] 朱琳， 楊杨. ID3算法的优化 [J]. 计算机工程与软件，2016，37（12）： 155-161.

[9] 谭俊璐，武建华.基于决策树规则的分类算法研究[J].计算机工程与设计，2010，31 （5）：354-358.

[10] BOVIC KILUNDU， CHRISTOPHE LETOT， PIERRE DEHOMBREUX， et al. Early detection of bearing damage by means of decisiontrees[C]. IFAC Proceedings Volumes，2008.

[11] HAN J C， RODRIGUEZ， BEHESHTI J C M.Diabetes data analysis and prediction model discovery using rapid miner [J]. International Conference on Future GenerationCommunication and Networking， 2008（3）：9-99.

[12] 苗煜飞，张霄宏.决策树C4.5 算法的优化与应用[J]. 计算机工程与应用，2015，51（13）： 255-258.

[13] 李瑞，程亚楠.一种改进的C4.5算法[J].科学技术与工程，2010，10（27）：6670-6674.

（责任编辑：杜能钢）