鄭 麟

(汕頭職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系,廣東 汕頭 515000)

0 引言

1 ID3算法的屬性選擇方法

1.1 ID3算法的基本思想

ID3算法用信息增益(熵)作為屬性的選擇標(biāo)準(zhǔn),即選擇具有最高信息增益(或最大熵壓縮)的屬性作為當(dāng)前結(jié)點(diǎn)的測試屬性,該屬性使得結(jié)果劃分中的樣本分類所需的信息量最小.具體方法是:檢測所有的屬性,選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn),由該屬性的不同取值建立分支(稱為分枝優(yōu)選),再對各分支的子集遞歸調(diào)用該方法建立

其中pi是任意樣本屬于Ti類的概率,即pi=si/s.因?yàn)樾畔⑹怯枚M(jìn)位編碼的,所以對數(shù)函數(shù)以2為底.如果以屬性A作為第一個(gè)決策樹劃分屬性,設(shè)屬性A有v個(gè)不同的值{v1,v2,…,vv},可以將S劃分為v個(gè)子集{S1,S2,…,Sv},用Sj表示,Sj中的樣本在屬性A上具有相同的值aj(j=1,2,…,v),對于給定子集Sj的期望信息由下式給出:

公式(2)實(shí)際上是由公式(1)而來,只不過將整個(gè)樣本集S換成樣本子集Sj,兩者的區(qū)別在公式(2)只需要計(jì)算屬性A的值等于aj的樣本子集Sj的熵,而公式(1)用來計(jì)算整個(gè)樣本S的總期望信息(即總熵).由此可知Pij=sij/sj,其中sij是子集Sj中屬于類Ti的樣本數(shù).所以樣本子集Sj中的樣本總數(shù)為s1j+s2j+…+snj,在計(jì)算由屬性A劃分后的總熵時(shí)我們必須在每個(gè)樣本子集Sj的熵前面乘上權(quán)值(s1j+s2j+…+snj)/s,其中s是樣本集S的總樣本數(shù),即用屬性A作為決策樹第一個(gè)劃分結(jié)點(diǎn)得到的熵為:

因此,劃分后的信息增益為原來的總熵減去劃分后的總熵即:

熵值E(A)越小,子集劃分的純度越高,因此算法選取具有最高信息增益的屬性作為給定集合S的測試屬性,創(chuàng)建一個(gè)結(jié)點(diǎn),并以該屬性標(biāo)記,對該屬性的每個(gè)值創(chuàng)建一個(gè)分支,并據(jù)此劃分樣本,如此反復(fù)不斷構(gòu)造決策樹的下一級(jí)直至所有的樣本子集只有一個(gè)類別,這時(shí)表明系統(tǒng)的熵為零,決策樹構(gòu)造過程完畢[5].

1.2 ID3屬性選擇的性能分析

ID3算法的屬性選擇方法簡單、基礎(chǔ)理論清晰,能夠快速和高效的構(gòu)造出平均深度較小的決策樹,但是該算法存在著一些缺陷[7]:首先,ID3算法在選擇信息增益作為分裂屬性的選擇標(biāo)準(zhǔn)時(shí),偏向于優(yōu)先選擇取值較多的屬性,而取值較多的屬性往往不是最優(yōu)的屬性,這在實(shí)際應(yīng)用中往往不太合理;其次,ID3算法對噪聲較為敏感,當(dāng)訓(xùn)練樣本集變動(dòng)時(shí),決策樹會(huì)隨之大幅度變化,不利于漸進(jìn)學(xué)習(xí).最后,該方法沒有考慮屬性間的相關(guān)性,不能處理屬性值缺省的情況,也不能處理連續(xù)型屬性.

