基于混合采樣的改進隨機森林算法研究

王 誠，趙曉培

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

隨著網絡數(shù)據(jù)存儲和數(shù)據(jù)收集能力的快速發(fā)展，獲取海量數(shù)據(jù)中有價值的信息已經成為人們研究的熱點之一，其中分類技術[1]作為數(shù)據(jù)挖掘[2]中的一大方向，是一種有監(jiān)督的機器學習方法。它是通過對訓練集進行訓練得到學習器模型，再用該模型對測試集進行測試得到分類結果。常用的分類器有最小距離法、貝葉斯、決策樹、支持向量機[3]、神經網絡[4]等，其中的決策樹是典型的單分類器，應用較為廣泛。但是單分類器存在明顯的缺陷，由此組合分類器應運而生，這種多分類器對多個單分類器進行組合、匯總，能夠提升分類性能，提高分類器的泛化能力。隨機森林算法[5]就是在這種背景下產生的一種多分類器，它是對決策樹算法的一種整合。

隨機森林(RF)[6]是一種組合分類器，大量的理論和實證研究都證明了隨機森林算法具有較高的預測準確率，對異常值和噪聲具有很好的容忍度，且不容易出現(xiàn)過擬合。但是，隨機森林算法對不平衡數(shù)據(jù)集的分類效果較差，尤其在疾病檢測[7]、故障診斷[8]及信用卡欺詐檢測[9]等應用領域，數(shù)據(jù)集數(shù)據(jù)分布明顯不均衡，其中少數(shù)類樣本數(shù)目過少，導致傳統(tǒng)分類器的準確率偏向于多數(shù)類，即便準確率很高也無法保證少數(shù)類樣本均分類正確。

面向不均衡數(shù)據(jù)分類的研究[10]也成為近年來研究的重點，提出解決不平衡數(shù)據(jù)[11]的分類策略[12]也層出不窮，總結起來可以歸為兩方面，一方面是從數(shù)據(jù)本身出發(fā)通過欠采樣或過采樣的方法，改變數(shù)據(jù)集中的多數(shù)類和少數(shù)類數(shù)據(jù)分布情況以此改變樣本數(shù)量的分布結構，達到數(shù)據(jù)的相對平衡，例如HA等[13]提出基于遺傳算法的欠采樣GAUS算法，通過損失最小化來優(yōu)化多數(shù)類子集以達到數(shù)據(jù)平衡以及Chawla等[14]提出SMOTE算法，通過過采樣在數(shù)據(jù)中人工合成[15]少數(shù)類樣本達到數(shù)據(jù)均衡；另一方面是從算法層面出發(fā)包括特征選擇和代價敏感等，通過對算法的改進來提高對不均衡數(shù)據(jù)分類的準確性，例如GUO等[16]提出的特征選擇與Adaboost相結合的集成學習算法，通過特征選擇提高分類器的分類性能。對于混合采樣，鄭建華等[17]提出對整個數(shù)據(jù)集引入過采樣因子后隨機過采樣，之后再隨機欠采樣對數(shù)據(jù)均衡。因此，文中從數(shù)據(jù)層面出發(fā)，提出了一種基于混合采樣的改進隨機森林算法HSRF(hybrid sampling random forest)，針對多數(shù)類和少數(shù)類進行分別采樣。首先通過隨機欠采樣和SMOTE算法相結合的方式對不平衡數(shù)據(jù)預處理實現(xiàn)數(shù)據(jù)均衡，同時引入聚類算法對SMOTE算法進行改進，提升其對少數(shù)類樣本的采樣性能；然后用均衡后的數(shù)據(jù)訓練決策樹，同時采用加權投票的方式進一步提高分類性能；最后構造出整個隨機森林分類模型。

1 隨機森林算法

隨機森林算法是由多棵相互獨立的決策樹分類器集成的大規(guī)模、高維度數(shù)據(jù)學習分類器。它利用bootstrap重抽樣方法從原始樣本中抽取多個樣本，對每個bootstrap樣本進行決策樹建模，然后將這些決策樹組合在一起，通過投票得出最終分類結果。隨機森林算法的構建過程如下：

(1)構建多個數(shù)據(jù)集，在包括k個樣本的數(shù)據(jù)集中，采用有放回的抽樣方式選擇k個樣本，構成中間數(shù)據(jù)集，然后在這個中間數(shù)據(jù)集的所有特征中隨機選擇幾個特征，作為最終的數(shù)據(jù)集；

(2)為每個數(shù)據(jù)集建立完全分裂的決策樹，利用CART為每個數(shù)據(jù)集建立一個完全分裂、沒有經過剪枝的決策樹，最終得到多棵CART決策樹；

