具有強(qiáng)化學(xué)習(xí)策略的決策樹算法

于安池,儲(chǔ)茂祥,楊永輝,董 秀

(1.遼寧科技大學(xué) 電子與信息工程學(xué)院,遼寧 鞍山 114000;2.煙臺(tái)汽車工程職業(yè)學(xué)院 汽車工程系,山東 煙臺(tái) 265500)

隨著大數(shù)據(jù)時(shí)代的來臨,技術(shù)的不斷提升,各領(lǐng)域?qū)?shù)據(jù)的處理要求越來越高。對(duì)于醫(yī)療、銀行等領(lǐng)域,不平衡數(shù)據(jù)的研究尤為重要。決策樹[1]作為數(shù)據(jù)挖掘領(lǐng)域的重要算法之一,具有效率高、只需要一次構(gòu)建、可反復(fù)使用、每一次預(yù)測(cè)的最大計(jì)算次數(shù)不超過決策樹深度的優(yōu)點(diǎn),但是決策樹在處理各類樣本數(shù)量不平衡的數(shù)據(jù)集時(shí),特征選擇標(biāo)準(zhǔn)偏向樣本數(shù)目更多的特征,導(dǎo)致負(fù)類的分類準(zhǔn)確率降低。

在對(duì)不平衡數(shù)據(jù)進(jìn)行分類時(shí),主要存在的問題是數(shù)據(jù)集本身的不平衡性和傳統(tǒng)決策樹算法的局限性。數(shù)據(jù)層面體現(xiàn)在數(shù)據(jù)集樣本數(shù)目的不平衡。對(duì)于一些情況而言,負(fù)類包含的信息更為重要,分類器不能夠充分訓(xùn)練負(fù)類樣本,造成負(fù)類的準(zhǔn)確度下降。在算法層面,分類器為了使準(zhǔn)確率最大,會(huì)誤分更多的負(fù)類樣本,犧牲了負(fù)類的分類準(zhǔn)確度。國(guó)內(nèi)外的學(xué)者對(duì)于不平衡數(shù)據(jù)的分類問題做了大量改進(jìn)。文獻(xiàn)[2]針對(duì)不平衡數(shù)據(jù)的處理方法進(jìn)行了總結(jié)和整理,主要分為在數(shù)據(jù)層面、特征層面和算法層面的改進(jìn)方法;文獻(xiàn)[3]通過提高負(fù)類權(quán)重的方法,將代價(jià)敏感與屬性選擇標(biāo)準(zhǔn)相結(jié)合,提出一種代價(jià)敏感決策樹方法;文獻(xiàn)[4]提出C4.5+δ、均勻分布熵和改進(jìn)分布熵函數(shù)3種針對(duì)不平衡數(shù)據(jù)的改進(jìn)決策樹方法;文獻(xiàn)[5]提出基于區(qū)間值屬性的單調(diào)決策樹;文獻(xiàn)[6]在建立代價(jià)敏感決策樹的基礎(chǔ)上對(duì)劣質(zhì)數(shù)據(jù)進(jìn)行清洗;文獻(xiàn)[7]采用級(jí)聯(lián)的思想,將多個(gè)AdaBoost決策樹集成,組合成級(jí)聯(lián)決策樹;文獻(xiàn)[8]提出一種基于歐式距離計(jì)算距離權(quán)值的改進(jìn)C4.5算法;文獻(xiàn)[9]將猶豫模糊集理論與決策樹算法結(jié)合,提出一種改進(jìn)的模糊決策樹算法。

綜上所述,將強(qiáng)化學(xué)習(xí)方法引進(jìn)決策樹算法的研究很少。文獻(xiàn)[10]提出一種基于強(qiáng)化學(xué)習(xí)累積回報(bào)策略的改進(jìn)決策樹算法,取得了很好的效果。但是,該方法使負(fù)類在屬性選擇時(shí)提高權(quán)重,會(huì)犧牲掉一部分正類的準(zhǔn)確度。本文借鑒強(qiáng)化學(xué)習(xí)中馬爾可夫決策過程,對(duì)決策樹算法進(jìn)行優(yōu)化,通過標(biāo)準(zhǔn)化互信息和馬修斯相關(guān)系數(shù)2個(gè)平衡的評(píng)價(jià)指標(biāo)加權(quán),對(duì)決策樹每次的分裂過程進(jìn)行獎(jiǎng)勵(lì),刺激它獲取更大的獎(jiǎng)勵(lì)。。

