0 引言

    瓦斯突出一直高居所有礦井事故之首,。如果能在事故發(fā)生之前進(jìn)行有效瓦斯突出預(yù)測,，對降低礦井瓦斯事故發(fā)生、提高煤礦安全生產(chǎn)效率,，具有非常重要的意義,。分類算法可以通過抽取歷史數(shù)據(jù)的重要信息以預(yù)測未來數(shù)據(jù)的發(fā)展。在煤礦瓦斯預(yù)測中,，決策樹算法因為模型簡單,，便于實時計算，可以處理離散型和連續(xù)型數(shù)據(jù),，且結(jié)果易于理解等特點(diǎn),，常被用于瓦斯預(yù)測模型構(gòu)建。

    決策樹算法的研究主要分為兩類：(1)對單決策樹算法的改進(jìn),，例如C4.5、CART,、SPRINT和SLIQ^[1],；(2)使用集成分類器，提高準(zhǔn)確性,，例如：Bagging,、Boosting和隨機(jī)森林（Random forests，RF）,。其中,，隨機(jī)森林屬于廣泛應(yīng)用的較好的集成分類器^[2]，可以解決單決策樹過擬合的分類準(zhǔn)確性低下問題,。本文的研究是基于隨機(jī)森林的改進(jìn),。

    分類器對一種類別的過多訓(xùn)練會導(dǎo)致另一類分類準(zhǔn)確度降低，從而使分類器易過擬合導(dǎo)致少數(shù)類準(zhǔn)確度降低,。在煤礦瓦斯預(yù)警中的具體體現(xiàn)是：瓦斯突出或危險狀況下的數(shù)據(jù)稀少,，為少數(shù)類，安全狀態(tài)下的數(shù)據(jù)占多數(shù),，為多數(shù)類,，導(dǎo)致分類器對少數(shù)類預(yù)測準(zhǔn)確率偏低，從而造成對可能發(fā)生瓦斯突出隱患的漏報現(xiàn)象,。

    面對不平衡數(shù)據(jù)分類問題,，傳統(tǒng)決策樹算法缺陷是對少數(shù)類學(xué)習(xí)不充分，易造成分類結(jié)果偏向多數(shù)類現(xiàn)象^[3],，使得表現(xiàn)為危險的異常情況,，其預(yù)測準(zhǔn)確率反而大大降低^[4]。針對此問題,，國內(nèi)外研究方法主要有兩方面：(1)改變數(shù)據(jù)分布結(jié)構(gòu),，利用過采樣和欠采樣的手段，使數(shù)據(jù)分布易于算法執(zhí)行和處理^[5-6]，但是此方法容易造成多數(shù)類信息缺失或少數(shù)類學(xué)習(xí)不充分,；(2)對分類器進(jìn)行改進(jìn),，改進(jìn)分類評價指標(biāo)，使分類器能夠較準(zhǔn)確地處理不平衡數(shù)據(jù)^[7-8],。在針對分類器的改進(jìn)中,，目前最流行的方法是加入代價敏感因子^[9]，其實現(xiàn)機(jī)理是對少數(shù)類分類錯誤給予一個較大權(quán)重的懲罰代價因子,，同時對多數(shù)類分類錯誤給予一個較小權(quán)重的懲罰代價因子,。例如，文獻(xiàn)[10]提出了一種代價敏感隨機(jī)森林算法,，在隨機(jī)森林的基礎(chǔ)上加入代價敏感因子,，以提高在不平衡數(shù)據(jù)問題上對少數(shù)類的預(yù)測。然而在隨機(jī)產(chǎn)生決策樹過程中,，因為少數(shù)類數(shù)據(jù)的訓(xùn)練樣本少和屬性選擇不全的原因,，依然存在只有個別決策樹對少數(shù)類得到充分訓(xùn)練，進(jìn)而導(dǎo)致結(jié)果偏向多數(shù)類的預(yù)測缺陷,。

    本文針對不平衡數(shù)據(jù)集特點(diǎn),，提出了一種基于混合屬性的代價敏感多決策樹算法，算法首先將Gini指標(biāo)和信息增益指標(biāo)線性組合作為屬性選擇策略,，進(jìn)而用代價敏感因子對組合策略進(jìn)行加權(quán),，最后使用輸入樣本的每個屬性作為多決策樹的根節(jié)點(diǎn)，改進(jìn)代價敏感隨機(jī)森林算法只采用部分屬性作為根屬性選擇方式缺陷,，達(dá)到保證多數(shù)類分類準(zhǔn)確性的前提下,，有效提高少數(shù)類分類準(zhǔn)確性的目的。

