雙重代價敏感隨機森林算法

周炎龍 孫廣路

摘要：針對分類器在識別不平衡數(shù)據(jù)時少數(shù)類準確率不理想的問題，提出了一種雙重代價敏感隨機森林算法，雙重代價敏感隨機森林算法分別在隨機森林的特征選擇階段和集成投票階段引入代價敏感學習。在特征選擇階段提出了生成代價向量時間復雜度更低的方法，并將代價向量引入到了分裂屬性的計算中，使其在不破壞隨機森林隨機性的同時更有傾向性地選擇強特征;在集成階段引入誤分類代價，從而選出對少數(shù)類數(shù)據(jù)更敏感的決策樹集合。在UCI數(shù)據(jù)集上的實驗結(jié)果表明，提出的算法較對比方法具有更高的整體識別率，平均提高2.46%，對少數(shù)類識別率整體提升均在5%以上。

關鍵詞：隨機森林;不平衡數(shù)據(jù);特征選擇;代價敏感

DOI：10.15938/j.jhust.2021.05.006

中圖分類號：TP181 文獻標志碼：A 文章編號：1007-2683（2021）05-0044-07

0 引言

隨著大數(shù)據(jù)時代的來臨，數(shù)據(jù)呈現(xiàn)數(shù)量多、不平衡等特點，即一個類樣本數(shù)量遠多于另一個類的樣本數(shù)量[1]，如何將其正確的分類是一種重要的數(shù)據(jù)分析技術。類別不平衡的數(shù)據(jù)普遍存在于現(xiàn)實生活的許多應用中。例如，用于疾病診斷預測的病歷數(shù)據(jù)中，許多少見卻非常重要的疾病樣本數(shù)遠小于正常或常見的疾病樣本數(shù)[2];用于互聯(lián)網(wǎng)人侵檢測的樣本數(shù)據(jù)中，正常的樣本數(shù)遠多于人侵的樣本數(shù)。若將傳統(tǒng)分類器應用于這些場景而不對類別的不平衡性做任何處理，就會使得多數(shù)類淹沒少數(shù)類（少數(shù)類往往是更重要的），得不到好的分類效果。因此，類別分布的不平衡問題是數(shù)據(jù)分類中很重要的一類問題。

針對類別不平衡數(shù)據(jù)的分類問題，研究人員在數(shù)據(jù)預處理和分類器模型算法2個方面提出很多改進方法。其中，在數(shù)據(jù)預處理方法中又分為數(shù)據(jù)分布和特征選擇。特征選擇的目的是從全部特征中選擇更適合于類別不平衡數(shù)據(jù)、能反映類別不平衡特點的子集來構建分類器模型，從而使得分類器在類別不平衡的前提下達到較好的性能[3]。數(shù)據(jù)分布調(diào)整主要通過數(shù)據(jù)重采樣或數(shù)據(jù)分組等手段使得類別在一定程度上達到平衡，從而消除類別不平衡問題。

除了通過特征選擇、數(shù)據(jù)分布調(diào)整來降低類別不平衡對分類算法的影響，還可以直接在算法層面，通過設計適用于不平衡數(shù)據(jù)特征的模型訓練算法來解決類別不平衡問題。這方面的研究工作主要有代價敏感學習，集成學習以及其他算法，如關聯(lián)分類算法、K近鄰算法等。

1 相關工作

隨機森林是由Breiman[4]提出的一種集成學習算法，通過組合若干個單分類器的分類結(jié)果，從而對測試樣本的類別做出分類。該算法與單個分類器相比，具有更好的分類效果和泛化能力。研究人員在隨機森林不同階段提出了優(yōu)化和改進方法。

在特征選擇階段，Paul等[5]提出了一種改進的隨機森林分類器。根據(jù)重要特征和不重要特征的個數(shù)，迭代地去除一些非重要的特征，構造了一個新的理論上限，即加入到森林中的樹的個數(shù)。以保證分類精度的提高，并且算法收斂于一組減少但重要的特征。Zhou等[6]提出一種特征代價敏感隨機森林算法（Feature Cost-Sensitive Random Forest，F(xiàn)CS-RF），該算法將代價敏感學習引入隨機森林算法的特征選擇階段，針對每棵決策樹通過其OOB（Out ofBag，OOB）數(shù)據(jù)計算出不同特征下的分類準確率，再通過提出的算法計算出代價向量，在不破壞隨機性的同時使隨機森林在選擇特征時會更傾向于代價高的特征（即分類準確率更高的特征）。然而該方法在特征間沒有明顯強弱關系的時候就會退化為普通的隨機森林算法。并且該方法沒有考慮特征間的相對關系，并且生成特征向量的時間復雜度過高。

