劉耀杰，劉獨玉

(西南民族大學(xué) 電氣信息工程學(xué)院，四川 成都 610041)

0 引 言

隨機森林算法(random forest，RF)是一種集成機器學(xué)習(xí)方法，利用隨機重采樣技術(shù)Bootstrap和節(jié)點隨機分裂技術(shù)構(gòu)建多棵決策樹，通過投票得到最終分類結(jié)果[1]。RF算法在含有缺失值和噪聲的數(shù)據(jù)集上表現(xiàn)出良好的魯棒性，并且可以利用并行計算方式加快學(xué)習(xí)速度，目前廣泛應(yīng)用于分類問題中。

分類是數(shù)據(jù)挖掘中最常見的任務(wù)，利用數(shù)據(jù)挖掘的方法充分發(fā)掘數(shù)據(jù)潛在信息應(yīng)用于分類預(yù)測中，建立預(yù)測模型，可以對待解決問題進行有效預(yù)測[2]。在現(xiàn)實場景中，大量的分類問題數(shù)據(jù)集分布并不均衡，而且每個分類的重要程度也不盡相同。然而大量的實踐經(jīng)歷和研究表明，隨機森林算法在樣本數(shù)量不均衡的情況下，由于算法追求全部樣本集分類精度最大化，導(dǎo)致對少類樣本分類和預(yù)測的準(zhǔn)確率遠(yuǎn)低于對多類樣本分類和預(yù)測的準(zhǔn)確率，即算法偏向于多類[3-4]。國內(nèi)外研究人員已經(jīng)做了大量的工作和嘗試，主要從兩個方面來解決不平衡分類問題，分別為數(shù)據(jù)預(yù)處理的方法[5-6]和算法級改進的方法[7-8]。但這些方法都存在一些不足之處，例如數(shù)據(jù)預(yù)處理方法可能造成數(shù)據(jù)的完整性缺失或者數(shù)據(jù)冗余，算法級改進可能造成模型的局部過擬合或加大計算資源開銷等。文中針對這一問題，對原有隨機森林算法的節(jié)點分類規(guī)則進行改進：在模型訓(xùn)練過程中，綜合考慮度量節(jié)點樣本分類占比與節(jié)點深度，增加有利于少量類樣本分類信息，從而提高少數(shù)樣本類的分類準(zhǔn)確率。

1 隨機森林算法

1.1 算法簡介

隨機森林算法由Leo Breiman(2001)[9]提出，通過自助法(Bootstrap)重采樣技術(shù)，從原始數(shù)據(jù)集N中有放回重復(fù)隨機抽取b個樣本生成新的訓(xùn)練樣本集合，通常抽樣個數(shù)b等于數(shù)據(jù)集樣本數(shù)，因為是有放回抽樣，所以有些樣本會被重復(fù)抽取，同時隨機漏掉一部分樣本，經(jīng)過采樣后的訓(xùn)練集樣本大小通常為原始樣本大小的三分之二；之后根據(jù)每個訓(xùn)練集分別建立決策樹，將訓(xùn)練好的多個決策樹分類器通過Bagging[10]方法集成，形成“森林”，通過投票的方法集成多個決策樹的分類結(jié)果，輸出最終結(jié)果。隨機森林算法中的決策樹在進行訓(xùn)練生長過程中，不進行優(yōu)化剪枝，生長條件僅限制于最大深度和葉節(jié)點相關(guān)屬性等生長控制條件，能有效防止決策樹過擬合；另外在訓(xùn)練決策樹過程中，對特征集也進行了隨機抽樣，通過無放回抽樣，每次使用特征集中的一部分進行決策樹構(gòu)建，通過特征集與樣本集的雙重隨機機制，構(gòu)成隨機森林算法的算法基本思想。

隨機森林算法步驟如下：

輸入:訓(xùn)練集S={(xi,yi),i=1,2,…,n},(X,Y)∈Rd×R，待測樣本xt∈Rd；

Fori=1,2,…,Ntree；

1.對原始訓(xùn)練集S進行Bootstrap抽樣，生成訓(xùn)練集Si；

2.使用Si生成一棵不剪枝的樹hi：

(1)從d個特征中隨機選取Mtry個特征；

(2)在每個節(jié)點上從各特征中依據(jù)Gini指標(biāo)選取最優(yōu)特征；

