一種基于混合采樣的非均衡數據集分類算法

張 明,胡曉輝,吳嘉昕

(蘭州交通大學 電子與信息工程學院,蘭州 730070)

1 引 言

大數據時代使得數據的知識獲取變得更加便捷,促進了數據密集型科學的發展.分類是機器學習和數據挖掘中重要的信息獲取手段之一,傳統的分類方法有線性判別分析法、決策樹、貝葉斯、Logistic回歸分析和支持向量機等[1-4],但傳統的分類算法沒有考慮數據的均衡性,在非均衡分類問題上仍面臨著巨大的挑戰.所謂非均衡數據,是指某一類樣本的數量明顯少于另一類樣本的數量,即多數類(負類)和少數類(正類)存在比例失衡[5].在非均衡數據集中少數類可能比多數類包含著更多有價值的信息,在這種情況下,正確識別少數類比正確識別多數類更加重要.

隨機森林[6]通過自助采樣[7]獲取樣本集,從而構建決策樹得到很好的分類預測效果,常被用于數據集分類研究[8,9]中.但在實際應用中,因為所獲得的數據常常表現為非均衡數據[10],所以在數據處理方面經常引入欠采樣和過采樣方法,對于非均衡數據集的處理Chawla 等人提出了SMOTE算法[11],該算法通過人為構造少數類樣本使得數據集趨于平衡.由于該方法沒有考慮到少數類內部分布不均的現象,針對文獻[11],Han等人后來又在SMOTE方法的基礎上提出了Borderline-SMOTE方法[12],該方法把少數類樣本分為安全樣本、邊界樣本和噪聲樣本3 類,并對邊界樣本進行近鄰插值.這些算法雖然都一定程度上改善了非均衡數據集處理的問題,但是因為這些算法都只是對少數類樣本進行過采樣處理,所以最后可能會導致樣本集分類時出現過擬合現象.由于欠采樣方法可能會失去許多樣本的信息,而過采樣方法可能會使少數類樣本過擬合.本文提出了一種新的基于混合采樣的隨機森林算法(USI).在對非均衡數據分類的研究中,基于混合采樣的隨機森林算法(USI)與基于樣本特性欠采樣的隨機森林算法(RU)、基于IS欠采樣的隨機森林算法、基于SMOTE過采樣的隨機森林算法(SMOTE)、基于USMOTE過采樣的隨機森林算法以及基于隨機欠采樣與SMOTE相結合的隨機森林算法(RU-SMOTE)進行比較,實驗結果表明改進算法(USI)進一步提高了在非均衡數據集上的G-mean值,F-value值,具有更高的綜合分類準確率.

2 傳統算法與原理

2.1 隨機森林

隨機森林[6]基本思想可概括為:包含多個決策樹的分類器.首先有放回地重復隨機抽取原始訓練樣本集中一定量的樣本生成新的訓練集,然后對這些訓練集建立決策樹模型得到不同的分類結果,最后統計分類結果來決定最優的分類結果.隨機森林算法詳細步驟如下:

1)設原始訓練集為N,采用Bootstrap重抽樣方法[7]有放回地隨機抽取t個新樣本集,構建t棵分類樹.每個樣本包含v個屬性;

2)在樣本v個屬性中進行隨機特征選擇,選擇m(m

3)每棵決策樹不做任何修剪,最大限度地生長,多個決策樹形成的分類器組成隨機森林;

4)當待測樣本X進入該隨機森林后,隨機森林里的每個決策樹對其進行判別,通過類似投票的方式將票數最多的類設為該樣本點的預測類別.

2.2 隨機欠采樣

在非均衡數據集處理中隨機欠采樣[13]方法主要是隨機刪除多數類中的一部分樣本,而對少數類樣本不做任何操作,由于在隨機刪除樣本的過程中存在隨機性和偶然性,會導致多數類樣本中的一些重要信息丟失,最終會影響在非均衡數據集中的綜合分類性能.

2.3 SMOTE算法

SMOTE算法[11]即合成少數類過采樣技術.如圖1所示,

