諶章義，伍臨莉

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

0 前言

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

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

本文就是基于粗糙集的基本理論，設(shè)計(jì)了一個分類貢獻(xiàn)函數(shù)來選擇分類貢獻(xiàn)最大的屬性作為分類節(jié)點(diǎn)，使最后生成的決策樹最小。通過在UCI數(shù)據(jù)集上做實(shí)驗(yàn)，與基于信息熵的C4.5算法，以及基于加權(quán)平均粗糙度的決策樹生成算法［3］進(jìn)行了比較。實(shí)驗(yàn)證明:應(yīng)用了分類貢獻(xiàn)函數(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的屬性值。當(dāng)屬性集合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)當(dāng)且僅當(dāng)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 分類貢獻(xiàn)函數(shù)的定義和說明

定義5 分類貢獻(xiàn)函數(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ù)。

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

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

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

算法歸納如下:

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

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

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

3 實(shí)例分析和比較

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

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

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

因?yàn)镃CF(a3)比CCF(a4)大，所以選擇屬性a3作為根節(jié)點(diǎn)。

表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é)點(diǎn)條件。

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

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

圖1 基于信息熵的決策樹和基于分類貢獻(xiàn)值的決策樹

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

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

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

5 結(jié)論

本文利用粗糙集理論中的條件屬性相對于決策屬性的確定性原理，提出了分類貢獻(xiàn)值的概念，分類貢獻(xiàn)值越大，說明該屬性所包含的確定性因素越多，所以將分類貢獻(xiàn)值最大的屬性選為分類屬性來構(gòu)造決策樹，同時通過分類貢獻(xiàn)值來全面地考慮了決策屬性每個劃分對條件屬性選擇的影響，使結(jié)果更接近真實(shí)情況。通過實(shí)驗(yàn)與基于信息熵構(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)懷，張強(qiáng)，等.一種基于粗糙集構(gòu)造決策樹的新方法［J］.計(jì)算機(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.