基于旋轉平衡森林的不平衡數據分類算法

周爾昊，高 尚，申 震

(江蘇科技大學 計算機學院，江蘇 鎮江 212100)

0 引 言

不平衡數據分類問題一直是機器學習領域研究的一大熱點。所謂不平衡數據分類問題，是指分類任務中不同類別的訓練樣本數目差別很大，由此訓練得到的分類器過于關注多數類而忽略了少數類分類精度。在現實生活中,該類問題也隨處可見。如檢測未知和已知的網絡入侵、衛星雷達圖像中漏油情況檢測、醫療行業中的病情診斷等[1,2]。在以上問題中，少數類別的分類準確性往往顯得更為重要，但目前大多數的機器學習分類算法往往基于類別平衡假設，導致其應用于不平衡數據時性能并不理想[3]。針對不平衡數據分類問題,學者們提出了相應的解決方法?？偟膩碚f可以分為以下3個角度：①從數據層出發，主要的方法有過采樣、欠采樣、數據合成以及一些相應的改進方法；②從算法層出發,主要的方法有代價敏感學習[4]、集成學習[5]等；③從數據層和算法層結合出發，主要方法有SMOTEBoost(synthetic minority over-sampling technique boosting)、RUSBoost(random under-sampling boosting)、代價敏感集成(AdaCost)等，前兩種算法是采樣方法和集成學習相結合，AdaCost則是代價敏感和集成學習結合的典型方法。

本文從數據層和算法層結合角度出發，提出了基于旋轉平衡森林(rotation balanced forest，ROBF)的不平衡數據分類算法。本算法運用旋轉森林基分類器差異性大、集成精度高的優勢，通過引入數據層面的Hyper-Safe-Level-Smote方法來緩解各訓練子集的不平衡率，再經集成獲得的模型可以更好處理不平衡數據。本文研究旨在完善旋轉森林算法處理不平衡數據分類問題的相關研究。

1 相關技術

1.1 旋轉森林

旋轉森林算法[6](rotation forest，ROF)是一種基于特征選擇的分類器集成方法。先將特征集隨機劃分為K個子集，接著對每個特征子集進行主成分分析(PCA)并保留全部主成分，最后通過旋轉矩陣得到新的樣本數據用以訓練基分類器。通過以上操作使得用于訓練各基分類器的樣本數據有所差異并且起到一定數據預處理效果。無論是差異性誤差圖或是分類器的分類精度，ROF算法都有更為出色的表現。

現設定F為特征集，C1,CL,……CL表示L個基分類器。其中基分類器采用決策樹算法，因為它對特征軸的旋轉更為敏感。用N×n的矩陣X表示訓練集中有N條樣本數據，且特征數為n。算法描述如下：

(1)將F隨機劃分為大小相等的K個子集，則每個子集約有M=n/K個屬性。

(3)重復步驟(2)，將得到的K個子特征集的主成分系數存入系數矩陣Ri

1.2 SMOTE及相關改進算法

在傳統過采樣的基礎上，Chawla等提出的合成少數類過采樣技術(synthetic minority over-sampling technique，SMOTE)是目前常用的解決數據分布不平衡問題的數據層面的方法之一。該方法本質上是一種基于特征空間的過采樣技術。相比于傳統的過采樣方法，SMOTE方法可以有效緩解過擬合問題并且提高模型在測試集上的泛化能力。但該算法仍然存在一定的局限性，SMOTE本質上還是不斷得到一些人工生成的樣本，會出現分類器過學習現象，同時訓練時間也會延長。文獻[8]中總結了SMOTE方法存在以下一些問題：①合成樣本的質量問題；②模糊類邊界問題；③少數類分布問題。針對SMOTE存在的問題，學者們提出了一些改進算法，主要分為兩類：一類是SMOTE算法本身的改進；一類是SMOTE與其它方法相結合。SMOTE改進算法有Borderline-SMOTE、Safe-Level-SMOTE、ADASYN、G-SMOTE[9]等；相關結合方法主要有欠采樣與SMOTE結合[10]、過濾技術與SMOTE結合[11]、聚類算法與SMOTE結合[12]等。

2 旋轉平衡森林算法

2.1 Hyper-Safe-Level-Smote

本文提出的Hyper-Safe-Level-Smote是對Safe-Level-Smote的改進方法。Safe-Level-SMOTE方法為每一個少數類樣本分配一個安全系數,以少數類樣本為根樣本，以安全系數高的少數類樣本為輔助樣本，以此來進行樣本合成。安全等級(safe level,sl)和安全等級率(safe level ratio，sl_ratio)如下式所定義，其中最近鄰樣本采用歐氏距離定義，t是算法中的超參數，即在樣本空間中選取距目標樣本歐氏距離最近的t個樣本

