一種非平衡數據分類的過采樣隨機森林算法

趙錦陽 盧會國,2 蔣娟萍,2 袁培培 柳學麗

1(成都信息工程大學電子工程學院 四川 成都 610225) 2(中國氣象局大氣探測重點開放實驗室 四川 成都 610225) 3(電子科技大學航空航天學院 四川 成都 611731) 4(南京財經大學信息工程學院 江蘇 南京 210000)

0 引 言

隨機森林RF[1]比單個決策樹分類器有較高的分類精度和較低的預測誤差，其適合多種環境，不需要剪枝，對噪聲數據不敏感等眾多優點，已在眾多領域得到了廣泛的應用；但和其分類器一樣，數據集的非平衡程度會很大地干擾分類器的分類。在現實生活中，非平衡數據的少數類樣本往往受到廣泛關注，例如在金融欺詐領域，不安全的數據信息所占的比例很小，然而這些很少的數據會造成重大的后果[2]。因此對非平衡數據的準確分類已成為重要話題，如何提高隨機森林對非平衡數據集的分類精度已受到業界人士的廣泛關注。

黃衍等[3]通過比較隨機森林和支持向量機在非平衡數據集分類問題上的性能，得出支持向量機在處理非平衡數據集要優于隨機森林。根據隨機森林的構造過程可知其對非平衡數據集分類差的原因在于隨機森林使用Bagging隨機選取訓練集，因為原訓練集為非平衡數據集，故少數類有較低的選中概率，進行多次循環之后，被選中的少數類勢必與原始數據集的少數類在數量上有較大差別，這樣使得訓練出的森林過于依賴多數類樣本，失去了代表性。對于面向非平衡數據集的隨機森林，如何提高少數類樣本被選中的概率，是優化森林算法的關鍵所在。

目前主要對數據層進行處理和改進分類器自身構建過程來提高分類器的預測精度。改進分類器自身算法主要涉及隨機森林中單個決策樹的生成，合理選擇屬性，使得森林中各決策樹之間的關聯度降到最低，同時使得各決策樹充分生長。而數據層方面主要將原始數據進行預處理，篩選出需要的數據信息，并將處理后的數據與分類器算法相結合進行分類。

對于數據預處理方法，吳瓊等[4]提出將NCL技術引入隨機森林算法，對非平衡數據進行NCL處理，然后用隨機森林算法對處理后的數據進行分類，結果表明改進后的隨機森林算法分類效果更好。由上述面向非平衡數據集的隨機森林分類差的原因，以及現有研究可知，對非平衡數據集進行預處理，可有效地提高隨機森林的預測精度。目前比較常用的數據層處理方法是對數據進行重采樣(欠采樣和過采樣)。欠采樣方法是適當的選取一部分多數類樣本(負類)，使得新數據集的多數類和少數類樣本的個數處于均衡狀態，由此可知選取的多數類樣本可能會丟失有效信息，從而造成合成的數據集與原數據集相差很大，不具有代表性；過采樣方法采用增加少數類樣本(正類)的思想，使得原數據集中重要信息保留下來，合成的數據能夠較好地表現出原數據的特征，因此在處理不平衡數據時，過采樣技術成為了主流方法。

過采樣技術中最為經典的是Chawla提出的SMOTE算法，其主要思想是找出數據集中少數類樣本集，在少數類樣本與其K近鄰之間的連線上產生合成樣本[5]。由其理論可知，SMOTE算法雖然增加了少數類樣本個數，但只是不加分析的復制樣本，并且在合成過程中也會出現重復問題，從而使得隨機森林對合成后的數據集分類性能沒有本質上的提高。

本文提出一種改進的算法——SCSMOTE算法，根據少數類樣本與多數類樣本的邊界區分程度，得到合適的候選樣本，并且計算出候選樣本的中心，在候選樣本與其中心連線上產生合成樣本，從而達到數據集的平衡。

1 算法設計

本節結合SMOTE算法的思想，提出一種基于候選樣本集中心的過采樣技術方法。

1.1 SMOTE算法

SMOTE是過采樣方法中的經典算法[6]，其主要思想基于k近鄰算法，每個少數類樣本確定k個近鄰的少數類，然后在少數類樣本與其近鄰樣本的連線上合成新的少數類樣本，通常近鄰參數k取5。

算法實現如下。

1) 對于每個正類樣本P_i，在正類樣本集中選取K個近鄰樣本，記為Q_k。

2) 按式(1)合成syn_i，其中g為確定合成樣本位置的隨機數，其值在(0,1)之間：

syn_i=P_i+g×(Q_k-P_i)

(1)

3) 將合成的syn_i樣本添加到原始正類集中得syn_dat樣本。

