一種面向不平衡分類的改進多決策樹算法

,,,

(1. 山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東濟南250358；2. 山東省分布式計算機軟件新技術(shù)重點實驗室，山東濟南250358；3. 山東警察學(xué)院公共基礎(chǔ)部，山東濟南250014)

在不平衡分類問題[1-3]中，樣本數(shù)量較少的稱作少數(shù)類或正類，樣本數(shù)量較多的稱作多數(shù)類或負類，許多實際數(shù)據(jù)集中兩類樣本之間的比例往往差距懸殊，并且大多數(shù)不平衡數(shù)據(jù)集中存在類重疊現(xiàn)象及噪聲樣本，這對于研究分類問題無疑帶來更多困難和挑戰(zhàn)。一些傳統(tǒng)分類器在處理不平衡分類問題時，為了提高整體分類準確率，會忽視少數(shù)類樣本對整體的影響，無法將它們準確分離出來；而少數(shù)類樣本中往往包含更重要的信息，因此分離少數(shù)類樣本成為一個棘手的問題。目前解決不平衡分類問題主要的方法有改變數(shù)據(jù)分布、集成學(xué)習(xí)等。改變數(shù)據(jù)分布最常見的方式為過采樣和欠采樣。過采樣[4-7]是指增加少數(shù)類樣本來保持數(shù)據(jù)平衡，例如Chawla等[4]提出的SMOTE。之后研究者將很多方法與SMOTE結(jié)合提升了算法性能，如KM-SMOTE[6]、IDP-SMOTE[7]等算法。欠采樣[8-10]通過刪除多數(shù)類樣本來保持數(shù)據(jù)平衡，如隨機欠采樣方法。Lin等[10]提出的基于聚類的欠采樣CBU(clustering-based undersampling)，雖然有效地提高了分類效果，但仍然可能忽略部分重要信息。集成學(xué)習(xí)[11-20]通過訓(xùn)練多個個體分類器并進行結(jié)合，能夠得到比單一分類器更好的泛化性能。經(jīng)典的集成學(xué)習(xí)方法如 RUSBoost[14]、UnderBagging[15]、 EasyEnsemble[16]等，都在一定程度上提升了分類器的性能。很多情況下將欠采樣與集成學(xué)習(xí)結(jié)合使用效果更好。Kang等[17]提出集成欠采樣方法EUS(ensemble under-sampling)，從多數(shù)類中多次抽取與少數(shù)類相同數(shù)目的樣本形成多個平衡樣本集，在一定程度上克服了欠采樣的信息丟失問題。Lu等[18]提出一種自適應(yīng)決策邊界的集成方法(adaptive ensemble undersampling-boost)，引入了一種自適應(yīng)的閾值確定方法。Nejatian等[20]采用集成欠采樣方法，訓(xùn)練決策樹作為基分類器，雖然效果有所提升，但對于決策樹的訓(xùn)練面臨著根節(jié)點的屬性選擇問題，如果盲目隨機地選擇分裂屬性，會對分類結(jié)果產(chǎn)生一定的影響。

針對上述問題，本文提出一種基于欠采樣與屬性選擇的多決策樹方法UAMDT。首先對多數(shù)類樣本進行Tomek link欠采樣[21-22]，然后通過集成欠采樣方法對多數(shù)類樣本進行隨機有放回采樣，采樣的數(shù)量與少數(shù)類樣本數(shù)量相同，將采樣后的多數(shù)類與少數(shù)類樣本結(jié)合成多個平衡子集進行集成學(xué)習(xí)。本文選擇決策樹作為基分類器，為了進一步精確分類結(jié)果，采用一種混合屬性度量[23]作為屬性選擇標準，混合屬性包含信息增益與基尼指數(shù)，基于不同的根節(jié)點信息構(gòu)建多決策樹。

1 基于欠采樣與屬性選擇的多決策樹方法UAMDT

