處理不平衡樣本集的欠采樣算法

丁福利，孫立民

（煙臺(tái)大學(xué) 計(jì)算機(jī)學(xué)院，山東 煙臺(tái)264005）

0 引 言

傳統(tǒng)的分類算法是以提高樣本的總體分類準(zhǔn)確率為目標(biāo)，且假定樣本集中各類樣本的數(shù)量是平衡的。然而在實(shí)際問題中卻存在著大量不平衡樣本集:某一類的樣本數(shù)量遠(yuǎn)少于其他類的樣本數(shù)量。例如，信用卡欺詐行為檢測(cè)、網(wǎng)絡(luò)入侵檢測(cè)[1]、醫(yī)學(xué)疾病診斷[2]等。大多數(shù)分類算法在對(duì)這些樣本集進(jìn)行分類時(shí)，往往對(duì)多類樣本的分類準(zhǔn)確率較高，而對(duì)少類樣本的分類準(zhǔn)確率偏低。然而在很多實(shí)際問題中，少數(shù)類的分類準(zhǔn)確率往往比多數(shù)類的分類準(zhǔn)確率更為重要。因此，提高少數(shù)類的分類準(zhǔn)確率成為分類問題中的一個(gè)研究熱點(diǎn)。

支持向量機(jī)是以統(tǒng)計(jì)學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則為基礎(chǔ)的學(xué)習(xí)機(jī)器[3]，雖然在分類領(lǐng)域有著廣泛的應(yīng)用，但是支持向量機(jī)在處理不平衡樣本集時(shí)，對(duì)少類樣本的分類效果也不理想。為此，研究者們提出了很多處理不平衡樣本分類的算法，其中以欠采樣算法較為常用。目前常用的欠采樣算法有隨機(jī)欠采樣和Tomek Link欠采樣[4]，這兩種算法雖然對(duì)少類樣本的分類準(zhǔn)確率有著較大的提高，但由于欠采樣算法較多地刪減多類樣本點(diǎn)，反而造成了多類樣本分類準(zhǔn)確率的大幅度下降。對(duì)此，本文提出一種欠采樣算法，首先選取恰當(dāng)?shù)暮撕瘮?shù)[5]找到最佳映射空間，其次再使用欠采樣算法對(duì)多類樣本進(jìn)行刪減。

本文的第一部分對(duì)支持向量機(jī)作一簡(jiǎn)單的介紹，第二部分對(duì)分類準(zhǔn)確率不平衡問題進(jìn)行了原因分析，第三部分介紹欠采樣算法以及實(shí)驗(yàn)驗(yàn)證。文章最后，給出了本文的結(jié)論。在以下分析中，對(duì)不平衡樣本集都是設(shè)定正類樣本的個(gè)數(shù)大于負(fù)類樣本的個(gè)數(shù)。即，正類為多類，負(fù)類為少類，并且正類樣本的個(gè)數(shù)記為N＋，負(fù)類樣本的個(gè)數(shù)記為N－。

1 支持向量機(jī)簡(jiǎn)介

設(shè)已知訓(xùn)練集T＝｛（x1，y1），（x2，y2），…（xl，yl）∈ （X×Y）l｝。其中xi∈X＝Rn，yi＝｛1，－1｝，i＝1，2，……，l。支持向量機(jī)首先通過核函數(shù)將輸入空間中的映射到特征空間[5]中的Φ（xi），并構(gòu)造以下最優(yōu)化問題

其中，w為特征空間中的權(quán)向量，C為懲罰因子，用來調(diào)節(jié)置信區(qū)間和經(jīng)驗(yàn)風(fēng)險(xiǎn)的權(quán)重[6]，為第i個(gè)樣本點(diǎn)所對(duì)應(yīng)的松弛變量，b為函數(shù)的閾值[7]。

通過引入朗格朗日乘子，將上述公式轉(zhuǎn)化為原問題的對(duì)偶問題

求解這個(gè)對(duì)偶問題，得到最終函數(shù)表達(dá)式

2 不平衡問題的原因分析