由上可知，如果一數據集正類樣本邊緣化嚴重，那么由于不加分析地在正類樣本之間復制產生新樣本，勢必會使原本就邊緣化的數據更加邊緣化，從而使得邊界更加難以區分。這種情況雖然在數量上改善了數據集的平衡性，但造成了隨機森林算法進行分類時的難度。

本文認為邊界樣本在分類中比遠離邊界的樣本更容易被錯分。但由上述可知，在產生新樣本時又不能刻意避開邊界樣本，因為一個類的邊界樣本或多或少會攜帶原始數據集的信息。因此本文根據少數類樣本與多數類樣本的邊界區分程度進行分析，對于存在有危險區域(正類邊界樣本的k近鄰樣本中負類樣本數量多于正類樣本數量)的數據集[7]而言，當危險區域中的數據樣本在全體正類樣本個數占比較高時，在合成新樣本時要盡量克服SMOTE算法不加分析復制邊界樣本的缺點，對危險區域樣本進行合理控制，從而減少分類器對邊界樣本的錯分率。對于有清晰邊界的數據集而言，即危險區域的正類樣本個數在全體正類樣本個數占比較少，此時危險區域不具有代表性，要盡可能克服SMOTE算法過采樣過程中模糊邊緣的問題。

本文認為危險區域的正類樣本數大于總正類樣本數量的四分之一時，邊界樣本攜帶原始數據集的多數信息，分類器容易把邊界樣本中的正類樣本判為負類樣本。故在合成新樣本時要對危險區域樣本加大學習力度，并進行合理控制。此時計算出危險區域的樣本中心，并把危險區域中的樣本作為候選樣本；對于危險區域的正類樣本個數小于總正類樣本數量的四分之一時，認為邊界樣本占據原始數據集的信息比重較小，此時計算全體正類樣本的中心，把全體正類作為候選樣本。用得到的候選樣本和樣本中心，得出一種新的學習算法：找出數據集的危險區域，若此區域中的正類樣本能較好地代表整體正類樣本，則把此區域作為候選樣本(反之以全體正類樣本為候選樣本)，計算候選樣本中心。在候選樣本和候選樣本中心的連線上產生新的正類樣本，把產生的新樣本合并到原始數據集中，從而使得數據平衡化。

1.2 非平衡數據集學習算法SCSMOTE

計算需要合成的正類樣本數量并得到合適的候選樣本，最后計算合成樣本位置實現對非平衡數據集的平衡化處理。

1.2.1 正類樣本數據的合成

設原始數據集T，其中負類樣本集合N={N1,N2,…,Nnnum},Ni=(ni1,ni2,…,nir)，其中nnum表示負類樣本數量，r代表樣本特征個數；正類樣本集合P={P1,P2,…,Ppnum}，Pi=(pi1,pi2,…,pir)，其中r代表樣本特征個數，pnum表示正類數量。

定義1危險區域

定義2危險區域樣本中心

危險區域樣本中心是指上述危險區域集S數據空間的中心，Scenter是與樣本維數相同的向量，計算公式表示為：

(2)

定義3正類樣本中心

正類樣本中心即正類樣本的中心點，記為Pcenter，根據上述定義及向量的概念，可得：

(3)

根據上述定義，本文首先選擇候選樣本集，對于危險區域樣本占比總正類樣本數較大的原始數據集而言，處于邊界的樣本經常會被錯分。因此選取危險區域的正類樣本為候選樣本集，此區域的樣本中心為候選樣本中心。對于危險區域樣本占比較小的原始數據集而言，為了避免在合成人造數據時使邊界區分度降低，選取總體正類樣本為候選樣本，正類中心為候選樣本中心。根據SMOTE算法思想，此算法根據危險區域正類樣本占比總正類樣本數的大小，分別用式(4)、式(5)在候選樣本與候選樣本中心之間合成新樣本。

Psynj=Si+rand(0,1)×(Scenter-Si)

(4)

式中：Si(i=1,2,…,dnum)為危險區域的正類樣本，dnum為此區域的正類樣本的總個數；

Scenter為此區域正類樣本的中心點；

Psynj為合成的樣本；

rand(0,1)用于確定合成樣本在連線上的具體位置；

Psynj=Pi+rand(0,1)×(Pcenter-Pi)

(5)

式中：Pi(i=1,2,…,pnum)為正類樣本，pnum為正類樣本總個數；Pcenter為正類樣本的中心點。

