文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.170338
中文引用格式： 張翕茜，李鳳蓮，張雪英，等. 基于代價(jià)敏感混合分裂策略的多決策樹(shù)算法[J].電子技術(shù)應(yīng)用，2017，43(10)：128-131，136.
英文引用格式： Zhang Xiqian，Li Fenglian，Zhang Xueying，et al. A multiple decision tree algorithm based on cost-sensitive hybrid splitting strategy[J].Application of Electronic Technique，2017，43(10)：128-131，136.
0 引言
瓦斯突出一直高居所有礦井事故之首。如果能在事故發(fā)生之前進(jìn)行有效瓦斯突出預(yù)測(cè)，對(duì)降低礦井瓦斯事故發(fā)生、提高煤礦安全生產(chǎn)效率，具有非常重要的意義。分類算法可以通過(guò)抽取歷史數(shù)據(jù)的重要信息以預(yù)測(cè)未來(lái)數(shù)據(jù)的發(fā)展。在煤礦瓦斯預(yù)測(cè)中，決策樹(shù)算法因?yàn)槟Ｐ秃?jiǎn)單，便于實(shí)時(shí)計(jì)算，可以處理離散型和連續(xù)型數(shù)據(jù)，且結(jié)果易于理解等特點(diǎn)，常被用于瓦斯預(yù)測(cè)模型構(gòu)建。
決策樹(shù)算法的研究主要分為兩類：(1)對(duì)單決策樹(shù)算法的改進(jìn)，例如C4.5、CART、SPRINT和SLIQ[1]；(2)使用集成分類器，提高準(zhǔn)確性，例如：Bagging、Boosting和隨機(jī)森林（Random forests，RF）。其中，隨機(jī)森林屬于廣泛應(yīng)用的較好的集成分類器[2]，可以解決單決策樹(shù)過(guò)擬合的分類準(zhǔn)確性低下問(wèn)題。本文的研究是基于隨機(jī)森林的改進(jìn)。
分類器對(duì)一種類別的過(guò)多訓(xùn)練會(huì)導(dǎo)致另一類分類準(zhǔn)確度降低，從而使分類器易過(guò)擬合導(dǎo)致少數(shù)類準(zhǔn)確度降低。在煤礦瓦斯預(yù)警中的具體體現(xiàn)是：瓦斯突出或危險(xiǎn)狀況下的數(shù)據(jù)稀少，為少數(shù)類，安全狀態(tài)下的數(shù)據(jù)占多數(shù)，為多數(shù)類，導(dǎo)致分類器對(duì)少數(shù)類預(yù)測(cè)準(zhǔn)確率偏低，從而造成對(duì)可能發(fā)生瓦斯突出隱患的漏報(bào)現(xiàn)象。
面對(duì)不平衡數(shù)據(jù)分類問(wèn)題，傳統(tǒng)決策樹(shù)算法缺陷是對(duì)少數(shù)類學(xué)習(xí)不充分，易造成分類結(jié)果偏向多數(shù)類現(xiàn)象[3]，使得表現(xiàn)為危險(xiǎn)的異常情況，其預(yù)測(cè)準(zhǔn)確率反而大大降低[4]。針對(duì)此問(wèn)題，國(guó)內(nèi)外研究方法主要有兩方面：(1)改變數(shù)據(jù)分布結(jié)構(gòu)，利用過(guò)采樣和欠采樣的手段，使數(shù)據(jù)分布易于算法執(zhí)行和處理[5-6]，但是此方法容易造成多數(shù)類信息缺失或少數(shù)類學(xué)習(xí)不充分；(2)對(duì)分類器進(jìn)行改進(jìn)，改進(jìn)分類評(píng)價(jià)指標(biāo)，使分類器能夠較準(zhǔn)確地處理不平衡數(shù)據(jù)[7-8]。在針對(duì)分類器的改進(jìn)中，目前最流行的方法是加入代價(jià)敏感因子[9]，其實(shí)現(xiàn)機(jī)理是對(duì)少數(shù)類分類錯(cuò)誤給予一個(gè)較大權(quán)重的懲罰代價(jià)因子，同時(shí)對(duì)多數(shù)類分類錯(cuò)誤給予一個(gè)較小權(quán)重的懲罰代價(jià)因子。例如，文獻(xiàn)[10]提出了一種代價(jià)敏感隨機(jī)森林算法，在隨機(jī)森林的基礎(chǔ)上加入代價(jià)敏感因子，以提高在不平衡數(shù)據(jù)問(wèn)題上對(duì)少數(shù)類的預(yù)測(cè)。然而在隨機(jī)產(chǎn)生決策樹(shù)過(guò)程中，因?yàn)樯贁?shù)類數(shù)據(jù)的訓(xùn)練樣本少和屬性選擇不全的原因，依然存在只有個(gè)別決策樹(shù)對(duì)少數(shù)類得到充分訓(xùn)練，進(jìn)而導(dǎo)致結(jié)果偏向多數(shù)類的預(yù)測(cè)缺陷。
本文針對(duì)不平衡數(shù)據(jù)集特點(diǎn)，提出了一種基于混合屬性的代價(jià)敏感多決策樹(shù)算法，算法首先將Gini指標(biāo)和信息增益指標(biāo)線性組合作為屬性選擇策略，進(jìn)而用代價(jià)敏感因子對(duì)組合策略進(jìn)行加權(quán)，最后使用輸入樣本的每個(gè)屬性作為多決策樹(shù)的根節(jié)點(diǎn)，改進(jìn)代價(jià)敏感隨機(jī)森林算法只采用部分屬性作為根屬性選擇方式缺陷，達(dá)到保證多數(shù)類分類準(zhǔn)確性的前提下，有效提高少數(shù)類分類準(zhǔn)確性的目的。
1 混合分裂屬性指標(biāo)的確定
決策樹(shù)構(gòu)建的準(zhǔn)確度主要取決于分裂屬性的選擇策略，本文采用組合策略是在結(jié)合C4.5和CART算法的基礎(chǔ)上，融合代價(jià)敏感因子形成的分裂屬性。其屬性選擇策略AS(Attribute Selection)如下：
式中，Ginisplit(A)(T)表示屬性A劃分后的Gini指數(shù)，是CART算法的分裂指標(biāo)；GainRatio表示屬性A劃分后的信息增益率，是C4.5算法的分裂指標(biāo)；C(Aj)表示集合T經(jīng)過(guò)屬性Aj分裂后的誤分代價(jià)。
定義1：誤分代價(jià)：對(duì)于二分類問(wèn)題，給定一個(gè)樣本集S，其含有s個(gè)樣本，Aj(j=1，2，…，n)個(gè)屬性。每個(gè)屬性Aj含有m個(gè)取值ai(i=1，2，…，m)。那么屬性Aj分裂后的所有子集總的誤分代價(jià)可以表示為：
式中，P(i)是分裂后樣本數(shù)量占分裂前的總概率，C(i)表示屬性值ai的樣本子集所構(gòu)成的總代價(jià)[11]。
2 代價(jià)敏感混合屬性多決策樹(shù)算法
隨機(jī)森林的每棵決策樹(shù)的訓(xùn)練樣本是隨機(jī)抽取的，在不平衡數(shù)據(jù)集中，少數(shù)類被抽取到的概率幾乎為零，因此在最后決策樹(shù)形成過(guò)程中，少數(shù)類不會(huì)得到充分訓(xùn)練，結(jié)果會(huì)偏向多數(shù)類。
傳統(tǒng)的決策樹(shù)分類算法在構(gòu)建決策樹(shù)過(guò)程中，通過(guò)對(duì)每個(gè)屬性的分裂點(diǎn)進(jìn)行決策計(jì)算，分裂點(diǎn)的選擇容易受屬性個(gè)數(shù)和訓(xùn)練樣本大小的影響。這種選取方法并未考慮根節(jié)點(diǎn)對(duì)決策樹(shù)構(gòu)建的影響，及其對(duì)預(yù)測(cè)結(jié)果的影響；尤其在不平衡數(shù)據(jù)分類問(wèn)題中，對(duì)少數(shù)類的錯(cuò)誤影響會(huì)造成致命后果。如果根節(jié)點(diǎn)選擇錯(cuò)誤，那么在后續(xù)分裂過(guò)程中想要糾正決策樹(shù)代價(jià)非常巨大。
本文提出了代價(jià)敏感混合屬性多決策樹(shù)算法 (Cost-sensitive Hybrid Measure Attributes Selection Multi-Decision Tree，CHMDT)，該算法原理框圖如圖1所示，其中采用每個(gè)屬性作為根節(jié)點(diǎn)分別建樹(shù)，即建樹(shù)過(guò)程使用了全部屬性。目的是訓(xùn)練過(guò)程中保證所有少數(shù)類和屬性得到充分學(xué)習(xí)。
2.1 CHMDT算法流程
CHMDT采用廣度優(yōu)先的算法設(shè)計(jì)，即先采用所有屬性作為各樹(shù)的根節(jié)點(diǎn)進(jìn)行分裂，然后每個(gè)根節(jié)點(diǎn)依據(jù)混合策略分裂屬性為依據(jù)單獨(dú)建樹(shù)，具體實(shí)現(xiàn)流程如下：
輸入：訓(xùn)練樣本集S
輸出：一個(gè)多決策樹(shù)
Make Multi-Decision Tree(S){
If(S滿足終止條件) Then return;
For(i=1;i<樣本中屬性個(gè)數(shù);i++)
以第i個(gè)屬性作為根節(jié)點(diǎn)分裂；
For(j=1;j<樣本中剩余屬性個(gè)數(shù);j++)
根據(jù)式(1)計(jì)算各屬性分裂點(diǎn)的混合分裂屬性指標(biāo)；
找出最佳分裂點(diǎn)，將S分為SL和SR；
Make Decision Tree(SL);
Make Decision Tree(SR);
返回訓(xùn)練規(guī)則集；
匯總規(guī)則集；
}
2.2 混合屬性單決策樹(shù)算法流程
CHMDT在根節(jié)點(diǎn)選擇確定之后分別采用代價(jià)敏感混合策略屬性單決策樹(shù)算法（Cost-sensitive Hybrid Measure Decision Tree，CHDT）建樹(shù)，采用式（1）的分裂指標(biāo)。算法流程如下：
Make Decision Tree(S){
If(S滿足終止條件) Then return;
For(i=1;i<S中屬性個(gè)數(shù);i++)
計(jì)算各屬性分裂點(diǎn)的混合分裂屬性指數(shù)；
找出最佳分裂點(diǎn)，將S分為SL和SR；
Make Decision Tree(SL);
Make Decision Tree(SR);
}
其中，SL代表S的左分枝，SR代表S的右分枝。決策樹(shù)最終是一棵二叉樹(shù)。
算法的終止條件為以下任一個(gè)條件滿足：(1)S中的訓(xùn)練樣本都為同一類別，即決策樹(shù)達(dá)到葉子節(jié)點(diǎn)；(2)S中訓(xùn)練樣本數(shù)達(dá)到某一閾值；(3)屬性全部分裂完畢，沒(méi)有待分裂屬性。
3 實(shí)驗(yàn)及分析
本實(shí)驗(yàn)?zāi)康闹饕球?yàn)證代價(jià)敏感混合屬性分裂指標(biāo)在少數(shù)類分類和整體準(zhǔn)確率預(yù)測(cè)性能的優(yōu)勢(shì)，以及提高所提出的CHMDT性能。
3.1 實(shí)驗(yàn)數(shù)據(jù)
實(shí)驗(yàn)數(shù)據(jù)集采用UCI和KEEL-Imbalanced Data Sets中的11個(gè)不同平衡率的非平衡數(shù)據(jù)集，詳情如表1所示。
3.2 實(shí)驗(yàn)設(shè)置
訓(xùn)練樣本與測(cè)試樣本比為2:1，保證類別比重不變。為避免偶然因素，每個(gè)測(cè)試集進(jìn)行10次交叉驗(yàn)證實(shí)驗(yàn)，每次實(shí)驗(yàn)訓(xùn)練樣本和測(cè)試樣本都打亂順序隨機(jī)分配。實(shí)驗(yàn)分為兩種場(chǎng)景進(jìn)行驗(yàn)證。
(1)場(chǎng)景一（驗(yàn)證代價(jià)敏感混合屬性性能好壞）：CLDT與CART、C4.5、ID3對(duì)比。
(2)場(chǎng)景二（驗(yàn)證CLMDT性能好壞）：CLMDT與RF、代價(jià)敏感混合屬性隨機(jī)森林（CH-RF）對(duì)比。
3.3 評(píng)價(jià)指標(biāo)
本文采用真實(shí)正類率和準(zhǔn)確率作為評(píng)價(jià)指標(biāo)，其中實(shí)驗(yàn)指標(biāo)類別信息定義如表2。
(1)真實(shí)正類率TPrate/負(fù)類率TNrate：正確預(yù)測(cè)的正類/負(fù)類與實(shí)際為正類/負(fù)類的樣本數(shù)量的比值(取值范圍為0～1)。其值越大說(shuō)明正類/負(fù)類預(yù)測(cè)越準(zhǔn)確，性能越好。
真實(shí)正類率：
(2)準(zhǔn)確率：正確預(yù)測(cè)的樣本數(shù)與總樣本數(shù)的比值（取值范圍為0～1）。其值越大說(shuō)明總體預(yù)測(cè)越準(zhǔn)確，性能越好。
3.4 實(shí)驗(yàn)結(jié)果
場(chǎng)景一： CHDT算法與其他單決策樹(shù)算法在真實(shí)正類率預(yù)測(cè)性能比較如圖2所示。具體分析實(shí)驗(yàn)結(jié)果可知，對(duì)數(shù)據(jù)ecoli、car-good、wine-red4、poker-8_vs_6，CHDT算法較ID3分別提升8%、11%、9%、8%。總體準(zhǔn)確率比較如圖3所示，可以看出，CHDT一直保持穩(wěn)定且較高的準(zhǔn)確率。
場(chǎng)景二：CHMDT算法與RF、CH-RF算法在真實(shí)正類率預(yù)測(cè)性能比較如圖4所示。對(duì)數(shù)據(jù)集new-thyroid1、ecoli、page-blocks0來(lái)說(shuō)，CHMDT算法相比其他兩種方法有一定的增長(zhǎng)；對(duì)數(shù)據(jù)集yeast、abolone-3_vs_11來(lái)說(shuō)，CHMDT算法相比其他兩種方法有較大提升；剩余數(shù)據(jù)集中，因?yàn)樯贁?shù)類樣本較少，RF和CH-RF出現(xiàn)“一邊倒”現(xiàn)象，少數(shù)類預(yù)測(cè)為0，但CHMDT算法均得到了一定的真實(shí)正類率預(yù)測(cè)結(jié)果。總體準(zhǔn)確率比較如圖5所示，可以看出，CHMDT算法較其他算法準(zhǔn)確率都略有提高。
3.5 結(jié)果分析
從場(chǎng)景一的實(shí)驗(yàn)結(jié)果來(lái)看，采用CHDT算法在保證較高真實(shí)正類率預(yù)測(cè)結(jié)果的同時(shí)，準(zhǔn)確率依然保持較高。從場(chǎng)景二的實(shí)驗(yàn)結(jié)果來(lái)看，RF算法在少數(shù)類訓(xùn)練樣本極少的情況下，預(yù)測(cè)結(jié)果會(huì)偏向多數(shù)類，CH-RF算法有適當(dāng)提升。總的來(lái)說(shuō)，CHMDT算法在少數(shù)類樣本稀缺的情況下有良好的少數(shù)類預(yù)測(cè)性能和較高的整體預(yù)測(cè)準(zhǔn)確性。
4 煤礦瓦斯預(yù)警有效性驗(yàn)證
本實(shí)驗(yàn)選取同一工作面、不同時(shí)刻的煤礦瓦斯監(jiān)測(cè)數(shù)據(jù)共461條，其中瓦斯突出數(shù)據(jù)26條，安全數(shù)據(jù)435條。屬性值分別來(lái)自井下16個(gè)不同測(cè)點(diǎn)的傳感器數(shù)據(jù)發(fā)回。CHDT算法與C4.5、ID3及CART預(yù)測(cè)性能比較如圖6所示，可以看出，CHDT算法對(duì)正類的預(yù)測(cè)正確率提高的同時(shí)，負(fù)類率及準(zhǔn)確率性能依然保持。多決策樹(shù)算法預(yù)測(cè)性能比較如圖7所示，可以看出，與RF及CH-RF算法相比，本文提出的CHMDT算法對(duì)正類樣本的預(yù)測(cè)性能有明顯提高，有效避免了因隨機(jī)選擇屬性導(dǎo)致的屬性信息丟失和少數(shù)類欠訓(xùn)練問(wèn)題，同時(shí)負(fù)類率及準(zhǔn)確率性能沒(méi)有受到影響。
5 結(jié)束語(yǔ)
本文基于C4.5和CART算法的分裂屬性用于非平衡數(shù)據(jù)集時(shí)少數(shù)類預(yù)測(cè)性能不佳的缺陷，提出了融合代價(jià)敏感指標(biāo)的混合策略分裂屬性，并將其作為隨機(jī)森林算法屬性選擇措施，得到了基于代價(jià)敏感混合策略分裂屬性的多決策樹(shù)算法CHMDT。實(shí)驗(yàn)結(jié)果表明，該方法有良好的少數(shù)類預(yù)測(cè)性能和較高的整體預(yù)測(cè)準(zhǔn)確性。將該方法用于煤礦瓦斯預(yù)警數(shù)據(jù)中，實(shí)驗(yàn)結(jié)果表明，本文所提出的方法可有效提高煤礦瓦斯預(yù)警數(shù)據(jù)整體預(yù)測(cè)性能。但采用所有屬性作為根節(jié)點(diǎn)信息，在屬性信息較多時(shí)，會(huì)存在算法復(fù)雜度偏高的問(wèn)題，為此，下一步將繼續(xù)研究基于分布式存儲(chǔ)架構(gòu)的多決策樹(shù)實(shí)現(xiàn)方式。
參考文獻(xiàn)
[1] KOTSIANTIS S B.Decision trees：a recent overview[J].Artificial Intelligence Review，2013，39(4)：261-283.
[2] BANFIELD R E，HALL L O，BOWYER K W，et al.A comparison of decision tree ensemble creation techniques[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2007，29(1)：173-80.
[3] XUE J H，HALL P.Why does rebalancing class-unbalanced data improve AUC for Linear discriminant analysis?[J].Pattern Analysis & Machine Intelligence IEEE Transactions on，2015，37(5)：1109-1112.
[4] 杜春蕾，張雪英，李鳳蓮，等.改進(jìn)的CART算法在煤層底板突水預(yù)測(cè)中的應(yīng)用[J].工礦自動(dòng)化，2014，40(12)：52-56.
[5] VARLAMIS I.Evolutionary data sampling for user movement classification[C].Evolutionary Computation.IEEE，2015：730-737.
[6] CATENI S，COLLA V，VANNUCCI M.A method for resampling imbalanced datasets in binary classification tasks for real-world problems[J].Neurocomputing，2014，135(8)：32-41.
[7] KRAWCZYK B，WOZNIAK M，SCHAEFER G.Cost-sensitive decision tree ensembles for effective imbalanced classification[J].Applied Soft Computing，2013，14(1)：554-562.
[8] SAHIN Y，BULKAN S，DUMAN E.A cost-sensitive decision tree approach for fraud detection[J].Expert Systems with Applications，2013，40(15)：5916-5923.
[9] LOMAX S，VADERA S.A survey of cost-sensitive decision tree induction algorithms[J].Acm Computing Surveys，2013，45(2)：227-268.
[10] 尹華，胡玉平，Yin Hua，等.一種代價(jià)敏感隨機(jī)森林算法[J].武漢大學(xué)學(xué)報(bào)工學(xué)版，2014，47(5)：707-711.
[11] SAHIN Y，BULKAN S，DUMAN E.A cost-sensitive decision tree approach for fraud detection[J].Expert Systems with Applications，2013，40(15)：5916-5923.
作者信息：
張翕茜1，李鳳蓮1，張雪英1，田玉楚1，2
（1.太原理工大學(xué) 信息工程學(xué)院，山西 晉中030600；
2.昆士蘭科技大學(xué) 電機(jī)工程及計(jì)算機(jī)科學(xué)學(xué)院，澳大利亞 布里斯班4001）