融合信息增益與基尼指數的決策樹算法

謝 鑫，張賢勇，楊霽琳

1.四川師范大學 數學科學學院，成都 610066 2.四川師范大學 智能信息與量子信息研究所，成都 610066 3.四川師范大學 計算機科學學院，成都 610066

大數據時代需求高效的信息獲取，這對數據分類及相關知識發現提出了更高要求。數據分類的方法主要有貝葉斯分類、神經網絡、支持向量機、決策樹等。其中，決策樹是機器學習與數據挖掘的一種基本分類策略，在決策支持、信息分析、醫療診斷等方面具有廣泛的研究與應用[1-3]。決策樹自1966年提出，而后主要關注結點選擇來進行決策樹構造、改進、優化。現有決策樹算法的節點度量函數選擇，具有偏向于信息熵、基尼指數、粗糙集理論三個方向。ID3（iterative dichotomiser 3）

算法[4]、C4.5算法[5]及其改進算法[6-7]選擇信息增益或信息增益率。CART（classification and regression tree）算法[8]及其改進算法[9-11]選擇基尼指數作為度量函數。例如，文獻[9]采用遞增式學習來改進CART算法，文獻[10]引入模糊邏輯來構建模糊CART算法，文獻[11]采用Fayyad邊界點與關鍵度量來改進CART算法，文獻[12]依托基尼指數來構建一種模型決策樹加速算法。借助粗糙集理論，RS（rough set）算法及其改進算法主要優先考慮屬性依賴度[13-14]。

信息增益與基尼指數可以表征數據的不確定性程度或雜亂度，從而對應的ID3算法與CART算法完成決策樹基本構建，但相關的分類效果還值得改進。信息熵和基尼指數具有相似的不確定性度量功能，但具有不同的表現形態與測量重點。信息熵側重于信息表示，對較亂數據具有更強表現力；基尼指數則側重于代數表示，更擅長較純集合分類。由此，兩種度量的深入結合具有意義，相關融合度量可望獲取優化決策樹算法，但是相關報告較少；文獻[15]將基尼系數關聯閾值來構建改進ID3算法，文獻[16]采用常數權重來進行線性組合集成。本文將信息增益和基尼指數進行自適應加權集成，產生具有更完備不確定性刻畫的融合度量IgGi，再自然構建對應決策樹算法IGGI（information gain and Gini index），適用于信息增益和基尼指數都不占絕對優勢的應用環境；最后，進行UCI數據實驗，對比ID3算法與CART算法來驗證IGGI算法的有效性與改進性。

1 兩種基本決策樹算法

給定一個決策系統DT=(U,C?D,{v c|c∈C},{I c|c∈C}),其中U={x1,x2,…,x||U}表示有限樣本集，C={c1,c2,…,c|C|}表示條件屬性集，D表示決策屬性集，V c表示c∈C的屬性值域，I c:U→vc是將對象x在屬性c上賦值I c(x)的信息函數。為方便，這種決策系統也簡記為決策表DT=(U,C?D)。相關的監督學習需要涉及條件部分與決策部分的兩種粒化（設條件屬性子集A?C）：

常用于探尋知識粒度層次的規律，如不確定性度量的粒化單調性[17]。

1.1 基于信息增益的ID3算法

來源于信息理論的信息熵關聯于系統信息含量，能夠表征樣本集合的不確定性，由此可以得到經典的決策樹歸納算法ID3[4]。

定義1[4]在決策表DT=(U,C?D)中，決策分類U/D的信息熵為：

ID3算法遍歷每一個屬性特征，選擇具有最優信息增益的特征來劃分數據，由此遞歸構造決策樹。ID3算法操作簡單，但容易導致偏移性與低精度，后續具有較多改進算法，包括C4.5算法等。

1.2 基于基尼指數的CART算法

來源于經濟統計的基尼（Gini）指數關聯于數據雜亂度，相關CART算法可以構造分類樹[8]。

定義2[8]在決策表DT=(U,C?D)中，決策分類U/D的基尼指數為：

CART算法采用基尼指數來實施屬性優選，由此建立分類樹。此外，CART算法還可以構建回歸樹。

2 基于信息增益與基尼指數融合度量的決策樹算法

基于上述ID3算法與CART算法，信息增益與基尼指數都適用于決策樹構造。下面挖掘它們的一種深入融合度量，進而建立一個強健的決策樹算法IGGI，最后采用一個決策表實例來澄清相關的機制與比較。

2.1 信息增益與基尼指數的融合度量

信息增益與基尼指數都是可以用于決策樹構造的基本不確定性度量。對于決策樹歸納，信息增益側重于信息表示，對較亂數據具有更強表現力；對比地，基尼指數強調代數表示，更擅長較純數據的分類處理。可見，信息增益與基尼指數具有異質無關性，兩者的融合度量可以系統集成兩者優點，從而建立更強健的決策樹算法。下面采用加權線性組合來構建融合度量，其中的信息增益粒化單調性是已有的，而其他度量的粒化非單調論斷都能夠通過實例或實驗來有效驗證。