已經(jīng)提出的C4.5算法能較好的解決不能處理連續(xù)屬性的問題,而對于其他缺陷,許多學(xué)者提出各種各樣的解決方法:針對屬性間的相關(guān)性問題,文獻(xiàn)[8]引進(jìn)屬性依賴度來改進(jìn)算法性能;針對優(yōu)先選擇取值較多屬性的缺陷,文獻(xiàn)[9]提出一種基于屬性貢獻(xiàn)度的決策樹算法,從屬性選優(yōu)上消除了多值屬性選擇的偏向;文獻(xiàn)[10]則提出一種合理且可靠的MID3改進(jìn)算法,在一定程度上解決多值偏向問題;文獻(xiàn)[11-12]引入屬性重要性和屬性取值數(shù)量2個(gè)參數(shù)對ID3算法的信息增益公式進(jìn)行改進(jìn),并根據(jù)凸函數(shù)的性質(zhì)簡化信息熵的計(jì)算,提高決策樹的構(gòu)造效率;文獻(xiàn)[7]使用泰勒公式和麥克勞林公式提出了新的屬性選擇標(biāo)準(zhǔn),改進(jìn)后的算法通過簡化信息熵的計(jì)算,提高了分類準(zhǔn)確度.由以上研究成果可知,許多研究者主要針對該算法優(yōu)先選擇取值較多屬性的缺陷,對屬性選擇標(biāo)準(zhǔn)進(jìn)行改良,本文在參考以上研究成果的基礎(chǔ)上,結(jié)合實(shí)際研究工作,在只對離散型屬性進(jìn)行劃分的前提下,提出屬性貢獻(xiàn)因子的概念并將其作為ID3算法屬性選擇的重要參考依據(jù),并對ID3屬性選擇方法在數(shù)學(xué)上進(jìn)行適當(dāng)?shù)牡葍r(jià)變換使其簡化,最后達(dá)到提高屬性分類精度和速度的目的.

2 信息熵的簡化與優(yōu)化

2.1 信息熵的近似變換

將公式(1)、(2)、(3)帶入到公式(4)可得信息增益的公式為:

對于I(s1,s2,…,sn)的部分,只要給定了訓(xùn)練樣本和類別數(shù),pi就是不變的,因此它在整個(gè)決策樹構(gòu)造中始終為定值,可以把它從公式(5)中去掉,只保留E(A)來考慮如何改進(jìn)算法.在E(A)中要進(jìn)行多次的對數(shù)計(jì)算,由文獻(xiàn)[13]可知log x函數(shù)在[0,1]上是凸函數(shù),Pij取值在[0,1]上,所以可以運(yùn)用凸函數(shù)的性質(zhì).

性質(zhì)1[13]設(shè)f(x)為凸函數(shù),X為非空集合,則由可推出

公式(6)是計(jì)算信息增益的簡化公式,由此完成了屬性選擇標(biāo)準(zhǔn)改進(jìn)的第一步.

2.2 屬性信息熵的優(yōu)化

ID3屬性選擇標(biāo)準(zhǔn)的主要缺陷是算法優(yōu)先選擇取值較多的屬性,因此應(yīng)著重在這方面進(jìn)行改良,已有的C4.5算法是通過信息增益率作為屬性選擇標(biāo)準(zhǔn),但是很明顯的這會(huì)阻礙選擇屬性值分布均勻的屬性,即偏袒取值較少的屬性,而較好的解決方法是即不偏袒取值較多的屬性,也不偏袒取值較少的屬性.本文提出了一種基于貢獻(xiàn)因子的屬性選擇標(biāo)準(zhǔn).主要思想是:首先根據(jù)公式(5)的屬性選擇標(biāo)準(zhǔn)計(jì)算出各個(gè)特征屬性的信息增益,從而選擇出信息增益最大(即信息熵E(A)最小)的屬性記為屬性A1,然后計(jì)算出屬性取值個(gè)數(shù)最多的屬性A2,如果A1≠A2,說明信息增益最大的屬性不是取值個(gè)數(shù)最多的屬性,選擇該屬性作為測試屬性不會(huì)產(chǎn)生多值偏向問題;如果A1=A2,則說明信息增益最大和取值個(gè)數(shù)最多的屬性為同一屬性,用它作為測試屬性易產(chǎn)生多值偏向問題,應(yīng)對該屬性的信息增益用貢獻(xiàn)因子來修正,以避免取值異常偏向.在用屬性A劃分時(shí)加入貢獻(xiàn)因子(用函數(shù)Contribute(A)表示)修正其信息增益,則得到公式(7):