在集成投票階段，用OOB數(shù)據(jù)計算出識別準確率，再通過不同的算法計算出每棵決策樹的權重，從而在最終樣本分類時使分類結(jié)果更傾向于分類準確率高的決策樹的分類結(jié)果[7-8]。這些方法在數(shù)據(jù)高度不平衡時，雖然能有較高的整體識別準確率，但是對少數(shù)類的識別準確率卻并不理想。Xie等[9]將加權隨機森林和平衡隨機森林相結(jié)合，通過抽樣技術與成本敏感相結(jié)合引入隨機森林集成投票階段的方法可以在保證整體識別準確率的同時提升少數(shù)類的識別準確率，但是該方法在時間和空間上消耗過大。

隨機森林算法雖然具有較好的分類效果和泛化能力，但是在數(shù)據(jù)不平衡度較大時，分類效果卻并不理想，為此可以引入代價敏感學習來解決此問題。目前對代價敏感學習的研究主要集中在代價敏感間接學習和代價敏感直接學習2個方面[10]。代價敏感間接學習主要是通過對數(shù)據(jù)集特征空間的重構，間接地進行代價敏感學習，從而改變已有數(shù)據(jù)集的不平衡度，代表性的方法是代價敏感元學習[11]。代價敏感直接學習則是在傳統(tǒng)學習算法的基礎上引入代價敏感因子，通過改進分類器模型的內(nèi)部構造，使基于最小錯誤率的分類器轉(zhuǎn)化為基于最小代價的代價敏感分類器。目前，主流的分類算法如人工神經(jīng)網(wǎng)絡[12]、樸素貝葉斯[13]、SVM[14-16]、決策樹[17-18]，AdaBoost[19-20]等都有著相應的代價敏感擴展算法。雖然近些年深度學習成為大家關注的焦點，并在各個領域效果顯著。但其可解釋性的探索仍處于初級階段[21]，并且模型的訓練需要大量的數(shù)據(jù)，在樣本數(shù)量不足時會發(fā)生欠擬合的現(xiàn)象。

2 基于雙重代價敏感的隨機森林算法

2.1 代價敏感的引入

目前代價敏感學習算法主要針對二分類問題，當目標被錯分成其他類的代價有較大差異時，區(qū)分這些代價是必要的，即使被錯分類，也希望被錯分到代價小的類上。針對二分類問題，代價敏感一般用代價矩陣（見表1）表示分類器分錯時要付出的代價。c0為少數(shù)類，c1為多數(shù)類，C（i，j）表示將類別j錯分類為i所要付出的代價。

2.2 雙重代價敏感隨機森林（Double Cost SensitiveRandom Forest，DCS-RF）

雙重代價敏感隨機森林算法（DCS-RF）主要分為生成代價向量、構建決策樹和集成投票3個階段，如圖1所示。

隨機森林算法對數(shù)據(jù)集隨機并有放回地抽樣N次作為一棵決策樹的訓練集。其中未被選擇到的數(shù)

2.2.1 代價向量的生成

在生成代價向量階段，F(xiàn)CS-RF算法利用隨機森林OOB數(shù)據(jù)計算出的誤差變化來計算特征的重要度得分，從而計算出代價向量，但其所耗時間過長。因此本文提出的獲取代價向量的方法僅利用OOB數(shù)據(jù)的準確率作為標準，經(jīng)實驗證明耗時更少。具體步驟如下：

1）初始化代價向量q=[r1，r2，…，rn]，n為特征數(shù)量。設定閾值ω和權值向量λ=[λ1，λ2，…，λn]，其中向量λ中的數(shù)值為[n，n-1，n-2，…，1]，n為特征數(shù)量。因此權值向量λ=[n，n-1，n-2，…，1]。設置m為每次選取的特征數(shù)量，常設m=■。利用OOB數(shù)據(jù)對每棵決策樹進行測試。設A為準確率，當Aj≥w，j=1，2，…，ntree時（其中ntree為決策樹的數(shù)量），將第j棵樹中所選擇的所有特征按照從根結(jié)點到葉子結(jié)點的順序排序，將各結(jié)點中所選的用作分裂屬性的特征構成集合Fj。對于集合Fj中所有的特征，通過式（3）依次計算得到特征i的特征系數(shù)ri。