引理1信息增益具有粒化單增性，而基尼指數具有粒化非單增性，即：

命題1信息增益與基尼指數線性無關，即：

基于引理1，信息增益與基尼指數分別具有粒化單調性與粒化非單調性，相關結果將由后續數據實驗中的屬性增鏈來觀測。從而命題1表明，信息增益和基尼指數具有線性無關性，該基本結論也會由實驗佐證。進而，利用線性組合構建信息增益和基尼指數的融合度量是可行的、有意義的。

定義3在決策表DT=(U,C?D)中，D關于A?C的信息增益與基尼指數的融合度量（記為IgGi）定義為：

其中α(A)=||U/A/ ||U為基于條件A或知識U/A的自適應系數。

命題2融合度量IgGi具有粒化非單增性，即：

定義3構建了融合度量IgGi。觀測式（4），gain(A)與1-Gini(D,A)具有表征屬性集A重要性的相同方向，它們的加權系數采用了關聯于知識U/A的自適應系數（自適應系數比常系數更易提升分類業績）。融合度量IgGi深入集成了信息增益與基尼指數，知識粒度系數α(A)起著權重調節功能，通過設置雙系數和為1來取得常規范圍[0,1]。顯然，IgGi隨著信息增益增大而增大，隨著基尼指數減少而增大。基于命題2，該線性集成度量具有粒化非單調性，該結論來源于引理1與定義3，并將由后續實驗反映。總之，基于信息增益與基尼指數的融合度量綜合了不確定性的信息表示與代數表示，能夠表征屬性特征分類純性的重要功能，適用于更加寬泛數據的分類問題，下面將由此建立決策樹新算法。為此，聚焦單屬性A={c}，并使用簡單符號gain(c)、Gini(D,c)、α(c)、IgGi(D,c)；此外，設arg表述度量m最值的屬性反演作用，即?c∈arg(·)?C有m(c)取得最值。

命題3設c1,c2∈C′?C，若α(c1)=α(c2)，則

基于定義3與命題3，更大信息增益與更小基尼指數的屬性具有取得更大融合度量值的傾向或可能。屬性優化關聯的一般結論是，信息增益的最大實現與基尼指數的最小實現沒有必然聯系，兩者中的單個最值或同時最值與混合度量最大值也沒有必然聯系。由此可見，信息增益與基尼指數對決策樹構造有所不同，而兩者的融合度量對決策樹構造具有有效性。

2.2 決策樹算法IGGI

基于上述混合度量，下面自然建立相關的決策樹算法（簡稱IGGI算法），主要利用IgGi混合度量進行特征選擇，具體描述如下。

算法決策樹算法IGGI

輸入：決策表DT=(U,C?D)。

輸出：決策樹。

步驟1遍歷相關決策樹所有屬性（設涉及屬性范圍為C′?C），計算相關混合度量值IgGi(D,c),?c∈C′。

步驟4對于多個子決策表DT1,DT2,…,DT n(c′)，遞歸地執行上面步驟1~3，直到所有條件粒屬于同一決策類或者所有條件屬性被檢測完。

步驟5返回決策樹。

這里，算法IGGI主要采用融合度量IgGi作為決策樹構造節點選擇的度量函數。具體地，步驟1循環計算所有混合度量值，步驟2確定最優屬性特征，步驟3依托優選屬性節點進行決策表與決策樹的分裂，步驟4實施決策樹生成的遞歸歸納，步驟5最終返回決策樹。考慮關聯于 ||C的IgGi基本運算，步驟1~2最多涉及時間計算量2 ||C與空間存儲量|C|，再加上步驟3~4涉及的上界 ||U，該算法的時間復雜性與空間復雜性的漸進分析為Ο(||C||U)，因此該算法是可行的。顯然，IGGI算法具有類似于ID3算法與CART算法的框架，但是采用了更加強健的混合度量（其具有更強的不確定性表示能力），故其意味著更好的決策樹分類業績，相關的優越性將被最后的數據實驗所體現與驗證。

2.3 決策表實例分析

這里提供一個決策表實例來說明上述決策樹算法IGGI。決策表如表1，具有13個樣本、5個條件屬性、1個決策屬性，決策屬性具有2類。

表1 決策表Table 1 Decision table

首先聚焦三種度量及其關系，為此采用式（1）的屬性增鏈進行度量計算，表2與圖1（其中α(A k)表示關聯于知識粒度的自適應系數）將同時提供信息增益、基尼指數、混合度量的結果。由此，可以部分驗證引理1與命題1、命題2，例如信息增益的粒化單調性、信息增益與基尼指數的線性獨立性等。

表2 基于屬性增鏈的三種度量值（實例）Table 2 Three kinds of measure values based on attribute-increase chain（Example）

圖1 基于屬性增鏈的三種度量變化（實例）Fig.1 Three kinds of measure changes based on attribute-increase chain（Example）

