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

2013-10-23 07:48谢秋华
三明学院学报 2013年2期
关键词:子集个数增益

谢秋华

(三明学院 信息工程学院 物联网应用福建省高校工程研究中心,福建 三明 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.

猜你喜欢
子集个数增益
拓扑空间中紧致子集的性质研究
怎样数出小正方体的个数
基于增益调度与光滑切换的倾转旋翼机最优控制
连通子集性质的推广与等价刻画
关于奇数阶二元子集的分离序列
等腰三角形个数探索
基于单片机的程控增益放大器设计
怎样数出小木块的个数
基于Multisim10和AD603的程控增益放大器仿真研究
怎样数出小正方体的个数