圖1給出了SCSMOTE算法合成新樣本的原理圖，其中空心圓代表正類樣本，正方形代表負類樣本，三角形代表候選樣本中心，實心黑點代表合成正類樣本。其合成新樣本的位置已在圖中標示。P1樣本的5個近鄰分別是P2、N1、N2、N3、N4，可知其5個近鄰中正類有1個，負類有4個，即把P1劃分到危險區域；而對于P2而言，其5個近鄰分別是P1、P3、P4、N1、N2，可知其近鄰中正類個數多于負類個數，故不能把P2劃分到危險區域。對每一個正類P_i進行上述過程，此時候選樣本為危險區域的樣本，計算出候選樣本中心，在候選樣本和候選樣本中心之間產生新的少數類樣本。

圖1 SCSMOTE算法原理圖

1.2.2 算法實現

在以上定義以及SMOTE算法的基礎上，基于R語言開發環境實現算法。設程序中原始樣本集合為X，target是數據集X的目標類屬性的向量，K、C為近鄰參數，用于標記指定樣本的近鄰個數，默認值為5。

算法1SCSMOTE(X,target,K,C)

1) 對于初始數據集X，計算并找出正類集合P_set，在整個初始集合X中對P_set中的每一個樣本P_i根據k近鄰算法原理計算其C個近鄰。若其C個近鄰類別中負類數量多于正類數量，且不全部為正類，則把此樣本放入危險區域Danger集合中。

2) 統計Danger區域樣本數量，當其小于(等于)總體正類數量的四分之一，即認為此時得到的危險區域不具有代表性，計算正類集合中心synP_center，把全體正類樣本作為候選樣本。

3) 當Danger區域樣本數量大于總體正類數量的四分之一，計算危險區域集合的中心syn_center，把危險區域中的樣本作為候選樣本。

4) 計算需要合成正類個數的平衡因子sum_dup。

5) 按條件選擇式(4)、式(5)確定合成樣本syn_dat。

2 實驗與結果分析

2.1 數據集

為了更好地驗證算法的有效性，從UCI數據集中選擇11個數據集作為驗證集，本文將選取的數據集分為訓練集和測試集，各數據集的基本信息見表1。

表1 各數據集樣本分布

其中選取的數據集abalone_I來自UCI中abalone數據集，abalone數據集中的樣本共有28個類別，人為將類別5作為正類樣本，類別6作為負類樣本。glass_I來自UCI中glass數據集，glass數據集中的樣本共有7個類別，人為將類別5、6、7合成一類作為正類樣本，其余樣本合為一類作為負類樣本。Yeast_I來自UCI中Yeast數據集，Yeast數據集中的樣本共有10個類別，人為的將類別EXC作為正類樣本，CYT作為負類樣本。Ecoli_I來自UCI中Ecoli數據集,共有8個類別，人為的將類別im作為正類樣本，其余的合為一類作為負類樣本。Breast數據集中的樣本共有6個類別，人為的將類別car作為正類樣本，其余法人合為一類作為負類樣本。Wine_I來自UCI中Wine數據集，共有3個類別，人為的將類別1作為正類樣本，類別2和類別3作為負類樣本。seeds_I數據集中的樣本共有3個類別，人為的將類別1作為正類樣本，類別2和類別3作為負類樣本。數據集具有不平衡特征的界限是數據集中少數類樣本個數與多數類樣本個數的比例低于1∶2[8]。本文采用R語言完成SCSMOTE、SMOTE和RF算法的構造。

2.2 評價度量

對于非平衡數據集來說，采用分類精度來評價分類器的性能是不合理的[9]。一般使用混淆矩陣來評估，分別將兩類分為正類(positive)、負類(negative)，如表2所示[10]。混淆矩陣的列用來表示類的預測結果，行用來表示類的實際類別[11]。其中，TP(ture positive)表示正類樣本中被劃分正確的樣本數，即真正類，TN(true negative)表示負類樣本中被劃分正確的樣本數，即真負類，FP(flase positive)表示正類樣本中被劃分錯誤的樣本數，即假正類，FN(flase negative)表示負類樣本中被劃分錯誤的樣本數，即假負類[12]。

表2 混淆矩陣

由表2，可得出準確率(Precision)、召回率(Recall)和真負類率如式(6)-式(8)所示，其是分類器最基本的指標[13]。定義為：

(6)

(7)

(8)

F-value是準確率和召回率的調和均值，定義如下：

(9)

式中：參數β一般取值1，可知只有準確率和召回率均較大時,F-value才會有較大值。

若要對算法進行總體評價，則要借助G-mean值，它是用來衡量分類器對正負樣本分類的平均性能[14]。其公式如下：

(10)

本文選用Recall、Precision、F-value、G-mean等值作為算法性能指標的度量。

2.3 實驗數據分析

