決策樹ID3新屬性選擇方法

王子京，劉 毓

（西安郵電大學 通信與信息工程學院，陜西 西安 710121）

0 引 言

ID3算法因簡潔高效而受到廣泛的關注，其選擇信息增益最大的條件屬性作為分裂節(jié)點，不過ID3存在多值屬性偏向的問題[1]。C4.5算法利用信息增益率作為屬性分裂的標準，在一定程度上避免了多值屬性偏向問題[2]。然而，ID3和C4.5算法都需要計算信息增益，涉及對數(shù)運算，計算量較大?；诖植诩痆3]以及粗糙邏輯的決策方法可以靈活地處理多種決策表，適用于大數(shù)據(jù)，輸出結果相對復雜。決策樹一般處理多條件屬性、單決策屬性的決策表，輸出結果較為簡單，與粗糙集方法相配合，可以優(yōu)勢互補，避免對數(shù)運算帶來的計算量以及多值屬性的偏向問題。

文獻[4]提出加權平均粗糙度的概念，計算每個條件屬性下近似與上近似的加權比來判斷該屬性的分類性能。這種方法偏向于屬性的分類效率。

文獻[5]提出條件屬性重要度的概念，將所有條件屬性正域集與去掉某一條件屬性后的正域集模的差值作為分裂屬性的標準。這種方法偏向于屬性的分類精度。然而，這兩種方法均未充分考慮條件屬性與決策屬性之間的邏輯關系，因而由這兩種方法求出的屬性分類能力差別可能過小，有時不足以作為分裂屬性的依據(jù)。

文獻[6]引入屬性協(xié)調度的概念，計算某個條件屬性與決策屬性的等價類與該條件屬性等價類的模的比值度量該條件屬性的分類能力。這個方法考慮了條件屬性與決策屬性的相關性，算法性能有一定的提高。

本文在屬性協(xié)調度的基礎上，考慮條件屬性與決策屬性之間的邏輯關系，提出相容度的概念，以條件屬性的相容度作為分裂數(shù)據(jù)集的標準。最后，在UCI的3個公共數(shù)據(jù)集上應用本文提出的新屬性選擇方法。結果表明，與傳統(tǒng)ID3算法相比，本文提出的改進算法具有更高的預測準確率。

1 ID3 算法原理

設一樣本集S={S1,S2,…,Sn}，樣本個數(shù)為。設D={D1,D2,…,Dm}為決策屬性集，Dj（j=1,2,…,m）表示第j類屬性，|Dj|表示Dj類下樣本個數(shù)。則D的信息熵info(D)表示為：

式中Pj為第j類的概率，一般用該類下樣本個數(shù)與總樣本個數(shù)的比值進行估計。

設A={A1,A2,…,Ak}為一個條件屬性集 ，A（ii=1,2,…,k）為第i個條件屬性的取值，|Ai|表示該取值下的樣本個數(shù)，Aij表示Ai下的第j類，|Aij|表示該類的樣本個數(shù)。那么條件屬性A劃分后的信息熵為：

屬性A劃分前后的信息熵之差為信息增益，表達式為：

ID3算法的核心思想是分別計算每個屬性劃分前后數(shù)據(jù)的信息熵之差（信息增益），分裂節(jié)點時，以最大信息增益的屬性為節(jié)點，即把最能有效分類的條件屬性用作節(jié)點分裂，以保證每次分裂的樣本最純，生成的決策樹較為簡潔。經過反復迭代，直至葉子節(jié)點只有一類或所有條件屬性均用作分裂節(jié)點。

2 粗糙集基本原理

對于上述運算量大和偏向選擇多值屬性的問題，有學者提出一種基于粗糙集的改進算法[7-8]，其核心思想是用條件屬性的粗糙度作為選擇分裂屬性的標準，無需對數(shù)運算，減少了運算量，避免了優(yōu)先選擇多值屬性。

2.1 信息系統(tǒng)

2.2 等價類與不可區(qū)分關系

在(U,R)中，R為一個等價關系，U R表示一個等價類構成的集合，即U上元素在等價關系下的分類構成的集合。設P是R的一個非空子集，那么∩P（所有等價關系的交集）也是一個等價關系，稱為不可區(qū)分關系，用IND（P）表示。不可區(qū)分關系下的等價類是信息系統(tǒng)的最小單元。

2.3 屬性協(xié)調度

在決策系統(tǒng)S=(U,C∪D,V,f)中，C是已知知識，可以看作變量；D是被表達的知識；等價類U/(C,D)表示條件屬性集與決策屬性集的交集，邏輯意義是在C已知的情況下，蘊含D的樣本集合，即C→D的樣本集合。它的模用|C∪D|表示，是度量C→D的邏輯關系強弱的測度，從統(tǒng)計學角度看，則是決策規(guī)則的頻度。屬性協(xié)調度[6]Con(X→D)的數(shù)學表達式如下：

式中：X是C的非空子集；|?|是求模運算。

