文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.170338
中文引用格式： 張翕茜，李鳳蓮，張雪英，等. 基于代價敏感混合分裂策略的多決策樹算法[J].電子技術應用，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 引言
瓦斯突出一直高居所有礦井事故之首。如果能在事故發生之前進行有效瓦斯突出預測，對降低礦井瓦斯事故發生、提高煤礦安全生產效率，具有非常重要的意義。分類算法可以通過抽取歷史數據的重要信息以預測未來數據的發展。在煤礦瓦斯預測中，決策樹算法因為模型簡單，便于實時計算，可以處理離散型和連續型數據，且結果易于理解等特點，常被用于瓦斯預測模型構建。
決策樹算法的研究主要分為兩類：(1)對單決策樹算法的改進，例如C4.5、CART、SPRINT和SLIQ[1]；(2)使用集成分類器，提高準確性，例如：Bagging、Boosting和隨機森林（Random forests，RF）。其中，隨機森林屬于廣泛應用的較好的集成分類器[2]，可以解決單決策樹過擬合的分類準確性低下問題。本文的研究是基于隨機森林的改進。
分類器對一種類別的過多訓練會導致另一類分類準確度降低，從而使分類器易過擬合導致少數類準確度降低。在煤礦瓦斯預警中的具體體現是：瓦斯突出或危險狀況下的數據稀少，為少數類，安全狀態下的數據占多數，為多數類，導致分類器對少數類預測準確率偏低，從而造成對可能發生瓦斯突出隱患的漏報現象。
面對不平衡數據分類問題，傳統決策樹算法缺陷是對少數類學習不充分，易造成分類結果偏向多數類現象[3]，使得表現為危險的異常情況，其預測準確率反而大大降低[4]。針對此問題，國內外研究方法主要有兩方面：(1)改變數據分布結構，利用過采樣和欠采樣的手段，使數據分布易于算法執行和處理[5-6]，但是此方法容易造成多數類信息缺失或少數類學習不充分；(2)對分類器進行改進，改進分類評價指標，使分類器能夠較準確地處理不平衡數據[7-8]。在針對分類器的改進中，目前最流行的方法是加入代價敏感因子[9]，其實現機理是對少數類分類錯誤給予一個較大權重的懲罰代價因子，同時對多數類分類錯誤給予一個較小權重的懲罰代價因子。例如，文獻[10]提出了一種代價敏感隨機森林算法，在隨機森林的基礎上加入代價敏感因子，以提高在不平衡數據問題上對少數類的預測。然而在隨機產生決策樹過程中，因為少數類數據的訓練樣本少和屬性選擇不全的原因，依然存在只有個別決策樹對少數類得到充分訓練，進而導致結果偏向多數類的預測缺陷。
本文針對不平衡數據集特點，提出了一種基于混合屬性的代價敏感多決策樹算法，算法首先將Gini指標和信息增益指標線性組合作為屬性選擇策略，進而用代價敏感因子對組合策略進行加權，最后使用輸入樣本的每個屬性作為多決策樹的根節點，改進代價敏感隨機森林算法只采用部分屬性作為根屬性選擇方式缺陷，達到保證多數類分類準確性的前提下，有效提高少數類分類準確性的目的。
1 混合分裂屬性指標的確定
決策樹構建的準確度主要取決于分裂屬性的選擇策略，本文采用組合策略是在結合C4.5和CART算法的基礎上，融合代價敏感因子形成的分裂屬性。其屬性選擇策略AS(Attribute Selection)如下：
式中，Ginisplit(A)(T)表示屬性A劃分后的Gini指數，是CART算法的分裂指標；GainRatio表示屬性A劃分后的信息增益率，是C4.5算法的分裂指標；C(Aj)表示集合T經過屬性Aj分裂后的誤分代價。
定義1：誤分代價：對于二分類問題，給定一個樣本集S，其含有s個樣本，Aj(j=1，2，…，n)個屬性。每個屬性Aj含有m個取值ai(i=1，2，…，m)。那么屬性Aj分裂后的所有子集總的誤分代價可以表示為：
式中，P(i)是分裂后樣本數量占分裂前的總概率，C(i)表示屬性值ai的樣本子集所構成的總代價[11]。
2 代價敏感混合屬性多決策樹算法
隨機森林的每棵決策樹的訓練樣本是隨機抽取的，在不平衡數據集中，少數類被抽取到的概率幾乎為零，因此在最后決策樹形成過程中，少數類不會得到充分訓練，結果會偏向多數類。
傳統的決策樹分類算法在構建決策樹過程中，通過對每個屬性的分裂點進行決策計算，分裂點的選擇容易受屬性個數和訓練樣本大小的影響。這種選取方法并未考慮根節點對決策樹構建的影響，及其對預測結果的影響；尤其在不平衡數據分類問題中，對少數類的錯誤影響會造成致命后果。如果根節點選擇錯誤，那么在后續分裂過程中想要糾正決策樹代價非常巨大。
本文提出了代價敏感混合屬性多決策樹算法 (Cost-sensitive Hybrid Measure Attributes Selection Multi-Decision Tree，CHMDT)，該算法原理框圖如圖1所示，其中采用每個屬性作為根節點分別建樹，即建樹過程使用了全部屬性。目的是訓練過程中保證所有少數類和屬性得到充分學習。
2.1 CHMDT算法流程
CHMDT采用廣度優先的算法設計，即先采用所有屬性作為各樹的根節點進行分裂，然后每個根節點依據混合策略分裂屬性為依據單獨建樹，具體實現流程如下：
輸入：訓練樣本集S
輸出：一個多決策樹
Make Multi-Decision Tree(S){
If(S滿足終止條件) Then return;
For(i=1;i<樣本中屬性個數;i++)
以第i個屬性作為根節點分裂；
For(j=1;j<樣本中剩余屬性個數;j++)
根據式(1)計算各屬性分裂點的混合分裂屬性指標；
找出最佳分裂點，將S分為SL和SR；
Make Decision Tree(SL);
Make Decision Tree(SR);
返回訓練規則集；
匯總規則集；
}
2.2 混合屬性單決策樹算法流程
CHMDT在根節點選擇確定之后分別采用代價敏感混合策略屬性單決策樹算法（Cost-sensitive Hybrid Measure Decision Tree，CHDT）建樹，采用式（1）的分裂指標。算法流程如下：
Make Decision Tree(S){
If(S滿足終止條件) Then return;
For(i=1;i<S中屬性個數;i++)
計算各屬性分裂點的混合分裂屬性指數；
找出最佳分裂點，將S分為SL和SR；
Make Decision Tree(SL);
Make Decision Tree(SR);
}
其中，SL代表S的左分枝，SR代表S的右分枝。決策樹最終是一棵二叉樹。
算法的終止條件為以下任一個條件滿足：(1)S中的訓練樣本都為同一類別，即決策樹達到葉子節點；(2)S中訓練樣本數達到某一閾值；(3)屬性全部分裂完畢，沒有待分裂屬性。
3 實驗及分析
本實驗目的主要是驗證代價敏感混合屬性分裂指標在少數類分類和整體準確率預測性能的優勢，以及提高所提出的CHMDT性能。
3.1 實驗數據
實驗數據集采用UCI和KEEL-Imbalanced Data Sets中的11個不同平衡率的非平衡數據集，詳情如表1所示。
3.2 實驗設置
訓練樣本與測試樣本比為2:1，保證類別比重不變。為避免偶然因素，每個測試集進行10次交叉驗證實驗，每次實驗訓練樣本和測試樣本都打亂順序隨機分配。實驗分為兩種場景進行驗證。
(1)場景一（驗證代價敏感混合屬性性能好壞）：CLDT與CART、C4.5、ID3對比。
(2)場景二（驗證CLMDT性能好壞）：CLMDT與RF、代價敏感混合屬性隨機森林（CH-RF）對比。
3.3 評價指標
本文采用真實正類率和準確率作為評價指標，其中實驗指標類別信息定義如表2。
(1)真實正類率TPrate/負類率TNrate：正確預測的正類/負類與實際為正類/負類的樣本數量的比值(取值范圍為0～1)。其值越大說明正類/負類預測越準確，性能越好。
真實正類率：
(2)準確率：正確預測的樣本數與總樣本數的比值（取值范圍為0～1）。其值越大說明總體預測越準確，性能越好。
3.4 實驗結果
場景一： CHDT算法與其他單決策樹算法在真實正類率預測性能比較如圖2所示。具體分析實驗結果可知，對數據ecoli、car-good、wine-red4、poker-8_vs_6，CHDT算法較ID3分別提升8%、11%、9%、8%。總體準確率比較如圖3所示，可以看出，CHDT一直保持穩定且較高的準確率。
場景二：CHMDT算法與RF、CH-RF算法在真實正類率預測性能比較如圖4所示。對數據集new-thyroid1、ecoli、page-blocks0來說，CHMDT算法相比其他兩種方法有一定的增長；對數據集yeast、abolone-3_vs_11來說，CHMDT算法相比其他兩種方法有較大提升；剩余數據集中，因為少數類樣本較少，RF和CH-RF出現“一邊倒”現象，少數類預測為0，但CHMDT算法均得到了一定的真實正類率預測結果。總體準確率比較如圖5所示，可以看出，CHMDT算法較其他算法準確率都略有提高。
3.5 結果分析
從場景一的實驗結果來看，采用CHDT算法在保證較高真實正類率預測結果的同時，準確率依然保持較高。從場景二的實驗結果來看，RF算法在少數類訓練樣本極少的情況下，預測結果會偏向多數類，CH-RF算法有適當提升。總的來說，CHMDT算法在少數類樣本稀缺的情況下有良好的少數類預測性能和較高的整體預測準確性。
4 煤礦瓦斯預警有效性驗證
本實驗選取同一工作面、不同時刻的煤礦瓦斯監測數據共461條，其中瓦斯突出數據26條，安全數據435條。屬性值分別來自井下16個不同測點的傳感器數據發回。CHDT算法與C4.5、ID3及CART預測性能比較如圖6所示，可以看出，CHDT算法對正類的預測正確率提高的同時，負類率及準確率性能依然保持。多決策樹算法預測性能比較如圖7所示，可以看出，與RF及CH-RF算法相比，本文提出的CHMDT算法對正類樣本的預測性能有明顯提高，有效避免了因隨機選擇屬性導致的屬性信息丟失和少數類欠訓練問題，同時負類率及準確率性能沒有受到影響。
5 結束語
本文基于C4.5和CART算法的分裂屬性用于非平衡數據集時少數類預測性能不佳的缺陷，提出了融合代價敏感指標的混合策略分裂屬性，并將其作為隨機森林算法屬性選擇措施，得到了基于代價敏感混合策略分裂屬性的多決策樹算法CHMDT。實驗結果表明，該方法有良好的少數類預測性能和較高的整體預測準確性。將該方法用于煤礦瓦斯預警數據中，實驗結果表明，本文所提出的方法可有效提高煤礦瓦斯預警數據整體預測性能。但采用所有屬性作為根節點信息，在屬性信息較多時，會存在算法復雜度偏高的問題，為此，下一步將繼續研究基于分布式存儲架構的多決策樹實現方式。
參考文獻
[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算法在煤層底板突水預測中的應用[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].武漢大學學報工學版，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.太原理工大學 信息工程學院，山西 晉中030600；
2.昆士蘭科技大學 電機工程及計算機科學學院，澳大利亞 布里斯班4001）