本文的仿真實驗均是在R語言中實現，記錄了隨機森林在三種實驗方案下的實驗數據，即未采樣、SMOTE采樣和本文的采樣算法。為了更好地分析近鄰參數K值的影響，首先隨機選取4個數據集進行不同的近鄰參數實驗分析，其F-value、G-mean值如圖2-圖3所示，橫坐標為K的取值， RF參數統一采用默認參數設置；然后對全部數據集采用默認的近鄰參數(K=5)進行三種算法預處理。

圖2 不同近鄰參數取值下的F-value值

圖3 不同近鄰參數取值下的G-mean值

從圖2和圖3可以看出，當K取不同值時，用SCSMOTE處理的數據集abalone_I、glass_I、SPECTE的F-value、G-mean值始終最大或者與SMOTE算法相等；對于數據集Statlog，SCSMOTE處理后的F-value值始終在最上方或者與SMOTE重合，而當K=5時，SCSMOTE算法的G-mean值比SMOTE算法要小，可知SCSMOTE算法提高了F-value值，卻降低了G-mean值。

為了整體分析算法的優勢，采用統一的近鄰參數(K=5)對全部數據集進行實驗分析，圖4-圖7繪制了11個數據集上3種算法的測試結果圖,其中，橫坐標為所選取的不同數據集，縱坐標取值在0～1之間。表3-表6是它們的對應值表，可以看出，使用SCSMOTE算法進行過采樣，少數類的分類性能有所上升。

圖4 少數類準確率(Recall)變化曲線圖

表3 少數類準確率(Recall)

圖5 準確率(Precision)變化曲線圖

表4 準確率(Precision)

圖6 F-value變化曲線圖

表5 F-value值

圖7 G-mean變化曲線圖

表6 G-mean值

由表3結合圖4可知，大部分數據集在SCSMOTE算法處理后，經RF分類的Recall值大于未使用算法處理和SMOTE算法，表明RF在對經過SCSMOTE算法處理后的數據集分類時，有效地降低了實際正類預測為負類的錯判個數。在表4和圖5中，可以看出數據集經過隨機森林分類后，準確率已經較高。然而大部分數據集在SMOTE算法處理后，經隨機森林分類的Precision值不升反而降低，表明數據集經SMOTE算法處理后，增多了實際負類預測為正類的錯判個數，從而使得Precision值有所降低，SMOTE算法并沒有從根本上提高分類器的分類準確率。大部分數據集在SCSMOTE算法處理后，經隨機森林分類的Precision值相比于未經任何算法處理進行隨機森林分類的Precision值有所提高，并且相對于SMOTE算法有顯著的優勢。在表5和圖6 中可以看到，對于非平衡程度高的數據集，其經過SCSMOTE算法處理后的數據集，經RF分類的F-value值高于未使用任何算法和SMOTE算法處理后的F-value值。而用于評價非平衡數據集整體性能的G-mean指標則可從表6中觀察，表6和圖7顯示SCSMOTE算法在大部分的數據集上的 G-mean 值有顯著的優勢，說明本文提出的算法在這些數據集上有較好的總體分類性能。

綜上所述，圖表中的Breast_I數據集的訓練集中正類樣本有12個，經過SCSMOTE算法處理后，得到危險區域中的正類樣本個數為3個，此時算法會選全部正類樣本作為候選集(種子樣本)。Wine_I數據集的訓練集中正類樣本個數為20個，經過SCSMOTE算法處理后，得到危險區域中的正類樣本個數為3個，此時算法會選全部正類樣本作為候選集(種子樣本)。Seeds數據集的訓練集中正類樣本個數為16個，經過SCSMOTE算法處理后，得到危險區域中的正類樣本個數為2個，此時算法會選全部正類樣本作為候選集(種子樣本)。由以上實驗結果表明本文提出的算法在一定程度上提高了隨機森林對非平衡數據分類的性能，分類效果有一定程度的改進，能夠在不降低隨機森林對多數類分類精度的同時，保證分類器對少數類的正確分類，并具有良好的適應性。

3 結 語

本文針對隨機森林(RF)對非平衡數據集進行分類時所表現的不足，在分類器訓練樣本數據集之前，引入數據預處理，提出一種新的過抽樣算法SCSMOTE。算法的關鍵是根據數據集自身分布情況，選擇合適的候選樣本，以增加對數據合成質量的控制。實驗結果表明，經過本文方法處理的數據集，在進行數據集分類時，能有效地提高隨機森林分類器的分類性能，使得隨機森林在病毒入侵、設備故障檢測領域具有顯著優勢。但算法程序中用于判定危險區域的近鄰參數k往往需要人工設定，如何通過自適應方法產生類的近鄰，是本文進一步的研究方向。