王利軍

(安徽經(jīng)濟管理學(xué)院信息工程系,安徽 合肥 230031)

Quinlan J R提出的ID3算法[1]是經(jīng)典的決策樹算法，該算法以信息增益作為屬性劃分的依據(jù)，選取信息增益最大的屬性作為分裂節(jié)點，從而生成決策樹.這樣的決策樹結(jié)構(gòu)簡單，易于理解.但這種選取方式傾向?qū)傩灾递^多的屬性，而這個屬性不一定是最優(yōu)的，為了避免這種多值依賴現(xiàn)象，許多學(xué)者提出了各種方案，如文獻[2]引入屬性的相關(guān)子集進行分類；文獻[3]引用權(quán)值來進行改進信息增益公式來解決多值依賴問題；文獻[4]提出了屬性優(yōu)先值的概念進行修正；文獻[5]引入屬性協(xié)調(diào)度這一概念來度量屬性的分類能力，該分類能力其實是屬性與類標號屬性之間的相關(guān)性的體現(xiàn)；文獻[6]提出的GINI指數(shù)作為衡量閥值，平衡信息增益對屬性值個數(shù)多的偏好問題.本文擬采用OneR算法計算出每個屬性的準確率來修正ID3算法的多值依賴問題.

另外關(guān)于信息增益公式簡化計算方面的問題，許多學(xué)者提出各種簡化方法，如文獻[7]利用等價無窮小的性質(zhì)來加快信息增益的計算效率；文獻[8]利用凸函數(shù)的性質(zhì)來簡化計算；文獻[9]利用知識依賴理論對公式進行簡化.本文擬采用冪級數(shù)展開式來簡化計算.

1 相關(guān)理論和舉例

1.1 決策樹ID3算法

ID3算法是決策樹中的常用算法，它是以信息論中的信息熵理論為依據(jù)的.

