王子京，劉 毓

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

0 引 言

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

文獻(xiàn)[4]提出加權(quán)平均粗糙度的概念，計(jì)算每個(gè)條件屬性下近似與上近似的加權(quán)比來(lái)判斷該屬性的分類性能。這種方法偏向于屬性的分類效率。

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

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

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

1 ID3 算法原理

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

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

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

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

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

2 粗糙集基本原理

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

2.1 信息系統(tǒng)

2.2 等價(jià)類與不可區(qū)分關(guān)系

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

2.3 屬性協(xié)調(diào)度

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

式中：X是C的非空子集；|?|是求模運(yùn)算。

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

3 改進(jìn)算法

改進(jìn)方法的主要思想是在屬性協(xié)調(diào)度的基礎(chǔ)上，考慮決策規(guī)則間的微觀邏輯關(guān)系，定義一個(gè)屬性相容度。用屬性相容度代替原來(lái)的屬性協(xié)調(diào)度作為分裂節(jié)點(diǎn)的標(biāo)準(zhǔn)。

3.1 主決策集與次決策集

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

3.2 屬性相容度

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

相容度的另一個(gè)表達(dá)式為：

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

3.3 改進(jìn)算法流程

改進(jìn)算法流程如下：

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

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

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

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

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

6）生成決策樹(shù)，剪枝。

3.4 實(shí)例分析

本文以訓(xùn)練樣本集為例說(shuō)明改進(jìn)算法的步驟。訓(xùn)練樣本集見(jiàn)表1。方便起見(jiàn)，4個(gè)條件屬性用A1，A2，A3和A4表示，決策屬性用D表示。易得：

則：

同理，可得：

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

4 實(shí)驗(yàn)及結(jié)果

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

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

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

本文分別應(yīng)用傳統(tǒng)ID3算法與改進(jìn)ID3算法生成決策樹(shù)，隨后用測(cè)試集測(cè)試預(yù)測(cè)準(zhǔn)確率，結(jié)果見(jiàn)表2。

表2 實(shí)驗(yàn)結(jié)果Table 2 Experimental results

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

5 結(jié) 語(yǔ)

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