謝秋華

（三明學(xué)院 信息工程學(xué)院 物聯(lián)網(wǎng)應(yīng)用福建省高校工程研究中心，福建 三明 365004）

隨著科技的進(jìn)步，社會(huì)各方面都獲得了極大的發(fā)展，在各個(gè)領(lǐng)域，都出現(xiàn)了一個(gè)同樣的問題：數(shù)據(jù)呈海量般增加，里面包含著許多對(duì)人們有用的信息而人們卻無從知曉。為了解決這個(gè)問題，人們提出了數(shù)據(jù)挖掘這一新方法。數(shù)據(jù)挖掘的功能有很多種，目前主要有：分類、關(guān)聯(lián)分析、聚類分析、異常檢測(cè)等，這些功能是相互聯(lián)系的，并不是各自孤立的。解決分類問題的一般方法有決策樹分類法、基于規(guī)則的分類法、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)和樸素貝葉斯分類法［1］。決策樹分類法目前較為常用的有 ID3、C4.5 等。

1 算法 C4.5

C4.5是在ID3的基礎(chǔ)上改進(jìn)后得到的，除了具有ID3的優(yōu)點(diǎn)，還具有以下優(yōu)點(diǎn)：

（1）不是根據(jù)信息增益而是根據(jù)信息增益率來選擇屬性，避免了ID3趨向于選擇取值多的屬性的缺點(diǎn)。

（2）增加了剪枝這一步驟，克服了過度擬合的缺點(diǎn)。

（3）能夠?qū)B續(xù)值的屬性進(jìn)行處理。

（4）能處理不完整數(shù)據(jù)。

C4.5算法選擇信息增益率最大的屬性作為分支屬性[2-4]，給出公式。

假定集合為B，當(dāng)前計(jì)算的屬性為X，則屬性X的信息增益率計(jì)算公式為：

假定屬性X有a個(gè)相異值{X1,X2,...,Xa},則屬性X把集合B劃分為a個(gè)子集{B1,B2,…,Ba},每個(gè)子集 Bi（i=1,2,…a）的記錄的屬性 X 的取值均為 Xi（i=1,2,…,a），則

其中，|Bi|表示集合Bi的記錄個(gè)數(shù)，|B|表示集合B的記錄個(gè)數(shù)。

假設(shè)集合B有m個(gè)類別屬性值，表示有m個(gè)相異的類Ci（i=1,2,…,m），若B中類別為Ci的記錄的個(gè)數(shù)為BCi（i=1,2,…,m），則對(duì)集合B進(jìn)行分類后的期望值為

其中|B|表示集合B的記錄個(gè)數(shù)。

（1）式中的分子

計(jì)算INF（X），沿用上述所定，集合B當(dāng)前計(jì)算的屬性為X，則產(chǎn)生a個(gè)分支，即屬性X把集合B劃分為B1，B2,…，Ba這a個(gè)子集，若子集Bi中類別為Cj的記錄個(gè)數(shù)為Bji，則

其中|B|為集合B所含的記錄個(gè)數(shù)，|Bi|、|Bj|分別為子集Bi和Bj所含的記錄個(gè)數(shù)[5]。

2 優(yōu)化C4.5

根據(jù)泰勒公式，

令（7）式右邊為-y+d（y），其中 d（y）表示余項(xiàng)，則（7）式為

按照前面的假定，假定集合B有m個(gè)相異類，每類的記錄個(gè)數(shù)分別為y1，y2，…，ym，則集合B的記錄個(gè)數(shù)為y1+y2+…+ym，假定當(dāng)前計(jì)算的屬性X有a個(gè)相異值，即X把集合B劃分為a個(gè)子集（分別為B1，B2，…，Ba），每個(gè)子集的記錄個(gè)數(shù)為 c1，c2，…，ca，則集合 B的記錄個(gè)數(shù)也可用c1+c2+…+ca表示，假定每個(gè)子集 Bi（i=1，2，…，a）的屬于 m 個(gè)相異類的記錄個(gè)數(shù)分別為 ci1，ci2，…，cim，則ci也可用ci1+ci2+…+cim表示。則根據(jù)公式（3）和（8）有

根據(jù)公式（5）、（6）和（8），有

根據(jù)（2）式和（8）式有

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

3 分析

從式子（1）～（6）可以看出，優(yōu)化前計(jì)算屬性信息增益率時(shí)要頻繁用到對(duì)數(shù)運(yùn)算，從式子（16）看出優(yōu)化后計(jì)算屬性信息增益率時(shí)只用到加減乘除運(yùn)算，從理論上可以看出，優(yōu)化前計(jì)算屬性信息增益率時(shí)要不斷調(diào)用對(duì)數(shù)函數(shù)，這樣會(huì)大大增加時(shí)間上的開銷，而優(yōu)化后的計(jì)算只用到加減乘除運(yùn)算，不需調(diào)用函數(shù)，時(shí)間開銷會(huì)減少，優(yōu)化前后的計(jì)算所用的數(shù)據(jù)結(jié)構(gòu)一致，因而優(yōu)化后空間復(fù)雜度不會(huì)增加。而且由前面的證明可知，優(yōu)化后計(jì)算所得的選擇屬性不會(huì)發(fā)生改變。由此可以得出結(jié)論：優(yōu)化后的C4.5算法能減少時(shí)間復(fù)雜度但不改變準(zhǔn)確率而且不會(huì)增加空間復(fù)雜度。通過以下實(shí)驗(yàn)數(shù)據(jù)可以看出所得的結(jié)論是正確的。

由于UCI數(shù)據(jù)集是數(shù)據(jù)挖掘中公共數(shù)據(jù)測(cè)試集，里面羅列了數(shù)據(jù)的屬性和類別，使用者可以用自己的數(shù)據(jù)挖掘方法去將UCI數(shù)據(jù)集分類，進(jìn)行必要的分析。因此在同樣的軟硬件環(huán)境中用UCI數(shù)據(jù)集對(duì)優(yōu)化前和優(yōu)化后的C4.5進(jìn)行測(cè)試，優(yōu)化前和優(yōu)化后所得的決策樹一樣，得到的結(jié)果如表1。可見，優(yōu)化后的C4.5能提高效率。

表1 C4.5和優(yōu)化后C4.5的比較

4 總結(jié)

通過簡(jiǎn)化C4.5算法屬性信息增益率的計(jì)算，將含有大量對(duì)數(shù)運(yùn)算的運(yùn)算簡(jiǎn)化為只含有加減乘除的運(yùn)算，使得實(shí)現(xiàn)時(shí)不用頻繁調(diào)用對(duì)數(shù)函數(shù)，減少了運(yùn)算時(shí)間，由于改進(jìn)后并不改變屬性信息增益率的排序，因而不會(huì)改變生成的決策樹，能夠在不提高空間復(fù)雜度和不改變準(zhǔn)確率的情況下提高分類效率。但研究只考慮改進(jìn)了分類效率，但是分類準(zhǔn)確度還需進(jìn)一步提高［6］。

［1］TAN PANG NING，MICHAEL STEINBACH，VIPIN KUMAR.數(shù)據(jù)挖掘?qū)д摚跰］.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］陳文偉，黃金才，趙新昱.數(shù)據(jù)挖掘技術(shù)［M］.北京：北京工業(yè)大學(xué)出版社，2002.

［6］陳秀瓊.一種融合粗集理論和神經(jīng)網(wǎng)絡(luò)的分類數(shù)據(jù)挖掘算法［J］.三明學(xué)院學(xué)報(bào)，2005，22（2）：185－190.