對每個少數類樣本X,得到其k近鄰,k取5,如5個最近鄰樣本Y1,Y2,Y3,Y4,Y5,然后在X與這5個樣本之間的連線上隨機生成新的少數類樣本Z1,Z2,Z3,Z4,Z5.它其實是對于隨機過采樣算法的一種改進算法,隨機過采樣增加少數類樣本的方法只是通過簡單復制樣本,這樣容易產生過擬合的問題,會使模型學習到的信息過于特別而不夠泛化.SMOTE算法詳細步驟如下:

1)少數類中每一個樣本x,以公式(1)歐幾里得距離D計算它到少數類樣本集中所有樣本的距離,得到其k近鄰[14],通常k取5;

(1)

2)對少數類樣本集進行分組,以歐幾里得距離最近的6個樣本分為1組;

3)根據公式(2),在每組樣本兩兩之間連線上隨機生成少數類樣本,加入樣本集;

4)當少數類樣本與多數類樣本比例不成1:1,執行步驟3).

Xnew=x+rand(0,1)*|x-t|

(2)

隨機欠采樣,SMOTE算法較好地改善了隨機森林處理非均衡數據集的問題,使得模型對樣本的分類預測正確率有所提高.但是隨機欠采樣方法會失去許多樣本的信息,而SMOTE過采樣方法會使樣本數據集的少數類過擬合.

3 分類算法改進

3.1 稀疏域和密集域檢測

在非均衡數據集的處理上,由于欠采樣方法可能會失去許多樣本的信息,而過采樣可能會使少數類樣本過擬合.而且傳統的方法分類前,往往先將稀疏區域數據作為噪聲數據直接刪除.但是,由于在非均衡數據集中多數類樣本與少數類樣本數量差異較大,如果稀疏區域數據中的少數類樣本數量過多,直接刪除稀疏區域數據會使數據集更加非均衡.假設一個數據集T,多數類樣本集為D,少數類樣本集為S.針對以上問題,本文提出基于混合采樣的非均衡數據集算法.首先采用基于變異系數[15]的樣本檢測方法識別非均衡數據集的稀疏域和密集域,基本思想如下:

1)在數據集T中計算出對象t到其k近鄰距離之和的平均值,其中對象d為t的k近鄰,Nkdist(t)為d的k近鄰的個數.每個點的密度用平均值的倒數表示

(3)

2)該對象k近鄰密度的標準差與它們的平均值的比值定義為t的變異系數,即

(4)

3.2 稀疏域樣本處理

稀疏域:改進的SMOTE—USMOTE

該方法首先把稀疏域中少數類樣本S分為安全樣本、邊界樣本和噪聲樣本3類,找出少數類的邊界樣本后,不僅從少數類樣本中求最近鄰,生成新的少數類樣本,而且在多數類樣本中求其最近鄰,生成新的少數類樣本,最后再對加入人工合成少數類后的稀疏域數據集進行適當的欠采樣處理[16],這會使得少數類樣本更加接近其真實值.

1)在少數類樣本S中,計算每個樣本點pi與所有訓練樣本的歐氏距離,獲得該樣本點的m近鄰,m=5.

2)在少數類樣本S中,設在m近鄰中有m′個屬于多數類樣本,顯然0≤m′≤m.若m′=m,pi被認為是噪聲樣本;若m/2≤m′

3)計算邊界樣本點pi′與少數類樣本S的k近鄰,k=5.選出α比例的樣本點與pi′進行隨機的線性插值,產生新的少數類,最后在多數類樣本D中選出1-α比例的樣本點與pi′進行線性插值,隨機產生新的少數類,α=0.7.

4)對加入人工合成少數類后的稀疏域數據集進行欠采樣處理,為了避免對多數類樣本進行欠采樣時去掉過多有用信息的數據,所以適當減少清理的程度.對于數據集的每一個樣本pi,找到它的2個近鄰,如果樣本pi屬于多數類,當分類后,它的2個近鄰屬于少數類時,則去掉樣本pi;如果樣本pi屬于少數類,并且它的2個近鄰屬于多數類,則去掉pi的2個多數類近鄰.

