一種非平衡數(shù)據(jù)分類的過采樣隨機(jī)森林算法

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

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

0 引 言

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

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

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

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

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

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

1 算法設(shè)計

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

1.1 SMOTE算法

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

算法實現(xiàn)如下。

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

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

syn_i=P_i+g×(Q_k-P_i)

(1)

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

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

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

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

1.2 非平衡數(shù)據(jù)集學(xué)習(xí)算法SCSMOTE

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

1.2.1 正類樣本數(shù)據(jù)的合成

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

定義1危險區(qū)域

定義2危險區(qū)域樣本中心

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

(2)

定義3正類樣本中心

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

(3)

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

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

(4)

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

Scenter為此區(qū)域正類樣本的中心點；

Psynj為合成的樣本；

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

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

(5)

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

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

圖1 SCSMOTE算法原理圖

1.2.2 算法實現(xiàn)

在以上定義以及SMOTE算法的基礎(chǔ)上，基于R語言開發(fā)環(huán)境實現(xiàn)算法。設(shè)程序中原始樣本集合為X，target是數(shù)據(jù)集X的目標(biāo)類屬性的向量，K、C為近鄰參數(shù)，用于標(biāo)記指定樣本的近鄰個數(shù)，默認(rèn)值為5。

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

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

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

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

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

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

2 實驗與結(jié)果分析

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

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

表1 各數(shù)據(jù)集樣本分布

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

2.2 評價度量

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

表2 混淆矩陣

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

(6)

(7)

(8)

F-value是準(zhǔn)確率和召回率的調(diào)和均值，定義如下：

(9)

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

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

(10)

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

2.3 實驗數(shù)據(jù)分析

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

圖2 不同近鄰參數(shù)取值下的F-value值

圖3 不同近鄰參數(shù)取值下的G-mean值

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

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

圖4 少數(shù)類準(zhǔn)確率(Recall)變化曲線圖

表3 少數(shù)類準(zhǔn)確率(Recall)

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

表4 準(zhǔn)確率(Precision)

圖6 F-value變化曲線圖

表5 F-value值

圖7 G-mean變化曲線圖

表6 G-mean值

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

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

3 結(jié) 語

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