C4.5数据挖掘算法的改进

谢秋华

（三明学院 信息工程学院 物联网应用福建省高校工程研究中心，福建 三明 365004）

随着科技的进步，社会各方面都获得了极大的发展，在各个领域，都出现了一个同样的问题：数据呈海量般增加，里面包含着许多对人们有用的信息而人们却无从知晓。为了解决这个问题，人们提出了数据挖掘这一新方法。数据挖掘的功能有很多种，目前主要有：分类、关联分析、聚类分析、异常检测等，这些功能是相互联系的，并不是各自孤立的。解决分类问题的一般方法有决策树分类法、基于规则的分类法、神经网络、支持向量机和朴素贝叶斯分类法［1］。决策树分类法目前较为常用的有 ID3、C4.5 等。

1 算法 C4.5

C4.5是在ID3的基础上改进后得到的，除了具有ID3的优点，还具有以下优点：

（1）不是根据信息增益而是根据信息增益率来选择属性，避免了ID3趋向于选择取值多的属性的缺点。

（2）增加了剪枝这一步骤，克服了过度拟合的缺点。

（3）能够对连续值的属性进行处理。

（4）能处理不完整数据。

C4.5算法选择信息增益率最大的属性作为分支属性[2-4]，给出公式。

假定集合为B，当前计算的属性为X，则属性X的信息增益率计算公式为：

假定属性X有a个相异值{X1,X2,...,Xa},则属性X把集合B划分为a个子集{B1,B2,…,Ba},每个子集 Bi（i=1,2,…a）的记录的属性 X 的取值均为 Xi（i=1,2,…,a），则

其中，|Bi|表示集合Bi的记录个数，|B|表示集合B的记录个数。

假设集合B有m个类别属性值，表示有m个相异的类Ci（i=1,2,…,m），若B中类别为Ci的记录的个数为BCi（i=1,2,…,m），则对集合B进行分类后的期望值为

其中|B|表示集合B的记录个数。

（1）式中的分子

计算INF（X），沿用上述所定，集合B当前计算的属性为X，则产生a个分支，即属性X把集合B划分为B1，B2,…，Ba这a个子集，若子集Bi中类别为Cj的记录个数为Bji，则

其中|B|为集合B所含的记录个数，|Bi|、|Bj|分别为子集Bi和Bj所含的记录个数[5]。

2 优化C4.5

根据泰勒公式，

令（7）式右边为-y+d（y），其中 d（y）表示余项，则（7）式为

按照前面的假定，假定集合B有m个相异类，每类的记录个数分别为y1，y2，…，ym，则集合B的记录个数为y1+y2+…+ym，假定当前计算的属性X有a个相异值，即X把集合B划分为a个子集（分别为B1，B2，…，Ba），每个子集的记录个数为 c1，c2，…，ca，则集合 B的记录个数也可用c1+c2+…+ca表示，假定每个子集 Bi（i=1，2，…，a）的属于 m 个相异类的记录个数分别为 ci1，ci2，…，cim，则ci也可用ci1+ci2+…+cim表示。则根据公式（3）和（8）有

根据公式（5）、（6）和（8），有

根据（2）式和（8）式有

由式子（1）、（4）、（10）、（12）、（14）有

3 分析

从式子（1）～（6）可以看出，优化前计算属性信息增益率时要频繁用到对数运算，从式子（16）看出优化后计算属性信息增益率时只用到加减乘除运算，从理论上可以看出，优化前计算属性信息增益率时要不断调用对数函数，这样会大大增加时间上的开销，而优化后的计算只用到加减乘除运算，不需调用函数，时间开销会减少，优化前后的计算所用的数据结构一致，因而优化后空间复杂度不会增加。而且由前面的证明可知，优化后计算所得的选择属性不会发生改变。由此可以得出结论：优化后的C4.5算法能减少时间复杂度但不改变准确率而且不会增加空间复杂度。通过以下实验数据可以看出所得的结论是正确的。

由于UCI数据集是数据挖掘中公共数据测试集，里面罗列了数据的属性和类别，使用者可以用自己的数据挖掘方法去将UCI数据集分类，进行必要的分析。因此在同样的软硬件环境中用UCI数据集对优化前和优化后的C4.5进行测试，优化前和优化后所得的决策树一样，得到的结果如表1。可见，优化后的C4.5能提高效率。

表1 C4.5和优化后C4.5的比较

4 总结

通过简化C4.5算法属性信息增益率的计算，将含有大量对数运算的运算简化为只含有加减乘除的运算，使得实现时不用频繁调用对数函数，减少了运算时间，由于改进后并不改变属性信息增益率的排序，因而不会改变生成的决策树，能够在不提高空间复杂度和不改变准确率的情况下提高分类效率。但研究只考虑改进了分类效率，但是分类准确度还需进一步提高［6］。

［1］TAN PANG NING，MICHAEL STEINBACH，VIPIN KUMAR.数据挖掘导论［M］.2版.北京：人民邮电出版社，2011.

［2］QUINLAN J R.C4.5：programs for machine learning［M］.San Mateo，：Morgan Kaufmann，1993.

［3］LIM T S，LOH W Y， SHIH Y S.A comparison of prediction accuracy，complexity，and training time of thirty－three old and new classification algorithms［J］.Machine Learning.2000（40）：203－229.

［4］RUGGIERI S.Efficient C4.5［J］.IEEE Transactions on Knowledge and data engineering，2002，14（2）：438－444.

［5］陈文伟，黄金才，赵新昱.数据挖掘技术［M］.北京：北京工业大学出版社，2002.

［6］陈秀琼.一种融合粗集理论和神经网络的分类数据挖掘算法［J］.三明学院学报，2005，22（2）：185－190.