決策樹ID3算法的優化*

王利軍

(安徽經濟管理學院信息工程系,安徽 合肥 230031)

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

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

1 相關理論和舉例

1.1 決策樹ID3算法

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

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

(1)

定義2 屬性的期望信息量：假設屬性A具有k個不同的值，則樣本數據集DB可根據屬性A的不同值劃分為k個子集{A1,A2,…,Ak}，每個分類為Aj(1≤j≤k)，設子集Aj在類DBi中的樣本個數為si,j,sj表示按屬性A分類后第j類的樣本個數，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算法以信息熵為基礎，選擇信息增益最大的屬性作為測試屬性，這樣的選擇方法則會產生多值偏向的問題，即屬性值較多的屬性優先成為測試屬性，而與類標號屬性關系相對密切的屬性不一定會被優先選擇，因此需要修改信息增益的計算公式使信息增益不會隨著屬性值個數的增加而遞增.

采用購車數據集來生成決策樹見表1.

表1 購車數據集

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

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

圖1 ID3算法構建的決策樹

1.2 ID3算法的改進

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

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

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

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

OneR算法步驟描述如下：首先確定類標號屬性后，再對每一個屬性的每一個值執行統計，統計每一個值在類標號屬性上出現的次數，找出出現次數最大的值所屬的類，并確定規則；然后計算每一個屬性的準確率，最后找出準確率最高的屬性集合

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

表2 OneR算法測試數據

對這三個測試屬性分別進行統計，統計結果見表3：

表3 測試屬性的統計結果

分析統計結果獲得每個屬性的準確率，從身高的統計數據中發現，身高為高的4個為男士，則設定規則為身高為高為男，則身高為高的4個男士為準確數據，同理獲得身高為矮的3個女士為準確數據，故身高的總準確數據為4+3=7，身高的準確率為7/10=70%；同理獲得體重的準確率為60%；頭發的準確率為90%.因此根據頭發來判斷性別的準確率是最高的，選擇頭發作為性別判斷的唯一規則.

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

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

(5)

1.2.2 基于冪級數展開式簡化計算

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

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

(6)

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

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

(7)

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

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

(8)

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

(9)

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

1.2.3 改進前后的決策樹比較

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

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

圖2 改進后的決策樹

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

2 驗證實驗

采用3種UCI測試數據集如表4，進行仿真實驗來驗證改進后的決策樹的優越性.驗證實驗的結果如表5所示.

表4 數據集信息

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

3 結語

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