王 越，萬 洪

(重慶理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

決策樹是一種比較常見的分類分析方法，具有效率高、知識的表達(dá)和規(guī)則的提取易于理解等特點，已得到廣泛的應(yīng)用。目前，構(gòu)造決策樹的方法有很多，其中 Quinlan［1－2］于 1986 年提出的 ID3算法和C4.5算法是最經(jīng)典的。這兩種算法的主要思想是:在各非葉子節(jié)點選擇信息增益最大的屬性(屬性組合)，自頂向下地劃分訓(xùn)練實例集，直到滿足無可分樣本、無剩余屬性或樣本同屬于一個類別等終止條件。但這些方法面臨的主要問題有:傾向于選擇取值較多的屬性，抗噪聲能力差，一棵決策樹中子樹有重復(fù)，以及有些屬性在一棵決策樹中的某一路徑上被多次檢驗，從而降低了分類的效率和效果［1］。

Z.Pawlak教授［3］于 1982 年提出粗糙集理論(rough set)［3］，從另一角度認(rèn)識知識，把論域的分類看作是知識，從而能非常嚴(yán)謹(jǐn)?shù)貙χR進(jìn)行理解。粗糙集理論對問題的處理方式獨特，不需要確定某些問題中的數(shù)量，而是從問題本身出發(fā)，這給決策樹的構(gòu)建帶來了便利。在信息處理、數(shù)據(jù)挖掘等認(rèn)知領(lǐng)域該理論已得到廣泛應(yīng)用［4］?？勺兙却植诩?］(variable precision rough set，VPRS)理論是Ziarko在Z.Pawlak粗糙集模型的基礎(chǔ)上，通過設(shè)定誤差閾值參數(shù)β(0.5≤β＜1)，在一定程度上放寬了對不可分辨關(guān)系的要求，使泛化能力和抗噪聲能力有很大的改進(jìn)。當(dāng)β=1時，變精度粗糙集就變成了Z.Pawlak粗糙集。ID3算法被提出以來，對此算法的改進(jìn)與研究已十分廣泛。文獻(xiàn)［6－8］均在原有算法上利用粗糙集理論進(jìn)行了各種改進(jìn)，這些方法中大部分以分類精度、屬性重要性、屬性依賴度以及正域等度量標(biāo)準(zhǔn)作為條件屬性的選擇條件，并取得了較好的效果。然而，這些改進(jìn)算法有些側(cè)重于屬性某一時刻的分類能力，沒有把屬性間的關(guān)系考慮在內(nèi);有些則側(cè)重于屬性的整體分類效果，忽略了屬性的某一時刻的分類能力，導(dǎo)致最終難以達(dá)到全局最優(yōu)的分類效果。

本文將屬性的當(dāng)前分類能力和屬性間的關(guān)聯(lián)度綜合在一起，提出變精度決策分類熵和信息決策熵的概念，并以信息決策熵作為決策樹屬性選擇的標(biāo)準(zhǔn);將屬性當(dāng)前分類能力和協(xié)調(diào)性相結(jié)合，通過調(diào)節(jié)誤差閾值參數(shù)β，有效地抑制了訓(xùn)練數(shù)據(jù)中的噪聲數(shù)據(jù)帶來的干擾，并允許在構(gòu)造決策樹的過程中劃入正區(qū)的實例類別存在一定的不一致性，簡化生成的決策樹，提高決策樹的泛化能力。理論分析和實驗結(jié)果表明:與經(jīng)典的ID3決策樹算法和文獻(xiàn)［6］中的算法相比，該算法能得到簡潔、高效的決策樹。

1 基于變精度粗糙集的信息決策熵

1.1 粗糙集的相關(guān)概念

粗糙集的基本概念和理論參見文獻(xiàn)［3－4］，本文僅介紹涉及到的基本概念。

定義1 決策系統(tǒng)［3］

一個決策系統(tǒng) S={ U，A，V，f}為一個有序的四元組，其中:U={x1，x2，…，xn}為論域，是所有對象{x1，x2，…，xn}的有限集合;A是屬性的有限集合，A=C∪D，C為條件屬性集，D為決策屬性集，且C∩D=Φ;V=是屬性值的集合，Va是屬性a的值域;f:U×A→V是一個信息函數(shù)，表示任意對象xi的屬性在V上的取值。該系統(tǒng)又稱為信息系統(tǒng)。

定義2 不可分辨關(guān)系［3］和協(xié)調(diào)度［3］

