謝 鑫，張賢勇，楊霽琳

1.四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，成都 610066 2.四川師范大學(xué) 智能信息與量子信息研究所，成都 610066 3.四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，成都 610066

大數(shù)據(jù)時(shí)代需求高效的信息獲取，這對(duì)數(shù)據(jù)分類(lèi)及相關(guān)知識(shí)發(fā)現(xiàn)提出了更高要求。數(shù)據(jù)分類(lèi)的方法主要有貝葉斯分類(lèi)、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、決策樹(shù)等。其中，決策樹(shù)是機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘的一種基本分類(lèi)策略，在決策支持、信息分析、醫(yī)療診斷等方面具有廣泛的研究與應(yīng)用[1-3]。決策樹(shù)自1966年提出，而后主要關(guān)注結(jié)點(diǎn)選擇來(lái)進(jìn)行決策樹(shù)構(gòu)造、改進(jìn)、優(yōu)化。現(xiàn)有決策樹(shù)算法的節(jié)點(diǎn)度量函數(shù)選擇，具有偏向于信息熵、基尼指數(shù)、粗糙集理論三個(gè)方向。ID3（iterative dichotomiser 3）

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

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

1 兩種基本決策樹(shù)算法

給定一個(gè)決策系統(tǒng)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是將對(duì)象x在屬性c上賦值I c(x)的信息函數(shù)。為方便，這種決策系統(tǒng)也簡(jiǎn)記為決策表DT=(U,C?D)。相關(guān)的監(jiān)督學(xué)習(xí)需要涉及條件部分與決策部分的兩種?；ㄔO(shè)條件屬性子集A?C）：

常用于探尋知識(shí)粒度層次的規(guī)律，如不確定性度量的?；瘑握{(diào)性[17]。

1.1 基于信息增益的ID3算法

來(lái)源于信息理論的信息熵關(guān)聯(lián)于系統(tǒng)信息含量，能夠表征樣本集合的不確定性，由此可以得到經(jīng)典的決策樹(shù)歸納算法ID3[4]。

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

ID3算法遍歷每一個(gè)屬性特征，選擇具有最優(yōu)信息增益的特征來(lái)劃分?jǐn)?shù)據(jù)，由此遞歸構(gòu)造決策樹(shù)。ID3算法操作簡(jiǎn)單，但容易導(dǎo)致偏移性與低精度，后續(xù)具有較多改進(jìn)算法，包括C4.5算法等。

1.2 基于基尼指數(shù)的CART算法

來(lái)源于經(jīng)濟(jì)統(tǒng)計(jì)的基尼（Gini）指數(shù)關(guān)聯(lián)于數(shù)據(jù)雜亂度，相關(guān)CART算法可以構(gòu)造分類(lèi)樹(shù)[8]。

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

CART算法采用基尼指數(shù)來(lái)實(shí)施屬性?xún)?yōu)選，由此建立分類(lèi)樹(shù)。此外，CART算法還可以構(gòu)建回歸樹(shù)。

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

基于上述ID3算法與CART算法，信息增益與基尼指數(shù)都適用于決策樹(shù)構(gòu)造。下面挖掘它們的一種深入融合度量，進(jìn)而建立一個(gè)強(qiáng)健的決策樹(shù)算法IGGI，最后采用一個(gè)決策表實(shí)例來(lái)澄清相關(guān)的機(jī)制與比較。

2.1 信息增益與基尼指數(shù)的融合度量

信息增益與基尼指數(shù)都是可以用于決策樹(shù)構(gòu)造的基本不確定性度量。對(duì)于決策樹(shù)歸納，信息增益?zhèn)戎赜谛畔⒈硎荆瑢?duì)較亂數(shù)據(jù)具有更強(qiáng)表現(xiàn)力；對(duì)比地，基尼指數(shù)強(qiáng)調(diào)代數(shù)表示，更擅長(zhǎng)較純數(shù)據(jù)的分類(lèi)處理?？梢?jiàn)，信息增益與基尼指數(shù)具有異質(zhì)無(wú)關(guān)性，兩者的融合度量可以系統(tǒng)集成兩者優(yōu)點(diǎn)，從而建立更強(qiáng)健的決策樹(shù)算法。下面采用加權(quán)線(xiàn)性組合來(lái)構(gòu)建融合度量，其中的信息增益?；瘑握{(diào)性是已有的，而其他度量的粒化非單調(diào)論斷都能夠通過(guò)實(shí)例或?qū)嶒?yàn)來(lái)有效驗(yàn)證。

引理1信息增益具有?；瘑卧鲂裕嶂笖?shù)具有?；菃卧鲂裕矗?/p>

命題1信息增益與基尼指數(shù)線(xiàn)性無(wú)關(guān)，即：

基于引理1，信息增益與基尼指數(shù)分別具有?；瘑握{(diào)性與粒化非單調(diào)性，相關(guān)結(jié)果將由后續(xù)數(shù)據(jù)實(shí)驗(yàn)中的屬性增鏈來(lái)觀測(cè)。從而命題1表明，信息增益和基尼指數(shù)具有線(xiàn)性無(wú)關(guān)性，該基本結(jié)論也會(huì)由實(shí)驗(yàn)佐證。進(jìn)而，利用線(xiàn)性組合構(gòu)建信息增益和基尼指數(shù)的融合度量是可行的、有意義的。

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

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

命題2融合度量IgGi具有?；菃卧鲂?，即：

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

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

基于定義3與命題3，更大信息增益與更小基尼指數(shù)的屬性具有取得更大融合度量值的傾向或可能。屬性?xún)?yōu)化關(guān)聯(lián)的一般結(jié)論是，信息增益的最大實(shí)現(xiàn)與基尼指數(shù)的最小實(shí)現(xiàn)沒(méi)有必然聯(lián)系，兩者中的單個(gè)最值或同時(shí)最值與混合度量最大值也沒(méi)有必然聯(lián)系。由此可見(jiàn)，信息增益與基尼指數(shù)對(duì)決策樹(shù)構(gòu)造有所不同，而兩者的融合度量對(duì)決策樹(shù)構(gòu)造具有有效性。