1 混合分裂屬性指標(biāo)的確定

    決策樹構(gòu)建的準(zhǔn)確度主要取決于分裂屬性的選擇策略,，本文采用組合策略是在結(jié)合C4.5和CART算法的基礎(chǔ)上,，融合代價敏感因子形成的分裂屬性。其屬性選擇策略AS(Attribute Selection)如下：

式中,，Gini_split(A)(T)表示屬性A劃分后的Gini指數(shù),，是CART算法的分裂指標(biāo)；GainRatio表示屬性A劃分后的信息增益率,，是C4.5算法的分裂指標(biāo),；C(A_j)表示集合T經(jīng)過屬性A_j分裂后的誤分代價。

    定義1：誤分代價：對于二分類問題,，給定一個樣本集S,，其含有s個樣本，A_j(j=1,，2,，…,，n)個屬性。每個屬性A_j含有m個取值a_i(i=1,，2,，…，m),。那么屬性A_j分裂后的所有子集總的誤分代價可以表示為：

式中,，P(i)是分裂后樣本數(shù)量占分裂前的總概率，C(i)表示屬性值ai的樣本子集所構(gòu)成的總代價^[11],。

2 代價敏感混合屬性多決策樹算法

    隨機(jī)森林的每棵決策樹的訓(xùn)練樣本是隨機(jī)抽取的,，在不平衡數(shù)據(jù)集中，少數(shù)類被抽取到的概率幾乎為零,，因此在最后決策樹形成過程中,，少數(shù)類不會得到充分訓(xùn)練，結(jié)果會偏向多數(shù)類,。

    傳統(tǒng)的決策樹分類算法在構(gòu)建決策樹過程中,，通過對每個屬性的分裂點(diǎn)進(jìn)行決策計算，分裂點(diǎn)的選擇容易受屬性個數(shù)和訓(xùn)練樣本大小的影響,。這種選取方法并未考慮根節(jié)點(diǎn)對決策樹構(gòu)建的影響，及其對預(yù)測結(jié)果的影響,；尤其在不平衡數(shù)據(jù)分類問題中,，對少數(shù)類的錯誤影響會造成致命后果。如果根節(jié)點(diǎn)選擇錯誤,，那么在后續(xù)分裂過程中想要糾正決策樹代價非常巨大,。

    本文提出了代價敏感混合屬性多決策樹算法 (Cost-sensitive Hybrid Measure Attributes Selection Multi-Decision Tree，CHMDT),，該算法原理框圖如圖1所示,，其中采用每個屬性作為根節(jié)點(diǎn)分別建樹，即建樹過程使用了全部屬性,。目的是訓(xùn)練過程中保證所有少數(shù)類和屬性得到充分學(xué)習(xí),。

2.1 CHMDT算法流程

    CHMDT采用廣度優(yōu)先的算法設(shè)計，即先采用所有屬性作為各樹的根節(jié)點(diǎn)進(jìn)行分裂,，然后每個根節(jié)點(diǎn)依據(jù)混合策略分裂屬性為依據(jù)單獨(dú)建樹,，具體實現(xiàn)流程如下：

    輸入：訓(xùn)練樣本集S

    輸出：一個多決策樹

    Make Multi-Decision Tree(S){

     If(S滿足終止條件) Then return;

     For(i=1;i<樣本中屬性個數(shù);i++)

    以第i個屬性作為根節(jié)點(diǎn)分裂；

    For(j=1;j<樣本中剩余屬性個數(shù);j++)

     根據(jù)式(1)計算各屬性分裂點(diǎn)的混合分裂屬性指標(biāo),；

     找出最佳分裂點(diǎn),，將S分為SL和SR；

     Make Decision Tree(SL);

     Make Decision Tree(SR);

    返回訓(xùn)練規(guī)則集,；

     匯總規(guī)則集,；

    }