2.2.2 分裂范式的構建

在構建決策樹階段，將代價向量引入屬性分裂Gini指數(shù)的計算中，得到新的Gini指數(shù)CGini（CostGini index）。

特征系數(shù)越低的特征對應的CGini的不純度越高，其作為分裂準則的效果越好。

2.2.3 集成投票

在決策樹的集成階段引入誤分類代價，將平均誤差代價（average error costs，AEC）作為集成標準，獲得對于少數(shù)類更敏感的決策樹集合，構建完整的DCS-RF算法。AEC可表示為

針對每棵決策樹j，分別計算對應的平均誤差代價：其中x10表示偽正例;x01表示偽反例;N是樣本總數(shù)量。

2.2.4 算法步驟

整體算法步驟如算法1所示。

算法1 雙重代價敏感隨機森林算法

3 實驗結(jié)果與分析

3.1 實驗設置

本文選擇了UCI的8組數(shù)據(jù)集，并對其中的多分類數(shù)據(jù)集進行調(diào)整，轉(zhuǎn)化為二分類數(shù)據(jù)集，具體描述如表2所示。8組數(shù)據(jù)分成2組，一組通過生成的代價向量中各個特征間的數(shù)值關系對數(shù)據(jù)集的特征強度進行了高、中、低的標注，檢測算法在不同特征強度數(shù)據(jù)集上的識別效果。并對FCS-RF和DCS-RF算法生成代價向量的時間進行比對。

另一組根據(jù)數(shù)據(jù)集的特征強度進行劃分，分別從高、中、低特征強度的數(shù)據(jù)集中各取出一組數(shù)據(jù)進行不平衡處理，使其呈現(xiàn)出5種不同的不平衡度如表3所示，對本方法在不同平衡度上的分類效果進行實驗驗證。在實驗開始前，需要對代價矩陣進行賦值。假設少數(shù)類為c0，多數(shù)類為c1。那么C（c1，c0）和C（c0，c1）就分別代表把少數(shù)類錯分為多數(shù)類的代價和將多數(shù)類錯分為少數(shù)類的代價。本文更加關注的是針對不平衡數(shù)據(jù)的識別率，即對少數(shù)類的識別準確率，所以C（c1，c0）的代價應該高于C（c0，c1）的代價。這樣我們就將C（c0，c1）的代價設為1，假設C（c1，c0）的代價是2就說明將c0錯分為c1的代價是將c1錯分為c0的代價的兩倍。通過調(diào)節(jié)C（c1，c0）的值N，分別計算其等于1，2，4，8，16，32，64時的結(jié)果。通過實驗計算發(fā)現(xiàn)C（c1，c0）=32時效果最佳。

同時對于決策樹的數(shù)量理論上是數(shù)量越多識別效果越好，但是消耗的時間也會增加，綜合考慮設置決策樹的數(shù)量為100，因為在決策樹的數(shù)量為100時即可達到分類精度。

3.2 結(jié)果分析

2種算法生成的代價向量如表4所示，分別選取高、中、低特征強度的數(shù)據(jù)集Wine，Cancer，Jain，Diabetes進行對比實驗。可以看到在高、中特征強度的數(shù)據(jù)集中，本文的特征選擇方法可以更加快速高效的挖掘出高強度特征。雖然不能保證特征的強弱排序都與FCS-RF所產(chǎn)生的順序相同，但高、中、低強度特征集合中的特征元素卻相同。同時隨著數(shù)據(jù)維度的增加，DCS-RF在代價向量的生成速度上更占優(yōu)勢如表5所示，速度提升普遍在2倍以上，數(shù)據(jù)維度是訓練集數(shù)據(jù)量乘以特征維度。

在不平衡數(shù)據(jù)分類問題中，關注整體識別準確率的同時更應關注少數(shù)目標類的分類準確率。本文選擇如下指標評價分類算法：準確率（accuracy），召回率（recall）和F-measure。分別對支持向量機（SVM），K最鄰近（KNN），隨機森林（RF），特征代價隨機森林（FCS-RF）和本文提出的雙重代價隨機森林（DCS-RF）算法進行對比。