為了降低類重疊現(xiàn)象對分類的影響，保持原始數(shù)據(jù)的分布，提升總體分類精度，本文提出一種改進的多決策樹方法UAMDT，主要包括3個階段：①利用Tomek link欠采樣去除多數(shù)類樣本中的噪聲；②通過集成欠采樣合成多個子訓(xùn)練集；③訓(xùn)練嵌入屬性選擇標準的決策樹進行集成分類。

1.1 Tomek link欠采樣技術(shù)

Tomek[14]在1976年對CNN進行了改進，提出了一個新的框架，在數(shù)據(jù)空間中不破壞潛在信息的情況下對邊界多數(shù)類樣本進行欠采樣，檢測和刪除多數(shù)類中的噪聲數(shù)據(jù)。根據(jù)定義，如果兩個樣本屬于不同類別且距離很近，則可將它們連接成一個Tomek link對，一旦兩個樣本構(gòu)成Tomek link對，就意味著要么其中一個樣本是噪聲，要么兩個樣本都處于邊界上。其基本思想是：給定一對樣本(Si,Sj)，Si屬于多數(shù)類，而Sj屬于少數(shù)類，兩點之間距離記為d(Si,Sj)，若不存在任意樣本Sk，使得d(Si,Sk)

1.2 集成欠采樣技術(shù)

為了更有效地利用兩類樣本中潛在有用的信息，保證每個集成分類器的多樣性，在進行數(shù)據(jù)處理時，首先對進行Tomek link欠采樣之后的多數(shù)類樣本Smaj進行s次隨機有放回采樣，每次采樣的樣本數(shù)目Mi與少數(shù)類樣本數(shù)目Smin相同，即|Mi|=|Smin|。然后將采樣后的多數(shù)類樣本與少數(shù)類樣本組合成新的子訓(xùn)練集Ti，此時每個子訓(xùn)練集都是平衡的，即不平衡比率rIR=1。具體過程如算法1。

算法1：

Input:多數(shù)類樣本集Smaj，少數(shù)類樣本集Smin，采樣次數(shù)s。

Output:子訓(xùn)練集集合{Ti|1≤i≤s}。

Procedure:

1.i=1；

2.從Smaj中隨機有放回采樣Mi個樣本，|Mi|=|Smin|；

3.新訓(xùn)練子集Ti=Mi∪Smin；

4.i=i+1；

5.重復(fù)2～4步直到i=s；

End。

1.3 屬性選擇標準

對整個訓(xùn)練集進行Tomek link欠采樣及集成欠采樣技術(shù)之后，形成的s個子訓(xùn)練集上分別構(gòu)建單決策樹分類器。決策樹是一種基于訓(xùn)練樣本的屬性對其進行分類的樹形結(jié)構(gòu)，從根節(jié)點到分支節(jié)點，遞歸地選擇最優(yōu)的劃分屬性，將整個數(shù)據(jù)集劃分成純度更高、不確定性更小的子集，最終將分類結(jié)果賦予葉子節(jié)點。如果不適當?shù)剡x擇根節(jié)點屬性，選擇的效果將沿著分支擴散到葉子，會導(dǎo)致最后分類錯誤率增加，因此選擇哪個分裂屬性作為根節(jié)點至關(guān)重要。已經(jīng)有一些屬性選擇準則，如信息增益(ID3決策樹)、信息增益比(C4.5決策樹)以及基尼指數(shù)(CART分類樹)等，都是用來度量樣本集純度的方式。

信息增益代表基于某個屬性劃分數(shù)據(jù)集前后不確定性的減少程度，因此信息增益越大，集合的純度越高。它偏向于多值屬性，獨立地度量每個訓(xùn)練集的純度，所以對于類概率向量分量中的排列不敏感。基尼指數(shù)表示在樣本集合中一個隨機選中的樣本被分錯的概率，因此基尼指數(shù)越小，樣本被分錯的概率越小，集合的純度就越高。假設(shè)某訓(xùn)練子集包含m個屬性值A(chǔ)1,A2,…,Am，類標簽由k表示，因為二分類問題中只有兩類樣本，因此k=1,2。將兩種度量線性結(jié)合，定義混合屬性度量h(α)如下：