1 C4.5算法原理

決策樹是一種采用貪心算法,自上而下遞歸構(gòu)造的類似于流程圖的樹結(jié)構(gòu),每一個(gè)從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的分支為一種分類規(guī)則,其內(nèi)部節(jié)點(diǎn)為選擇的特征,葉子節(jié)點(diǎn)存放的是類標(biāo)號(hào)。決策樹常用的算法有ID3算法、C4.5算法等。C4.5算法具體步驟如下:

(1)設(shè)S為樣本集,樣本個(gè)數(shù)為n,樣本集S中有m個(gè)類別Dj(j=1,2,…,m),dj為Dj類的樣本個(gè)數(shù)。則數(shù)據(jù)集的類別信息熵Ent(S)表示為:

(1)

(2)設(shè)特征a有k個(gè)離散值{a1,a2,…,ak},根據(jù)特征a的離散值將數(shù)據(jù)集D分成k個(gè)子數(shù)據(jù)集{S1,S2,…,Sk},其中Si是S中特征為aj的數(shù)據(jù)集。如果特征aj被選為當(dāng)前節(jié)點(diǎn),那么用特征aj對(duì)當(dāng)前樣本進(jìn)行劃分。Sij為子集Si中屬于Dj類的個(gè)數(shù),則按特征aj劃分?jǐn)?shù)據(jù)集的條件信息熵為:

(2)

(3)由(1)式和(2)式可得,特征A劃分前后的信息熵之差為信息增益,表達(dá)式為:

Gain(S,A)=Ent(S)-Ent(S|a)

(3)

(4)按照特征A劃分后的信息增益率為:

(4)

其中特征A的分裂信息為:

雖然C4.5算法具有很多的優(yōu)勢(shì),但是在處理不平衡數(shù)據(jù)上仍有不足,當(dāng)數(shù)據(jù)集不平衡時(shí),為了更高的準(zhǔn)確率,信息增益率在選擇特征時(shí)會(huì)偏向數(shù)據(jù)更多的類別,而在一些情況下如醫(yī)療診斷、電信詐騙等,負(fù)類的信息往往更為重要。

2 基于強(qiáng)化學(xué)習(xí)策略的改進(jìn)

傳統(tǒng)的C4.5算法選用信息增益率作為特征選擇的標(biāo)準(zhǔn),而面對(duì)不平衡數(shù)據(jù)集時(shí),選擇結(jié)果會(huì)偏向正類,造成負(fù)類分類精度降低,然而這些負(fù)類往往更為重要。如果有監(jiān)督學(xué)習(xí)希望分類器正確地對(duì)實(shí)例分類,那么強(qiáng)化學(xué)習(xí)的目標(biāo)是每一個(gè)行動(dòng)都要為最終的目標(biāo)——最大化長(zhǎng)期回報(bào)努力,即獲得最多的累計(jì)獎(jiǎng)勵(lì)。強(qiáng)化學(xué)習(xí)模型主要包含狀態(tài)、動(dòng)作、行動(dòng)和獎(jiǎng)勵(lì)4個(gè)元素。與一般的馬爾科夫過程不同,馬爾科夫決策過程考慮了動(dòng)作,即系統(tǒng)下一個(gè)狀態(tài)不僅和當(dāng)前的狀態(tài)有關(guān),也和當(dāng)前采取的動(dòng)作有關(guān)。根據(jù)馬爾可夫決策過程量化每一個(gè)特征對(duì)實(shí)現(xiàn)最終目標(biāo)貢獻(xiàn)的價(jià)值,這個(gè)過程就是使負(fù)類樣本被正確分類時(shí)實(shí)現(xiàn)價(jià)值最大化。這個(gè)過程用價(jià)值函數(shù)來衡量,本文將價(jià)值函數(shù)和信息增益率相結(jié)合作為新的特征選擇策略,并對(duì)每一層決策樹的價(jià)值函數(shù)進(jìn)行計(jì)算,使得決策樹達(dá)到最優(yōu)化。