定義1 類標號屬性的期望信息量：設(shè)包含s個數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)集DB，若DB中類標號屬性可劃分為n個分類，每個分類表示為DBi(1≤i≤n),每個分類包含的樣本數(shù)據(jù)為si，pi表示屬于第i個類標志值的概率，即pi=si/s(0

(1)

定義2 屬性的期望信息量：假設(shè)屬性A具有k個不同的值，則樣本數(shù)據(jù)集DB可根據(jù)屬性A的不同值劃分為k個子集{A1,A2,…,Ak}，每個分類為Aj(1≤j≤k)，設(shè)子集Aj在類DBi中的樣本個數(shù)為si,j,sj表示按屬性A分類后第j類的樣本個數(shù)，pi,j表示第j類屬于第i個類標志值的概率，即pi,j=si,j/sj(0

(2)

定義3 屬性A的信息熵：公式如下：

(3)

定義4 屬性A的信息增益：公式如下：

Gain(A)=I(s1,s2,…,sn)-E(A)

(4)

決策樹ID3算法以信息熵為基礎(chǔ)，選擇信息增益最大的屬性作為測試屬性，這樣的選擇方法則會產(chǎn)生多值偏向的問題，即屬性值較多的屬性優(yōu)先成為測試屬性，而與類標號屬性關(guān)系相對密切的屬性不一定會被優(yōu)先選擇，因此需要修改信息增益的計算公式使信息增益不會隨著屬性值個數(shù)的增加而遞增.

采用購車數(shù)據(jù)集來生成決策樹見表1.

表1 購車數(shù)據(jù)集

各個測試屬性的信息熵如下所示：

故Gain(收入水平)=I(8,6)-E(收入水平)=0.448 88，Gain(駕車技術(shù))=I(8,6)-E(駕車技術(shù))=0.257 8，Gain(商務(wù)人士)=I(8,6)-E(商務(wù)人士)=0.048 119，Gain(喜歡季節(jié))=I(8,6)-E(喜歡季節(jié))=0.467 72，則Gain(喜歡季節(jié))最大，使用喜歡季節(jié)作為初始節(jié)點，是否購車其實跟客戶喜歡的季節(jié)關(guān)聯(lián)度不是太大，ID3算法存在多值依賴問題，故構(gòu)建的決策樹如圖1所示.

圖1 ID3算法構(gòu)建的決策樹

1.2 ID3算法的改進

本文將對決策樹ID3算法進行兩個方面的改進，第一個方面：引入準確率修正信息增益公式解決多值偏向問題；第二個方面：引入冪級數(shù)展開式簡化計算優(yōu)化性能.

1.2.1 基于準確率的信息增益修正

以信息增益最大的屬性為測試屬性的決策樹ID3算法存在的多值偏向問題，為了解決這一問題，需要對信息增益公式進行修正，修正公式不僅需要考慮屬性的值取個數(shù)，還需要考慮屬性與類標號屬性之間的關(guān)系.本文引入OneR(One Rule)算法來解決這一問題.

OneR算法是一種極為簡單的分類算法模型，它可以根據(jù)訓(xùn)練集中的一個特征實現(xiàn)對數(shù)據(jù)的分類，而這個特征必須是準確率最高的，這樣的特征則會與類標號屬性關(guān)系密切，這樣就可以解決多值偏向的問題

OneR算法步驟描述如下：首先確定類標號屬性后，再對每一個屬性的每一個值執(zhí)行統(tǒng)計，統(tǒng)計每一個值在類標號屬性上出現(xiàn)的次數(shù)，找出出現(xiàn)次數(shù)最大的值所屬的類，并確定規(guī)則；然后計算每一個屬性的準確率，最后找出準確率最高的屬性集合

下面舉例說明如何計算準確率，比如測試數(shù)據(jù)包含10條數(shù)據(jù)信息見表2，以性別為類標號屬性，除編號外的三個屬性(身高、體重和頭發(fā))為測試屬性.

表2 OneR算法測試數(shù)據(jù)

對這三個測試屬性分別進行統(tǒng)計，統(tǒng)計結(jié)果見表3：

表3 測試屬性的統(tǒng)計結(jié)果

分析統(tǒng)計結(jié)果獲得每個屬性的準確率，從身高的統(tǒng)計數(shù)據(jù)中發(fā)現(xiàn)，身高為高的4個為男士，則設(shè)定規(guī)則為身高為高為男，則身高為高的4個男士為準確數(shù)據(jù)，同理獲得身高為矮的3個女士為準確數(shù)據(jù)，故身高的總準確數(shù)據(jù)為4+3=7，身高的準確率為7/10=70%；同理獲得體重的準確率為60%；頭發(fā)的準確率為90%.因此根據(jù)頭發(fā)來判斷性別的準確率是最高的，選擇頭發(fā)作為性別判斷的唯一規(guī)則.

每個屬性的準確率Accuracy一定程度上反映該屬性與類標號屬性的關(guān)聯(lián)程度，準確度越高關(guān)聯(lián)度越大，本文對公式(4)進行改進，增加有關(guān)準確率的權(quán)值系數(shù)，這樣就可以在計算信息增益時考慮屬性與類標號屬性的關(guān)聯(lián)性，以此來解決多值偏向問題，修改后的信息增益公式(5)如下所示：

Gain(A)=Accuracy·[I(s1,s2,…,sn)-E(A)]

(5)

1.2.2 基于冪級數(shù)展開式簡化計算

ID3算法每次選擇測試屬性時，都需要計算每個候選屬性的信息增益，計算過程中包含形如:

常見的冪級數(shù)公式如(6)所示：

(6)

設(shè)pi=(1-ki)/(1+ki)，kj∈[0,1)，可得ki=(1-pi)/(1+pi),pi∈[0,1)，推導(dǎo)過程如下：

因ki的取值范圍符合公式(6)的要求，故可以對上式進行冪級數(shù)轉(zhuǎn)化，最終得到如下結(jié)果：

(7)

考慮精度和運算量，故保留前兩項，近似推導(dǎo)過程：

再將ki=(1-pi)/(1+pi)代入可得(8)式：

(8)

再將pi=si/s代入(8)中得到：

(9)

至此，對數(shù)運算已轉(zhuǎn)化成公式(9)所包含的簡單加減乘除運算，而且si和s都是整數(shù)，減少了計算成本，雖然采用冪級數(shù)近似計算會產(chǎn)生誤差，但本文采用了準確率對信息增益進行了修正，該準確率也會相應(yīng)地減少誤差.

1.2.3 改進前后的決策樹比較

基于表1的購車數(shù)據(jù)集中各個測試屬性的準確率分別為Accuracy(收入水平)=12/14，Accuracy(駕車技術(shù))=11/14，Accuracy(商務(wù)人士)=9/14和Accuracy(喜歡季節(jié))=11/14.

采用冪級數(shù)近似計算得到I(8,6)=0.981 839，采用冪級數(shù)近似計算實現(xiàn)公式(5)得到的信息增益分別為Gain(收入水平)= 0.399 357 9，Gain(駕車技術(shù))=0.217 7，Gain(商務(wù)人士)=0.0328 14和Gain(喜歡季節(jié))=0.368 84, 這時發(fā)現(xiàn)Gain(收入水平)最大，選擇收入水平作為決策樹的初始節(jié)點，更符合客觀實際，從而一定程度上解決了ID3算法的多值偏向問題.基于準確率的信息增益近似計算結(jié)果構(gòu)建的決策樹如圖2所示：

圖2 改進后的決策樹

比較圖1和圖2，首先，可以發(fā)現(xiàn)初始節(jié)點由4個分枝的“喜歡季節(jié)”變成了3個分枝的“收入水平”，收入水平對是否購車的影響最大，才是是否購車的主要因素，這才符合客觀實際；其次，葉子節(jié)點數(shù)由原先的8個變成現(xiàn)在的7個，改進后的決策樹更加精簡.

2 驗證實驗

采用3種UCI測試數(shù)據(jù)集如表4，進行仿真實驗來驗證改進后的決策樹的優(yōu)越性.驗證實驗的結(jié)果如表5所示.

表4 數(shù)據(jù)集信息

仿真實驗從節(jié)點數(shù)、挖掘精度和建樹時間上進行驗證，發(fā)現(xiàn)改進后生成決策樹的節(jié)點數(shù)明顯減少，表明改進后的決策樹更加精簡，并且挖掘精度上均有提升，另外從建樹時間上看，改進后的算法可以加快建樹效率.總之，本文提出的兩個方面的改進可以對ID3算法進行一定的優(yōu)化，達到了預(yù)期的效果.

3 結(jié)語

本文采用OneR算法中的準確率對信息增益公式進行了修正，從而一定程度上解決了ID3算法的多值偏向問題，另外采用冪級數(shù)展開式對ID3算法的計算進行了簡化，加快了運算效率，在準確率的協(xié)助下近似誤差也得到一定的減小.最后采用仿真實驗對改進前后生成決策樹的節(jié)點數(shù)、挖掘精度和建樹時間進行比較，驗證了改進后的算法的優(yōu)越性.下一步的工作是對改進后的決策樹進行進一步的修剪，使決策樹得到最優(yōu)最簡狀態(tài).