一種基于加權(quán)Jaccard距離的決策樹集成選擇方法

于 凱,王立宏

(煙臺大學計算機與控制工程學院,山東 煙臺 264005)

在數(shù)據(jù)挖掘和機器學習中,決策樹是常用的分類方法.它利用現(xiàn)有數(shù)據(jù)構(gòu)建具有較強泛化能力的預測模型,對未知的對象進行預測分析[1].決策樹學習算法是不穩(wěn)定的,因為訓練數(shù)據(jù)集的微小變化都可能導致決策樹形態(tài)上的很大差異[2-3].對決策樹的研究一方面在于如何度量決策樹的穩(wěn)定性或多樣性[2-5],另一方面在于如何給出穩(wěn)定的預測結(jié)果[6-9].現(xiàn)有文獻中定義了2種類型的多樣性:結(jié)構(gòu)多樣性和語義多樣性.例如,RCJac[3]和TMD[4]是結(jié)構(gòu)多樣性度量,而kappa[5]是語義多樣性度量.結(jié)構(gòu)類似的決策樹可能會給出類似的分類結(jié)果(語義),而反之則不一定成立.多分類器集成(Ensemble)是機器學習中的研究熱點,決策樹的集成可以整合各個決策樹,給未知對象一個可信的預測結(jié)果.研究表明,為了獲得較好的泛化能力,決策樹集成的準確性、多樣性和間隔等都是關(guān)鍵因素[10].決策樹的準確性可以用訓練誤差來度量,而多樣性需要深入的研究.目前多樣性的研究主要集中在以下3個方面:(1)各決策樹的生成過程,如Bagging[6]、隨機森林[7-8]、Adaboost[9]、權(quán)重優(yōu)化[10]等;(2)各決策樹在驗證數(shù)據(jù)集上的預測結(jié)果差異,如kappa[5];(3)各決策樹的形態(tài)差異,如RCJac[3]和TMD[4].周志華等基于樹匹配多樣性來度量決策樹的結(jié)構(gòu)多樣性,同時考慮結(jié)構(gòu)和語義多樣性,以選擇預測能力強的集成[4].本文提出的加權(quán)Jaccard距離WJD(weighted Jaccard distance)從決策樹的形態(tài)和在驗證集合上的預測類別兩方面來度量決策樹的多樣性,是決策樹之間語義和結(jié)構(gòu)的綜合多樣性度量.考慮到不同的決策樹對驗證集合產(chǎn)生的劃分不同,而每個劃分塊都帶有類別標簽,因此通過加權(quán)比較有相同標簽的劃分塊組成的子劃分之間的Jaccard距離就可以度量決策樹之間的差異.在UCI數(shù)據(jù)集上的對比實驗表明,WJD是一種有效的多樣性度量方法,基于WJD的決策樹集成選擇能夠提高集成的分類精度.

1 加權(quán)Jaccard距離

1.1 基本概率分配之間的Jaccard距離

Jaccard指數(shù)是一種經(jīng)典的相似性度量.2個有限集A和B之間的Jaccard指數(shù)JI計算如下:

(1)

設(shè)數(shù)據(jù)集D={x1,x2,…,xN},其冪集為2D,其中N=|D|．Jaccard指數(shù)矩陣J是一個(2N-1)×(2N-1)矩陣,A行B列對應的元素為JI(A,B),其中A和B是非空集合,A?D,B?D.已有文獻證明J是正定的[11].

(2)

設(shè)m1和m2是數(shù)據(jù)集D上的2個BPA,m1和m2之間的Jaccard距離定義如下[12]:

(3)

其中,J是Jaccard矩陣.

1.2 決策樹之間的加權(quán)Jaccard距離

本文定義了一種新的加權(quán)Jaccard距離WJD來比較決策樹,WJD是決策樹之間的語義和結(jié)構(gòu)的綜合多樣性度量,它涉及到?jīng)Q策樹葉子的標簽和葉子上實例的分布.在對WJD進行性能分析后,我們還用它選擇多樣化的決策樹,并對決策樹的集成進行實驗分析.

