《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 嵌入式技術(shù) > 設(shè)計應(yīng)用 > 基于代價敏感混合分裂策略的多決策樹算法
基于代價敏感混合分裂策略的多決策樹算法
2017年電子技術(shù)應(yīng)用第10期
張翕茜1，李鳳蓮1，張雪英1，田玉楚1，2
1.太原理工大學(xué) 信息工程學(xué)院，山西 晉中030600； 2.昆士蘭科技大學(xué) 電機工程及計算機科學(xué)學(xué)院，澳大利亞 布里斯班4001
摘要： 煤礦瓦斯預(yù)警可視為是否安全的分類問題，數(shù)據(jù)呈現(xiàn)不平衡分布特點。為此，提出一種混合策略屬性選擇多決策樹分類算法：算法融合代價敏感因子，結(jié)合C4.5和CART屬性選擇方法作為分裂指標(biāo)，并采用了基于不同根節(jié)點信息的多決策樹建樹方法。首先采用11個非平衡數(shù)據(jù)集進行算法有效性驗證，實驗結(jié)果表明，該方法可以有效針對不平衡數(shù)據(jù)進行分類，保證高準(zhǔn)確率的前提下，有效提高了少數(shù)類預(yù)測準(zhǔn)確性；進而將該算法用于煤礦瓦斯數(shù)據(jù)預(yù)測，結(jié)果表明，所提出方法可以有效提高煤礦瓦斯數(shù)據(jù)的總體預(yù)測性能。
中圖分類號： TP391
文獻標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.170338
中文引用格式： 張翕茜，李鳳蓮，張雪英，等. 基于代價敏感混合分裂策略的多決策樹算法[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.
A multiple decision tree algorithm based on cost-sensitive hybrid splitting strategy
Zhang Xiqian1，Li Fenglian1，Zhang Xueying1，Tian Yuchu1，2
1.College of Information Engineering，Taiyuan University of Technology，Jinzhong 030600，China； 2.School of Electrical Engineering and Computer Science，Queensland University of Technology，Brisbane QLD 4001，Australia
Abstract： Coal mine gas early warning can be regarded as security classification problem, and the data show unbalanced distribution characteristics. Therefore, this paper presents a Cost-sensitive Hybrid Measure Attributes Selection Multi-Decision Tree(CHMDT) algorithm. It combines C4.5 and CART by hybrid measure as the attribute split selection method, which also considers cost-sensitive factor. The algorithm uses multi-decision tree building method based on different root node. The paper first uses 11 imbalanced data sets to illustrate the validity of the algorithm. Experimental results show that the proposed method can effectively deal with imbalanced datasets and improve the prediction accuracy of minority class under the high total accuracy performance. Moreover, the experimental results on coal mine gas early warning data show that the proposed algorithm can effectively improve the predicting performance of coal mine gas data.
Key words : imbalanced data；cost-sensitive；hybrid-attribute；multi-decision tree；coal mine gas early-warning

0 引言

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

    決策樹算法的研究主要分為兩類：(1)對單決策樹算法的改進，例如C4.5、CART、SPRINT和SLIQ[1]；(2)使用集成分類器，提高準(zhǔn)確性，例如：Bagging、Boosting和隨機森林（Random forests，RF）。其中，隨機森林屬于廣泛應(yīng)用的較好的集成分類器[2]，可以解決單決策樹過擬合的分類準(zhǔ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)對分類器進行改進，改進分類評價指標(biāo)，使分類器能夠較準(zhǔn)確地處理不平衡數(shù)據(jù)[7-8]。在針對分類器的改進中，目前最流行的方法是加入代價敏感因子[9]，其實現(xiàn)機理是對少數(shù)類分類錯誤給予一個較大權(quán)重的懲罰代價因子，同時對多數(shù)類分類錯誤給予一個較小權(quán)重的懲罰代價因子。例如，文獻[10]提出了一種代價敏感隨機森林算法，在隨機森林的基礎(chǔ)上加入代價敏感因子，以提高在不平衡數(shù)據(jù)問題上對少數(shù)類的預(yù)測。然而在隨機產(chǎn)生決策樹過程中，因為少數(shù)類數(shù)據(jù)的訓(xùn)練樣本少和屬性選擇不全的原因，依然存在只有個別決策樹對少數(shù)類得到充分訓(xùn)練，進而導(dǎo)致結(jié)果偏向多數(shù)類的預(yù)測缺陷。

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

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

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

jsj3-gs1-2.gif

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

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

    jsj3-gs3.gif

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

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

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

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

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

jsj3-t1.gif

2.1 CHMDT算法流程

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

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

    輸出：一個多決策樹

    Make Multi-Decision Tree(S){

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

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

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

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

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

     找出最佳分裂點，將S分為SL和SR；

     Make Decision Tree(SL);

     Make Decision Tree(SR);

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

     匯總規(guī)則集；

    }

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

    CHMDT在根節(jié)點選擇確定之后分別采用代價敏感混合策略屬性單決策樹算法（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++)

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

        找出最佳分裂點，將S分為SL和SR；

        Make Decision Tree(SL);

        Make Decision Tree(SR);

    }

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

    算法的終止條件為以下任一個條件滿足：(1)S中的訓(xùn)練樣本都為同一類別，即決策樹達到葉子節(jié)點；(2)S中訓(xùn)練樣本數(shù)達到某一閾值；(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所示。

jsj3-b1.gif

3.2 實驗設(shè)置

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

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

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

3.3 評價指標(biāo)

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

jsj3-b2.gif

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

    真實正類率：

     jsj3-gs4-5.gif

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

    jsj3-gs6.gif

3.4 實驗結(jié)果

    場景一： CHDT算法與其他單決策樹算法在真實正類率預(yù)測性能比較如圖2所示。具體分析實驗結(jié)果可知，對數(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)確率。

jsj3-t2.gif

jsj3-t3.gif

    場景二：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é)果。總體準(zhǔn)確率比較如圖5所示，可以看出，CHMDT算法較其他算法準(zhǔn)確率都略有提高。

jsj3-t4.gif

jsj3-t5.gif

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個不同測點的傳感器數(shù)據(jù)發(fā)回。CHDT算法與C4.5、ID3及CART預(yù)測性能比較如圖6所示，可以看出，CHDT算法對正類的預(yù)測正確率提高的同時，負類率及準(zhǔn)確率性能依然保持。多決策樹算法預(yù)測性能比較如圖7所示，可以看出，與RF及CH-RF算法相比，本文提出的CHMDT算法對正類樣本的預(yù)測性能有明顯提高，有效避免了因隨機選擇屬性導(dǎo)致的屬性信息丟失和少數(shù)類欠訓(xùn)練問題，同時負類率及準(zhǔn)確率性能沒有受到影響。

jsj3-t6.gif

jsj3-t7.gif

5 結(jié)束語

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

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。