h(α)=αG(Ai)-(1-α)I(Ai)。

(1)

其中：G(Ai)表示基于分裂屬性Ai劃分數(shù)據(jù)集的基尼指數(shù)；I(Ai)表示基于分裂屬性Ai劃分數(shù)據(jù)集前后的信息增益；α是加權(quán)系數(shù)，表示每個度量的相對貢獻度?；嶂笖?shù)G(Ai)定義如下：

(2)

(3)

其中：N表示數(shù)據(jù)集T的樣本總數(shù)；Nk表示屬于第k類的樣本數(shù)量；Pk表示選中的樣本屬于第k類的概率。

信息增益I(Ai)可表示為劃分數(shù)據(jù)集前后熵的差值，定義如下：

I(Ai)=E-E′，

(4)

(5)

(6)

其中：E表示劃分數(shù)據(jù)集之前的熵值；E′表示劃分數(shù)據(jù)集之后的熵值；n表示基于屬性Ai劃分數(shù)據(jù)集之后的子集數(shù)；Nj表示第j個子集的樣本數(shù)。

利用混合屬性度量可以將信息增益與基尼指數(shù)的優(yōu)點相結(jié)合，同時彌補兩者的缺陷。由于混合屬性度量h(α)由信息增益與基尼指數(shù)線性結(jié)合，信息增益越大，基尼指數(shù)越小，h(α)越小，集合的純度越高，因此應(yīng)該選擇具有最小h(α)值的屬性Ai作為根節(jié)點的分裂屬性。

因此，在每個訓(xùn)練子集上構(gòu)建單決策樹時，將訓(xùn)練子集中包含的所有屬性按h(α)值大小進行排列，選擇具有最小h(α)值的屬性作為該決策樹的根節(jié)點的分裂屬性。

1.4 UAMDT算法設(shè)計

將多個單決策樹進行集成預(yù)測的多決策樹算法，預(yù)計分類結(jié)果比單決策樹更準確。因此，本文采用投票機制構(gòu)建多決策樹，對于每一個樣本，集成所有單決策樹的分類投票結(jié)果，將投票次數(shù)最多的類別指定為最終的輸出。本文提出的基于欠采樣與屬性選擇的多決策樹方法UAMDT如算法2，流程圖見圖1。

算法2：

Input:訓(xùn)練集T，權(quán)重系數(shù)α，采樣次數(shù)s。

Output:集成分類器UAMDT。

Procedure:

1.將多數(shù)類樣本進行Tomek link欠采樣，記為Smaj，少數(shù)類樣本記為Smin；

2.i=1；

3.從Smaj中隨機有放回采樣Mi個樣本，|Mi|=|Smin|，采樣次數(shù)為s，產(chǎn)生子訓(xùn)練集集合{Ti|1≤i≤s}，Ti=Mi∪Smin；

4.將子訓(xùn)練集Ti中的屬性值按屬性選擇標準h(α)=αG(Ai)-(1-α)I(Ai)進行排序，尋找h(α)最小的屬性值；

5.將h(α)最小的屬性值作為根節(jié)點的分裂屬性，訓(xùn)練單決策樹SDT1；

6.i=i+1；

7.重復(fù)步驟3～6直到i=s；

8.采用投票機制，集成單決策樹SDT1,SDT2,…,SDTs的分類投票結(jié)果，構(gòu)建多決策樹UAMDT；

End。

圖1 UAMDT算法流程Fig.1 UAMDT flowchart

2 實驗設(shè)計

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