設(shè)數(shù)據(jù)集D如上定義,標簽集為C={c1,c2,…,ck},T1和T2是2棵決策樹.如果用T1來測試數(shù)據(jù)集D,D中的每個實例都會落到一個相應的葉節(jié)點中.這樣一個葉節(jié)點就對應一些實例的集合,各葉子形成D的一個劃分P1={P1,1,P1,2,…,P1,M},與P1相對應的標簽為L1=,即P1,j的標簽為L1,j,其中L1,j∈C,j=1,…,M,M是非空葉節(jié)點的個數(shù).同理用T2來測試可得到(P2,L2).

對決策樹T1和T2的比較可以通過比較(P1,L1)和(P2,L2)來完成.需要注意的是,必須是同一標簽的子劃分進行比較.因為在分類時,不同標簽的子劃分給出不同的預測,它們之間的相似性計算沒有意義.

例如,D={1,2,…,12}有2個帶標簽的劃分:

(P1,L1)=({{1,2,3},{4,5,6},{7,8,9,10},

{11,12}},),

(P2,L2)=({{1,2,4,5},{3,6,11,12},{7,8,

9,10}},).

此時P1中的{{1,2,3},{7,8,9,10}}與P2中的{{1,2,4,5},{7,8,9,10}}進行比較,P1中的{{4,5,6},{11,12}}與P2中的{{3,6,11,12}}進行比較.顯然,這是不同集合的劃分之間的比較.常用的劃分比較方法如ARI[13]和Jaccard指數(shù)[14]都不適用.因此,本文定義了一種新的加權(quán)Jaccard距離來比較(P1,L1)和(P2,L2).

定義1 加權(quán)Jaccard距離(WJD)

(4)

其中:γc是加權(quán)系數(shù),m1,c和m2,c分別是P1和P2標簽為c的dBPA的約束項.

加權(quán)系數(shù)γc定義如下:

(5)

其中:P1,i是P1的第i個劃分塊,P2,j是P2的第j個劃分塊.

對于上例,可以得出:

m1,c1是P1中標簽為c1的約束BPA,m1,c1的非零項如下:

m1,c1({1,2,3})=3/12=0.250,

m1,c1({7,8,9,10})=4/12=0.333.

類似地,m2,c1的非零項如下:

m2,c1({1,2,4,5})=4/12=0.333,

m2,c1({7,8,9,10})=4/12=0.333.

在2個子劃分中{7,8,9,10}相同,m函數(shù)相減后{7,8,9,10}的函數(shù)值為0,因此,

dBPA(m1,c1,m2,c1)=

同理,m1,c2和m2,c2如下:

m1,c2({4,5,6})=3/12=0.250,

m1,c2({11,12})=2/12=0.167,

m2,c2({3,6,11,12})=4/12=0.333.

于是可得dBPA(m1,c2,m2,c2)=0.343.

最后加權(quán)Jaccard距離為:JW(P1,P2,L1,L2)=0.625×0.327+0.375×0.343=0.333.

WJD與文獻[3]中的RCJac是不同的.如果不考慮劃分的標簽,或認為每個劃分塊標記為相同的標簽,則WJD與RCJac是相等的.在分類問題中WJD更有意義,它涉及到劃分塊的標簽并比較有相同標簽的劃分塊組成的子劃分.另外,WJD與加權(quán)的Jaccard系數(shù)[15]從定義上看也是完全不同的.

1.3 加權(quán)Jaccard距離的性質(zhì)

定理1 如果P1中標簽為c的子劃分與P2中相同標簽的子劃分相等,那么dBPA(m1,c,m2,c)=0,反之亦然.

證明已知矩陣J是正定的,則dBPA(m1,c,m2,c)=0當且僅當m1,c=m2,c(見公式(3)),根據(jù)公式(2)對m的定義可知,P1中標簽為c的子劃分與P2中標簽為c的子劃分相等.

其中,

(6)

(7)

