一种改进的C4.5决策树算法

王志春 刘丽娜

【关键词】数据挖掘 决策树 C4.5算法 信息增益率

1 引言

数据挖掘中决策树是解决分类问题的方法之一，是一种归纳学习算法。通过一组属性值向量和相应的类，采用归纳学习算法构造分类器和预测模型，能够从一组无序和无规则的数据中生成决策树形式的分类规则。决策树基本不依赖于任何专业领域的知識，所以在分类，预测和规则提取等领域都被广泛的应用。70 年代末，J.ROSS Quinlan提出了ID3算法后，在机器学习和知识发现领域决策树算法都得到了进一步应用和发展。

ID3算法的核心是选择属性时，用信息增益（information gain）作为选择属性的度量标准，在测试每一个非叶子结点时，能获得关于被测试记录最大的类别信息。虽然ID3算法具有算法清晰，方法简单和学习能力较强的优点，但是ID3算法不能处理连续的属性值，并且依赖于训练数据集的质量，只对数据集较小的情况有效，训练数据集在逐渐变大时，决策树可能会随之改变。由于ID3算法存在着许多需要改进的地方，为此，J.ROSS.Quinlan于1993提出了C4.5算法，对ID3算法进行了补充和改进。C4.5 算法具有ID3 算法优点的同时也改进和扩展了算法，使其产生易于理解和准确率较高的分类规则。相比于ID3算法，C4.5算法用信息增益率来选择属性，而不是ID3算法所用的信息增益；在ID3算法的基础上还增加了对连续属性的离散化、对不完整属性的处理能力和产生规则等功能。

2 C4.5算法

2.1 信息增益和信息增益率

设D是m个不同值的训练集有m个不同类Ci （i=1，2，…，m），设Ci， d是元组的集合，D和Ci， d中的元组个数是|D|和|Ci， d|。

2.1.1 信息增益

ID3算法中选择具有最高信息增益的属性作为节点N的分裂属性，使元组分类的信息量最小。期望信息为：

用|Ci， d|/|D|估计D中任意元组属于类Ci的概率Pi。Info（D）为D的熵。

若D的元组用属性A可分成v个不同的类{D1， D2，…，Dn}， Dj包含D中的元组且在A上有值aj，则属性A的信息熵为：

A属性上该划分的获得的信息增益为：

2.1.2 信息增益率

信息增益率用“分裂信息”值将信息增益规范化，假设以属性A的值为基准对样本进行分割，训练数据集D用分类信息SplitInfoA作为初始信息量划分成对应于属性A的有v个输出的v 个划分信息。定义如下：

信息增益率定义为信息增益与初始信息量的比值：

C4.5算法选取信息增益比最高的属性为集合D的测试属性，创建一个节点并为每个属性创建分支划分样本。

2.2 C4.5算法实现

假设用D代表当前样本集，当前候选属性集用A表示，则C4.5算法的流程图如图1所示。

3 C4.5算法的改进

3.1 C4.5算法改进原理

C4.5算法得到很好的应用，但是还存在一些不足，C4.5 算法因为要对数据集进行多次的扫描和排序所以算法的效率降低。根据信息量计算公式的特点，改进划分函数的属性选择度量计算公式和连续属性处理方法，简化信息量的计算复杂度，提高C4.5算法的执行效率。

C4.5算法由于大量使用了对数函数进行熵值运算，增加了计算机的运算时间，降低了每一次属性选择时算法的运算效率，所以为了解决这个问题，引入泰勒中值定理和麦克劳林展开式，对熵值中的对数运算进行变换，优化熵值运算，缩短其运算时间。

C4.5 算法对每个分割点都要计算相应的熵值，才能得到最优的分割点，所以在选择最佳的属性分割点时效率较低。为了解决这个问题，引入边界点定义和Fayyad 定理。

边界点定义：设序列L={x1， x2，…， xn}为升序排列的有序序列，实例X所属的类为Cx。如果有实例xi和xj（其中j=i+1），且Cxi≠Cxj，则边界点Bp =（xi +xj）/2。

Fayyad 定理：连续属性 X 各个候选分割点对应的信息熵值的最小值一定在边界点 Bp上取得。

由以上定理可知，连续属性的最优分割点在计算时，只需要通过比较属性值序列在边界点的最小信息熵值，就可以计算出该属性的最大修正信息增益率，减少了候补分割点，因此可以大大提高了计算的效率。

3.2 实验及结果分析

使用Weka 作为数据挖掘平台，对改进C4.5算法与传统C4.5算法的分类性能进行比较。实验所需数据来自于UCI数据集中IRIS的样本实例。算法执行效率及分类正确率实验结果如图2、3所示。

随着样本实例数的增加，改进算法的执行效率得到提高的同时分类的正确率也有一定的提升，因此改进的 C4.5 算法缩短了数据分析的等待时间，提高工作效率，保障了分类正确率。

4 结束语

本文通过对决策树分类算法C4.5的分析，在此基础上，针对该算法所存在的不足之处，改进了熵值的计算和连续属性最优分割点的计算，并用实验验证，得到较好的验证结果。

参考文献

[1]Quialan J R.hduetion ofdecision trees[M].Machine Learning，1986，（1）： 81-106.

[2]陈青山.决策树算法在高校教学质量评价系统中的应用研究[C].西南交通大学硕士论文，2010.

[3]Quialan J R.C4.5：Programs for Machine Learning[M].NewYork：Morgan Kaufnan， 1993.

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

[5]杨学兵，张俊.决策树算法及其核心技术[J].计算机技术与发展，2007，17（1）：44-46.