sl=t個最近鄰樣本中少數類樣本數

(1)

sl_ratio=某個少數類安全等級/該少數類t個最近鄰樣本中某一少數類的安全等級

(2)

該方法從某一正類(少數類)樣本p的最近鄰t個樣本中隨機選取一個樣本q作為輔助樣本，通過分類討論p、q之間安全等級率的大小，選擇在合適的位置插值或者不插值。以此保證新合成的樣本均落在安全區域內。但該算法存在以下問題：①模糊類邊界問題。對處在類邊界的少數類樣本進行插值，若輔助樣本同樣處在類邊界上，隨著合成樣本的增多會使類邊界愈加模糊，雖然數據不平衡率得到改善，但是大大增加了分類算法的難度；②該方法對于新合成樣本的分布約束力較小。算法本意是希望合成樣本更靠近安全等級更高的原始樣本，但在某些情況下合成結果卻并不理想,新樣本的實際分布未達到預期效果。

針對Safe-Level-SMOTE方法存在的問題，本文做出了以下改進：①設定安全等級劃分標準J。根據所有少數類樣本的安全等級再進行一次劃分，得到高安全樣本和低安全樣本兩類。對于某一少數類樣本而言，若其屬于高安全樣本，則使用原始插值方法不變；若其屬于低安全樣本，則遍歷其t個最近鄰樣本并選取其中安全等級最高的少數類樣本作為輔助樣本進行插值。這樣操作雖然犧牲了一定的樣本多樣性，但能夠保證即使是對那些處于類邊界的少數類進行插值，依舊有較大概率使得新樣本落在安全區域。這一改進有效解決模糊類邊界問題，降低了算法的分類難度；②針對樣本分布與預期有偏差的問題，本文改進的思路是通過人為添加控制因子α、β來約束合成樣本的空間分布以達到預期。參照算法1，去除p、q均為噪聲的情況，再加入α、β后可以得到如下的插值規則

其中，sl_ratio=slp/slq(slp和slq定義見式(1))，根據sl_ratio的不同情況，gap在相應的區間取隨機值，最后通過步驟(4)中的第5)～第6)步完成特征插值。分析α和β的取值范圍，控制因子的引入是為了約束樣本的空間分布，在這里即是考慮讓合成樣本更靠近高安全等級的樣本。根據上述的插值規則，首先可以確定的是α和β應為(0,1)之間的隨機數，前者使得合成樣本更靠近p，后者使得合成樣本更靠近q。例如若p的安全等級為3，q的安全等級為2，這時sl_ratio>1，若不加入控制因子，gap的取值范圍應是[0,2/3]。當加入控制因子α∈(0,1) 后，gap的取值范圍縮小了，即樣本有更大概率更加靠近安全等級更高的p。為了進一步探究控制因子的取值對于樣本合成的影響，對(0,1)這一區間做進一步細分，以α為例，劃分規則如下所示

理論上，當控制因子取強約束范圍時，合成樣本最為靠近高安全等級樣本。但這同時會存在一個問題，即新合成樣本與原始少數類樣本的相似度增加，樣本多樣性減少，盲目合成這些原始樣本的“復制”樣本并不會對模型性能有所提升，同時還會產生過擬合現象。所以，針對不同的具體數據集，在充分考慮其樣本分布的前提下，為控制因子選擇合適的約束標準就顯得有意義了。根據上述劃分標準，α和β各有3組取值范圍，總計9組情況。在本文3.1節中，設計了在修改后的鳶尾花數據集上找到最優控制因子約束強度的預實驗。并且后續正式實驗中也均通過預實驗找到了合適的控制因子約束強度。

Hyper-Safe-Level-Smote方法的步驟如算法1所示。

算法1：Hyper-Safe-Level-Smote

輸入：一個包含了全部原始正類樣本的數據集D

輸出：一個包含了全部合成樣本的數據集D′

(1)初始化D′=?。

(2)對數據集D中的每一個正類樣本p， 從其最近鄰的t個樣本中隨機選取一個正類樣本q作為輔助樣本， 用2.1節中式(1)、 式(2)分別計算p、q的安全等級slp、slq， 以及它們的安全等級率sl_ratio。 若slq=0， 則設置sl_ratio=∞。

(3)判斷p的安全等級， 如果slp≥J， 則將其歸為高安全樣本(high-safe)； 反之歸為低安全樣本(low-safe)。

(4)For each high-safepinD:

for (atti=1 tonumattrs){；numattrs是屬性(atti)數。

1) if (sl_ratio=∞ ANDslp≠0){；q是噪聲， 這時將直接復制樣本p來達到遠離樣本點q的目的。

gap=0}