由上面的討論可以得到貢獻(xiàn)因子Contribute(A)的表達(dá)式如下:

由于sgn(sij)≤sij

2.3 屬性信息熵的綜合改進(jìn)

以上討論了ID3屬性選擇標(biāo)準(zhǔn)的簡化與優(yōu)化,結(jié)合公式(6)、(7)、(8)和(9)可以得到屬性A的信息增益E(A)的綜合改進(jìn)公式:

由公式(5)和公式(10)可以得到最后的信息增益計(jì)算公式:

可以使用公式(11)計(jì)算改進(jìn)后的信息增益,達(dá)到簡化計(jì)算和優(yōu)化決策樹劃分的作用.

3 實(shí)驗(yàn)及結(jié)果分析

3.1 小數(shù)據(jù)集測試分析

為說明基于貢獻(xiàn)因子的ID3算法的優(yōu)勢,先進(jìn)行小數(shù)據(jù)集測試以達(dá)到簡化分析的目的.測試的數(shù)據(jù)集使用UCI經(jīng)典數(shù)據(jù)集soybean中隨機(jī)取出的30條記錄,該數(shù)據(jù)集包括8個(gè)屬性,最后一個(gè)是類屬性class,前面7個(gè)屬性用來預(yù)測soybean(大豆)病變的類型,分別運(yùn)行了傳統(tǒng)的ID3算法(使用公式(5))和基于貢獻(xiàn)因子的ID3算法(使用公式(11))計(jì)算各個(gè)屬性的信息增益,實(shí)驗(yàn)結(jié)果如表1所示.

表1 小數(shù)據(jù)集分析結(jié)果

由實(shí)驗(yàn)結(jié)果可知,用傳統(tǒng)ID3算法計(jì)算出來的信息增益中,屬性

canker-lesion(潰瘍病變)的增益最大,但是其擁有的屬性取值個(gè)數(shù)也最大,作為第一個(gè)劃分結(jié)點(diǎn)值得商榷,在加入貢獻(xiàn)因子之后,屬性leafspot-size(葉斑大小)的信息增益變?yōu)樽畲?而其屬性取值個(gè)數(shù)并不是最大的,很明

顯取屬性leafspot-size作為劃分屬性較為合理.從生物學(xué)角度來看,潰瘍病變作為大豆病變的一種普遍癥狀,并不能對病變進(jìn)行合理分類,而葉斑大小很大程度上是和病變的類型相關(guān)的,這也解釋了使用leafspot-size作為劃分屬性的合理性.從分類準(zhǔn)確率、未知率和運(yùn)行時(shí)間方面來評(píng)估兩種方法如表2所示.

從表2可以看出,改進(jìn)后的ID3屬性劃分方法不僅在分類準(zhǔn)確率上有所提高,而且由于簡化了對數(shù)函數(shù)的計(jì)算,所以在運(yùn)行時(shí)間上也有所改進(jìn).

表2 小數(shù)據(jù)集上的算法性能比較

3.2 不同量級(jí)的數(shù)據(jù)集測試分析

為說明改進(jìn)算法具有普適性,采用各種不同量級(jí)的UCI數(shù)據(jù)集對其進(jìn)行測試,實(shí)驗(yàn)中選用樣本個(gè)數(shù)和屬性個(gè)數(shù)從小到大的數(shù)據(jù)集進(jìn)行測試,各數(shù)據(jù)集的分布情況如表3所示.

表3 數(shù)據(jù)集的分布情況

在上面5個(gè)數(shù)據(jù)集上分別采用傳統(tǒng)的ID3算法和基于貢獻(xiàn)因子的ID3算法進(jìn)行分類,結(jié)果如表4所示.