(3)節(jié)點分裂直到達到生長上限。

End

輸出：樹的集合{hi,i=1,2,…,Ntree}；對待測樣本xt，決策樹hi輸出hi(xt)。

1.2 算法優(yōu)勢

隨機森林算法具有如下一些優(yōu)點：

(1)隨機森林算法可以處理高維數(shù)據(jù)，并且不用做特征選擇。隨機森林算法可以對特征的重要程度進行自排序和篩選，也可以對樣本特征進行打分。

(2)模型泛化能力強，不容易過擬合。創(chuàng)建隨機森林的時候，對generalization error使用的是無偏估計，通過多重隨機，算法具有良好的泛化能力。

(3)訓(xùn)練速度快，可以并行計算。由于每個基分類器都是獨立的，所以在內(nèi)存允許的條件下可以進行并行計算，大大提高了算法效率。

(4)對樣本缺失值不敏感，甚至在缺失值較多的情況下也可以獲得較好的訓(xùn)練精度。

1.3 算法缺陷

在實際應(yīng)用中，隨機森林算法會有如下不足：

(1)對于有不同取值的屬性的數(shù)據(jù)，取值劃分較多的屬性會對隨機森林產(chǎn)生更大的影響，所以隨機森林在這種數(shù)據(jù)上產(chǎn)出的屬性權(quán)值是不可信的。

(2)隨機森林算法在某些噪聲較大的分類或回歸問題上存在過擬合。

(3)對于不平衡數(shù)據(jù)集，雖然算法有一定的平衡效果，但由于分類結(jié)果傾向于最大分類正確率，少量類樣本分類結(jié)果依然不理想。

2 不平衡分類問題研究現(xiàn)狀

現(xiàn)實中針對不平衡數(shù)據(jù)集分類問題，國內(nèi)外研究人員已經(jīng)做了大量的工作和嘗試，主要從數(shù)據(jù)層面[5-6]和算法層面[7-8]來解決不平衡分類問題。數(shù)據(jù)層面主要通過調(diào)整正負(fù)樣本比例來平衡數(shù)據(jù)集。算法層面主要通過改進傳統(tǒng)算法或設(shè)計新算法來適應(yīng)不平衡數(shù)據(jù)集。

2.1 數(shù)據(jù)層面改進

數(shù)據(jù)層面的改進通常較簡單，主要有三種方法：少量類樣本過采樣、大量類樣本欠采樣和混合采用。通過平衡數(shù)據(jù)集，有效改善傳統(tǒng)分類器對少量類樣本的辨識精度[3]。文獻[6]提出了一種基于模糊樣本修剪和非監(jiān)督型的數(shù)據(jù)集欠采樣解決方法，通過K-means模糊樣本修剪技術(shù)處理樣本集內(nèi)部噪聲數(shù)據(jù)和邊界點，再利用非監(jiān)督方法對大量類樣本集進行欠采樣，在縮小樣本間數(shù)量差異的同時盡量降低數(shù)據(jù)集的信息損失。然而過采樣會增大數(shù)據(jù)集規(guī)模，一方面使訓(xùn)練時間增長，另一方面容易使模型過擬合。欠采樣則會造成整體數(shù)據(jù)集信息缺失。

2.2 算法層面改進

對于算法層面的研究主要是改進傳統(tǒng)算法來更好地適應(yīng)不平衡分類數(shù)據(jù)集，或者研究出新的算法讓分類的規(guī)則更加適應(yīng)不平衡分類數(shù)據(jù)集。傳統(tǒng)算法一般追求整體分類精度最優(yōu)，如果訓(xùn)練集是不平衡分類數(shù)據(jù)集，則分類器會提升整體準(zhǔn)確率來進行建模，從而導(dǎo)致正樣本的分類精度較低，負(fù)樣本的分類精度較高。文獻[7]提出一種基于代價敏感機制的GBDT算法，針對樣本分類間的不平衡性及重要程度引入代價敏感指標(biāo)權(quán)重，在構(gòu)建GBDT算法模型過程中加大了少量類樣本在梯度提升過程中的權(quán)重，對于少量類樣本分類精度的提升取得了一定效果。文獻[8]在隨機森林算法模型構(gòu)建過程中對決策子樹引入了權(quán)重指標(biāo)，通過模型二次訓(xùn)練，在第一次訓(xùn)練給出決策子樹權(quán)重的基礎(chǔ)上提升二次訓(xùn)練模型的準(zhǔn)確率，通過給出集成學(xué)習(xí)模型中不同子分類器的權(quán)重提升模型效果，但這種方法弱化了隨機森林算法在充分隨機化下的抗干擾能力，一定程度上增加了過擬合風(fēng)險。