不平衡問題指的是:在數(shù)量不平衡的樣本集中，各類樣本的分類準(zhǔn)確率往往相差較大。對(duì)于該問題，以往的原因分析認(rèn)為，由于支持向量機(jī)以提高總體分類準(zhǔn)確率為目標(biāo)，所以當(dāng)兩類樣本數(shù)量相差較大的時(shí)候，為了能夠提高總體分類準(zhǔn)確率，就不得不忽略少類樣本點(diǎn)的分類準(zhǔn)確率。這種分析存在這樣的問題:當(dāng)兩類樣本在特征空間上相距較遠(yuǎn)或互不重疊時(shí)，即使多類樣本的個(gè)數(shù)再怎么增加，但多類樣本中的支持向量的個(gè)數(shù)并不會(huì)隨之增加，而不會(huì)導(dǎo)致分類準(zhǔn)確率的不平衡問題。文獻(xiàn)[8]也指出，如果樣本集在特征空間上可分性較強(qiáng)，即使兩類樣本個(gè)數(shù)上不平衡，但它們依然都能取得較好的分類效果。

如圖1所示，圖中的兩類樣本之間完全線性可分。在這種情況下，無論兩類樣本的個(gè)數(shù)相差多么懸殊，但兩類的支持向量個(gè)數(shù)卻相差并不懸殊，也就不存在不平衡問題。因此，提高樣本間的可分性對(duì)于解決不平衡問題有著重要的意義，而樣本間的可分性與核函數(shù)的選取有較大關(guān)系。

圖1 樣本點(diǎn)分布

文獻(xiàn)[9，10]中指出，樣本集的可分性與特征空間上兩類樣本間的類中心間距有關(guān)。這種說法雖然有一定的道理，卻存在這樣一個(gè)缺陷:雖然兩類樣本相距較遠(yuǎn)時(shí)，樣本的可分性會(huì)隨之增強(qiáng)。但樣本相距越遠(yuǎn)并不代表兩類樣本間的類中心間距越大。這是因?yàn)?，核函?shù)的不同導(dǎo)致類中心間距的數(shù)量級(jí)大小也不同，樣本間的類中心間距無法準(zhǔn)確地衡量樣本間的可分性。例如，對(duì)于多項(xiàng)式核函數(shù)

當(dāng)g和r取值為1，d取較大值時(shí)，在該核函數(shù)的映射下，樣本間的類中心間距必然會(huì)大幅度增大，如表1所示。

表1 類間距與核函數(shù)

在表1中，第一列是多項(xiàng)式核函數(shù)中d的取值，第二列和第三列分別是UCI[11]中Iris和Wine這兩個(gè)樣本集的類間距。從上表中可以看出，當(dāng)多項(xiàng)式核函數(shù)中d的取值很大的時(shí)候，在特征空間下的類間距也大幅度變大，但樣本集的可分性并不一定會(huì)隨之增強(qiáng)，有時(shí)反而會(huì)變?nèi)酢Ｒ虼?，用類中心間距衡量類間可分性是不恰當(dāng)?shù)摹＃ū疚闹杂枚囗?xiàng)式核函數(shù)舉例，是因?yàn)楦咚购撕瘮?shù)的表達(dá)式為K（x，y）＝exp（－g×x－y2），由于括號(hào)里的式子－g×x－y2≤0，0＜k（x，y）≤1。這個(gè)核函數(shù)無論g如何取值，其類間距都相差不太明顯。）

圖2 樣本點(diǎn)分布 （可分性較強(qiáng)）

圖3 樣本點(diǎn)分布 （可分性較差）

從圖2和圖3中可以看出，盡管圖3中的類間距更大，但其可分性卻較差。這是因?yàn)椋m然圖3和圖2相比，類間距增大了，但兩類的類半徑卻更大，導(dǎo)致兩個(gè)類之間發(fā)生了重疊，因此才出現(xiàn)了可分性較差的現(xiàn)象。在上述兩個(gè)圖中，圖2中兩類樣本點(diǎn)相距較遠(yuǎn)，其類間距相對(duì)于類半徑較大。此時(shí)，類間可分性較強(qiáng)。圖3中，兩類樣本點(diǎn)相距較近，其類間距相對(duì)于類半徑較小。此時(shí)，類間可分性較差。在圖3所示的情況下，多類樣本所在區(qū)域覆蓋了少類樣本所在的區(qū)域，支持向量機(jī)為追求總體分類準(zhǔn)確率就不得不把相當(dāng)一部分少類樣本劃分為多類樣本，這樣便產(chǎn)生了分類準(zhǔn)確率的不平衡問題。