為評估本文算法對不平衡分類的有效性和可靠性，選擇KEEL數(shù)據(jù)庫中的9個不平衡數(shù)據(jù)集D1～D9以及來自于UCI的Breast cancer數(shù)據(jù)集D10進行實驗，選取的數(shù)據(jù)集的樣本總數(shù)在214至1 484之間，不平衡比率在1.9到41.4之間。具體數(shù)據(jù)集如表1所示。

表1 數(shù)據(jù)集

2.2 評估標準

對于不平衡數(shù)據(jù)分類，最常見的評估標準有G-mean、準確率Accuracy、AUC值等。三者的定義需要用到表2的混淆矩陣。

表2 混淆矩陣

通常用G-mean值用來評測一個算法的綜合性能，定義為：

(7)

(8)

(9)

其中：RTP是真正類率，表示正類樣本分類正確的概率；RTN是真負類率，表示負類樣本分類正確的概率。如果分類器偏向某一類，那么G-mean值會很小，所以G-mean值越大，分類器的性能越好。

準確率ηAccuracy表示分類預(yù)測正確的樣本占總樣本的比例，定義為：

(10)

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

為了全面驗證本文提出的UAMDT算法對于不平衡數(shù)據(jù)分類的有效性，在10個數(shù)據(jù)集上設(shè)計了3個對比實驗。在實驗中將集成欠采樣的抽樣次數(shù)s設(shè)置為20，權(quán)重系數(shù)α設(shè)置為0.6。實驗采用五折交叉驗證，實驗1與實驗2使用G-mean值與準確率作為分類器評價指標，實驗3使用AUC作為評估標準。

實驗1：為了驗證屬性選擇標準的適用性，將ASDT與ID3、C4.5、CART單決策樹進行對比實驗。ASDT算法是在原始數(shù)據(jù)集上對多數(shù)類樣本進行Tomek link欠采樣之后，選擇h(α)最小的屬性作為根節(jié)點的分裂屬性訓(xùn)練單一決策樹。

圖2和圖3分別給出了ASDT與ID3、C4.5、CART算法的準確率和G-mean值比較，實驗結(jié)果表明，ASDT的平均準確率優(yōu)于其他3種方法，其次分別是CART、C4.5和ID3。而圖3顯示ASDT的G-mean值明顯高于ID3、C4.5和CART，原因是ASDT相對于其他3種算法而言，具有更精細的屬性選擇標準，ASDT結(jié)合了信息增益與基尼指數(shù)兩種準則，充分結(jié)合了兩種度量的優(yōu)勢，而其他3種算法使用的是單一屬性選擇標準。ID3算法只使用了信息增益作為分裂標準，但信息增益偏向取值較多的屬性；C4.5算法作為改進，以信息增益比作為屬性選擇標準，在信息增益的基礎(chǔ)上增加一個懲罰參數(shù)；CART決策樹以基尼指數(shù)作為分裂標準，但CART是二叉樹，只能根據(jù)某個屬性將數(shù)據(jù)分配到兩個集合。實驗證明了混合屬性選擇標準的適用性和有效性，并且當選擇對分類結(jié)果更有影響的屬性時分類效果更好。

圖2 ASDT與ID3、C4.5、CART的準確率比較Fig.2 Comparison of accuracy between ASDT and ID3, C4.5, CART

圖3 ASDT與ID3、C4.5、CART的G-mean值比較Fig.3 Comparison of G-mean between ASDT and ID3, C4.5, CART

實驗2：為了驗證本文算法UAMDT對于不平衡分類的可行性，將隨機森林RF與UAMDT算法進行對比實驗。隨機森林是一種經(jīng)典的多決策樹算法，本質(zhì)是集成學(xué)習(xí)的Bagging方法，訓(xùn)練多個單決策樹進行集成。