2) else if(sl_ratio=1){；p、q的安全等級相同， 選擇在p、q間隨意插值

gap∈,1] }

3) else if(sl_ratio>1){；p的安全等級高于q， 選擇在更靠近p的位置進行樣本合成，α用于約束合成樣本空間分布

gap∈[0,α(1/sl_ratio)] }

4) else if(sl_ratio<1){；q的安全等級高于p， 選擇在更靠近q的位置進行樣本合成，β用于約束合成樣本空間分布

gap∈[1-β(sl_ratio),1] }

5)dif=q[atti]-p[atti]

6)s[atti]=p[atti]+gap·dif}

D′=D′∪{s}

(5)For each low-safepinD:

遍歷p的t個最近鄰樣本并選取其中安全等級最高的少數類樣本作為q

for (atti= 1 tonumattrs){

if (sl_ratio=∞ ANDslp=0){；p、q均是噪聲，這時將不在p、q間進行任何插值操作

gap=0 }

重復步驟(4)中的1)～6)}

更新D′

(6)returnD′

2.2 旋轉平衡森林算法及流程圖

利用旋轉森林差異性大、分類精度高的優勢,在旋轉后得到的新數據集上引入Hyper-Safe-Level-SMOTE，緩解了各基分類器訓練集的不平衡率,經整合后獲得可以有效處理不平衡數據的新的集成模型。將結合后的算法叫作旋轉平衡森林,意為在旋轉過程中即平衡多數類與少數類的類別分布?，F設定F為特征集，C1,CL,……CL表示L個基分類器,用N×n的矩陣X表示樣本集有N條n維的數據。第Ci個(1≤i≤L)基分類器的構造流程圖如圖1所示。算法步驟如下：

(1)對特征集F進行無放回的隨機采樣K次(K是算法的超參數)，得到K個大小相等的特征子集,每個子集約有M=n/K個屬性。

(2)對于每一個特征子集，從數據集中進行75%的有放回取樣，得到對應該特征子集的子樣本集，利用PCA對特征子集進行特征變換，得到K個變換后的特征子集,每個子集包含M個特征數。PCA是一種常見的數學變換方法，常用于數據降維，可用于提取數據的主要特征分量。ROBF中的PCA不是用于降維，原因是為了不丟失原有數據信息，ROBF保留了全部主成分，故PCA在這里僅起到特征變換作用。且新特征子集是原始特征子集在新空間的映射，本質還是原來的數據，只不過表現形式不一樣。

(3)將步驟(2)得到的K個特征子集的主成分系數存入系數矩陣Ri，根據原始特征集排列順序重新旋轉矩陣Ri得R′i。

(4)通過XR′i獲得新訓練集Xi， 在新訓練集上使用Hyper-Safe-Level-Smote方法進行少數類樣本插值，緩解新訓練集的不平衡率。在插值后的新訓練集上訓練基分類器Ci。

(5)重復以上步驟L次得到L個基分類器，整合各分類器預測結果并輸出。

圖1 旋轉平衡森林第Ci個基分類器構造流程

3 實 驗

3.1 控制因子相關預實驗

經典數據集鳶尾花數據集(iris)總共包含150個樣本,每類各50個數據,每條數據有4項特征。這里對其修改,使其呈現二分類上的不平衡。修改后數據集見表1。

表1 修改后的iris數據集

實驗前，選取其中70%作為訓練數據，其它為測試數據。訓練數據中少數類個數為21，測試數據中少數類個數為9。以測試集上少數類的分類正確個數衡量不同強度控制因子對模型性能的影響。分類器選用旋轉森林算法，插值方法即為Hyper-Safe-Level-SMOTE。實驗結果如圖2所示，其中橫坐標的編號1-9代表α和β分別取強約束+強約束、強約束+弱約束、強約束+適當約束、弱約束+強約束、弱約束+弱約束、弱約束+適當約束、適當約束+強約束、適當約束+弱約束、適當約束+適當約束。縱坐標代表不同編號下測試集上少數類的分類正確個數。

圖2 控制因子約束強度對少數類分類的影響

從實驗結果可以看出，修改后的iris數據集在α和β均取適當約束時分類器獲得最好效果。

3.2 數據集

為了驗證ROBF算法在不平衡數據分類問題上的有效性，本文從UCI上選擇了6組數據集。通過調整使這些數據集呈現二分類上的不平衡。實驗數據集不平衡度從1.87到28.4。經調整后的數據集情況見表2。

3.3 評價標準

對于二分類問題,通常用混淆矩陣來衡量分類算法的有效性，見表3。在這里正類即為少數類，負類即為多數類。