支持向量機(jī)的分類效果跟核函數(shù)的選取有較大關(guān)系，核函數(shù)選得好，兩類之間類間距相對(duì)于類半徑較大，則樣本集的可分性強(qiáng)。由上述內(nèi)容可知，在對(duì)核函數(shù)進(jìn)行選取時(shí)，應(yīng)當(dāng)選取能夠使兩類相距較遠(yuǎn)的核函數(shù)。即兩類的類間距較大，而兩類的類半徑相對(duì)較小。將類間距記為D，正類和負(fù)類樣本的類半徑分別記為:R＋和R－。因此，衡量類間可分性用來表示。將記為μ，當(dāng)μ取較大值時(shí)，類間可分性增強(qiáng)；當(dāng)取較小值時(shí)，類間可分性變?nèi)酢?/p>

3 欠采樣算法步驟與實(shí)驗(yàn)

3.1 實(shí)驗(yàn)所用樣本集

從 UCI[11]上選取Iris，Wine，Breast Cancer，Pima Indians Diabetes，German Credit Data，Contraceptive Method Choice進(jìn)行實(shí)驗(yàn)。將Breast Cancer簡(jiǎn)記為Breast，將Pima Indians Diabetes簡(jiǎn)記為Pima，將German Credit Data簡(jiǎn)記為German，將Contraceptive Method Choice簡(jiǎn)記為CMC。其中，將類別個(gè)數(shù)大于2的樣本集，第一類記為負(fù)類（少類），其余類記為正類 （多類），以此來構(gòu)造不平衡樣本集。

3.2 核函數(shù)的選取

類半徑的計(jì)算過程為:首先計(jì)算得到特征空間下的類中心點(diǎn)，然后計(jì)算類中心點(diǎn)到類中每一個(gè)點(diǎn)的距離的平均值作為類半徑。例如，正類樣本的類半徑計(jì)算公式如下

同理，可計(jì)算得，并根據(jù)計(jì)算得到的D和R＋、R－，求出μ。

實(shí)驗(yàn)待選的核函數(shù)采用LIBSVM[12]中最常用的3種核函數(shù)，分別為線性核函數(shù)，多項(xiàng)式核函數(shù)，高斯核函數(shù)。常用核函數(shù)見表2。

表2 常用核函數(shù)

對(duì)于各類核函數(shù)，其參數(shù)的取值為｛2－10，2－9，2－8，…，20，…28，29，210｝，求出能夠使得取最大值的核函數(shù)。結(jié)果如表3所示。

表3 核函數(shù)的選取

3.3 欠采樣過程

當(dāng)核函數(shù)選定后，對(duì)多類樣本點(diǎn)進(jìn)行欠采樣。由于距少類樣本中心點(diǎn)的多類樣本點(diǎn)為噪聲點(diǎn)的可能性較大，因此對(duì)多類樣本點(diǎn)進(jìn)行欠采樣時(shí)，應(yīng)當(dāng)首先考慮刪減這些樣本點(diǎn)。欠采樣具體過程如下。

（1）在選定好的特征空間上，計(jì)算出多類樣本中每個(gè)樣本點(diǎn)到少類樣本中心點(diǎn)的距離d。

（2）對(duì)多類樣本點(diǎn)按照d從小到大的順序進(jìn)行排序。

（3）設(shè)定參數(shù)ε，從多類樣本中根據(jù)d從小到大的順序依次刪除ε×（N＋－N－）個(gè)樣本點(diǎn)。

其中，參數(shù)的取值范圍為[0，1]，取0表示不刪減，取1表示將多類樣本刪減到和少類樣本同樣的個(gè)數(shù)。

（4）將經(jīng)過欠采樣后的多類樣本與少類樣本合并，重新訓(xùn)練SVM模型。

3.4 實(shí)驗(yàn)結(jié)果分析

