幾何平均參與評價劃分屬性的決策樹

王 卓，聶 斌，羅計根

(1.南昌大學 軟件學院，江西 南昌 330047；2.江西中醫藥大學 計算機學院，江西 南昌 330004)

0 引 言

屬性選擇度量作為啟發式方法，很大程度上決定了決策樹的分類效果，是決策樹研究的關注點之一。

信息增益準則對可取值數目較多的屬性有所偏好，信息增益率準則對可取值數目較少的屬性有所偏好[1,2]，隨后有CART、PUBLIC、SPRINT算法等，另外，也有從剪枝的角度優化決策樹。還有一些研究者從其它方面改進決策樹算法[3-15]，取得了較好的效果。文中側重折中劃分屬性受屬性取值多少的影響，提出幾何平均參與評價劃分屬性的決策樹研究。

1 信息增益與信息增益率

常用的屬性選擇度量有：信息增益、信息增益率和基尼指數。為了折中劃分屬性受屬性取值多少的影響，采用幾何平均參與評價劃分屬性。便于描述，期望、信息增益、信息增益率的相關定義、定理、公式等請參見文獻[1,2]。

1.1 信息增益

假設期望為Info(·)，則對訓練集D中的元組分類所需要的期望為

(1)

設按屬性A劃分對訓練集D的元組分類所需要的期望信息為

(2)

則信息增益為

Gain(A)=Info(D)-InfoA(D)

(3)

1.2 信息增益率

分裂信息

(4)

信息增益率為

(5)

實踐過程中，因為信息增益率準則對可取值數目較少的屬性有所偏好，所以，C4.5算法并不是直接選擇信息增益率最大的候選劃分屬性，而是使用了一個啟發式算法。計算屬性的全部未用屬性算術平均信息增益方法為

(6)

2 信息增益和信息增益的幾何平均值

信息增益和信息增益的幾何平均值(geometric average of information gain and information gain rate，GAIGIGR)計算方法如下

(7)

(8)

3 基于信息增益與信息增益率的幾何平均值建立決策樹算法

為了折中劃分屬性受屬性取值多少的影響，基于信息增益與信息增益率的幾何平均值(GAIGIGR)建立決策樹算法的基本思想為：首先，從候選劃分屬性中，篩選出高于信息增益算術平均水平的屬性；然后，分別計算這些屬性的信息增益率和信息增益的幾何平均值，從中選擇幾何平均值最大的屬性，建立分支決策；最后，用遞歸方法建立決策樹。

3.1 算法描述

GAIGIGR決策樹算法描述為：

輸入：訓練數據集D，屬性集A，閾值ε；

輸出：決策樹T。

(1)如果訓練集D中所有元組屬于同一類Cj，則置Tree為單結點樹，并將Cj作為該結點的類，返回Tree；

(2)否則，沒有剩余屬性用以劃分元組，采用多數表決方式，將訓練集D中元組最多的類Cj作為該結點的類，返回Tree；

(3)否則，按式(3)計算A中各屬性對D的信息增益，并從大到小排序；

(4)按式(6)計算A中各屬性對D的信息增益的算術平均值；

(5)結合(3)(4)，刪除小于信息增益算術平均值的屬性信息增益；

(6)按式(7)或式(8)求剩下屬性的信息增益和信息增益率的幾何平均值GAIGIGR(A)，選擇該值最大的屬性Ag；

(7)如果Ag的值小于閾值ε，則置T為單結點樹，并將D中實例數最大的類Cj作為該結點的類，返回T；

(8)否則，對Ag中的每一可能值ai，依Ag=ai將D分割為子集，即若干非空Di，將Di中實例數最大的類作為標記，構建子結點，由結點及其子結點構成樹T，返回T；

(9)對結點i，以Di為訓練集，以A-{Ag}為屬性集，遞歸地調用(1)～(8)，得到子樹Ti，返回Ti。

3.2 算法的理論分析

信息增益與信息增益率的幾何平均，參與評價劃分屬性，生成決策樹，減少了對屬性取值多與取值少的偏好，從而盡可能地減少生成不平衡樹的可能性，同時減少過擬合現象，在一定程度上可以提高分類準確性和提升生成決策樹的效率。

4 實驗與結果

為了驗證采用信息增益與信息增益率幾何平均值選擇分裂屬性建立決策樹算法有效性，選取了ID3、C4.5，以及CART這3個經典算法進行比較。

4.1 實驗數據及說明