設(shè)決策系統(tǒng) S={ U，A，V，f}，其中 A=C∪D，C為條件屬性集，D為決策屬性集。設(shè)B是屬性集合的一個子集，B在U上產(chǎn)生的一個不可分辨關(guān)系:IND(B)={(x，y)∈U × U:f(x，a)=f(y，a)，?a∈Β}，它表示對象x和y關(guān)于屬性集A的子集B是不可區(qū)分的。

對于?d∈D，B?b的協(xié)調(diào)度為

定義3 下近似和上近似［4］

設(shè)一個子集為X，對象a的論域為U，其中U的一個等價關(guān)系為R，則所有與a不可分辨的對象所組成的集合可表示為[a]R，即由a決定的等價類。當(dāng)集合能表示成基本等價類組成的并集時，則稱集合是可以精確定義的;否則，集合只能通過近似的方式來刻畫。集合X關(guān)于R的下近似定義為

實際上，R－(X)表示的是由某些已有的條件判斷某個對象肯定屬于集合X的所組成的最大的對象的集合，也稱為X的正域，記作POSR(X)。相反，判斷肯定不屬于集合X的對象組成的集合稱為X的負(fù)域，記作NEGR(X)。集合X關(guān)于R的上近似定義為

從表達(dá)式可以看出，R－(X)是[a]R與X相交時所有非空的等價類的并集，是某些對象可能屬于X時所組成的最小集合。

定義4 給定決策系統(tǒng) S={ U，A，V，f}，A=C∪D，C為條件屬性集，D為決策屬性集，對于每個子集和等價關(guān)系 R，U/R={y1，y2，…，yn}，則X的β－下近似和β－上近似可定義為［9］:

1.2 變精度決策分類熵

定義5 給定決策系統(tǒng) S= U，A，V，(f)，其中A=C∪D，C為條件屬性集，D為決策屬性集。對于每個條件屬性Ci∈C，定義式(6)為變精度正目標(biāo)分類比例(||為基數(shù)，即集合中元素的個數(shù))。

定義式(7)為變精度負(fù)目標(biāo)分類比例。

定義式(8)為Ci相對于D的變精度決策分類熵。

γ( Ci)與ID3算法中的信息熵的形式相類似，代表條件屬性分類能力的強(qiáng)度，由于精度因子β的存在，故稱其為屬性Ci相對于決策屬性D的變精度決策分類熵，簡稱屬性Ci的變精度決策分類熵。

1.3 屬性選擇標(biāo)準(zhǔn)——信息決策熵

由以上分析可得:變精度決策分類熵是條件屬性相對于目標(biāo)分類的分類能力的度量。在基于變精度決策分類熵進(jìn)行分類時，其分類思想是:希望能先識別出一部分對象，每次盡量減少分類對象的數(shù)量，并且通過調(diào)節(jié)精度因子β來提高決策樹的泛化能力。變精度決策分類熵也能在構(gòu)造決策樹時簡化算法，因為它不需要考查屬性的每一種可能的取值，同時它以目標(biāo)分類作為參照，可以對屬性的選擇范圍進(jìn)行約束，減少了算法的運行時間，同時選擇分類能力高的屬性可以構(gòu)建優(yōu)越的決策樹。但是令人遺憾的是，此方法沒有考慮屬性間的依賴關(guān)系和當(dāng)前屬性對將來分類的影響，僅僅是將屬性的當(dāng)前分類能力作為屬性的選擇標(biāo)準(zhǔn)。為了更好地優(yōu)化算法，把屬性之間的協(xié)調(diào)度考慮進(jìn)來，將兩者相結(jié)合得到屬性選擇依據(jù)的新指標(biāo)——屬性 B的信息決策熵(information decision entropy，IDE)?？紤]單變量決策樹情況，B={ Ci}，Ci∈C，則有

式(9)中α是權(quán)重系數(shù)，用來調(diào)節(jié)屬性選擇的側(cè)重性，是IDE( Ci)屬性選擇要求的綜合體現(xiàn)。α的值對分類的結(jié)果是有影響的，但是為了達(dá)到預(yù)期要求，可以根據(jù)分類效果來調(diào)整 α的取值。由IDE( Ci)的定義可知，IDE(Ci)的取值范圍是［0，1］。因此，IDE( Ci)的值越大，屬性集中的對象屬于同一類別的概率就越大，IDE( Ci)的值為1表示每個屬性集中的對象屬性為同一類別。