3 基于葉節(jié)點分裂規(guī)則改進的隨機森林優(yōu)化算法

3.1 算法思路

隨機森林算法在訓(xùn)練過程中，為獲得優(yōu)良的泛化能力，通常會限制樹的深度和參與訓(xùn)練的特征集大小，這意味著部分有用信息被隨機性丟棄了。每次節(jié)點分裂都是利用當(dāng)前可用特征所蘊含的信息，將節(jié)點劃分為兩個“純度”更高的節(jié)點，也就是說會分裂出一個大量類樣本占比相對父節(jié)點更高的子節(jié)點和另一個少量類樣本占比相對父節(jié)點更高的子節(jié)點，即“誘導(dǎo)”森林中已經(jīng)“生長”到條件限制深度的決策樹偏向少量類節(jié)點繼續(xù)“生長”。

隨機森林中每個決策樹的葉節(jié)點構(gòu)成了分類預(yù)測打分的基礎(chǔ)結(jié)構(gòu)[11]，在對測試樣本進行分類決策的過程中，每棵決策樹都參與投票，在決策樹進行分類過程中到達的葉節(jié)點中正負(fù)樣本的比例構(gòu)成了投票的基本打分[12]，然而由于數(shù)據(jù)集的不平衡性，葉節(jié)點中大量類樣本占比通常占優(yōu)勢，這種狀態(tài)下必然導(dǎo)致少量類樣本誤分率偏高。

原有算法針對不平衡數(shù)據(jù)集未做單獨處理，文中針對不平衡數(shù)據(jù)集做了相應(yīng)改進，提出了一種針對不平衡數(shù)據(jù)集的節(jié)點再分裂規(guī)則，對于少量類占比高于某一閾值的節(jié)點，進行再次分裂。由于隨機森林算法的“誘導(dǎo)生長”過程依然存在一定的隨機性[13]，并且在節(jié)點分裂過程中備選特征集依賴于隨機森林算法中的特征隨機化，所以改進算法在增加決策樹最大深度的同時盡量減小了模型過擬合風(fēng)險，通過這種方法可以進一步發(fā)掘蘊含少量類樣本分類的有效信息，增加最終分類決策中少量類樣本的投票權(quán)重。

3.2 算法描述

算法流程如圖1所示。

算法步驟如下：

(1)計算樣本集少量類樣本數(shù)占比；

(2)根據(jù)設(shè)定隨機森林決策樹數(shù)目進行樣本與屬性的雙重抽樣，同時記錄每個抽樣樣本集備選屬性集；

(3)構(gòu)造決策樹，依據(jù)設(shè)定決策樹深度及最小葉節(jié)點規(guī)模利用抽樣后的樣本集進行模型訓(xùn)練，在決策樹達到當(dāng)前生長條件準(zhǔn)備構(gòu)造葉節(jié)點時，判斷當(dāng)前節(jié)點P值是否大于設(shè)定閾值，若滿足條件，則加入備選屬性集循環(huán)分裂節(jié)點直到節(jié)點深度達到特征值數(shù)量上限或當(dāng)前節(jié)點P值小于設(shè)定閾值，構(gòu)造葉節(jié)點；

(4)利用不同抽樣樣本集以步驟3構(gòu)造多個決策樹模型；

(5)使用測試集樣本進行驗證，利用已經(jīng)構(gòu)建的多棵決策樹對每一個測試樣本綜合輸出分類結(jié)果，其中每一個決策樹模型單獨輸出一個分類概率，最終輸出分類結(jié)果為多決策樹模型輸出結(jié)果的加權(quán)平均值。

4 實 驗

4.1 實驗描述

實驗硬件平臺為Intel Core i7-4700MQ型號CPU和8 GB內(nèi)存的PC；代碼執(zhí)行平臺為QT5，算法實現(xiàn)語言采用C++；實驗數(shù)據(jù)來源為標(biāo)準(zhǔn)數(shù)據(jù)集UCI上的不同數(shù)量級、不同屬性個數(shù)、樣本分布均衡程度不同的五個二分類數(shù)據(jù)集，數(shù)據(jù)集的數(shù)據(jù)分布情況見表1。