2.2 混合屬性單決策樹算法流程

    CHMDT在根節(jié)點(diǎn)選擇確定之后分別采用代價敏感混合策略屬性單決策樹算法（Cost-sensitive Hybrid Measure Decision Tree,，CHDT）建樹，采用式（1）的分裂指標(biāo),。算法流程如下：

    Make Decision Tree(S){

     If(S滿足終止條件) Then return;

     For(i=1;i<S中屬性個數(shù);i++)

        計算各屬性分裂點(diǎn)的混合分裂屬性指數(shù),；

        找出最佳分裂點(diǎn)，將S分為SL和SR,；

        Make Decision Tree(SL);

        Make Decision Tree(SR);

    }

    其中,，SL代表S的左分枝，SR代表S的右分枝,。決策樹最終是一棵二叉樹,。

    算法的終止條件為以下任一個條件滿足：(1)S中的訓(xùn)練樣本都為同一類別，即決策樹達(dá)到葉子節(jié)點(diǎn),；(2)S中訓(xùn)練樣本數(shù)達(dá)到某一閾值,；(3)屬性全部分裂完畢，沒有待分裂屬性,。

3 實驗及分析

    本實驗?zāi)康闹饕球炞C代價敏感混合屬性分裂指標(biāo)在少數(shù)類分類和整體準(zhǔn)確率預(yù)測性能的優(yōu)勢,，以及提高所提出的CHMDT性能。

3.1 實驗數(shù)據(jù)

    實驗數(shù)據(jù)集采用UCI和KEEL-Imbalanced Data Sets中的11個不同平衡率的非平衡數(shù)據(jù)集,，詳情如表1所示,。

3.2 實驗設(shè)置

    訓(xùn)練樣本與測試樣本比為2:1，保證類別比重不變,。為避免偶然因素,，每個測試集進(jìn)行10次交叉驗證實驗，每次實驗訓(xùn)練樣本和測試樣本都打亂順序隨機(jī)分配,。實驗分為兩種場景進(jìn)行驗證,。

    (1)場景一（驗證代價敏感混合屬性性能好壞）：CLDT與CART、C4.5,、ID3對比,。

    (2)場景二（驗證CLMDT性能好壞）：CLMDT與RF、代價敏感混合屬性隨機(jī)森林（CH-RF）對比,。

3.3 評價指標(biāo)

    本文采用真實正類率和準(zhǔn)確率作為評價指標(biāo),，其中實驗指標(biāo)類別信息定義如表2。

    (1)真實正類率TP_rate/負(fù)類率TN_rate：正確預(yù)測的正類/負(fù)類與實際為正類/負(fù)類的樣本數(shù)量的比值(取值范圍為0～1),。其值越大說明正類/負(fù)類預(yù)測越準(zhǔn)確,，性能越好。

    真實正類率：

    (2)準(zhǔn)確率：正確預(yù)測的樣本數(shù)與總樣本數(shù)的比值（取值范圍為0～1）,。其值越大說明總體預(yù)測越準(zhǔn)確,，性能越好。