對KNN分類標準采取的是歐氏距離，K值設置為2。SYM中核函數(shù)采用RBF，迭代次數(shù)為50，松弛變量為20，懲罰因子0.6。表6顯示了5種不同的分類算法在8組不同特征強度的數(shù)據(jù)集上的整體識別準確率?？梢钥闯鲈诰哂懈咛卣鲝姸群椭刑卣鲝姸鹊臄?shù)據(jù)集上，DCS-RF和FCS-RF算法的識別率明顯高于其他的分類算法。在低特征強度的數(shù)據(jù)集上，F(xiàn)CS-RF算法對低特征強度數(shù)據(jù)不敏感，所以會退化成普通的隨機森林算法，其結(jié)果也與隨機森林沒有任何區(qū)別。由于DCS-RF算法在集成階段引入誤分類代價，所以在處理低特征強度的數(shù)據(jù)時，整體識別準確率仍能高于隨機森林和FCS-RF算法。同時在絕大多數(shù)的數(shù)據(jù)集上明顯高于其他4種分類算法，有著更高的識別準確率。另外我們可以注意到，雖然在Wine數(shù)據(jù)集上隨機森林，F(xiàn)CS-RF和DCS-RF達到了接近100%的識別準確率，但是經(jīng)過實驗證明，3種分類算法到達該準確率使用的決策樹數(shù)量完全不同，比值為10：7：5。由此可以看出相比于隨機森林和FCS-RF兩種算法，DCS-RF達到相同的識別效果所使用的決策樹數(shù)量更少。

通過表7、8中各類算法在數(shù)據(jù)集上的召回率和F-measure可以看出，DCS-RF算法因為在決策樹的集成階段引入了代價敏感學習的原因，所以其對少數(shù)類樣本的分類效果始終優(yōu)于其他的算法。

為了驗證算法在不平衡數(shù)據(jù)上的識別效果，圖2顯示了5種算法在Cancer，Jain和Diabetes數(shù)據(jù)集的不同平衡度上的召回率。數(shù)據(jù)的不平衡度分為5個級別，其中Cancer數(shù)據(jù)集中少數(shù)類占比分別是42.3%，32.3%，22.4%，12.4%，2.5%：Jain數(shù)據(jù)集中少數(shù)類占比分別是25.94%，20.72%，15.83%，10.39%，7.17%;Diabetes數(shù)據(jù)集少數(shù)類占比分別是34.90%，30.36%，25.15%，19.09%，11.98%。

通過圖2（a）、（b）可以看出隨著少數(shù)類所占比例的減少，RF及其變種算法對于少數(shù)類的識別率的波動幅度相對平緩。但是SVM和KNN算法的表現(xiàn)則并不理想。在圖2（c）上可以看到，由于特征強度低，F(xiàn)CS-RF算法已經(jīng)完全退化為RF算法，但基于隨機森林本身良好的魯棒性，其召回率的下降速度相對于SVM和KNN算法更平緩。同時也能看出DCS-RF算法由于在決策樹集成階段誤分類代價的引入，其召回率始終高于其他幾種算法，即對少數(shù)類有著更高的識別率。

4 結(jié)論

針對分類器在識別不平衡數(shù)據(jù)時少數(shù)類準確率不理想的問題，提出了一種基于雙重代價敏感的隨機森林算法，分別在隨機森林的特征選擇階段和集成投票階段引入代價敏感學習，使其對少數(shù)類數(shù)據(jù)敏感。在保證特征間強弱關系的前提下，提出了獲取代價向量耗時更少的方法;同時將代價向量引入到Gini指數(shù)中，在不破壞隨機性的前提下，更有傾向地選擇強特征;最后在集成階段引入了誤分類代價，使其在提高整體識別準確率的同時對不平衡數(shù)據(jù)中的少數(shù)類也有著較好的識別準確率。通過與SVM、KNN、隨機森林、FCS-RF的實驗對比，證明了本文提出的DCS-RF方法的有效性，在保證多數(shù)類準確的基礎上提高了少數(shù)類的識別準確率。但該算法的代價矩陣需要人為去規(guī)定，如何自主生成合理且有效的代價矩陣則是下一階段的研究目標。