2 基于信息決策熵的決策樹構(gòu)造算法(IDEDT)

2.1 數(shù)據(jù)預(yù)處理

連續(xù)屬性離散化:連續(xù)的屬性只有經(jīng)過離散化后才能應(yīng)用在粗糙集理論中。目前，有關(guān)連續(xù)屬性的離散化已有多種方法，如基于動態(tài)層次聚類離散化［10］、基于信息熵［11］等。

條件屬性約簡:為使空間降維，屬性必須經(jīng)過約簡處理。目前關(guān)于屬性(知識)的約簡也有多種方法，如基于可辨識矩陣的約簡［12］、基于互信息的約簡［13］、基于二進(jìn)制區(qū)分矩陣的約簡［14］等。

2.2 決策樹的構(gòu)造

把信息決策熵作為屬性選擇依據(jù)來進(jìn)行決策樹構(gòu)建的基本思想是:首先根據(jù)計算選擇最佳的條件屬性，特殊情況下，當(dāng)精度因子β取某一值時，某條件屬性的變精度正目標(biāo)分類比例為0，此時，此屬性的變精度決策分類熵計算沒有意義。這種情況下，令其信息決策熵等于屬性協(xié)調(diào)度，并將其作為屬性選擇的標(biāo)準(zhǔn)。當(dāng)所有條件屬性的變精度正目標(biāo)分類比例均為0時，調(diào)節(jié)精度因子β重新計算。當(dāng)某條件屬性的變精度正目標(biāo)分類比例為1時，優(yōu)先選擇此屬性作為測試屬性，不再計算其他屬性的信息決策熵，以提高算法運行效率。計算出最佳屬性計算之后，用此屬性作為依據(jù)去構(gòu)造決策樹，該屬性的值的個數(shù)決定決策樹的分支數(shù)。之后，再在每一個分支中用同樣的方法選擇劃分屬性。同時，為避免決策樹中屬性的重復(fù)選取，在屬性集合中將選擇過的屬性刪除。當(dāng)決策樹的某一分支中的所有對象都屬于一個決策類時，就把該分支設(shè)為葉結(jié)點，結(jié)點名為該決策類名，算法直到樹中所有的分支都到達(dá)葉結(jié)點時結(jié)束。

現(xiàn)將本文提出的基于信息決策熵的決策樹構(gòu)造的算法描述如下:

輸入:決策系統(tǒng) S={ U，A，V，f}，A=C∪D，C為條件屬性集，D為決策屬性集，精度因子β，權(quán)重系數(shù)α。

輸出:單變量決策樹T。

算法步驟:

步驟1 初始化，對決策系統(tǒng)S進(jìn)行約簡，其中的一個約簡記為:S'=(U'，C'∪D)。

步驟2 構(gòu)造一個根節(jié)點為N(M，C)的樹，其中M和C分別為全體樣本集和全體屬性集。

步驟3 IF U'為空，則返回。

步驟4 IF U'中的全部樣本都屬于同一類C，則返回N為葉節(jié)點，并標(biāo)記為類C。

步驟5 IF C'為空，則返回N為葉節(jié)點，標(biāo)記N中出現(xiàn)最多的類。

步驟6 對 C'中的每一個條件屬性a∈C'，做以下操作:

1)根據(jù)a和決策屬性D，得到對U'的初始劃分模式(等價類);

2)根據(jù)劃分模式，計算a與決策屬性D之間的協(xié)調(diào)度;

3)計算a的決策分類熵;

4)計算a的信息決策熵IDE( a)。

步驟7 選擇信息決策熵最大的屬性作為測試屬性，假設(shè)測試屬性為a，根據(jù)a的不同取值將U'分為V個不相交的子集 U'j(j=1，2，…，v)。在每個子集中構(gòu)成一個分支，隨后從條件屬性集中刪除選取過的屬性a，即C'=C'－a;當(dāng)所有條件屬性的信息決策熵均為0時，調(diào)節(jié)精度因子β，重復(fù)步驟6。