2.1 價(jià)值函數(shù)

為了解決不平衡數(shù)據(jù)的分類問題,本文引入2個(gè)價(jià)值函數(shù):

(1)標(biāo)準(zhǔn)化互信息[11-12](Normalized Mutual Information,NMI)可以用來衡量預(yù)測(cè)結(jié)果與真實(shí)結(jié)果的相似度。NMI通常用于檢測(cè)網(wǎng)絡(luò)劃分結(jié)果與真實(shí)劃分結(jié)果之間的差異,并計(jì)算正確率。互信息提供的是特征和類別之間的絕對(duì)信息量,不能真實(shí)反映特征集相對(duì)于類別集整體的表達(dá)能力,這是因?yàn)樗趯?shí)踐中隨著特征集和類別集的自身規(guī)模變化而變化。NMI針對(duì)H(X)和H(Y)的整體大小進(jìn)行標(biāo)準(zhǔn)化處理,以消除H(X)和H(Y)大小的影響,使其能精確的反映出這些變化。

(2) 馬修斯相關(guān)系數(shù)[13](Matthews Correlation Coefficient,MCC) 主要用于衡量二分類問題,其綜合考慮了混淆矩陣大小的比率得分。它是一個(gè)比較均衡的指標(biāo),對(duì)于樣本不平衡情況下也可以使用。MCC的取值范圍在[-1,1],取值為1表示預(yù)測(cè)的結(jié)果與實(shí)際結(jié)果完全一致,取值為0表示預(yù)測(cè)的結(jié)果還不如隨機(jī)預(yù)測(cè)的結(jié)果,-1表示預(yù)測(cè)結(jié)果與實(shí)際的結(jié)果完全不一致?？梢钥闯?MCC本質(zhì)上是描述預(yù)測(cè)結(jié)果與實(shí)際結(jié)果之間的相關(guān)系數(shù)。

這2個(gè)價(jià)值函數(shù)都是平衡指標(biāo),用來提高負(fù)類的權(quán)重,使負(fù)類的準(zhǔn)確率提高。

2.2 特征選擇標(biāo)準(zhǔn)

傳統(tǒng)的決策樹構(gòu)造方法都是在決策樹完全構(gòu)建好后再對(duì)其分類效果進(jìn)行評(píng)價(jià)的。為了獲得高的準(zhǔn)確率,傳統(tǒng)決策樹的結(jié)果會(huì)偏向樣本數(shù)多的類別。為此,本文將強(qiáng)化學(xué)習(xí)的思想引入,每個(gè)特征的標(biāo)準(zhǔn)化互信息和馬修斯相關(guān)系數(shù)加權(quán),并與信息增益率相結(jié)合作為新的特征選擇標(biāo)準(zhǔn)AS。

(1)設(shè)2個(gè)類別(X,Y)的聯(lián)合分布為p(i,j),即各類別判斷正確的樣本數(shù)占總樣本數(shù)的概率;設(shè)邊緣分布分別為p(i),即在預(yù)測(cè)結(jié)果中各類別樣本數(shù)占總樣本數(shù)的概率;設(shè)互信息MI(X,Y)是聯(lián)合分布p(i,j)與邊緣分布乘積p(i)p(j)的相對(duì)熵。

(5)

(6)

(2)設(shè)TP為真負(fù)類的數(shù)量,TN為真正類的數(shù)量,FP為假負(fù)類的數(shù)量,FN為假正類的數(shù)量。根據(jù)混淆矩陣得出CMCC為:

(7)

其中:N為樣本個(gè)數(shù);W=(TP+FN)/N;V=(TP+FP)/N。

(3)根據(jù)(6)式、(7)式,可以得到一個(gè)新的價(jià)值函數(shù)f:

f=ωCMCC+(1-ω)CNMI

(8)

其中,ω為權(quán)重。

(4)新的特征選擇標(biāo)準(zhǔn)AS定義為:

AS=(2Gain-ratio-1)f

(9)

改進(jìn)后算法的基本流程如下：

(1)輸入訓(xùn)練集S,特征集A。

(2)若S=?,則返回決策樹T。

(3)若訓(xùn)練集S中所有樣本都屬于同一個(gè)類別,則T為單節(jié)點(diǎn)樹,并將該類別作為該節(jié)點(diǎn)的類標(biāo)記,返回T。

