郭亞偉,白治江

(上海海事大學(xué) 信息工程學(xué)院,上海 201306)

?

基于混合重采樣的非平衡數(shù)據(jù)SVM訓(xùn)練方法

郭亞偉,白治江

(上海海事大學(xué) 信息工程學(xué)院,上海 201306)

摘要：針對(duì)傳統(tǒng)的SVM算法在非平衡數(shù)據(jù)分類中分類效果不理想的問(wèn)題，提出一種基于分類超平面和SMOTE過(guò)采樣方法(HB_SMOTE)。該方法首先對(duì)原始訓(xùn)練樣本集使用WSVM算法找到分類超平面，然后按一定標(biāo)準(zhǔn)剔除負(fù)類中被錯(cuò)分的樣本、靠近分類超平面的樣本以及遠(yuǎn)離分類超平面的樣本。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明：與RU_SMOTE等重采樣方法相比，HB_SMOTE方法對(duì)正類樣本和負(fù)類樣本都具有較高的分類準(zhǔn)確率。

關(guān)鍵詞：非平衡數(shù)據(jù)集；SMOTE；分類超平面；SVM；混合重采樣

引用格式：郭亞偉,白治江. 基于混合重采樣的非平衡數(shù)據(jù)SVM訓(xùn)練方法[J].微型機(jī)與應(yīng)用，2016,35(12)：52-54，58.

0引言

支持向量機(jī)(SVM)[1]因其能夠有效地避免維數(shù)災(zāi)難，實(shí)現(xiàn)全局最優(yōu)，具有嚴(yán)謹(jǐn)?shù)睦碚摶A(chǔ)和良好的泛化能力，現(xiàn)已成為機(jī)器學(xué)習(xí)領(lǐng)域的熱點(diǎn)問(wèn)題。傳統(tǒng)的SVM方法需要其各類樣本集的規(guī)模相同。然而在現(xiàn)實(shí)生活中，往往會(huì)遇到一些非平衡數(shù)據(jù)分類問(wèn)題，如入侵檢測(cè)、文本分類、醫(yī)療診斷等。使用這些數(shù)據(jù)對(duì)SVM方法進(jìn)行訓(xùn)練建模時(shí)，分類決策面會(huì)向少數(shù)類偏移，導(dǎo)致少數(shù)類的分類準(zhǔn)確率降低。國(guó)內(nèi)外學(xué)者針對(duì)此類問(wèn)題進(jìn)行了深入的研究，提出了許多不同的處理方案。

目前，針對(duì)非平衡數(shù)據(jù)下SVM分類問(wèn)題的研究主要集中在算法層面和數(shù)據(jù)重采樣兩個(gè)方面。算法層面主要是代價(jià)敏感性方法。這種方法雖然增加了少數(shù)(正)類的分類準(zhǔn)確率，但卻犧牲了多數(shù)(負(fù))類的分類準(zhǔn)確率，總的分類效果也受到了極大的影響[2]。數(shù)據(jù)重采樣技術(shù)主要是過(guò)采樣和欠采樣。過(guò)采樣主要包括隨機(jī)過(guò)采樣、SMOTE[2]算法、Borderline-SMOTE[3]技術(shù)等。這些過(guò)采樣方法雖然可以確保原始分類信息的完整性，但是由于新合成的正類樣本不能準(zhǔn)確表達(dá)原始樣本集的信息，從而導(dǎo)致過(guò)擬合，同時(shí)也會(huì)增加計(jì)算復(fù)雜度。欠采樣主要包括隨機(jī)欠采樣、基于聚類欠采樣的極端學(xué)習(xí)機(jī)[4]等。單一的欠采樣技術(shù)雖然可以降低計(jì)算復(fù)雜度，但是在刪除樣本時(shí)通常會(huì)導(dǎo)致負(fù)類樣本中部分信息缺失，影響分類準(zhǔn)確性。

參考文獻(xiàn)[5]表明相較于單一的采樣方法，混合重采樣方法往往能夠得到更好的分類效果。參考文獻(xiàn)[6]表明對(duì)于分類來(lái)說(shuō)最重要的數(shù)據(jù)是位于邊界的樣本，噪聲樣本和距離分類邊界較遠(yuǎn)的樣本對(duì)數(shù)據(jù)信息的貢獻(xiàn)不大。據(jù)此，本文提出了一種基于混合重采樣和分類超平面的分類方法并在UCI數(shù)據(jù)集上進(jìn)行建模訓(xùn)練，驗(yàn)證算法的有效性。

1基本的分類方法

1.1SMOTE算法

SMOTE算法[2]是由CHAWLA N V等人提出的一種過(guò)采樣方法。該算法步驟如下。