實驗采用了4份數據，包括Iris數據集(http://archive.ics.uci.edu/ml/datasets/Iris)，Breast Cancer Wisconsin數據集(http://archive.ics.uci.edu/ml/datasets/Breast+Can-cer+Wisconsin+%28Original%29)，天氣數據集(http://blog.csdn.net/czp11210/article/details/51161531),QSAR biodegradation Data Set(http://archive.ics.uci.edu/ml/datasets/QSAR+biodegradation)。

Iris數據集：條件屬性(自變量)4個，分類屬性(因變量)1個，樣本總數為150條。

Breast Cancer Wisconsin數據集：條件屬性有腫塊厚度、細胞大小的均勻性、細胞形狀的均勻性、邊際附著力等9個，分類屬性1個，樣本總數為699條。

天氣集數據：4個自變量，并且全部為離散型自變量，因變量1個，樣本總數13條。

QSAR biodegradation Data Set：41個自變量(屬性)，樣本總數1055條。

以上數據集實驗驗證時，按7∶3比例，隨機將樣本分成訓練集和測試集建模，葉子節點最大容許個數為3；葉子節點最大容許誤差為0.001。另外，天氣數據集樣本較少，用五折交叉驗證的方式進行建模，其它數據集采用十折交叉驗證的方式進行建模。

4.2 實驗結果

計算設備配置為：AMD A10-8700P Radeon R6，10Compute Cores 4C+6G 1.80 GHz，RAM 8.00 GB，64位操作系統。對以上4份實驗數據，利用信息增益和信息增益的幾何平均值GAIGIGR、信息增益(information gain，IG)(ID3)、信息增益率(information gain rate，IGR)(C4.5)以及GINI指數(CART)作為屬性劃分的標準，建立決策樹模型。分別就不同數據集的分類準確性、計算時間等方面進行比較分析，比較的結果如圖1至圖7，圖表采用Microsoft Office excel 2007編輯制作，圖中下半區為實驗結果的數據信息，上半區是以柱形和顏色為標識的圖形區；橫坐標為各種劃分屬性的方法，縱坐標表示分類準確度；上半區柱形從左至右排列，對應下半區數據從上至下的行，并與顏色對應。圖表相關的表述說明：(ID3+C4.5+CART)/3是ID3、C4.5、CART這3種方法結果的平均數。

圖1 鳶尾花數據集的分類預測結果比較

圖2 鳶尾花數據集的計算時間結果比較

(1)Iris數據集的實驗結果

1)準確性比較：①在訓練集、測試集及十次十折交叉驗證單方面：4種屬性劃分的準確性都很高，稍各有優勢；②在訓練集、測試集及十次十折交叉驗證的平均數方面：GAIGIGR在3種測試方法中的準確性平均值最高；③在信息增益、信息增益率以及GINI指數三者結果的平均值而言：GAIGIGR的準確性在訓練集、測試集稍高，在10次10折交叉驗證稍低。

2)計算時間比較

采用4種屬性劃分標準建立決策樹、計算其準確性、生成決策樹圖等，GAIGIGR方法的運行時間僅為16 ms，是4種方法中時間最少的，且優勢明顯。

圖3 乳腺癌數據集的分類預測結果比較

圖4 乳腺癌數據集的計算時間結果比較

圖5 天氣數據集的分類預測結果比較

圖6 QSAR biodegradation 數據集的分類預測結果比較

圖7 QSAR biodegradation 數據集的計算時間結果比較

(2)Breast Cancer Wisconsin數據集的實驗結果

1)準確性比較：①在訓練集、測試集及10次10折交叉驗證單方面：4種屬性劃分的準確性都很高，稍各有優勢；②在訓練集、測試集及10次10折交叉驗證的平均數方面：GAIGIGR方法比C4.5方法好；③在信息增益、信息增益率以及GINI指數三者結果的平均值而言：GAIGIGR的準確性在訓練集、測試集稍低；在10次10折交叉驗證稍高。

2)計算時間比較

采用4種屬性劃分標準建立決策樹、計算其準確性、生成決策樹圖等，GAIGIGR的計算時間比信息增益稍高，但比信息增益率以及GINI指數計算時間要低得多。

(3)天氣集數據的實驗結果

1)準確性比較：①在訓練集、測試集及10次10折交叉驗證單方面：4種屬性劃分的準確性都不穩定，在訓練集上較高，在測試集及5次5折交叉驗證方面，波動較大；②在訓練集、測試集及10次10折交叉驗證的平均數方面：GAIGIGR方法比CART方法好；③在信息增益、信息增益率以及GINI指數三者結果的平均值而言：GAIGIGR的準確性在訓練集持平，在測試集稍低，在5次5折交叉驗證稍高。

2)計算時間比較

采用4種屬性劃分標準建立決策樹、計算其準確性、生成決策樹圖等，計算時間都接近于0，效果都很好。

(4)QSAR biodegradation Data Set的實驗結果

1)準確性比較：①在訓練集、測試集及10次10折交叉驗證單方面：4種屬性劃分的準確性都不夠穩定，在訓練集上較高，在測試集及10次10折交叉驗證方面，波動較大；②在訓練集、測試集及10次10折交叉驗證的平均數方面：GAIGIGR方法最好；③在信息增益、信息增益率以及GINI指數三者結果的平均值而言：GAIGIGR的準確性在訓練集持平，在測試集稍低，在5次5折交叉驗證稍高。

2)計算時間比較

對于本數據集而言，GAIGIGR的計算時間比信息增益稍高，但明顯優于信息增益率以及GINI指數計算時間。

5 結束語

通過4份不同規模數據實驗，利用GAIGIGR，信息增益，信息增益率，GINI指數作為屬性劃分的標準時：①在訓練集、測試集及10次10折交叉驗證單方面：4種屬性劃分的準確性都較高，偶爾波動較大；②在訓練集、測試集及10次10折交叉驗證的平均數方面：GAIGIGR方法最好；③比較信息增益、信息增益率以及GINI指數三者結果的平均值而言：GAIGIGR方法準確性較好；④在運行時間方面：GAIGIGR方法有明顯優勢。

文中采集的一次實驗結果表明，利用GAIGIGR，信息增益，信息增益率，GINI指數作為屬性劃分的標準的準確率都很高，而GAIGIGR能很好地解決屬性值傾向的問題，穩定性好，可行有效。

在研究和實驗中發現，每次隨機將樣本分成訓練集和測試集建模時的結果會有一定的差異，如何使得實驗結果相對穩定，是下一步研究的重點。