(4)若特征集A為空集,則T為單節(jié)點(diǎn)樹,并將S中樣本數(shù)最多的類別作為類標(biāo)記,返回T。

(5)根據(jù)(9)式計(jì)算S中各特征的AS,選擇AS最大的特征,作為該節(jié)點(diǎn)的分裂特征。

(6)對(duì)于第i個(gè)節(jié)點(diǎn),將作為新的訓(xùn)練集,對(duì)當(dāng)前特征以外的特征進(jìn)行遞歸調(diào)用步驟(2)～步驟(5)。

(7)輸出決策樹T。

改進(jìn)后決策樹算法流程如圖1所示。

圖1 決策樹改進(jìn)算法流程

3 實(shí)驗(yàn)結(jié)果及分析

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

本實(shí)驗(yàn)采用UCI公開數(shù)據(jù)集中7個(gè)不平衡的數(shù)據(jù)集進(jìn)行測(cè)試,見表1所列。本文實(shí)驗(yàn)平臺(tái)為Matlab R2016b。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 實(shí)驗(yàn)結(jié)果

本文分別對(duì)傳統(tǒng)的C4.5算法、基于強(qiáng)化學(xué)習(xí)改進(jìn)的C4.5算法(CRDT)以及本文提出的基于馬爾可夫決策過程的MCC決策樹算法和NMI決策樹算法進(jìn)行測(cè)試,分別比較預(yù)測(cè)的負(fù)類準(zhǔn)確率、正類準(zhǔn)確率以及總體準(zhǔn)確率。對(duì)比結(jié)果分別見表2～表4所列,如圖2～圖4所示。

圖2 負(fù)類準(zhǔn)確率對(duì)比

圖3 正類準(zhǔn)確率對(duì)比

圖4 整體準(zhǔn)確率對(duì)比

表2 負(fù)類準(zhǔn)確率

表3 正類準(zhǔn)確率

表4 整體準(zhǔn)確率

本文測(cè)試的基于標(biāo)準(zhǔn)化互信息的改進(jìn)決策樹算法和基于馬修斯相關(guān)系數(shù)的改進(jìn)決策樹算法的效果不太穩(wěn)定。對(duì)于數(shù)據(jù)集2、4、6、7,MCC方法在保證整體準(zhǔn)確率的基礎(chǔ)上,提高了負(fù)類的準(zhǔn)確率。數(shù)據(jù)集為3、5時(shí)，NMI方法對(duì)于負(fù)類準(zhǔn)確率提升效果更好。與以上2種方法比較,將2個(gè)價(jià)值函數(shù)加權(quán)后的改進(jìn)決策樹算法效果最好。

將本文加權(quán)后的改進(jìn)決策樹算法與傳統(tǒng)的C4.5算法和基于強(qiáng)化學(xué)習(xí)的改進(jìn)決策樹算法比較,這種算法對(duì)于負(fù)類的分類效果以及整體的分類效果均有顯著提高。由于提高了負(fù)類在分類中的權(quán)重,導(dǎo)致數(shù)據(jù)集1、2對(duì)正類的分類效果有所下降。綜上所述,本文改進(jìn)后的決策樹算法對(duì)于不平衡數(shù)據(jù)的分類效果比原有算法有所提升。

4 結(jié) 論

本文針對(duì)不平衡數(shù)據(jù)分類精度不高的問題,提出了一種基于馬爾可夫決策過程的決策樹算法。通過標(biāo)準(zhǔn)化互信息和馬修斯相關(guān)系數(shù)2個(gè)平衡的價(jià)值函數(shù)加權(quán),使負(fù)類的權(quán)重提高。利用當(dāng)前狀態(tài)的價(jià)值函數(shù)作為下一個(gè)狀態(tài)的屬性選擇標(biāo)準(zhǔn),對(duì)決策樹算法進(jìn)行優(yōu)化。對(duì)比實(shí)驗(yàn)結(jié)果,非平衡數(shù)據(jù)的負(fù)類分類準(zhǔn)確率及整體準(zhǔn)確率均得到顯著提高。今后將進(jìn)一步研究新算法的工作效率,并將算法推廣到實(shí)際應(yīng)用。