應(yīng)用分類貢獻函數(shù)的決策樹構(gòu)造方法

諶章義，伍臨莉

(洛陽師范學(xué)院信息技術(shù)學(xué)院，河南洛陽471022)

0 前言

在決策樹的構(gòu)建中一個關(guān)鍵問題就是選擇合適的分類屬性，使最后生成的決策樹最小，也就是說決策樹的分支最少。目前，已有多種選擇屬性構(gòu)造決策樹的方法，如ID3(以及其改進算法C4.5)、CART、CHAID、QUEST等，其中最經(jīng)典的就是Quinlan提出的基于信息熵的方法ID3，C4.5［1］。這種方法已廣泛應(yīng)用于實際的分類問題。但是基于信息熵的方法存在的主要問題是一棵決策樹中子樹有重復(fù)，而且有些屬性會在一棵決策樹中的某一路徑上被多次檢驗，從而降低了分類的效率和效果。

為此，很多學(xué)者在決策樹生成算法中引入了粗糙集的概念，以提高分類效率［2－9］。粗糙集理論是波蘭數(shù)學(xué)家Pawlak在1982年提出的一種分析數(shù)據(jù)的數(shù)學(xué)理論［10］，主要用來處理不確定和不精確信息。其特點是不需要預(yù)先給定某些特征和屬性的數(shù)量描述，而是直接從給定問題的描述集合出發(fā)，找出該問題的內(nèi)在規(guī)律，其基本思想更接近現(xiàn)實情況。該理論已廣泛應(yīng)用于數(shù)據(jù)挖掘、人工智能、模式識別等認知領(lǐng)域。

本文就是基于粗糙集的基本理論，設(shè)計了一個分類貢獻函數(shù)來選擇分類貢獻最大的屬性作為分類節(jié)點，使最后生成的決策樹最小。通過在UCI數(shù)據(jù)集上做實驗，與基于信息熵的C4.5算法，以及基于加權(quán)平均粗糙度的決策樹生成算法［3］進行了比較。實驗證明:應(yīng)用了分類貢獻函數(shù)后，構(gòu)造的決策樹與傳統(tǒng)的基于信息熵方法構(gòu)造的決策樹相比較，其復(fù)雜性低，且能有效提高分類效果。

1 相關(guān)概念與原理

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

一個決策系統(tǒng)是一個有序四元組:S=(U，A，V，f)，其中U是全域，是由對象構(gòu)成的集合，U={x1， x2，…，xm};A是屬性集合，A=C∪D，其中C是條件屬性集，D是決策屬性集;V=Va是屬性值的集合，Va是屬性a的值域;f:U×A→V是一個信息函數(shù)，對每一個a∈A和x∈U，定義了一個信息函數(shù)f(x，a)∈Va，即信息函數(shù)f指定U中每一個對象x的屬性值。當屬性集合A不劃分為條件屬性子集合和決策屬性子集合時，該系統(tǒng)又稱為信息系統(tǒng)。

定義2核

設(shè)P?C，若γP=γC，且不存在R?P，使得γR=γC，則稱P為C的一個(相對于決策屬性D的)屬性約簡。所有C的屬性約簡的交稱為C的核，記為Core(C)。

屬性a∈Core(C)當且僅當a是不可缺少的屬性。

定義3 不可區(qū)分關(guān)系

對決策系統(tǒng)S=(U，A，V，f)，?B?A是條件屬性集合的一個子集，稱二元關(guān)系IND(B)為S的不可區(qū)分關(guān)系:IND(B)={(x，y)∈U×U?a∈B，f(x，a)=f(y，a)}。它表示對象x和y關(guān)于屬性集A的子集B是不可區(qū)分的。

定義4 區(qū)分矩陣

所謂一個區(qū)分矩陣S，記作M(S)，是如下定義的一個n×n矩陣:

因此，矩陣元素cij是區(qū)分對象xi和xj的所有屬性的集合。

很容易看出，若B是A的滿足下面條件的一個最小子集，則B?A是A的縮減，B∩c≠φ，對于M(S)中任一非空元素c(c≠φ)。

換句話說，縮減是這樣的屬性最小子集，它能區(qū)分用整個屬性集可區(qū)分的所有對象。