(1)對(duì)正類中的每一個(gè)樣本x，計(jì)算它到該類中其他每個(gè)樣本的歐氏距離，獲取其k個(gè)最近鄰樣本，并記錄近鄰下標(biāo)。

(2)按照兩類數(shù)據(jù)集不均衡的比率設(shè)置正類的采樣倍率N,對(duì)所有正類樣本x，從k個(gè)最近鄰中隨機(jī)選取xi(i=1，…，N)。

(3)對(duì)每一個(gè)近鄰xi，分別與原始樣本x按照xnew=x+rand(0,1)×(xi-x)合成新樣本。

(4)把合成的新樣本與原始訓(xùn)練樣本集并為新的訓(xùn)練集，并在該樣本集上學(xué)習(xí)。

1.2SVM與WSVM

SVM是在統(tǒng)計(jì)學(xué)習(xí)理論中結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則基礎(chǔ)上提出的機(jī)器學(xué)習(xí)方法[1]。其原理是尋找一個(gè)最優(yōu)分類超平面，使得該超平面在保證分類精度的同時(shí)，能夠使超平面兩側(cè)的空白區(qū)域最大化。此外，它還能通過(guò)核函數(shù)將低維空間中的線性不可分問(wèn)題轉(zhuǎn)化為高維空間中的線性可分問(wèn)題。設(shè)訓(xùn)練樣本集為(xi,yi),i=1,2,…,l,x∈Rn,y∈{±1}，超平面記作(w·φ(x))+b=0，其中φ(x)為x從輸入空間Rn到特征空間H的變換。將構(gòu)造最優(yōu)超平面問(wèn)題轉(zhuǎn)化為求解二次凸規(guī)劃問(wèn)題，即：

s.t

yi(w·φ(xi)+b)≥1-ξi，ξi≥0,i=1,2,…，l

分類判別式為:

為解決由于樣本集失衡導(dǎo)致的分類決策面偏移問(wèn)題，引入了基于代價(jià)敏感的WSVM，主要思想是對(duì)錯(cuò)分的正類和負(fù)類樣本分別賦予不同的懲罰系數(shù)C+和C-，約束表達(dá)式變?yōu)椋?/p>

s.t.

yi(w·φ(xi)+b)≥1-ξi，ξi≥0,i=1,2,…，l

2混合重采樣方法

2.1RU_SMOTE算法

許多學(xué)者綜合考慮了過(guò)采樣與欠采樣的弊端和優(yōu)點(diǎn)，提出兩類采樣方法同時(shí)使用的混合重采樣方法[5]。RU_SMOTE算法[7]是一種使用隨機(jī)欠采樣與SMOTE相結(jié)合的混合重采樣方法。算法思想為：先確定合成樣本的比例γ，利用SMOTE算法增加相應(yīng)比例的正類樣本；然后使用隨機(jī)欠采樣刪除負(fù)類樣本，使數(shù)據(jù)達(dá)到平衡；通過(guò)改變?chǔ)谜{(diào)整合成樣本的數(shù)量和數(shù)據(jù)規(guī)模；最后使用SVM分類。該算法既能去除負(fù)類樣本降低數(shù)據(jù)規(guī)模，又能增添新的樣本信息，緩解由于樣本集失衡而帶來(lái)的分類決策面的偏移。

2.2HB_SMOTE(Hyperplane Based SMOTE)算法

上述混合重采樣方法雖然取得了比單一采樣方法更好的分類效果，但并沒(méi)有克服隨機(jī)欠采樣的盲目性。對(duì)于分類來(lái)說(shuō)位于邊界的樣本為重要樣本[6]，噪聲樣本和距離分類邊界較遠(yuǎn)的樣本則是次要樣本，剔除這些樣本不會(huì)引起太多的信息損失。基于這種思想，本文提出了一種改進(jìn)的混合重采樣算法：首先采用WSVM算法尋找分類邊界，亦即分類超平面；然后按一定標(biāo)準(zhǔn)將被錯(cuò)分的和靠近分類超平面以及遠(yuǎn)離超平面的負(fù)類樣本刪除，再對(duì)正類利用SMOTE方法進(jìn)行過(guò)采樣使正負(fù)類數(shù)據(jù)達(dá)到平衡并且引入新的樣本信息；最后使用SVM建模訓(xùn)練。

算法的具體實(shí)現(xiàn)步驟如下。

(2)確定SMOTE合成新樣本的比率γ。對(duì)正類樣本進(jìn)行相應(yīng)比率的合成過(guò)采樣，組成新的正類樣本集。

(3)對(duì)步驟(1)訓(xùn)練集中的每一個(gè)負(fù)類樣本xi，計(jì)算xi到分類邊界f(x)的距離di，并對(duì)di進(jìn)行排序。

(4)對(duì)于排好序的di，選取n個(gè)最大的dj(j=1,2，…，n)和m個(gè)最小的dj(j=1,2，…，m)，分別從原訓(xùn)練集中刪除與dj對(duì)應(yīng)的這些n+m個(gè)點(diǎn)。將剩下的負(fù)類樣本與步驟(2)中新正類樣本一起作為新的訓(xùn)練集。

(5)對(duì)新的訓(xùn)練集使用SVM算法進(jìn)行分類。

(6)可以選取不同γ、n和m重復(fù)步驟(4)以獲取合適的新負(fù)類樣本集。其中n和m決定于γ的變化。

3實(shí)驗(yàn)分析

3.1評(píng)價(jià)標(biāo)準(zhǔn)

許多傳統(tǒng)的分類學(xué)習(xí)算法主要采用準(zhǔn)確率(正確分類的樣本數(shù)目占所有樣本總數(shù)目的比率)作為分類學(xué)習(xí)的評(píng)價(jià)指標(biāo)，它所對(duì)應(yīng)的混淆矩陣[8]見(jiàn)表1。

表1　混淆矩陣

對(duì)于非平衡數(shù)據(jù)集而言，用準(zhǔn)確率來(lái)評(píng)價(jià)分類器的性能是不合理的。因?yàn)楹芏嗲闆r下雖然總的分類精度很高，但實(shí)際上正類的分類精度卻可能很低。如果正類樣本數(shù)占總樣本數(shù)的1%，即使正類樣本全部分錯(cuò)，分類精度還是會(huì)達(dá)到99%。但這卻是無(wú)意義的。因此需要采用新的評(píng)價(jià)方法。定義如下指標(biāo)：

