周爾昊，高 尚，申 震

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

0 引 言

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

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

1 相關(guān)技術(shù)

1.1 旋轉(zhuǎn)森林

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

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

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

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

1.2 SMOTE及相關(guān)改進算法

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

2 旋轉(zhuǎn)平衡森林算法

2.1 Hyper-Safe-Level-Smote

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

sl=t個最近鄰樣本中少數(shù)類樣本數(shù)

(1)

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

(2)

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

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

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

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

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

算法1：Hyper-Safe-Level-Smote

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

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

(1)初始化D′=?。

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

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

(4)For each high-safepinD:

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

1) if (sl_ratio=∞ ANDslp≠0){；q是噪聲， 這時將直接復(fù)制樣本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個最近鄰樣本并選取其中安全等級最高的少數(shù)類樣本作為q

for (atti= 1 tonumattrs){

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

gap=0 }

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

更新D′

(6)returnD′

2.2 旋轉(zhuǎn)平衡森林算法及流程圖

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

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

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

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

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

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

圖1 旋轉(zhuǎn)平衡森林第Ci個基分類器構(gòu)造流程

3 實 驗

3.1 控制因子相關(guān)預(yù)實驗

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

表1 修改后的iris數(shù)據(jù)集

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

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

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

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

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

3.3 評價標準

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

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

表2 修改后的數(shù)據(jù)集

表3 二分類混淆矩陣

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

(3)

(4)

(5)

(6)

3.4 實驗設(shè)計與結(jié)果分析

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

表4 各數(shù)據(jù)集控制因子最優(yōu)約束強度

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

表5 不同算法在數(shù)據(jù)集上的AccuracyRate對比

表6 不同算法在數(shù)據(jù)集上的TPR對比

表7 不同算法在數(shù)據(jù)集上的G-mean對比

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

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

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

圖3 5種算法的TPR比較

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

4 結(jié)束語

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