5)稀疏域中重構后的樣本集形成新的樣本集Train1.

3.3 密集域樣本處理

密集域:改進的欠采樣算法—IS

對多數類樣本集D進行劃分,首先采用k近鄰方法將多數類樣本集分為噪聲樣本、邊界樣本和安全樣本,然后在邊界樣本集中選定一個樣本點c,以c為圓心r為半徑形成的圓內,n表示在圓內所包含的樣本數量.如果在圓內的總樣本大于等于n/2,則刪除該樣本點,否則保留樣本點.具體流程如下:

1)采用k近鄰方法將多數類樣本集分為噪聲樣本、邊界樣本和安全樣本.刪除噪聲樣本,保留安全樣本[11];

2)在邊界樣本集中,選定樣本點c,確定以樣本點c為圓心,r為半徑的圓形區域,調整控制r大小使圓形區域內的樣本數量為10;

3)如果在圓內的總樣本數大于或等于5,則刪除該樣本點,否則保留樣本點.一直重復以上步驟直到達到設定的采樣樣本數;

4)密集域中重構后的樣本集形成新的樣本集Train2.

3.4 基于混合采樣的隨機森林算法流程

各樣本定義如下:設稀疏域樣本A大小LA、密集域樣本B大小LB、稀疏域樣本中的少數類樣本a1大小La1、稀疏域樣本中的多數類樣本a2大小La2、密集域樣本中的多數類樣本b1大小Lb1、密集域樣本中的少數類樣本b2大小Lb2.

USI算法的流程見圖2.該算法首先采用基于變異系數的稀疏點檢測方法識別非均衡數據集的稀疏域和密集域,設置變異系數閾值,如果樣本的變異系數大于該閾值,則劃分為稀疏域樣本集,否則為密集域樣本集;然后,對稀疏域中的少數類,采用USMOTE算法進行過采樣,過采樣倍率為N;對于稀疏域中的多數類不做處理直接加入訓練集中;最后,對于密集域中的多數類樣本,采用IS算法進行欠采樣,欠采樣倍率為M.

N=La2/La1

(5)

M=Lb1/Lb2

(6)

本文提出的基于混合采樣的USI算法的具體步驟如下:

Step 1.遍歷S(fori:S)計算出每個樣本Xi的變異系數.

a)以歐氏距離計算出樣本Xi到每個樣本的距離并加入G集合中,對G集合進行排序;

b)找出Xi的k近鄰,計算樣本Xi分別到k個樣本的距離之和Gnum;

c)求得每個樣本的密度Td(Xi)=Gnum/k;

d)求出每個樣本的變異系數V(Xi).

Step 2.如果V(Xi)>Vp,Xi劃分到稀疏域A,否則劃分到密集域B.

Step 3.遍歷LA,如果Xi是少數類樣本,則加入集合a1;否則加入集合a2.

Step 4.對A中的a1樣本,采用改進SMOTE的USMOTE算法以N倍采樣率生成新樣本,得到樣本集Ca1,此樣本集與a1,a2形成新樣本集Train1.

圖2 算法流程圖Fig.2 Algorithm flow chart

Step 5.在B集合中采用IS算法對多數類樣本以欠采樣倍率M形成新樣本集Train2.

Step 6.Train1和Train2形成訓練集Train-data進行訓練.

Step 7.對新樣本集Train-data采用隨機森林進行分類.

本文提出的基于混合采樣的隨機森林算法(USI)相比其他算法,首先通過引進“變異系數”識別非均衡數據集的稀疏域和密集域,然后分別對稀疏域和密集域進行改進的過采樣和欠采樣方法,本文提出的USI算法克服了其他欠采樣方法如RU、IS算法可能會失去許多樣本的信息,而過采樣方法如SMOTE、USMOTE算法以及混合采樣RU-SMOTE算法可能會使少數類樣本過擬合等問題.

4 實驗分析

4.1 非均衡數據分類研究評價準則