下面展現算法IGGI的實施過程，并給出具體的決策樹構造與結果。對于決策表1，需要計算所有單屬性的混合度量值IgGi(D,ck)(k=1,2,3,4,5)，相關的過程與結果參見表3。

表3 基于單屬性序列的三種度量值（實例）Table 3 Three kinds of measure values based on single-attribute sequence（Example）

基于表3可見，三種度量都是在c4、c5處取得最優值，該結果驗證了命題3。關于算法IGGI，步驟2將選取一個混合度量最優值節點，設為c5。步驟3是建立c5為根節點，進行決策表分裂。具體地，U/{c5}具有兩個類：{x2,x3,x4,x5,x9,x10,x12,x13}、{x1,x6,x7,x8,x11}，它們分別是標簽為1的8元集與標簽為2的5元集。由此，原來的決策表將分為兩個具有4屬性的子表（均不含屬性c5），分別具有8元與5元。步驟4將對這兩個子表遞歸地進行上述屬性優選與決策表分裂過程。步驟5最終給出相關的決策樹，如圖2其具有4層6個葉子。事實上，算法ID3與CART也會得到相同的結果。相關分析說明了算法IGGI的有效性，其對比于已有兩種算法的差異性與改進性將在下述數據實驗中深入展現。

圖2 基于IGGI算法的實例決策樹Fig.2 Decision tree of example based on IGGI algorithm

3 數據實驗驗證

最后實施相關數據實驗，驗證IGGI算法對比于ID3算法與CART算法的有效性與先進性。為此，從UCI機器學習數據庫（http：//archive.ics.uci.edu/ml）[18]中抽取6個數據集，具體信息參見表4。在實驗中，首先進行數據預處理（包括刪除具有缺失值的樣本，進行連續數據的等距劃分離散化），然后計算屬性增鏈上的三種度量，最后實施三種決策樹算法。

表4 實驗數據集Table 4 Experimental data sets

對于自然屬性增鏈（式（1）），相關的三種度量值描繪于圖3，其中數據集Divorce在屬性增鏈第7節點上就呈現度量最值，故只給了前面部分。由此可見引理1與命題1、命題2的理論結果。在增鏈方向上，信息增益是單增的，基尼指數是非單增的，兩種度量是非線性相關的，而數據集Iris在(A2,A3,A4)以及數據集Zoo在(A12,A13,A14)的局部振動能夠有效說明IgGi混合度量的粒化非單調性。

圖3 基于屬性增鏈的三種度量變化（實驗）Fig.3 Three kinds of measure changes based on attribute-increase chain（Experiment）

在決策樹實驗中，將數據集均分為10份，隨機選擇9份作為訓練集，1份作為測試集，進行十折交叉法驗證。三種算法的最終結果如表5與圖4（其中符號√標記最優值），這里關注“準確度”與“葉子數”兩種經典評估指標。

基于表5與圖4結果，下面對比分析ID3、CART、IGGI三種算法，從而揭示IGGI算法的相關優勢。首先，考慮決策樹準確度這一主要指標。在Tea、Zoo、Divorce、Car四個數據集中，IGGI算法的準確度高于其他兩種算法；在Phishing數據集中，IGGI算法和ID3算法準確度一樣，同時達到最優；在Iris數據集中，IGGI的結果介于CART算法與ID3算法之間，取得次優業績。可見，IGGI算法在大部分數據集上滿足準確性最優。其次，考慮葉子數這一結構指標。在Car數據集中，IGGI算法的葉子數最少，故優于其他兩種算法；在Iris、Zoo兩個數據集中，IGGI算法取得次優葉子數；在Tea、Divorce、Phishing三個數據集中，IGGI算法的葉子數和其他兩種算法的差異并不大。對比于ID3與CART，IGGI算法在葉子數上具有最優、次優優勢，且靠后時沒有顯著性劣勢。最后，可以綜合六個數據集計算結果，提供相關的統計分析；IGGI算法具有最優準確度，而其平均葉子數196對比于最優的177是可以接受的。綜上，IGGI算法采用深入的度量集成與信息融合，從而追求與獲取主要的決策樹分類準確性，相關的計算與結果都是有效的，且一般優于ID3算法與CART算法，因此具有更強的適用性。

表5 三種決策樹算法的實驗結果對比表Table 5 Comparative table of experiment results of three decision tree algorithms

圖4 三種決策樹算法的實驗結果對比圖Fig.4 Comparative figure of experiment results of three decision tree algorithms

4 結束語

決策樹算法主要依賴于不確定性度量構建，如ID3算法來源于信息增益而CART算法來源于基尼指數。本文集成信息增益與基尼指數來深入構造IgGi融合度量，進而設計了決策樹分類的IGGI算法。基于理論研究與實驗結果，IgGi度量與IGGI算法具有創新性、可行性、有效性；特別地，IGGI算法改進了經典的ID3算法與CART算法，具有更好的環境適應與分類業績。接下來，IgGi度量還可以考慮結合其他不確定性度量（如屬性依賴度），從而進一步提升IGGI算法的應用空間。