2.2 決策樹(shù)算法IGGI

基于上述混合度量，下面自然建立相關(guān)的決策樹(shù)算法（簡(jiǎn)稱(chēng)IGGI算法），主要利用IgGi混合度量進(jìn)行特征選擇，具體描述如下。

算法決策樹(shù)算法IGGI

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

輸出：決策樹(shù)。

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

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

步驟5返回決策樹(shù)。

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

2.3 決策表實(shí)例分析

這里提供一個(gè)決策表實(shí)例來(lái)說(shuō)明上述決策樹(shù)算法IGGI。決策表如表1，具有13個(gè)樣本、5個(gè)條件屬性、1個(gè)決策屬性，決策屬性具有2類(lèi)。

表1 決策表Table 1 Decision table

首先聚焦三種度量及其關(guān)系，為此采用式（1）的屬性增鏈進(jìn)行度量計(jì)算，表2與圖1（其中α(A k)表示關(guān)聯(lián)于知識(shí)粒度的自適應(yīng)系數(shù)）將同時(shí)提供信息增益、基尼指數(shù)、混合度量的結(jié)果。由此，可以部分驗(yàn)證引理1與命題1、命題2，例如信息增益的?；瘑握{(diào)性、信息增益與基尼指數(shù)的線(xiàn)性獨(dú)立性等。

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

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

下面展現(xiàn)算法IGGI的實(shí)施過(guò)程，并給出具體的決策樹(shù)構(gòu)造與結(jié)果。對(duì)于決策表1，需要計(jì)算所有單屬性的混合度量值IgGi(D,ck)(k=1,2,3,4,5)，相關(guān)的過(guò)程與結(jié)果參見(jiàn)表3。

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

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

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

3 數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證

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

表4 實(shí)驗(yàn)數(shù)據(jù)集Table 4 Experimental data sets

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

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

在決策樹(shù)實(shí)驗(yàn)中，將數(shù)據(jù)集均分為10份，隨機(jī)選擇9份作為訓(xùn)練集，1份作為測(cè)試集，進(jìn)行十折交叉法驗(yàn)證。三種算法的最終結(jié)果如表5與圖4（其中符號(hào)√標(biāo)記最優(yōu)值），這里關(guān)注“準(zhǔn)確度”與“葉子數(shù)”兩種經(jīng)典評(píng)估指標(biāo)。

基于表5與圖4結(jié)果，下面對(duì)比分析ID3、CART、IGGI三種算法，從而揭示IGGI算法的相關(guān)優(yōu)勢(shì)。首先，考慮決策樹(shù)準(zhǔn)確度這一主要指標(biāo)。在Tea、Zoo、Divorce、Car四個(gè)數(shù)據(jù)集中，IGGI算法的準(zhǔn)確度高于其他兩種算法；在Phishing數(shù)據(jù)集中，IGGI算法和ID3算法準(zhǔn)確度一樣，同時(shí)達(dá)到最優(yōu)；在Iris數(shù)據(jù)集中，IGGI的結(jié)果介于CART算法與ID3算法之間，取得次優(yōu)業(yè)績(jī)?？梢?jiàn)，IGGI算法在大部分?jǐn)?shù)據(jù)集上滿(mǎn)足準(zhǔn)確性最優(yōu)。其次，考慮葉子數(shù)這一結(jié)構(gòu)指標(biāo)。在Car數(shù)據(jù)集中，IGGI算法的葉子數(shù)最少，故優(yōu)于其他兩種算法；在Iris、Zoo兩個(gè)數(shù)據(jù)集中，IGGI算法取得次優(yōu)葉子數(shù)；在Tea、Divorce、Phishing三個(gè)數(shù)據(jù)集中，IGGI算法的葉子數(shù)和其他兩種算法的差異并不大。對(duì)比于ID3與CART，IGGI算法在葉子數(shù)上具有最優(yōu)、次優(yōu)優(yōu)勢(shì)，且靠后時(shí)沒(méi)有顯著性劣勢(shì)。最后，可以綜合六個(gè)數(shù)據(jù)集計(jì)算結(jié)果，提供相關(guān)的統(tǒng)計(jì)分析；IGGI算法具有最優(yōu)準(zhǔn)確度，而其平均葉子數(shù)196對(duì)比于最優(yōu)的177是可以接受的。綜上，IGGI算法采用深入的度量集成與信息融合，從而追求與獲取主要的決策樹(shù)分類(lèi)準(zhǔn)確性，相關(guān)的計(jì)算與結(jié)果都是有效的，且一般優(yōu)于ID3算法與CART算法，因此具有更強(qiáng)的適用性。

表5 三種決策樹(shù)算法的實(shí)驗(yàn)結(jié)果對(duì)比表Table 5 Comparative table of experiment results of three decision tree algorithms

圖4 三種決策樹(shù)算法的實(shí)驗(yàn)結(jié)果對(duì)比圖Fig.4 Comparative figure of experiment results of three decision tree algorithms

4 結(jié)束語(yǔ)

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