根據(jù)上述過程進(jìn)行實(shí)驗(yàn)，對(duì)于每個(gè)樣本集，隨機(jī)抽取80%的樣本作為訓(xùn)練樣本，其余的20%的樣本作為測(cè)試樣本。隨機(jī)抽取10次進(jìn)行實(shí)驗(yàn)，并求取平均值。實(shí)驗(yàn)以G－mean[2]為評(píng)價(jià)標(biāo)準(zhǔn)衡量實(shí)驗(yàn)結(jié)果的好壞。如表4所示，表中第一列為樣本集名稱，第二至六列為不同方法下實(shí)驗(yàn)所得到的G－mean。將標(biāo)準(zhǔn)支持向量機(jī)方法記為方法1，將隨機(jī)欠采樣方法記為方法2，將Tomek Link欠采樣方法記為方法3，將LIBSVM[12]自帶的處理不平衡樣本集的方法記為方法4，本文方法記為方法5。

表4 實(shí)驗(yàn)結(jié)果表 （G－mean）

對(duì)于表4縱向比較可知，無論是何種算法，它的實(shí)驗(yàn)結(jié)果與樣本集本身具有一定的關(guān)系。將表4橫向比較可得如下結(jié)論:本文方法的實(shí)驗(yàn)效果優(yōu)于其他方法，說明本文方法的科學(xué)有效性。表5為各類方法的總體分類準(zhǔn)確率。根據(jù)這兩個(gè)表可得，本文方法不僅在G－mean上效果優(yōu)于其他方法，在總體分類準(zhǔn)確率上依然很高。由于本文的方法以提高樣本間的可分性為首要目標(biāo)，不僅能夠提高少類樣本的分類準(zhǔn)確率，并且將多類樣本的分類準(zhǔn)確率的損失降到最低，取得了較好的實(shí)驗(yàn)結(jié)果。

表5 實(shí)驗(yàn)結(jié)果表 （總體分類準(zhǔn)確率）

在本文所描述的算法中，涉及到一個(gè)實(shí)驗(yàn)參數(shù)ε。表6所示不同的樣本集下，參數(shù)ε和值μ的關(guān)系。由該表可以明顯地看出，參數(shù)ε的選取與μ值成負(fù)相關(guān) （經(jīng)表6計(jì)算可得:兩者的相關(guān)系數(shù)[13]為－0.93，接近于－1）。這是因?yàn)楫?dāng)值較大時(shí)，兩類樣本相距較遠(yuǎn)，樣本間的可分性增強(qiáng)，這時(shí)便不需要進(jìn)行大量的欠采樣依然能夠獲得較好的分類效果，參數(shù)ε應(yīng)當(dāng)取較小值。反之亦然。

表6 μ值和參數(shù)ε

4 結(jié)束語

本文針對(duì)支持向量機(jī)在處理不平衡樣本集時(shí)所出現(xiàn)的分類準(zhǔn)確率不平衡問題，在對(duì)其做出準(zhǔn)確的原因分析的基礎(chǔ)上，提出了一種核函數(shù)選取與欠采樣相結(jié)合的算法，并通過UCI標(biāo)準(zhǔn)樣本集進(jìn)行實(shí)驗(yàn)，從而驗(yàn)證了本文算法的科學(xué)有效性。在對(duì)表4和表5進(jìn)行縱向比較中發(fā)現(xiàn)，對(duì)于某些樣本集 （例如:German和CMC），常用的核函數(shù)很難取得較好的映射效果。因此，在今后對(duì)于不平衡問題，首要問題應(yīng)該充分考慮更多的核函數(shù)，選取最佳映射。只有這樣才能取得更好的實(shí)驗(yàn)結(jié)果，才能從根本上解決樣本的不平衡問題。

[1]GONG Shangfu，ZHAO Chunlan，SHE Xiangyang.Intrusion detection system based on R－SVM[J].Computer Engineering and Design，2012，33 （10）:3777－3782（in Chinese）.[龔尚福，趙春蘭，厙向陽.基于R－SVM的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33 （10）:3777－3782.]

[2]SUN Xiaoyan.Study of classification algorithm on unbalanced data sets[D].Jinan:Shandong Normal University，2012（in Chinese）.[孫曉燕.不平衡數(shù)據(jù)集分類問題研究[D].濟(jì)南:山東師范大學(xué)，2012.]