步驟8 對于每個分支，遞歸的調(diào)用IDEDT( Uj，C'∪D)。

步驟9 返回。

3 實例分析

下面采用文獻(xiàn)［6］中的決策系統(tǒng)作為數(shù)據(jù)源，分別同文獻(xiàn)［6，8］中提出的算法進(jìn)行比較。決策系統(tǒng)如表1所示。

表1 決策系統(tǒng)

為了方便和其他2種算法進(jìn)行比較，決策系統(tǒng)沒有進(jìn)行約簡，其中:論域 U={1，2，3，…，12};條件屬性 C={a1，a2，a3，a4};決策屬性 d={1，2}。取 β=0.8，α=0.3，IDEDT 方法構(gòu)造決策樹的過程如下(只計算a1的信息決策熵):

根據(jù)算法，取最大的信息決策熵作為測試屬性，故選a1。填充當(dāng)前節(jié)點構(gòu)建子節(jié)點并判斷它們是否滿足終止條件，發(fā)現(xiàn)當(dāng)a1等于1時，論域中只有一個對象不能被正確分類，其精確度為7/8=0.875＞0.8。因此，可以認(rèn)為a1等于1時滿足終止條件。a1=2時不滿足終止條件，則對它們分別遞歸調(diào)用構(gòu)建算法。最后建立的決策樹如圖1所示。

圖1 IDEDT算法構(gòu)造的決策樹

圖1是基于本文提出的IDEDT算法構(gòu)造的決策樹。從圖1可以看到:決策樹的復(fù)雜性(樹中所有節(jié)點的個數(shù))為6，葉節(jié)點數(shù)為4，對應(yīng)規(guī)則為4條。圖2是文獻(xiàn)［8］中提出的算法構(gòu)造的決策樹，其復(fù)雜性和節(jié)點個數(shù)和本文算法一樣。圖3是利用文獻(xiàn)［6］中的算法構(gòu)造的決策樹，決策樹的復(fù)雜性為8，葉節(jié)點數(shù)為5，對應(yīng)規(guī)則為5條。圖4是基于信息熵的算法構(gòu)造的決策樹，決策樹的復(fù)雜性為12，葉節(jié)點數(shù)為7，對應(yīng)規(guī)則為7條?？梢园l(fā)現(xiàn)，本文中的算法以及文獻(xiàn)［6］和文獻(xiàn)［8］中的算法相比原始的基于信息熵的ID3算法都有一定的改進(jìn)。然而本文算法和文獻(xiàn)［8］中的算法在本實例中構(gòu)造的決策樹的復(fù)雜性相差不大，而且本文算法的計算還相對復(fù)雜。在實驗部分把這4種算法在不同的數(shù)據(jù)集中進(jìn)行比較，可以發(fā)現(xiàn):本文中的IDEDT算法相比其他算法而言，它構(gòu)造出的決策樹在深度、規(guī)模、規(guī)則、長度等方面都有明顯的優(yōu)勢。主要原因在于本文算法中的屬性選擇標(biāo)準(zhǔn)信息決策熵綜合考慮了條件屬性的當(dāng)前分類能力和條件屬性與決策屬性之間的依賴度，而且算法中的精度因子使決策樹的泛化能力有很大的提高。為了避免屬性的重復(fù)選取，將選取過的條件屬性從屬性集中刪除，從而使生成的決策樹規(guī)模小而分類能力強(qiáng)。

圖2 文獻(xiàn)［8］中算法構(gòu)造的決策樹

圖3 文獻(xiàn)［6］中算法構(gòu)造的決策樹

圖4 ID3算法構(gòu)造的決策樹

表2 不同算法生成的決策樹的比較(準(zhǔn)確率/%)

4 實驗結(jié)果

為了測試算法的性能，本文在UCI［16］提供的部分?jǐn)?shù)據(jù)集上分別運行了IDEDT算法、文獻(xiàn)［6］中的算法、文獻(xiàn)［8］中的算法和傳統(tǒng)的基于信息熵的ID3算法，所選的數(shù)據(jù)集都經(jīng)過了數(shù)據(jù)的預(yù)處理。用10層交叉的方法測試3種方法構(gòu)造的決策樹的平均分類精確度，對于沒有測試集的數(shù)據(jù)集按照2∶1的比例劃分成相應(yīng)的訓(xùn)練集和測試集。同時為了更好地對這3種算法進(jìn)行比較，隨機(jī)抽取每一個數(shù)據(jù)集，把它分為10個不同的子集;然后，用上述4種算法分別在數(shù)據(jù)子集上進(jìn)行決策樹的構(gòu)造;最后對平均葉子節(jié)點數(shù)進(jìn)行統(tǒng)計，并且在不同的算法參數(shù)α設(shè)置下進(jìn)行實驗計算，確定合適的算法參數(shù)取值。得到的結(jié)果如表2所示。沒有特別說明時，實驗中取 β=0.8。