(3)預測新數(shù)據(jù)，利用隨機森林進行預測試時，在解決分類問題方面主要是將k棵決策樹的結果采用投票的方式得到，如公式(1)所示。

C(x)=yi,當yi,yj?Y且|T(x)=yi|>|T(x)=yj|

(1)

其中，Y為數(shù)據(jù)類別集合，yi,yj是數(shù)據(jù)類別集合Y中的任意元素，|T(x)=yi|表示隨機森林中對樣本x的預測結果為yi的決策樹的個數(shù)。

2 算法改進

隨機森林算法在處理不均衡數(shù)據(jù)方面分類性能較差，不平衡數(shù)據(jù)是指類分布明顯不均衡的數(shù)據(jù)，對于不平衡數(shù)據(jù)的處理，傳統(tǒng)平衡化的方法主要是通過欠采樣和過采樣來進行數(shù)據(jù)均衡。欠采樣是通過減少部分多數(shù)類樣本數(shù)量來降低類間不平衡比例，使數(shù)據(jù)集趨于平衡。過采樣則是增加不平衡數(shù)據(jù)集中少數(shù)類樣本的數(shù)量，通過合成新的少數(shù)類樣本來均衡數(shù)據(jù)。但是，兩種采樣方法單獨使用會存在弊端：一方面，欠采樣會導致數(shù)據(jù)集中的有用信息丟失；另一方面，過采樣會增加冗余數(shù)據(jù)。因此，文中將兩種采樣方法綜合起來，利用各自的優(yōu)點提出了基于混合采樣的改進隨機森林算法HSRF。首先，對于不均衡數(shù)據(jù)集進行預處理，采用隨機欠采樣處理多數(shù)類，同時用改進的SMOTE算法對少數(shù)類進行過采樣，使數(shù)據(jù)集達到均衡；然后，用均衡的數(shù)據(jù)集訓練決策樹構建隨機森林；最后，給決策樹賦予不同的權重根據(jù)加權投票原則提高模型的分類性能。

2.1 改進的SMOTE算法

SMOTE(synthetic minority oversampling technique)算法是Chawla等提出的處理不平衡數(shù)據(jù)的算法，該算法通過在數(shù)據(jù)中增加人工合成的少數(shù)類樣本使類分布平衡，降低了過擬合的可能性，提高了分類器在測試集上的泛化性能。

SMOTE算法針對少數(shù)類數(shù)據(jù)中的每一個數(shù)據(jù)樣本X，搜索它的最近鄰樣本K個，再在這些最近鄰數(shù)據(jù)集中隨機選擇N個樣本。則對每一個原始樣本數(shù)據(jù)，選擇了K個近鄰樣本中的N個樣本,接下來便是在原始樣本數(shù)據(jù)以及它的近鄰樣本之間進行插值操作。公式如下:

Xnew=X+rand(0,1)*(Mi-X)

i=1,2,…,N

(2)

其中，Xnew為新插值的樣本；X為選擇的原始樣本數(shù)據(jù)；rand(0,1)表示0與1之間的某一隨機數(shù)；Mi為原始樣本數(shù)據(jù)X的最近鄰K個樣本中選取的N個樣本。

但是，SMOTE算法也存在明顯的缺陷，該算法在對少數(shù)類過采樣的過程中不能考慮到邊緣數(shù)據(jù)的分布狀態(tài)，容易造成邊界模糊的問題。因此，文中采用聚類算法對SMOTE算法進行改進，先使用聚類算法對少數(shù)類進行聚類操作，根據(jù)聚類的區(qū)域進行插值增加人造樣本數(shù)據(jù)，這樣能很好地解決邊界模糊問題。其主要步驟如下：

(1)先用聚類算法對少數(shù)類進行聚類操作，獲得少數(shù)類數(shù)據(jù)中各簇的分布狀態(tài)；

(2)計算各個簇的簇心，每一個聚類的簇心為{c1,c2,…,cn}；

(3)在簇內簇心與簇內樣本的連線上進行人工樣本生成。新插值的公式如下：

Xnew=ci+rand(0,1)*(X-ci)

i=1,2,…,N,X∈ci

(3)

其中，Xnew為新插值的樣本；ci為簇心；X是以ci為簇心聚類中的原始樣本；rand(0,1)表示0與1之間的某一隨機數(shù)。

2.2 加權投票原則