屬性協(xié)調度可以表達屬性的分類能力，協(xié)調度越大的屬性越重要。屬性協(xié)調度實際是決策表中前后件相同的集合與前件集合的模的比值。不過，屬性協(xié)調度是一個宏觀的統(tǒng)計，未能考慮各個決策規(guī)則的相容關系，在很多情況下兩個條件屬性的協(xié)調度差值過小，使得決策依據(jù)不夠充分。實際上，決策規(guī)則中有不少是相互矛盾（不相容）的，有必要微觀地考慮各個決策間的關系以提高算法性能。

3 改進算法

改進方法的主要思想是在屬性協(xié)調度的基礎上，考慮決策規(guī)則間的微觀邏輯關系，定義一個屬性相容度。用屬性相容度代替原來的屬性協(xié)調度作為分裂節(jié)點的標準。

3.1 主決策集與次決策集

設存在一個條件屬性集C與一個決策屬性集D，則中，與決策規(guī)則C→Ri矛盾的集合是依次對IND(C,D)下的集合求模，模值最大集合定義為主決策集，模值次大的集合定義為次決策集。顯然，主決策集與次決策集間呈矛盾關系。對于一個條件屬性而言，最壞的一種情況是主決策集與次決策集的模值相等。

3.2 屬性相容度

式中：X為C的非空子集；|?|是求模運算。由于考慮了次決策集對主決策集的影響，故式（5）為嚴相容度。

相容度的另一個表達式為：

由于將次決策集舍去，不予考慮，故式（6）為寬相容度。比較兩個條件屬性的相容度時，若式（4）計算結果相同，可進一步用式（5）計算，保證這兩個條件屬性的區(qū)分度。

3.3 改進算法流程

改進算法流程如下：

1）數(shù)據(jù)初始化，將所有條件屬性標記為活躍屬性；

2）求出各個條件屬性的主決策集與次決策集的模值；

3）用式（5）計算所有條件屬性的相容度，若有兩個或兩個以上屬性的相容度相近，繼續(xù)用式（6）計算；

4）選擇相容度最大的條件屬性作為分裂節(jié)點分隔樣本集，并將該屬性去除活躍屬性標記；

5）繼續(xù)選擇活躍屬性，繼續(xù)分裂樣本集，直至活躍屬性不存在或達到葉子節(jié)點；

6）生成決策樹，剪枝。

3.4 實例分析

本文以訓練樣本集為例說明改進算法的步驟。訓練樣本集見表1。方便起見，4個條件屬性用A1，A2，A3和A4表示，決策屬性用D表示。易得：

則：

同理，可得：

顯然，A3屬性的相容度大于其他屬性的相容度，因此選擇A3作為分裂節(jié)點。這里A1屬性有3個取值，而A3屬性有2個取值，昆蘭用信息熵的方法選擇A1屬性作為分裂節(jié)點。而本文的改進算法選擇A3作為分裂節(jié)點，說明改進算法避免了多值屬性的偏向問題。

4 實驗及結果

4.1 數(shù)據(jù)集介紹

本文選用3個UCI公開數(shù)據(jù)集測試改進算法的性能。這3個數(shù)據(jù)集分別是：kr-vs-kp數(shù)據(jù)集、house-votes-84數(shù)據(jù)集和tic-tac-toe數(shù)據(jù)集。其中，kr-vs-kp數(shù)據(jù)集樣本個數(shù)為3 196，條件屬性個數(shù)為36。house-votes-84數(shù)據(jù)集樣本個數(shù)為435，條件屬性個數(shù)為16。tic-tac-toe數(shù)據(jù)集樣本個數(shù)為958，條件屬性個數(shù)為9。這3個屬性集的取值均為離散值。本文所有仿真實驗均在Matlab 2011軟件中完成。

4.2 實驗結果及分析

本文分別應用傳統(tǒng)ID3算法與改進ID3算法生成決策樹，隨后用測試集測試預測準確率，結果見表2。

表2 實驗結果Table 2 Experimental results

不難發(fā)現(xiàn)，改進算法得出的準確率從總體上優(yōu)于傳統(tǒng)ID3算法的準確率。改進的ID3算法引入粗糙集的思想，充分把握條件屬性與決策屬性的邏輯關系，計算屬性的相容度，有效杜絕多值屬性的偏向問題。實驗結果符合理論預期。對于海量數(shù)據(jù)而言，傳統(tǒng)ID3算法需計算條件屬性的信息熵增益，涉及大量對數(shù)運算，而基于粗糙集的改進算法只需求出各個等價類的交集與模值。因此，改進ID3算法更適用于一般數(shù)據(jù)。

5 結 語

本文針對傳統(tǒng)ID3算法中存在的多值屬性偏向問題，提出基于粗糙集的改進方法，計算屬性相容度分裂數(shù)據(jù)集。仿真實驗證明，該方法具有一定的優(yōu)越性。在原有粗糙集的改進思路基礎上，所提方法進一步提出屬性相容度，充分考慮了條件屬性與決策屬性之間的邏輯關系，因而具有更高的預測準確率。