推論設(shè)S1,c和S2,c分別表示P1和P2中標簽為c的子劃分.如果S1,c∩S2,c={P1,i1,P1,i2,…,P1,ik},那么

其中

證明與定理2的證明類似.

從定理2及其推論可知,S1,c與S2,c之間相同的部分越多,它們之間的dBPA就越小.

定理3 如果P1和P2是數(shù)據(jù)集D的2個劃分,L1和L2是對應的標簽集合,那么JW(P1,P2,L1,L2)=0當且僅當P1=P2,L1=L2.

證明因為dBPA(m1,c,m2,c)≥0且γc>0,所以JW(P1,P2,L1,L2)=0當且僅當對每個標簽c,dBPA(m1,c,m2,c)=0.根據(jù)定理1,dBPA(m1,c,m2,c)=0當且僅當P1中標簽為c的子劃分與P2中相同標簽的子劃分相等.所以,JW(P1,P2,L1,L2)=0當且僅當P1=P2,L1=L2.

定理3說明2個帶標簽的劃分之間的WJD是正定的,并且WJD的值越大,2個劃分之間的差異越大.因此,我們能夠通過比較WJD來比較決策樹的差異,進而挑選差異較大的成員構(gòu)成決策樹的集成.

2 決策樹的集成選擇

研究表明,一個精確的、多樣性的子集成可能會比整個集成有更高的預測精度,因此選擇性集成或者集成的剪枝成為了研究熱點[16-17]．本文以提出的WJD為決策樹之間的距離,采用層次聚類算法選擇部分決策樹,形成一個集成子集．

2.1 決策樹的生成

給定數(shù)據(jù)集D,本文使用10折交叉驗證的方法進行實驗測試.

首先,將數(shù)據(jù)集D隨機分成大小相等的10份,每次選用其中1份作為測試集De,剩余部分作為訓練集和驗證集Dt,D=De∪Dt.

然后,用數(shù)據(jù)集Dt生成決策樹,并用生成的決策樹對Dt進行預測以獲得Dt的劃分.在實驗中使用了2種決策樹生成方式:Bagging[6]和AdaBoost[9].在使用Bagging時,對數(shù)據(jù)集Dt進行放回式抽樣(Bootstrap),訓練得到?jīng)Q策樹模型．重復這個過程100次,得到含有100棵樹的決策樹池.在使用AdaBoost時,先將訓練樣本進行初始化,使每個樣本的權(quán)重相等,訓練得到一棵決策樹,然后更新樣本權(quán)重,增大分類錯誤的樣本的權(quán)重,減小分類正確的樣本的權(quán)重,最后得到有100棵樹的決策樹池.決策樹池的大小設(shè)定為100棵樹是參照文獻[18-19]的做法.

最后,對于數(shù)據(jù)集D的剩余9份分別使用上述過程,得到10個含有100棵樹的決策樹池.

關(guān)于訓練集、驗證集和測試集的設(shè)計問題,通常的做法是將整個數(shù)據(jù)集隨機劃分成3個彼此不相交的部分,各部分占的比例是60∶20∶20[20]或者1∶1∶1[4]等.但是當數(shù)據(jù)集較小時,這樣的劃分會導致訓練數(shù)據(jù)集過小,訓練得到的模型擬合不足.還可以將訓練集全部用來作為驗證集,這樣能充分利用訓練數(shù)據(jù),但是容易導致模型對訓練數(shù)據(jù)的過擬合[21].

在實驗中,訓練集是Dt的子集.由于對數(shù)據(jù)集Dt進行放回式抽樣,Bagging中實際訓練決策樹模型的數(shù)據(jù)大約占Dt的63%[6].WJD是計算同一個數(shù)據(jù)集的2個不同劃分P1和P2之間的距離,如果直接將Dt的剩余部分(約占37%)定義為驗證集,那么每次抽樣都會使其發(fā)生變化,不能滿足對WJD的定義要求,因此驗證集取Dt.Adaboost也是放回式抽樣,驗證集也取Dt.

2.2 決策樹的多樣性選擇