在非均衡數據分類研究評價[17,18]中以TP表示少數類樣本被正確分類的樣本個數,FN表示少數類樣本被錯誤分類的樣本個數,FP表示多數類樣本被錯誤分類的樣本個數,TN表示多數類樣本被正確分類的樣本個數.設1為少數類,0為多數類.

真正率(查全率):即實際類別為1的樣本中,被模型正確分類的樣本所占比例:

TPR=TP/(TP+FN)

(7)

真負率:即實際類別為0的樣本中,被模型正確分類的樣本所占比例:

TNR=TN/(FP+TN)

(8)

假正率:即實際類別為0的樣本中,被模型錯誤分類的樣本所占比例:

FPR=FP/(TN+FP)

(9)

假負率:即實際類別為1的樣本中,被模型錯誤分類的樣本所占比例:

FPR=FN/(TP+FN)

(10)

精度(查準率):即所有預測為1的樣本中,正確預測的樣本所占比例:

rPr=TP/(FP+TP)

(11)

4.1.1 F-value準則

在非均衡數據評價標準中,F-value是一個綜合性的評價標準[20],如公式(12)所示:

(12)

其中TPR表示查全率,其公式如(7)所示,rPr表示查準率,其公式如(11)所示.β是一個系數,通常取值為1.根據F-value表達式可以看出,F-value可以正確的衡量分類器的每一項的性能,如果一個分類器分類后得到的召回率和精確率值都比較高,那么F-value的值也會比較高,表明該分類器性能較好,對少數類的識別精度越高.

4.1.2 G-mean準則

G-mean評價標準中包含兩個子度量標準[21].第一個是TPR,它主要是用來衡量分類器對少數類樣本的靈敏度,其公式如(7)所示.第二個則是TNR,它主要是用來衡量多數類的識別性能,其對應公式如(8)所示.將這兩個衡量標準結合得到G-mean評價指標,如公式(13):

(13)

其中TPR是分類器對少數類的分類精度,TNR是分類器對多數類的分類精度.根據G-mean的表達式可以看出,在不考慮TNR的值大小的前提下,不管TPR的數值大還是數值小都不能保證G-mean的值大.同樣,在不考慮TPR的值大小的前提下,不管TNR的數值大還是數值小都不能保證G-mean的值大,只有少數類預測準確率和多數類預測準確率都高的時候,G-mean值才會增加.因此可以說G-mean值能更加全面的評價分類器的性能.

4.2 數據集描述

UCI數據庫是加州大學歐文分校(University of CaliforniaIrvine)提出的用于機器學習的數據庫,UCI數據集是一個常用的標準測試數據集,為了評價本算法的性能,因此采用了

表1 數據表
Table 1 Sample data table

數據集維數少數類/多數類非均衡率credit17439/45618.78%pima819419/5688534.1%page1096/56314.5%iris429/1853.5%ecoli877/25929.7%german2510926/7652314.2%

UCI機器學習數據庫中的6組有代表性的非均衡數據集,如表1是數據特征信息,數據是結構化數據,需要對其做特征縮放,將特征縮放至同一個規格.數據預處理將訓練集和測試集歸一化到[0,1]區間.如果樣本集中包含幾個類別,則選擇其中一類樣本或者將數量較少的幾類樣本合并后作為少數類,其余作為多數類.采用python語言進行實驗,這6組非均衡數據集分別是credit數據集,pima數據集,page數據集,iris數據集,ecoli數據集,german數據集.每次實驗將樣本集隨機劃分,80%為訓練集20%為測試集.

4.3 實驗分析與結果(不同算法在非均衡數據集上的比較)