Acc+=TP/(TP+FN)

Acc-=TN/(FP+TN)

Precision=TP/(FP+TP)

Recall=TP/(TP+FN)

本文中，使用G_mean和F_measure作為評(píng)價(jià)準(zhǔn)則:

G_mean性能指標(biāo)同時(shí)兼顧了正負(fù)類樣本的分類性能，只有二者的值都大時(shí)，G_mean才會(huì)大，因此G_mean主要是代表了非平衡數(shù)據(jù)集的總體的分類性能。性能指標(biāo)F_measure則綜合考慮正類樣本的查全率和查準(zhǔn)率，只有二者的值都大時(shí)，F(xiàn)_measure才會(huì)大，所以它主要是度量分類器對(duì)正類的分類效果。

3.2實(shí)驗(yàn)

本文所采用的實(shí)驗(yàn)數(shù)據(jù)都來(lái)自于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)，分別為Glass數(shù)據(jù)集、Vowel數(shù)據(jù)集和Segment數(shù)據(jù)集。由于這3個(gè)數(shù)據(jù)集都是多類數(shù)據(jù)集，為簡(jiǎn)化起見(jiàn)，先將數(shù)據(jù)集都變?yōu)槎惙诸悊?wèn)題。對(duì)Glass數(shù)據(jù)集選取類標(biāo)為“7”的數(shù)據(jù)作為正類，將其余的類合并作為負(fù)類。而對(duì)Vowel和Segment數(shù)據(jù)集分別選取類標(biāo)為“hed”和“brickface”的數(shù)據(jù)作為正類。這3個(gè)數(shù)據(jù)集的詳細(xì)描述詳見(jiàn)表2。

表2　數(shù)據(jù)集描述

實(shí)驗(yàn)設(shè)計(jì)如下：使用MATLAB作為仿真環(huán)境并使用LIBSVM工具箱作為實(shí)現(xiàn)工具。本文采用10折交叉驗(yàn)證的方法對(duì)數(shù)據(jù)集進(jìn)行驗(yàn)證，在實(shí)驗(yàn)中將本文的HB_SMOTE與SMOTE、隨機(jī)欠采樣、RU_SMOTE方法作對(duì)比，通過(guò)改變SMOTE新樣本的比率得到不同比率下的分類結(jié)果，如表3～表6所示。

表3　Glass的分類情況

表4　Vowel的分類情況

表5　Segment的分類情況

表6　4種分類方法在3組數(shù)據(jù)集上的G_mean值對(duì)比