圖1 算法流程 表1 樣本集數(shù)據(jù)分布

編號數(shù)據(jù)名稱樣本個數(shù)屬性個數(shù)正類樣本占比1data_banknote_authentication1 37150.4452credit_card_clients30 000230.2213spambase4 600570.3944ionosphere350340.3605census-income299 283410.062

為了說明算法改進效果，實驗在相同條件下分別驗證標(biāo)準(zhǔn)隨機森林算法與改進算法的分類結(jié)果。實驗過程采用五折交叉驗證，通過實驗結(jié)果比對分析算法改進效果及性能。分類結(jié)果評價指標(biāo)為誤分率、召回率(TPR)、真負(fù)率(TNR)。定義樣本數(shù)據(jù)經(jīng)過模型分類后的四種結(jié)果為：TP:預(yù)測為正，實際為正；FP:預(yù)測為正，實際為負(fù)；TN:預(yù)測為負(fù)，實際為負(fù)；FN:預(yù)測為

4.2 實驗結(jié)果及分析

實驗結(jié)果多指標(biāo)對比見表2。

表2 實驗結(jié)果多指標(biāo)對比

通過實驗結(jié)果對比發(fā)現(xiàn)：改進算法相對原標(biāo)準(zhǔn)算法TPR指標(biāo)均有不同程度的提高，一般情況下訓(xùn)練樣本越大，樣本集的信息越豐富，也越能夠反映真實情況下樣本的分布情況；實驗中樣本集規(guī)模較大、特征豐富的樣本集TPR指標(biāo)提升效果最為明顯，同時雖然TNR指標(biāo)和整體誤分率指標(biāo)有輕微下降，但下降幅度相對TPR指標(biāo)提升效果不明顯；參與測試的六個樣本集中有四個誤分率指標(biāo)變化控制在5‰以內(nèi)，TNR指標(biāo)變化控制在5‰左右，其中樣本數(shù)量最大的兩個樣本集(2號樣本集樣本量為30 000，5號樣本集為300 000)的誤分率指標(biāo)變化都為2‰，TNR變化值分別為3.2%和0.4%，而TPR提升值分別為10.2%和8.9%。

結(jié)果表明：在樣本類分布不均衡的5個實驗樣本中運用改進的隨機森林算法，少量類樣本分類準(zhǔn)確率都有所提高，同時樣本集整體誤分率、TNR指標(biāo)波動相比TPR指標(biāo)并沒有產(chǎn)生明顯的下降；改進的隨機森林算法在大樣本，高維度的不平衡數(shù)據(jù)集上效果明顯，在取得良好的TPR指標(biāo)提升效果的同時，數(shù)據(jù)集誤分率與TNR指標(biāo)下降波動低于TPR增加幅度一個數(shù)量級以上。

5 結(jié)束語

文中提出一種基于不平衡數(shù)據(jù)集的節(jié)點分裂規(guī)則改進隨機森林分類器，用于解決樣本不平衡對隨機森林分類效果的不良影響。該算法在構(gòu)建子樹的過程中針對節(jié)點分裂機制引入樣本類占比，針對訓(xùn)練樣本集原有樣本類占比值直接作為節(jié)點分裂參考指標(biāo)產(chǎn)生的不穩(wěn)定性，引入開平方函數(shù)，利用該函數(shù)一階導(dǎo)數(shù)遞減性，弱化樣本類占比值直接作為閾值指標(biāo)帶來的潛在不穩(wěn)定性，有針對性地引入一定比例的備選特征集應(yīng)用于對于增加少量類樣本分類權(quán)重有明顯價值的少數(shù)節(jié)點，在挖掘少量類樣本潛在信息的同時避免了決策子樹深度增加帶來的葉節(jié)點指數(shù)增長，從而降低了過擬合風(fēng)險。在樣本失衡比例不同的多個UCI數(shù)據(jù)集上的實驗結(jié)果表明，相對于原有隨機森林算法，該算法提高了少量類的分類準(zhǔn)確率，樣本量越大，特征空間維數(shù)越高，算法表現(xiàn)越好。但是算法在少量類低維樣本數(shù)據(jù)集上的表現(xiàn)不穩(wěn)定，效果相對較差，還有待進一步完善。