在集成中決策樹的準確性和多樣性都是必不可少的,因此在用Bagging方法得到的10個決策樹池中,從每個決策樹池中選擇50棵對Dt預測精度最高的樹,然后構(gòu)建成一個新的決策樹池.本文使用單鏈接的層次聚集聚類的方法選擇決策樹[22],2棵樹之間的距離定義為它們的WJD.得到K個簇后,每個簇中選取與簇中其他樹平均距離最小的樹來代表這個簇.最后,將得到的K棵樹組成集成,過程如圖1所示.在這里,K的數(shù)值表示的是對新的決策樹池(由選擇的50棵精度較高的樹構(gòu)成)剪枝后子集成的大小,K<50.

在用AdaBoost算法得到的決策樹池中,決策樹是通過迭代的方式生成的,與Bagging算法的生成方式不同,因此我們并沒有從池中的100棵決策樹中挑選出50棵樹出來,而是直接對池中的100棵樹進行聚類,得到K個簇,然后從每個簇中選取一個與該簇中其他樹平均距離最小的樹構(gòu)成集成.此處,K的數(shù)值表示對AdaBoost算法得到的決策樹池剪枝后得到的子集成大小.

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)集

使用UCI上的6個數(shù)據(jù)集進行實驗測試.表1是對所使用的UCI數(shù)據(jù)集的一些特征描述.

表1 實驗數(shù)據(jù)集描述Tab.1 Description of datasets

3.2 實驗方案

對比算法包括MDM[18,23]及2種多樣性度量技術(shù)kappa[5]和RCJac[3].MDM是通過啟發(fā)式方法從候選池中逐個選擇分類器來構(gòu)建有序子集成的;kappa是基于語義多樣性度量的,只考慮了樣本的標簽;RCJac是基于結(jié)構(gòu)多樣性度量的,只考慮了葉節(jié)點上的實例分布,并未使用葉節(jié)點的標簽;而WJD是語義和結(jié)構(gòu)的多樣性度量,它涉及到?jīng)Q策樹葉子的標簽和葉子上實例的分布.

為了保證對這些技術(shù)進行公平的實驗比較,本文采用相同的實驗方案,使用相同的決策樹池,使用相同的數(shù)據(jù)集進行驗證和測試.給定數(shù)據(jù)集D,用10折交叉驗證的方式生成決策樹池,使用了Bagging和AdaBoost 2種算法構(gòu)建集成,如2.1節(jié)所述.與常用的靜態(tài)分類器選擇方法相同,我們先在驗證集上找到精度最高的子集成,然后用得到的子集成來預測未知樣本.

文獻[18]提出在Bagging集成中,20%～40%的分類器就能構(gòu)成一個較高精度的子集成.在本文實驗中對更大的范圍(10%～60%)進行了測試,以找到一個精度最高的子集成,然后對未知樣本進行測試.在AdaBoost算法得到的決策樹池中,對10%～80%的范圍進行了實驗,測試能否對其進行剪枝,期望得到一個精度更高的子集成.

使用基于聚類的方法構(gòu)建子集成,子集成的大小是聚類的簇個數(shù)(見2.2節(jié)),也是MDM中用于構(gòu)建子集成的決策樹的數(shù)量.根據(jù)文獻[18]和[23],將MDM的參數(shù)p設(shè)置為0.075.對Bagging算法生成的子集成,使用多數(shù)投票方法來對測試樣本進行預測;對AdaBoost算法生成的子集成,使用相應的加權(quán)投票方法對測試樣本進行預測.

多數(shù)投票及加權(quán)投票都是用于分類器的靜態(tài)選擇方法,本文還測試了一種動態(tài)集成方法LCA(local class accuracy)[24].LCA先讓分類器對待測樣本做出預測,然后找出待測樣本在驗證集中的k近鄰內(nèi)被預測為與待測樣本相同類別的樣本,并計算出分類器對這些樣本的分類準確率,最后選擇準確率最高的那一個分類器.競爭域RoC(region of competence)定義為測試樣本的k近鄰,其中k值范圍是3～10,測試數(shù)據(jù)集中使用性能最佳的k值.我們沒有考慮k值小于3的情況,因為通常會出現(xiàn)所有的候選樹對k近鄰內(nèi)樣本預測正確率為零的情況.根據(jù)文獻[24],將k的最大值設(shè)置為10.