表2為6種算法在6種數據集上的G-mean值比較,可以看出,本文提出的USI算法與基于樣本特性欠采樣(RU)的隨機森林算法、基于IS欠采樣的隨機森林算法(IS)、基于SMOTE過采樣的隨機森林算法(SMOTE)、基于USMOTE過采樣的隨機森林算法(USMOTE)以及基于隨機欠采樣與SMOTE相結合的隨機森林算法(RU-SMOTE)進行比較,其G-mean值比其他算法都有較大幅度的提升.當決策樹個數設置為9時,credit數據集中RU算法的G-mean值是0.8991,IS算法的G-mean值是0.9031,SMOTE算法的G-mean值是0.9193,USMOTE算法的G-mean值是0.9263,RU-SMOTE算法的G-mean值達到0.9325,USI算法的G-mean值達到0.9693.說明credit數據集中稀疏域樣本點對分類性能影響較大,導致其他算法表現較差,而USI算法通過引進變異系數,采用改進的混合采樣方法克服了以上問題.

表2 不同算法上的G-mean值對比
Table 2 Comparison of G-mean values on different algorithms

數據集G-meanRU ISSMOTE USMOTERU-SMOTEUSIcreditpimapageiris ecoli german0.89910.90570.77820.62810.62530.8482 0.90310.91350.78010.64310.67210.85050.9193 0.92930.78850.67590.68740.86440.92630.93830.81560.67930.76450.87730.93250.94020.81730.71320.79370.88130.96930.96360.85220.79340.89220.9076

圖3給出6種算法在選取的4組數據集(credit、page、pima、german數據集)上不同決策樹個數對應的G-mean值,各算法的G-mean值均隨著決策樹個數增加而增加,剛開始增加較快,并最終趨于平穩.本文提出改進的USI算法的G-mean值均比其他算法有一定幅度提高.說明USI算法對少數類樣本和多數類樣本的預測準確率都有所提高.

表3 不同算法上的F-value值對比
Table 3 Comparison of F-value values on different algorithms

數據集G-meanRU ISSMOTE USMOTERU-SMOTEUSIcreditpimapageiris ecoli german0.87810.86230.77400.74710.62530.9105 0.88450.87330.77920.75610.74130.91660.9023 0.87660.78140.77650.78960.93320.91420.89350.78920.78660.78760.93620.92650.90520.80120.79320.79540.93910.9458 0.94060.84130.91450.78340.9552

表3為6種算法在6種數據集上的F-value值比較,可以看出,除了ecoli數據集,其他數據集上USI算法的F-value值均得到提高.當決策樹個數設置為9時,iris數據集中RU算法的F-value值是0.7471,IS算法的F-value值是0.7561,SMOTE算法的F-value值是0.7765,USMOTE算法的F-value值是0.7866,RU-SMOTE算法的F-value值達到0.7932,USI算法的F-value值達到0.9145.其中,USI算法性能大幅度提升.說明iris數據集中,其他算法可能會使樣本數據集的少數類過擬合,導致查全率和查準率較低.USI算法通過引進變異系數采用改進的混合采樣方法克服了以上問題,提高了分類準確率.

圖3 不同數據集上的G-mean值比較Fig.3 Comparison of G-mean values on different data sets

圖4 不同數據集上的F-value值比較Fig.4 Comparison of F-value values on different data sets

圖4給出6種算法在選取的4組數據集(credit、page、pima、german數據集)上不同決策樹個數對應的F-value值,可以看出各算法的F-value值均隨著決策樹個數增加而增加.本文提出改進的USI算法的F-value值均比其他算法有一定幅度提高.說明USI算法的綜合分類準確率有所提高.

5 結 語

在非均衡數據集分類算法的研究中,由于欠采樣方法可能會失去許多樣本的信息,而過采樣方法可能會使少數類樣本過擬合.本文提出了一種基于混合采樣的算法(USI)來平衡數據集.該算法通過引進變異系數界定稀疏域和密集域,對于稀疏域中的少數類樣本,采用改進SMOTE算法的過采樣方法(USMOTE)合成新的少數類樣本,對于密集域中的多數類樣本,采用改進的欠采樣方法(IS)形成新的多數類樣本,最后將平衡后的數據集送入由多個決策樹組成的分類器隨機森林中進行訓練,并與其他分類算法進行比較,實驗結果表明,本文提出的算法(USI)進一步提高了在非均衡數據集上的G-mean值,F-value值,分類準確率均優于其他算法.