表4 不同量級(jí)數(shù)據(jù)集上的算法性能比較

由實(shí)驗(yàn)結(jié)果可知,基于貢獻(xiàn)因子的ID3算法在不同量級(jí)的數(shù)據(jù)集下的分類準(zhǔn)確率和分類未知率均優(yōu)于傳統(tǒng)的ID3算法.在中小量級(jí)的數(shù)據(jù)集中,改進(jìn)的算法亦表現(xiàn)良好,運(yùn)行時(shí)間較短;而在大型數(shù)據(jù)集中,改進(jìn)的算法由于計(jì)算貢獻(xiàn)因子的時(shí)間消耗增加,導(dǎo)致算法的總運(yùn)行時(shí)間會(huì)比傳統(tǒng)算法稍慢,但是從提高分類準(zhǔn)確率的效果來看,這點(diǎn)時(shí)間消耗是值得的.

4 結(jié)束語

基于貢獻(xiàn)因子的決策樹屬性選擇方法對傳統(tǒng)的ID3屬性選擇方法作了改進(jìn):首先簡化了信息熵的計(jì)算復(fù)雜度,提高算法的運(yùn)行速度;然后提出了貢獻(xiàn)因子的概念,平衡了ID3算法的屬性取值偏向,改善了分類結(jié)果.實(shí)驗(yàn)結(jié)果分析表明,對于相同的數(shù)據(jù)集,相較于傳統(tǒng)的ID3算法,基于貢獻(xiàn)因子的算法提高了決策樹分類的準(zhǔn)確率,縮短了運(yùn)行時(shí)間.但是,屬性的重要程度和屬性取值個(gè)數(shù)之間還存在著復(fù)雜的關(guān)系,本文只是平衡了屬性取值個(gè)數(shù)的問題,如何將重要程度和取值之間聯(lián)系起來并考慮處理缺失值是今后研究的重點(diǎn).

[1]Tan P N,Steinbach M,Vipin K.Introduction to data mining[M].北京:機(jī)械工業(yè)出版社,2011.

[2]Quinlan J R.Induction of decision trees[J].Machine Learning,1986,1(1):81-106.

[3]董廣,王興起.基于決策分類熵的決策樹構(gòu)造算法及應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2009,29(11):3103-3106.

[4]陶榮,張永勝,杜宏保.基于粗集論中屬性依賴度的ID3改進(jìn)算法[J].河南科技大學(xué)學(xué)報(bào):自然科學(xué)版,2010,31(1):42-45.

[5]Quinlan J R.Simplifying decision trees[J].Internet Journal of Man-Machine Studies,1987,27(3):221-234.

[6]Han J,Kamber M.數(shù)據(jù)挖掘:概念與技術(shù)[M].范明,孟小峰,譯.2版.北京:機(jī)械工業(yè)出版社,2006.

[7]謝妞妞,劉於勛.決策樹屬性選擇標(biāo)準(zhǔn)的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(34):115-118.

[8]史岳鵬,朱顥東.基于類別相關(guān)性和優(yōu)化的ID3特征選擇[J].數(shù)據(jù)采集與處理,2011,26(2):230-234.

[9]孫淮寧,胡學(xué)鋼.一種基于屬性貢獻(xiàn)度的決策樹學(xué)習(xí)算法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2009,32(8):1137-1141.

[10]王永梅,胡學(xué)鋼.基于用戶興趣度和MID3決策樹改進(jìn)方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(27):155-157.

[11]張 琳,陳燕,李桃迎,等.決策樹分類算法研究[J].計(jì)算機(jī)工程,2011,37(13):66-70.

[12]朱顥東.ID3算法的改進(jìn)和簡化[J].上海交通大學(xué)學(xué)報(bào),2010,44(7):883-886.

[13]陳紀(jì)修,金路,於崇華.數(shù)學(xué)分析[M].北京:高等教育出版社,2004.

[14]周海波.基于決策樹的分類算法研究[D].蘭州:蘭州大學(xué),2009.