謝秋華

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

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

1 算法 C4.5

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

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

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

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

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

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

假定集合為B，當(dāng)前計算的屬性為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的記錄個數(shù)，|B|表示集合B的記錄個數(shù)。

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

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

（1）式中的分子

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

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

2 優(yōu)化C4.5

根據(jù)泰勒公式，

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

按照前面的假定，假定集合B有m個相異類，每類的記錄個數(shù)分別為y1，y2，…，ym，則集合B的記錄個數(shù)為y1+y2+…+ym，假定當(dāng)前計算的屬性X有a個相異值，即X把集合B劃分為a個子集（分別為B1，B2，…，Ba），每個子集的記錄個數(shù)為 c1，c2，…，ca，則集合 B的記錄個數(shù)也可用c1+c2+…+ca表示，假定每個子集 Bi（i=1，2，…，a）的屬于 m 個相異類的記錄個數(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)化前計算屬性信息增益率時要頻繁用到對數(shù)運算，從式子（16）看出優(yōu)化后計算屬性信息增益率時只用到加減乘除運算，從理論上可以看出，優(yōu)化前計算屬性信息增益率時要不斷調(diào)用對數(shù)函數(shù)，這樣會大大增加時間上的開銷，而優(yōu)化后的計算只用到加減乘除運算，不需調(diào)用函數(shù)，時間開銷會減少，優(yōu)化前后的計算所用的數(shù)據(jù)結(jié)構(gòu)一致，因而優(yōu)化后空間復(fù)雜度不會增加。而且由前面的證明可知，優(yōu)化后計算所得的選擇屬性不會發(fā)生改變。由此可以得出結(jié)論：優(yōu)化后的C4.5算法能減少時間復(fù)雜度但不改變準(zhǔn)確率而且不會增加空間復(fù)雜度。通過以下實驗數(shù)據(jù)可以看出所得的結(jié)論是正確的。

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

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

4 總結(jié)

通過簡化C4.5算法屬性信息增益率的計算，將含有大量對數(shù)運算的運算簡化為只含有加減乘除的運算，使得實現(xiàn)時不用頻繁調(diào)用對數(shù)函數(shù)，減少了運算時間，由于改進后并不改變屬性信息增益率的排序，因而不會改變生成的決策樹，能夠在不提高空間復(fù)雜度和不改變準(zhǔn)確率的情況下提高分類效率。但研究只考慮改進了分類效率，但是分類準(zhǔ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é)報，2005，22（2）：185－190.