3.4 實驗結(jié)果

    場景一： CHDT算法與其他單決策樹算法在真實正類率預(yù)測性能比較如圖2所示,。具體分析實驗結(jié)果可知,，對數(shù)據(jù)ecoli,、car-good、wine-red4,、poker-8_vs_6,，CHDT算法較ID3分別提升8%、11%,、9%,、8%?？傮w準(zhǔn)確率比較如圖3所示,，可以看出，CHDT一直保持穩(wěn)定且較高的準(zhǔn)確率,。

    場景二：CHMDT算法與RF,、CH-RF算法在真實正類率預(yù)測性能比較如圖4所示。對數(shù)據(jù)集new-thyroid1,、ecoli,、page-blocks0來說，CHMDT算法相比其他兩種方法有一定的增長,；對數(shù)據(jù)集yeast,、abolone-3_vs_11來說，CHMDT算法相比其他兩種方法有較大提升,；剩余數(shù)據(jù)集中,，因為少數(shù)類樣本較少，RF和CH-RF出現(xiàn)“一邊倒”現(xiàn)象,，少數(shù)類預(yù)測為0，但CHMDT算法均得到了一定的真實正類率預(yù)測結(jié)果,?？傮w準(zhǔn)確率比較如圖5所示，可以看出,，CHMDT算法較其他算法準(zhǔn)確率都略有提高,。

3.5 結(jié)果分析 

    從場景一的實驗結(jié)果來看，采用CHDT算法在保證較高真實正類率預(yù)測結(jié)果的同時,，準(zhǔn)確率依然保持較高,。從場景二的實驗結(jié)果來看，RF算法在少數(shù)類訓(xùn)練樣本極少的情況下,，預(yù)測結(jié)果會偏向多數(shù)類,，CH-RF算法有適當(dāng)提升?？偟膩碚f,，CHMDT算法在少數(shù)類樣本稀缺的情況下有良好的少數(shù)類預(yù)測性能和較高的整體預(yù)測準(zhǔn)確性,。

4 煤礦瓦斯預(yù)警有效性驗證

    本實驗選取同一工作面、不同時刻的煤礦瓦斯監(jiān)測數(shù)據(jù)共461條,，其中瓦斯突出數(shù)據(jù)26條,，安全數(shù)據(jù)435條。屬性值分別來自井下16個不同測點(diǎn)的傳感器數(shù)據(jù)發(fā)回,。CHDT算法與C4.5,、ID3及CART預(yù)測性能比較如圖6所示，可以看出,，CHDT算法對正類的預(yù)測正確率提高的同時,，負(fù)類率及準(zhǔn)確率性能依然保持。多決策樹算法預(yù)測性能比較如圖7所示,，可以看出,，與RF及CH-RF算法相比，本文提出的CHMDT算法對正類樣本的預(yù)測性能有明顯提高,，有效避免了因隨機(jī)選擇屬性導(dǎo)致的屬性信息丟失和少數(shù)類欠訓(xùn)練問題,，同時負(fù)類率及準(zhǔn)確率性能沒有受到影響。

5 結(jié)束語

    本文基于C4.5和CART算法的分裂屬性用于非平衡數(shù)據(jù)集時少數(shù)類預(yù)測性能不佳的缺陷,，提出了融合代價敏感指標(biāo)的混合策略分裂屬性,，并將其作為隨機(jī)森林算法屬性選擇措施，得到了基于代價敏感混合策略分裂屬性的多決策樹算法CHMDT,。實驗結(jié)果表明,，該方法有良好的少數(shù)類預(yù)測性能和較高的整體預(yù)測準(zhǔn)確性。將該方法用于煤礦瓦斯預(yù)警數(shù)據(jù)中,，實驗結(jié)果表明,，本文所提出的方法可有效提高煤礦瓦斯預(yù)警數(shù)據(jù)整體預(yù)測性能。但采用所有屬性作為根節(jié)點(diǎn)信息,，在屬性信息較多時,，會存在算法復(fù)雜度偏高的問題，為此,，下一步將繼續(xù)研究基于分布式存儲架構(gòu)的多決策樹實現(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ù)測中的應(yīng)用[J].工礦自動化，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,，等.一種代價敏感隨機(jī)森林算法[J].武漢大學(xué)學(xué)報工學(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ī)科學(xué)學(xué)院,，澳大利亞 布里斯班4001）