圖4和圖5分別給出了UAMDT和RF的準確率和G-mean值比較，實驗結(jié)果表明，兩種方法的準確率沒有較大差異，相差最大值為0.018。而除了數(shù)據(jù)集D8之外，UAMDT的G-mean值都高于隨機森林RF。隨機森林RF是在Bagging的基礎(chǔ)上改進的算法，Bagging算法是對數(shù)據(jù)集進行隨機放回抽取多次，形成多個訓(xùn)練集，而這些訓(xùn)練集可能是不平衡的，并且它們的不平衡比率也可能不相同。而本文提出的UAMDT是經(jīng)集成欠采樣之后，在多個平衡訓(xùn)練集上訓(xùn)練決策樹，且在每棵決策樹的根節(jié)點加入了對應(yīng)訓(xùn)練集中使分類效果最好的分裂屬性，因此UAMDT的性能優(yōu)于隨機森林RF。

圖4 UAMDT與RF的準確率比較Fig.4 Comparison of accuracy between UAMDT and RF

圖5 UAMDT與RF的G-mean值比較Fig.5 Comparison of G-mean between UAMDT and RF

實驗3：將UAMDT算法與已經(jīng)提出的一些經(jīng)典算法進行比較，包括CBU(clustering-based undersampling)、RUS(RUSBoost)、UB(UnderBagging)、EE(EasyEnsemble)算法。表3給出了5種算法在10個數(shù)據(jù)集上的AUC值及平均值，實驗表明除了數(shù)據(jù)集D2、D3、D8及D10之外，UAMDT都獲得了最高的AUC，且平均值也達到最高值0.907，其次分別是EE、RUS、UB和CBU算法。綜合看來，UAMDT優(yōu)勝次數(shù)多達7次，明顯提高了分類性能。UAMDT算法相較于其他4種方法來說，采用Tomek link欠采樣降低了類重疊對數(shù)據(jù)集的影響，減小了不平衡比率IR，對于之后的分類起到了一定的作用，包括采用集成欠采樣技術(shù)，這些數(shù)據(jù)處理措施使得UAMDT對于區(qū)分少數(shù)類樣本具有更強的適應(yīng)性。

表3 CBU、RUS、UB、EE、UAMDT等5種算法的AUC值比較

3 結(jié)束語

針對不平衡分類問題，為了更有效地利用數(shù)據(jù)信息，保持數(shù)據(jù)原始分布，本文利用集成學(xué)習(xí)的思想，提出一種基于欠采樣與屬性選擇的多決策樹方法UAMDT，對多數(shù)類樣本進行Tomek link欠采樣與集成欠采樣，在增大兩類樣本之間距離的同時，保留數(shù)據(jù)信息，保證了訓(xùn)練子集的多樣性和差異性，使得訓(xùn)練的各基分類器可以處理不同的數(shù)據(jù)。混合屬性度量結(jié)合了信息增益與基尼指數(shù)兩種度量的優(yōu)點，在每個訓(xùn)練子集中尋找使分類效果最好的屬性，作為每棵決策樹根節(jié)點的分裂屬性。最后利用投票機制將單決策樹的預(yù)測結(jié)果匯合，構(gòu)建最終的多決策樹。本文在來自KEEL以及UCI數(shù)據(jù)庫中的10個不平衡數(shù)據(jù)集上進行了3組對比實驗，以準確率、G-mean值以及AUC作為評估分類性能的指標，實驗結(jié)果表明本文算法對整體分類性能有了明顯的提升，說明了本文算法在不平衡分類領(lǐng)域是有效和可行的。實驗亦證明本文算法可用于一些具體應(yīng)用領(lǐng)域，如在醫(yī)療方面預(yù)測和診斷疾病等，從而發(fā)現(xiàn)異常，使患者及時得到醫(yī)治。

本文在選取分裂屬性時，并未考慮屬性對各樣本的影響程度，并且本文只選取了小型數(shù)據(jù)集進行實驗，在一些數(shù)據(jù)集上效果一般，對于大型數(shù)據(jù)集不確定是否同樣適用尚未可知，因此，在之后的研究工作中，需要對算法進行細節(jié)的改進，并針對效果較差的數(shù)據(jù)集以及大型數(shù)據(jù)集進行進一步的考察和研究。