2 屬性選擇原理和算法

2.1 分類貢獻函數(shù)的定義和說明

定義5 分類貢獻函數(shù)

對決策系統(tǒng)S=(U，A，V，f)，xi，xj∈U，A是屬性集合，A=C∪D，其中C是條件屬性集;D是決策屬性集。其對應(yīng)的區(qū)分矩陣是M(S)，ak是核中的一個屬性，cij是M(S)的矩陣元素。

這里，cij∩ak≠φ。I(cij∩ak)=1，如果ak是矩陣元素cij的一個屬性;否則，I(cij∩ak)=0。n(cij)是矩陣元素cij中的屬性個數(shù)。

分類貢獻函數(shù)CCF(ak)的前面一部分的決策屬性不同，d(xi)≠d(xj)，這表明屬性對象xi，xj不屬于同一類，所以ak適合于作分類節(jié)點;后面一部分的決策屬性相同。d(xi)=d(xj)，表明對象xi，xj屬于同一類，所以ak不適合作為分類節(jié)點。而則是屬性ak在區(qū)分矩陣元素cij中所占的比重。這樣前后兩部分差值就是所希望得到的分類貢獻值，該值越大，那么說明該屬性越適合作為分類節(jié)點。

2.2 基于分類貢獻函數(shù)的決策樹構(gòu)造算法(CCF)

基本思想是:先使用區(qū)分矩陣確定屬性的核(如果沒有核，則用其縮減)，然后通過分類貢獻函數(shù)確定核中各個屬性的分類貢獻值，取值大的屬性作為節(jié)點。接著用選擇的屬性去劃分決策系統(tǒng)，相應(yīng)于該屬性的每一個取值產(chǎn)生一個子集，再在每一個子集中用同樣的方法選擇分類屬性作為節(jié)點。這一算法遞歸地應(yīng)用到導(dǎo)出的每一個分支上，直到樹中所有分支都到達葉節(jié)點為止。

算法歸納如下:

(1)根據(jù)決策表生成區(qū)分矩陣，確定核，有3種情況:①沒有核，則求出其最小縮減。②核中只有一個屬性。③核中有多個屬性。

(2)節(jié)點條件:①計算縮減里面屬性的分類貢獻函數(shù)值，選擇值最大的一個屬性作為節(jié)點。②選擇這個核作為節(jié)點，不用計算。③計算核中各屬性的分類貢獻函數(shù)值，選擇值最大的一個屬性作為節(jié)點。

(3)根據(jù)所選定屬性的不同取值，將決策系統(tǒng)分為不同子集，在每一個子集中分別重復(fù)步驟(1)和步驟(2)，直到所有的對象都劃定到某一類中。

3 實例分析和比較

本算法與經(jīng)典的基于信息熵算法的主要區(qū)別在于選擇分類屬性的標準不同。下面通過決策表實例對二者構(gòu)造的決策樹進行比較，見表1和表2。

由上述分類貢獻函數(shù)算法來構(gòu)造決策樹，首先生成相應(yīng)的區(qū)分矩陣:

步驟1:構(gòu)造表1的區(qū)分矩陣，通過表2的區(qū)分矩陣可以很容易求得核{a3，a4}，這里核有兩個屬性，要分別計算它們的分類貢獻值以決定取那一個作為根節(jié)點。屬性a3，a4的分類貢獻函數(shù)計算如下:

因為CCF(a3)比CCF(a4)大，所以選擇屬性a3作為根節(jié)點。

表1 決策表

表2 決策表對應(yīng)的區(qū)分矩陣

步驟2:根據(jù)屬性a3的不同取值將決策表系統(tǒng)分為3個子集:a3=1，a3=2和a3=3。

步驟3:應(yīng)用相同的過程在a3=1，a3=2和a3=3的子集上直到它們滿足節(jié)點條件。