對于分類任務來說，隨機森林算法采用的是簡單投票原則，該原則是將同樣的權值賦值到每棵決策樹上，忽略了不同分類器之間的強弱差異，無法區(qū)分分類性能優(yōu)秀和分類性能欠佳的分類器，從而導致分類性能優(yōu)秀的決策樹的能力得不到發(fā)揮，而分類性能欠佳的決策樹對最終分類結果帶來一定負面的影響，最終導致分類結果存在偏差。因此，文中采用加權投票的方法增強優(yōu)秀決策樹在投票中所占的比重，同時削弱分類性能欠佳的決策樹的比重，以此增加隨機森林算法的分類性能。具體步驟如下：

(1)通過Bagging算法從均衡后的數(shù)據(jù)集N中進行隨機抽樣，形成樣本子集。同時會存在未被抽取的OOB數(shù)據(jù)，OOB中每個樣本沒有被抽到的概率約等于0.368，由公式(4)所示。設T為訓練完成的決策樹分類器集合；

(2)T測試OOB數(shù)據(jù)，得到每棵決策樹對OOB數(shù)據(jù)的正確分類的比率；

(3)對樣本子集使用隨機森林進行檢測分類并加權統(tǒng)計；

(4)選出得票最多作為最終結果。

2.3 混合采樣和隨機森林算法結合的HSRF算法

HSRF算法相比于原始隨機森林算法有兩點改進：第一，針對原始隨機森林算法處理不均衡數(shù)據(jù)準確率低的問題，采用了混合采樣對數(shù)據(jù)集進行預處理，用隨機欠采樣處理數(shù)據(jù)集中的多數(shù)類，同時用改進后的SMOTE算法處理數(shù)據(jù)中的少數(shù)類，使數(shù)據(jù)集達到均衡狀態(tài)；第二，改進隨機森林算法中的簡單投票原則，采用加權投票原則，給決策樹賦予不同的權值，更好地區(qū)分分類器的強弱差異。HSRF算法的流程如圖1所示。

圖1 HSRF算法流程

3 實 驗

3.1 實驗環(huán)境

實驗環(huán)境的硬件方面主要采用的配置為：Intel(R) Core(MT) i7-4600U CPU @ 2.10 GHz處理器 、8 G內存、64位Windows 10 企業(yè)版操作系統(tǒng)。軟件環(huán)境為Java環(huán)境，使用Weka開放源碼包。

3.2 實驗數(shù)據(jù)集

實驗用到的5個數(shù)據(jù)集均來自美國加州大學UCI公開數(shù)據(jù)集，分別是頁面塊分類數(shù)據(jù)集(page)、人工字符數(shù)據(jù)集(artificial)、鮑魚數(shù)據(jù)集(abalone)、皮馬印第安人數(shù)據(jù)集(pima)、衛(wèi)星數(shù)據(jù)集(satellite)。這5個數(shù)據(jù)集都是用于分類問題的不均衡數(shù)據(jù)集，少數(shù)類和多數(shù)類之間的不平衡比在0.26左右，表現(xiàn)了數(shù)據(jù)集中數(shù)據(jù)極度不平衡，有利于展現(xiàn)出HSRF算法對于不平衡數(shù)據(jù)的處理性能。具體參數(shù)如表1所示。

表1 數(shù)據(jù)集的具體參數(shù)

3.3 評價指標

對于傳統(tǒng)的分類算法，一般采用分類精度作為評價指標，然而對于不平衡數(shù)據(jù)集，用分類精度來評價分類器的性能是不準確的。因此對于不平衡數(shù)據(jù)一般采用G-mean、F-value和ROC曲線(AUC面積)作為評價指標，這些基本上都是建立在混淆矩陣的基礎上的。混淆矩陣如表2所示。

表2 混淆矩陣

這個矩陣是定義在驗證集上的，表示分類算法可能遇到的情況，其中正類樣本和負類樣本表示驗證集上的真實類標，預測正類和預測負類表示分類算法的預測類標。

(1)幾何均值G-mean表示正類分類精度和負類精度的集合平均值，公式如下：

(5)

(2)F-value是一種綜合考慮負類查全率和查準率的指標，綜合衡量隨機森林的分類性能，公式如下：

(6)

其中，precision和recall分別表示查準率和查全率，β的取值范圍為(0,1]，通常取1。precision和recall的公式分別如下所示：

(7)

(8)

(3)ROC曲線是不平衡數(shù)據(jù)分類問題中最經常采用的度量指標，在衡量隨機森林在不平衡數(shù)據(jù)上的整體分類性能，依然可以采用ROC曲線來描述，ROC曲線在坐標軸上越接近左上方則可認為隨機森林處理不平衡數(shù)據(jù)分類問題的效果越好。但是ROC曲線很難直接反映分類器的分類效果，因此，文中采用量化的AUC面積指標來衡量。AUC面積指標指的是ROC曲線之下的面積大小，AUC指標接近于1，則反映出分類器的分類效果越好。