[3]LIU Susu，SUN Limin.Performance comparison of regression prediction on support vector machine and RBF neural network[J].Computer Engineering and Design，2011，32 （12）:4202－4205（in Chinese）.[劉蘇蘇，孫立民.支持向量機(jī)與RBF神經(jīng)網(wǎng)絡(luò)回歸性能比較研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32 （12）:4202－4205.]

[4]YANG Zhiming，PENG Yu，PENG Xiyuan.Research on classification technique for imbalanced dataset based on support vector machines[J].Chinese Journal of Scientific Instrument，2009，30 （5）:1094－1099（in Chinese）.[楊智明，彭宇，彭喜元.基于支持向量機(jī)的不平衡數(shù)據(jù)集分類方法研究[J].儀器儀表學(xué)報(bào)，2009，30 （5）:1094－1099.]

[5]ZHANG Rui，GAO Hong，ZHANG Liwei.A new set of hemite kernel functions for support vector machine[J].Journal of Shanxi University（Natural Science Edition），2012，35 （1）:38－42（in Chinese）.[張瑞，高紅，張立偉.一類新的支持向量機(jī)核函數(shù)——埃爾米特核函數(shù)[J].山西大學(xué)學(xué)報(bào) （自然科學(xué)版），2012，35 （1）:38－42.]

[6]XIAO Jian，YU Long，BAI Yifeng.Survey of the selection of kernels and hyper－parameters in support vector regression[J].Journal of Southwest Jiaotong University，2008，43 （3）:297－303（in Chinese）.[肖建，于龍，白裔峰.支持向量回歸中核函數(shù)和超參數(shù)選擇方法綜述[J].西南交通大學(xué)學(xué)報(bào)，2008，43 （3）:297－303.]

[7]SHAN Yugang，WANG Hong，DONG Shuang.Improved multi－classification algorithm of one－against－one SVM[J].Computer Engineering and Design，2012，33 （5）:1837－1841（in Chinese）.[單玉剛，王宏，董爽.改進(jìn)的一對(duì)一支持向量機(jī)多分類算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2012，33 （5）:1837－1841.]

[8]ZHAO Zixiang，WANG Guangliang，LI Xiaodong.An improved SVM based under－sampling method for classifying imbalanced data[J].Acta Scientiarum Naturalium Universitatis Sunyatseni，2012，51 （6）:10－16 （in Chinese）.[趙自翔，王廣亮，李曉東.基于支持向量機(jī)的不平衡數(shù)據(jù)分類的改進(jìn)欠采樣方法[J].中山大學(xué)學(xué)報(bào) （自然科學(xué)版），2012，51 （6）:10－16.]

[9]CAI Zheyuan，YU Jianguo，LI Xianpeng，et al.Feature selection algorithm based on kernel distance measure[J].Pattern Recognition and Artificial Intelligence，2010，23 （2）:235－240（in Chinese）.[蔡哲元，余建國，李先鵬，等.基于核空間距離測(cè)度的特征選擇[J].模式識(shí)別與人工智能，2010，23（2）:235－240.]

[10]LIU Susu，DING Fuli，SUN Limin.A novel kernel matrix method for SVM kernel parameter optimization[J].Journal of Yantai U－niversity（Natural Science and Engineering Edition），2013，26（2）:131－135（in Chinese）.[劉蘇蘇，丁福利，孫立民.優(yōu)化支持向量機(jī)核參數(shù)的核矩陣方法研究[J].煙臺(tái)大學(xué)學(xué)報(bào) （自然科學(xué)與工程版），2013，26 （2）:131－135.]

[11]UC irvine machine learing repository[OL].http:／／archive.ics.uci.edu／ml／.2013

[12]Chang C C，Lin C J.LIBSVM:A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology，2011，2 （3）.

[13]XU Yongqun，DENG Sanyao，LI Xingwang，et al.Application of comparison method with correlation coefficient array in identification of Chinese herbs[J].Spectroscopy and Spectral Analysis，2007，27 （11）:2239－2242（in Chinese）.[徐永群，鄧三堯，李興旺，等.陣列相關(guān)系數(shù)比對(duì)法在中藥鑒別中的應(yīng)用研究[J].光譜學(xué)與光譜分析，2007，27 （11）:2239－2242.]