參考文獻：

[1]AU H，SALLEH M N B M，SAEDUDIN R，et al.ImbalanceClass Problems in Data Mining：A Review[J].Indonesian Jour-nal of Electrical Engineering and Computer Science，2019，14（3）：1560.

[2]SUN Y，WONG A K C，KAMEL M S.Classification of Imbal-anced Data：A Review[J].International Journal of Pattern Rec-ognition&Artificial Intelligence，2009，23（4）;687.

[3]宋智超，康健，孫廣路，等.特征選擇方法中三種度量的比較研究[J].哈爾濱理工大學學報，2018，23（1）：111.

[4]BREIMAN L.Random Forests[J].Machine Learning，2001，45（1）：5.

[5]PAUL A，MUKHERJEE D P，DAS P，CHINTHA R.ImprovedRandom Forest for Classification[J].IEEE Transactions on ImageProcessing，2018，27（8）：4012.

[6]ZHOU Q，ZHOU H，LI T，et al.Cost-sensitive Feature SelectionUsing Random Forest：Selecting Low-cost Subsets of InformativeFeatures[J].Knowledge Based Systems，2016（95）：1，

[7]楊宏宇，徐晉.基于改進隨機森林算法的Android惡意軟件檢測[J].通信學報，2017，37（4）：8.

[8]蔡加欣，馮國燦，湯鑫，等.基于局部輪廓和隨機森林的人體行為識別[J].光學學報，2014，34（10）：204.

[9]XIE Y，LI X，NGAI E W，et al.Customer Churn Prediction U-sing Improved Balanced Random Forests[J].Expert Systems withApplications，2009，36（3）：5445.

[10]凌曉峰，SHENG，Victor，等.代價敏感分類器的比較研究[J].計算機學報，2007，30（8）：1203.

[11]DOMINGOS P.Meta cost：A General Method for Marking Classifi-ers Cost-sensitive[C]//Proc.5th ACM SIGKDD InternationalConf.Knowledge Discovery and Data Mining，1999：155.

[12]ZHANG Z，LUO X，GARCA S，et al.Cost-Sensitive Back-propa-gation Neural Networks with Binarization Techniques in AddressingMulti-class Problems and Non-competent Xlassifiers[J].AppliedSoft Computing，2017（56）：357.

[13]蔣盛益，謝照青，余雯.基于代價敏感的樸素貝葉斯不平衡數(shù)據(jù)分類研究[J].計算機研究與發(fā)展，2011，48（S1）：387.

[14]DHAR S，CHERKASSKY V.Development and Evaluation ofCost-Sensitive Universum-SVM[J].IEEE Transactions on Sys-tems，Man，and Cybernetics，2015，45（4）：806.

[15]周宇航，周志華.代價敏感大間隔分布學習機[J].計算機研究與發(fā)展，2016，53（9）：1964.

[16]HIANMEHR A，MASNADISHIRAZI H，VASCONCELOS N，etal.Cost-sensitive Support Vector Machines[J].Neurocomputing，2019：50.

[17]齊志鑫，王宏志，周雄，等.劣質(zhì)數(shù)據(jù)上代價敏感決策樹的建立[J].軟件學報，2019，30（3）：114.

[18]LI F，ZHANG X.Cost-Sensitive and Hybrid-Attribute MeasureMulti-Decision Tree over Imbalanced Data Sets[J].InformationSciences An International Journal，2018（22）：242.

[19]付忠良.多分類問題代價敏感AdaBoost算法[J].自動化學報，2011，37（8）：973.

[20]ZELENKOV Y.Example-dependent Cost-sensitive AdaptiveBoosting[J].Expert Systems with Application，2019，135（11）：71.

[21]成科揚，王寧，師文喜，等.深度學習可解釋性研究進展[J].計算機研究與發(fā)展，2020，57（6）：1208.

（編輯：溫澤宇）

收稿日期：2020-07-08

基金項目：國家自然科學基金（61702140）;黑龍江省留學歸國人員科學基金（LC2018030）;黑龍江省普通高校基本科研業(yè)務費專項資金資助（JMRH2018XM04）.

作者簡介：孫廣路（1979-），男，博士，教授，博士研究生導師.

通信作者：周炎龍（1996-），男，碩士研究生，E-mail：zy1279751705@163.com.