由表3～表5可以看出，SMOTE算法性能優(yōu)于隨機(jī)欠采樣，主要因?yàn)殡S機(jī)欠采樣算法隨機(jī)刪除樣本的同時(shí)也將有用信息刪除。而RU_SMOTE算法要優(yōu)于SMOTE算法和隨機(jī)欠采樣算法，主要因?yàn)樽鳛榛旌喜蓸悠渚C合了SMOTE算法和隨機(jī)欠采樣的優(yōu)點(diǎn)。HB_SMOTE算法的G_mean和Acc-比其他3種算法高，表明其總體效果要優(yōu)于其他3種算法，這是因?yàn)樵撍惴ㄌ蕹素?fù)類樣本集中的噪聲樣本和無(wú)用樣本，從而增加了有效樣本的比率。結(jié)合表3～表5可以看出，SMOTE合成新樣本的比率不同，優(yōu)化結(jié)果也不盡相同，通過(guò)改變SMOTE合成新樣本的比率可以尋求更優(yōu)的結(jié)果。由表6可以看出HB_SMOTE的值要優(yōu)于其他3種方法，這表明該分類器在一定程度上能夠提升正類的分類效果。

4結(jié)論

SVM在解決小樣本、非線性分類問(wèn)題上具有顯明的優(yōu)勢(shì)，更重要的是其具有良好的泛化能力。但是在現(xiàn)實(shí)生活中廣泛存在著非平衡數(shù)據(jù)分類的問(wèn)題，傳統(tǒng)的SVM算法對(duì)于少數(shù)類樣本的識(shí)別準(zhǔn)確率較低。本文基于SMOTE過(guò)采樣技術(shù)提出了一種改進(jìn)的混合重采樣方法(HB_SMOTE)：首先通過(guò)WSVM找到分類超平面，據(jù)此刪除那些負(fù)類樣本集中越界和靠近超平面的樣本以及那些遠(yuǎn)離超平面的樣本，從而減少負(fù)類樣本集中的噪聲點(diǎn)和無(wú)效點(diǎn)。而通過(guò)SMOTE算法所合成的正類樣本點(diǎn)則能夠增加少數(shù)類樣本集的信息量和密度。在UCI數(shù)據(jù)集上對(duì)比4種算法的實(shí)驗(yàn)結(jié)果表明，HB_SMOTE算法性能明顯優(yōu)于其他3種算法，表明該分類器在相對(duì)較少的增加運(yùn)算規(guī)模的基礎(chǔ)上能夠提升少數(shù)類的分類精度。

[1] VAPNIK V N.The nature of statistical learning theory[M].New York:Springer，2000.

[2] 鄭文昌，陳淑燕，王宣強(qiáng).面向不平衡數(shù)據(jù)集的SMOTE-SVM交通事件檢測(cè)算法[J].武漢理工大學(xué)學(xué)報(bào)，2012，34(11):58-62.

[3] 王和勇，樊泓坤，姚正安.SMOTE和Biased-SVM相結(jié)合的不平衡數(shù)據(jù)分類方法[J].計(jì)算機(jī)科學(xué)，2008，35(5):174-176.

[4] 徐麗麗，閆德勤，高晴.基于聚類欠采樣的極端學(xué)習(xí)機(jī)[J].微型機(jī)與應(yīng)用，2015，34(17):81-84.

[5] 歐陽(yáng)源遊.基于混合采樣的非平衡數(shù)據(jù)集分類研究[D].重慶：重慶大學(xué)，2014.

[6] 陶新民，郝思媛，張冬雪，等.基于樣本特性欠取樣的不均衡支持向量機(jī)[J].控制與決策，2013，28(7):978-984.

[7] 林宇，黃迅，徐凱.基于RU_SMOTE_SVM的金融市場(chǎng)極端風(fēng)險(xiǎn)預(yù)警研究[J].預(yù)測(cè)，2013，32(4):15-20.

[8] 林智勇，郝志峰，楊曉偉.若干評(píng)價(jià)準(zhǔn)則對(duì)不平衡數(shù)據(jù)學(xué)習(xí)的影響[J].華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版)，2010，38(4):147-155.

中圖分類號(hào)：TP3

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.19358/j.issn.1674- 7720.2016.12.017

(收稿日期：2016-01-27)

作者簡(jiǎn)介：

郭亞偉(1992-)，女，碩士，主要研究方向：信息處理與模式識(shí)別。

白治江(1962-)，男，博士，副教授，主要研究方向：模式識(shí)別、人工智能。

SVM training with imbalanced dataset based on mixed resampling

Guo Yawei，Bai Zhijiang

(College of Information Engineering Shanghai Maritime University, Shanghai 201306, China)

Abstract:The classification result of classical SVM algorithm in the case of unbalanced data set is unsatisfactory. Therefore, a class hyperplane based SMOTE methods (HB_SMOTE) is presented. The new method firstly finds the class hyperplane by using WSVM on the original imbalanced dataset, then according to a specific criterion, the negative class is discarded into the misclassified samples, the samples close to hyperplane and the samples far away to the hyperplane. Finally the experiment results on the UCI dataset show the new method performs in higher accuracy, compared to the RU_SMOTE and other similar algorithms.

Key words:imbalanced data sets；synthetic minority over-sampling technique；hyperplane；support vector machine；mixed resampling