3.4 實驗過程

實驗將每個數(shù)據(jù)集按照4∶1的比例隨機分為訓練集和測試集，用求取平均值的方式來進行結果判定。改進算法的具體實驗過程為：首先，針對具體算法對5個數(shù)據(jù)集的數(shù)據(jù)進行預處理操作，按照實驗要求設定各種參數(shù)；然后，在改進的SMOTE算法對于訓練集中的少數(shù)類處理的時候，將聚類算法的迭代次數(shù)的最大值設為50，隨機選取5個點作為簇心開始聚類，當?shù)_到最大值時，算法結束，記錄最終簇心點，接著對該簇心點進行插值操作；最后，根據(jù)各個分類器的性能給決策樹賦予不同的權值，通過加權投票得出分類結果。

此外，實驗通過對比三種不同的分類算法來驗證改進算法的分類性能。第一種是原始隨機森林算法；第二種是通過SMOTE算法后的隨機森林算法SRF；第三種就是文中提出的HSRF算法。

3.5 實驗結果分析

實驗對比了三種算法分別在5個數(shù)據(jù)集上各自的評價指標，實驗結果如表3所示。

表3 三種算法在5個數(shù)據(jù)集上的性能指標對比

將RF算法、SRF算法和HSRF算法在5個數(shù)據(jù)集上的各性能指標繪制成柱狀圖，如圖2～圖4所示。

根據(jù)圖2可以看出，相比于RF算法的G-mean值，SRF算法和HSRF算法在分類結果G-mean值的表現(xiàn)上更好。這五個數(shù)據(jù)集在不做數(shù)據(jù)預處理，直接通過RF算法進行分類的情況下，可以看出隨著數(shù)據(jù)集pima、satellite、abalone、artificial的不平衡比逐漸增加，算法的G-mean值越小，最低達到了40.8%，由此看出G-mean值可以很好地反映分類器在不均衡數(shù)據(jù)集上的分類性能。SRF算法相比于RF算法，通過對少數(shù)類的插值來均衡數(shù)據(jù)，一定程度上提升了算法的分類性能，而HSRF算法對不平衡數(shù)據(jù)的整體分類性能更高。

圖2 G-mean值比較

根據(jù)圖3可以看出，隨著算法的逐步改進，數(shù)據(jù)集反映的F-value值在不斷地提升，HSRF算法最高可以達到97.1%，有很好的分類效果，而原始隨機森林RF算法的F-value值基本都在90%以下，說明原始隨機森林RF算法在處理不均衡數(shù)據(jù)集上的性能較差。

圖3 F-value值比較

根據(jù)圖4的AUC面積指標可以看出，HSRF算法在采用混合采樣對數(shù)據(jù)集均衡化處理之后，AUC指標有較大的提升，數(shù)值都遠超過了其他兩種算法，最高達到98.7%。同時在柱狀圖的對比中可以看出，在數(shù)據(jù)非均衡比高的數(shù)據(jù)集中，改進的幅度不是很大，而在不平衡程度增加的情況下，AUC的數(shù)值有明顯的提升，說明改進后的算法在處理不平衡數(shù)據(jù)分類問題上有很好的魯棒性。

圖4 AUC值比較

從圖2、圖3和圖4可以看出，相比于RF算法和SRF算法，HSRF算法在處理不平衡數(shù)據(jù)上的分類性能更好。綜上所述，基于混合采樣的改進隨機森林算法HSRF與RF算法和SRF算法相比較，不論是在處理不均衡數(shù)據(jù)的性能上，還是在最終的分類效果上都有明顯的提升。

4 結束語

面對不平衡數(shù)據(jù)的分類問題，基于混合采樣對隨機森林算法進行了改進，提出了HSRF算法。一方面，該算法針對原始隨機森林算法處理不均衡數(shù)據(jù)準確率低的問題，采用了混合采樣對數(shù)據(jù)集進行預處理，用隨機欠采樣處理數(shù)據(jù)集中的多數(shù)類，同時用改進后的SMOTE算法處理數(shù)據(jù)中的少數(shù)類，使數(shù)據(jù)集達到均衡狀態(tài)；另一方面，算法改進了隨機森林算法中的簡單投票原則，采用加權投票原則，給決策樹賦予不同的權值，更好地區(qū)分分類器的強弱差異。結果表明，基于混合采樣的改進隨機森林算法在處理不均衡數(shù)據(jù)方面的分類能力比其他分類算法更好。然而HSRF算法也存在一些缺陷，該算法的分類效率較低，所以下一步的研究是在不降低分類性能的前提下提高分類效率。