圖1a是在表1上基于信息熵的方法構(gòu)造的決策樹，而圖1b就是用該方法在表1的決策表上構(gòu)造的決策樹。從圖1的兩個決策樹中可以看到:圖1a中決策樹的復(fù)雜性(樹中所有結(jié)點的個數(shù))為12，對應(yīng)7個葉結(jié)點;圖1b中決策樹的復(fù)雜性為10，對應(yīng)6個葉結(jié)點。顯然從樹的大小來看，前者比后者少2個結(jié)點，少1個葉結(jié)點。通過這個簡單的例子可以看出:本文提出的基于分類貢獻值的概念構(gòu)造的決策樹可以降低樹的復(fù)雜性。這意味著存儲同一信息表所對應(yīng)的決策樹，基于分類貢獻值的方法比基于信息熵的方法所占用的空間少;又由于前者比后者得到的葉結(jié)點少，所以更易于作決策;同時也避免了在決策樹的一條路徑上多次檢驗?zāi)骋粚傩缘膯栴}。

4 實驗結(jié)果

圖1 基于信息熵的決策樹和基于分類貢獻值的決策樹

在UCI［10］提供的數(shù)據(jù)集上分別運行了分類貢獻函數(shù)和C4.5，用十倍交叉的方法驗證兩種方法構(gòu)造決策樹的分類精度。本文的算法用C++語言實現(xiàn)，在PentiumⅣ3.2 GHz處理器、512 M內(nèi)存、WindowsXP環(huán)境下運行。C4.5的源程序來自［11］。表3給出了實驗結(jié)果。

從表3中可以看出:與基于信息熵的方法C4.5相比較，基于分類貢獻值的方法有較好的平均分類精確度，同時構(gòu)造的決策樹有較低的復(fù)雜性。與文獻［3］基于加權(quán)平均粗糙度的決策樹生成算法相比，分類效果基本相同。但是基于加權(quán)平均粗糙度的決策樹生成算法要計算所有屬性的平均粗糙度，而本算法只計算核(或其縮減)里面的屬性。

表3 兩生成算法在UCI數(shù)據(jù)集上的比較

5 結(jié)論

本文利用粗糙集理論中的條件屬性相對于決策屬性的確定性原理，提出了分類貢獻值的概念，分類貢獻值越大，說明該屬性所包含的確定性因素越多，所以將分類貢獻值最大的屬性選為分類屬性來構(gòu)造決策樹，同時通過分類貢獻值來全面地考慮了決策屬性每個劃分對條件屬性選擇的影響，使結(jié)果更接近真實情況。通過實驗與基于信息熵構(gòu)造決策樹的方法相比較，用本文提出的方法所構(gòu)造的決策樹，復(fù)雜性低，且有較高的平均分類精確度。

［1］ Quinlan JR.C4.5:Programs for Machine Learning［M］.San Mateo，CA:Morgan Kaufmann，1993.

［2］ Chandra B，Varghese PP.Moving Towards Efficient Decision Tree Construction［J］.Information Sciences，2009，179:1059－1069.

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

［4］ 張先榮.粗糙集理論在智能數(shù)據(jù)分析中的應(yīng)用［J］.河南科技大學(xué)學(xué)報:自然科學(xué)版，2008，29(5):88－90.

［5］ 程楠，祝彥知.基于模糊積分多元決策模型的電源開發(fā)排序［J］.河南科技大學(xué)學(xué)報:自然科學(xué)版，2009，30(2):45－49.

［6］ Chandra B，Kothari R，Paul P.A New Node Splitting Measure for Decision Tree Construction［J］.Pattern Recognition，2010，43(8):2725－2731.

［7］ Geetha S，Ishwarya N，Kamaraj N.Evolving Decision Tree Rule Based System for Audio Stego Anomalies Detection Based on Hausdorff Distance Statistics［J］.Information Sciences，2010，180(13):2540－2559.

［8］ Shi L，Weng M，Ma X M，et al.Rough Set Based Decision Tree Ensemble Algorithm for Text Classification［J］.Journal of Computational Information Systems，2010，6(1):89－95.

［9］ Pawlak ZW.Rough Sets and Intelligent Data Analysis［J］.Information Sciences，2002，147:1－12.

［10］ Murphy P，AhaW.UC Irvine Machine Learning Repository［DB/OL］.http://archive.ics.uci.edu/ml/，2009.

［11］ Zhou ZH.AISoftwares＆Codes［CP/OL］.http://cs.nju.edu.cn/zhouzh/zhouzh.files/ai_resource/software.htm，2009.