劉耀杰，劉獨玉

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

0 引 言

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

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

1 隨機森林算法

1.1 算法簡介

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

隨機森林算法步驟如下：

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

Fori=1,2,…,Ntree；

1.對原始訓練集S進行Bootstrap抽樣，生成訓練集Si；

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

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

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

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

End

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

1.2 算法優(yōu)勢

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

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

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

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

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

1.3 算法缺陷

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

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

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

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

2 不平衡分類問題研究現狀

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

2.1 數據層面改進

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

2.2 算法層面改進

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

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

3.1 算法思路

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

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

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

3.2 算法描述

算法流程如圖1所示。

算法步驟如下：

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

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

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

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

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

4 實 驗

4.1 實驗描述

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

圖1 算法流程 表1 樣本集數據分布

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

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

4.2 實驗結果及分析

實驗結果多指標對比見表2。

表2 實驗結果多指標對比

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

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

5 結束語

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