應用分類貢獻函數的決策樹構造方法

諶章義，伍臨莉

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

0 前言

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

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

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

1 相關概念與原理

定義1 決策系統

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

定義2核

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

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

定義3 不可區分關系

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

定義4 區分矩陣

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

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

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

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

2 屬性選擇原理和算法

2.1 分類貢獻函數的定義和說明

定義5 分類貢獻函數

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

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

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

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

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

算法歸納如下:

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

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

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

3 實例分析和比較

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

由上述分類貢獻函數算法來構造決策樹，首先生成相應的區分矩陣:

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

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

表1 決策表

表2 決策表對應的區分矩陣

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

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

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

4 實驗結果

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

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

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

表3 兩生成算法在UCI數據集上的比較

5 結論

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

［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］ 蔣蕓，李戰懷，張強，等.一種基于粗糙集構造決策樹的新方法［J］.計算機應用，2004，24(8):21－23.

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

［5］ 程楠，祝彥知.基于模糊積分多元決策模型的電源開發排序［J］.河南科技大學學報:自然科學版，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.