對于不平衡數據分類算法性能的衡量往往不能僅依據準確率，故除準確率外本文還選取了真正例率(TPR)和G-mean來衡量算法性能。TPR值反映的是少數類中有多少樣本被真正預測為少數類；G-mean是特異度(Specificity)

表2 修改后的數據集

表3 二分類混淆矩陣

和TPR的幾何平均值，由于同時考慮了正類和負類樣本分類的性能，所以它對于不平衡的二分類數據集來說是一種較好的度量。式(3)～式(6)分別是準確率、TPR、Specificity和G-mean的計算公式

(3)

(4)

(5)

(6)

3.4 實驗設計與結果分析

實驗過程中，通過分割將數據集的80%用作訓練，20%用作測試。采用5折交叉驗證來避免過擬合。為了驗證ROBF算法在處理不平衡數據時的有效性,本文選取了AdaCost、RUSBoost、Borderline-SMOTE+ROF、ADASYN+ROF這4種算法在6組數據集上與ROBF進行對比實驗。前兩者是Adaboost針對不平衡問題的改進算法,后兩者是為了驗證在旋轉森林模型下，Hyper-Safe-Level-SMOTE方法相較于其它SMOTE的優勢性。RUSBoost采用C4.5作為基分類器，其它算法均使用CART作為基分類器。另3個ROBF中涉及的參數是Hyper-Safe-Level-SMOTE方法中最近鄰樣本數t、劃分安全等級標準J和控制因子α、β的強度，在實驗中分別設置為t=5和J=3。各數據集上α、β的約束強度見表4，表4結果均是在各數據集上做類3.1節預實驗后得出的最優控制因子約束強度。在此基礎上，ROBF與其它4種算法的實驗結果見表5～表7。

表4 各數據集控制因子最優約束強度

從實驗結果分析，ROBF算法相較于其它4種算法在準確率上并未有明顯提升，在vowel和crowdsourced上其準確率略低于RUSBoost算法，這說明ROBF在提升少數類分類精度的同時會降低多數類的分類精度。

表5 不同算法在數據集上的AccuracyRate對比

表6 不同算法在數據集上的TPR對比

表7 不同算法在數據集上的G-mean對比

ROBF的TPR值與其它算法相比有較大提升，這是因為經Hyper-Safe-Level-SMOTE合成的數據有著更大的概率落入安全區域，這意味著合成后的新數據中有更多的少數類樣本被正確預測為少數類。Borderline+ROF由于其在區分噪聲和類邊界樣本上的不準確性，導致TPR值低于ROBF算法。RUSBoost的TPR值在clients上明顯低于其它算法，這很可能是因為在隨機欠采樣過程中刪掉許多有潛在價值的多數類樣本。

G-mean同時衡量了多數類和少數類的分類性能，從表5可以看出ROBF在其中4個數據集上是占優的，這是因為除了注重少數類的分類精度，Hyper-Safe-Level-SMOTE較好解決了模糊類邊界問題，進一步提升了分類器的分類性能。相比之下，Borderline+ROF與ADASYN+ROF雖然和Hyper-Safe-Level-SMOTE應用于同一個集成模型之上，但前兩者的插值效果相比于Hyper-Safe-Level-SMOTE還是略有不足的。在高度不平衡的clients數據集上，Adacost取得了最高的G-mean值，ROBF略低，這是因為在數據量較大且不平衡度較高的數據集中，少數類只占據了小部分，多數類的分類性能影響著G-mean值的高低。綜上，ROBF算法不僅在少數類分類問題上有著更出色的性能，而且在多數類分類上也有著良好表現。

為了更加直觀體現ROBF算法的優勢，圖3和圖4展示了在6組數據集上5種算法的TPR和G-mean的實驗結果折線圖。從圖可以看出，ROBF在處理不平衡數據分類問題上是有效的。

圖3 5種算法的TPR比較

圖4 5種算法的G-mean比較

4 結束語

針對不平衡分類中的二分類問題,本文從數據層和算法層結合的角度出發,提出了一種基于旋轉森林的改進模型—旋轉平衡森林。該模型選用基分類器差異性大，集成精度高的旋轉森林算法作為基模型，通過引入改進的Hyper-Safe-Level-SMOTE方法，在緩解訓練集不平衡率的同時，成功解決了模糊類邊界問題，使得改進后的模型在處理不平衡數據時對少數類擁有更好的分類性能。在未來研究中，將繼續針對模型做進一步的探索，如：①在旋轉森林模型中，是否可以通過改變75%的重采樣中正、負類比例來使訓練模型更注重少數類分類；②Hyper-Safe-Level-SMOTE中控制因子的范圍取值是人工設定的,約束強度的選擇也僅是相對最優,是否可以設置自適應的控制因子來尋求最優的約束強度。