3.3 結(jié)果分析

表2給出了各算法在采用Bagging生成的決策樹池上使用Majority Voting的平均預測精度,MVall是選出的50棵精度最高的決策樹的Majority Voting結(jié)果.從W/T/L(Wins,Ties and Losses)指標可以看出,WJD表現(xiàn)要比kappa(語義多樣性)和RCJac(結(jié)構(gòu)多樣性)好,與MDM具有相似的性能.WJD在3個數(shù)據(jù)集上表現(xiàn)優(yōu)于MVall.

表2 對Bagging生成的決策樹池使用多數(shù)投票預測精度,并根據(jù)(W/T/L)進行性能比較Tab.2 Prediction accuracy using Majority Voting for Bagging and performance comparison in terms of (W/T/L)

表3給出了各算法在采用Bagging生成的決策樹池上使用LCA的平均預測精度,可以看出WJD的表現(xiàn)是最好的.WJD在5個數(shù)據(jù)集上表現(xiàn)優(yōu)于MVall.

表4給出了各算法在采用AdaBoost生成的決策樹池上使用加權(quán)投票方式的平均預測精度,WVall是決策樹池中的100棵樹的加權(quán)投票結(jié)果.可以看出,WJD的表現(xiàn)要優(yōu)于MDM和kappa,與RCJac的性能相似.WJD在4個數(shù)據(jù)集上表現(xiàn)比WVall要好,在1個數(shù)據(jù)集上表現(xiàn)相當.

表3 在Bagging算法生成的決策樹池中,使用LCA預測精度,并根據(jù)(W/T/L)進行性能比較Tab.3 Prediction accuracy using LCA for Bagging and performance comparison in terms of (W/T/L)

表4 在AdaBoost算法生成的決策樹池中,使用加權(quán)投票預測精度,并根據(jù)(W/T/L)進行性能比較Tab.4 Prediction accuracy using Weighed Voting for AdaBoost and performance comparison in terms of (W/T/L)

表5給出了在用AdaBoost算法生成的決策樹池上使用LCA的平均正確率.可以看出,WJD的表現(xiàn)明顯優(yōu)于其他3種方法,在4個數(shù)據(jù)集上表現(xiàn)優(yōu)于WVall,在1個數(shù)據(jù)集上與WVall相當.

表5 對AdaBoost生成的決策樹池使用LCA預測精度,并根據(jù)(W/T/L)進行性能比較Tab.5 Prediction accuracy using LCA for AdaBoost and performance comparison in terms of (W/T/L)

從表2—5中可以看出,本文提出的WJD比其他3種方法有更好的表現(xiàn).kappa是語義多樣性度量,RCJac是結(jié)構(gòu)多樣性度量.實驗表明,本文提出的語義和結(jié)構(gòu)多樣性度量方法WJD能夠更好地對測試數(shù)據(jù)進行預測.從實驗中可以看出,使用合適的相似性度量方法,基于聚類的剪枝算法會比有序剪枝算法MDM有更好的表現(xiàn).此外,與所有樹的預測結(jié)果相比較,本文方法對Bagging和AdaBoost的剪枝是有效的,可以得到精度較高的子集成.

4 結(jié) 論

在決策樹集成系統(tǒng)中,多樣性是重要的特征.本文中提出的加權(quán)Jaccard距離是基于決策樹中帶標簽劃分的多樣性度量.我們分析了WJD的性質(zhì),總結(jié)了3個定理并予以證明.接下來的實驗中,采用MDM算法及2種多樣性度量方法kappa和RCJac與WJD進行實驗對比.實驗結(jié)果表明,本文提出的WJD對測試數(shù)據(jù)的預測精度更高.