從表2可以看出，與基于信息熵的ID3方法和文獻(xiàn)中的算法相比較，基于信息決策熵的方法有較高的平均分類精確度，同時構(gòu)造的決策樹有較低的復(fù)雜性。

作為一種分類算法，分類的準(zhǔn)確率和從樹中導(dǎo)出的規(guī)則的簡潔程度都是衡量決策樹性能優(yōu)越性的一種重要指標(biāo)，規(guī)模越小的決策樹產(chǎn)生的規(guī)則越簡潔，有利于規(guī)則的理解和使用。由于IDEDT算法并不是對所有訓(xùn)練數(shù)據(jù)進(jìn)行精確匹配，而是還考慮了條件屬性的當(dāng)前分類能力和條件屬性與決策屬性之間的依賴度，因而，同ID3算法、文獻(xiàn)［6］的算法以及文獻(xiàn)［8］中的算法相比，構(gòu)建的決策樹規(guī)模大幅度降低。同時也說明本文算法相對于文獻(xiàn)［8］中的算法，在處理大的數(shù)據(jù)集時有更好的效果。

5 結(jié)束語

本文在變精度粗糙集理論基礎(chǔ)上進(jìn)行分析，引出了信息決策熵的概念，并將其應(yīng)用于決策樹的構(gòu)建。信息決策熵綜合考慮條件屬性的當(dāng)前分類能力和條件屬性與決策屬性之間的依賴度。實例分析實驗證明。本文的算法是有效的，但對于IDEDT算法暫且只能處理離散型的數(shù)據(jù)，下一步工作將是對算法進(jìn)行修改使其能處理連續(xù)型的數(shù)據(jù)。另外，IDEDT算法中的兩個參數(shù)α和β對算法的分類精度的影響與數(shù)據(jù)集中數(shù)據(jù)的具體分布有關(guān)，尋求最佳的α和β以提高算法的性能將是下一步的工作重點。

［1］Quinlan J R.Induction of Decision Trees［J］.Machine Learning，1986，1(1):81 －106.

［2］Quinlan J R.C4.5:Programs for Machine Learning［M］.San Mateo，CA:Morgan Kaufmann，1993.

［3］Pawlak Z.Rough Sets［J］.International Journal of Computer Information Science，1982，11(5):341 －356.

［4］韋萍萍.結(jié)合ROUGH集的決策樹構(gòu)建方法［J］.重慶工學(xué)院學(xué)報:自然科學(xué)版，2007，21(8):101－103.

［5］Ziarko W.Variable precision rough set model［J］.Journal of Computer and System Sciences，1993，46(1):39 －59.

［6］董廣，王興起.基于決策分類熵的決策樹構(gòu)造算法及應(yīng)用［J］.計算機(jī)應(yīng)用，2009，29(11):3104 －3016.

［7］蔣蕓，李戰(zhàn)懷，張強(qiáng)，等.一種基于粗糙集構(gòu)造決策樹的新方法［J］.計算機(jī)應(yīng)用，2010，24(8):21 －23.

［8］常志玲，周慶敏.基于變精度粗糙集的決策樹優(yōu)化算法研究［J］.計算機(jī)工程與設(shè)計，2006，27(17):3175－3177.

［9］龐哈利，高政威，左軍偉，等.基于變精度粗糙集的分類決策樹構(gòu)造方法［J］.系統(tǒng)工程與電子技術(shù)，2008，30(11):2161－2163.

［10］苗奪謙.Rough Set理論中連續(xù)屬性的離散化方法［J］.自動化學(xué)報，2009，27(3):296 －302.

［11］Han jiawei，Kamber M.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京:機(jī)械工業(yè)出版社，2001.

［12］常犁云，王國胤，吳渝.一種基于Rough set理論的屬性約簡及規(guī)則提取方法［J］.軟件學(xué)報，2009，10(11):1206－1211.

［13］苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法［J］.計算機(jī)研究與發(fā)展，2010，36(6):681 －684.

［14］楊萍，李濟(jì)生，黃永宣.一種基于二進(jìn)制區(qū)分矩陣的屬性約簡算法［J］.信息與控制，2010，38(1):70 －74.

［15］Blake C，Merz C J.UCI repository of machine learning databases［EB/OL］.［2002 －09 －20］.http://www.ics.uci.edu/～ mlearn/MLRepository.