郭亞偉,白治江

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

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

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

0引言

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

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

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

1基本的分類方法

　　1.1SMOTE算法

　　SMOTE算法［2］是由CHAWLA N V等人提出的一種過采樣方法。該算法步驟如下。

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

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

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

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

　　1.2SVM與WSVM

　　SVM是在統(tǒng)計學(xué)習(xí)理論中結(jié)構(gòu)風(fēng)險最小化原則基礎(chǔ)上提出的機器學(xué)習(xí)方法［1］。其原理是尋找一個最優(yōu)分類超平面，使得該超平面在保證分類精度的同時，能夠使超平面兩側(cè)的空白區(qū)域最大化。此外，它還能通過核函數(shù)將低維空間中的線性不可分問題轉(zhuǎ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)超平面問題轉(zhuǎn)化為求解二次凸規(guī)劃問題，即：

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

2混合重采樣方法

　　2.1RU_SMOTE算法

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

　　2.2HB_SMOTE(Hyperplane Based SMOTE)算法

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

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

　　（1）使用WSVM算法對原始數(shù)據(jù)集進行訓(xùn)練，尋找分類超平面，即:f(x)=∑li=1α*yiK(Xi,X)+b*=0。

　　（2）確定SMOTE合成新樣本的比率γ。對正類樣本進行相應(yīng)比率的合成過采樣，組成新的正類樣本集。

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

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

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

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

3實驗分析

　　3.1評價標(biāo)準(zhǔn)

　　許多傳統(tǒng)的分類學(xué)習(xí)算法主要采用準(zhǔn)確率(正確分類的樣本數(shù)目占所有樣本總數(shù)目的比率)作為分類學(xué)習(xí)的評價指標(biāo)，它所對應(yīng)的混淆矩陣［8］見表1。真實負(fù)類FPTN對于非平衡數(shù)據(jù)集而言，用準(zhǔn)確率來評價分類器的性能是不合理的。因為很多情況下雖然總的分類精度很高，但實際上正類的分類精度卻可能很低。如果正類樣本數(shù)占總樣本數(shù)的1%，即使正類樣本全部分錯，分類精度還是會達(dá)到99%。但這卻是無意義的。因此需要采用新的評價方法。定義如下指標(biāo)：

　　Acc+=TP/(TP+FN)

　　Acc－=TN/(FP+TN)

　　Precision=TP/(FP+TP)

　　Recall=TP/(TP+FN)

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

　　G_mean=Acc+·Acc－

　　F_measure=2×Recall×PrecisionRecall+Precision

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

　　3.2實驗

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

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

　　由表3~表5可以看出，SMOTE算法性能優(yōu)于隨機欠采樣，主要因為隨機欠采樣算法隨機刪除樣本的同時也將有用信息刪除。而RU_SMOTE算法要優(yōu)于SMOTE算法和隨機欠采樣算法，主要因為作為混合采樣其綜合了SMOTE算法和隨機欠采樣的優(yōu)點。HB_SMOTE算法的G_mean和Acc－比其他3種算法高，表明其總體效果要優(yōu)于其他3種算法，這是因為該算法剔除了負(fù)類樣本集中的噪聲樣本和無用樣本，從而增加了有效樣本的比率。結(jié)合表3~表5可以看出，SMOTE合成新樣本的比率不同，優(yōu)化結(jié)果也不盡相同，通過改變SMOTE合成新樣本的比率可以尋求更優(yōu)的結(jié)果。由表6可以看出HB_SMOTE的值要優(yōu)于其他3種方法，這表明該分類器在一定程度上能夠提升正類的分類效果。

4結(jié)論

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

參考文獻

　　［1］ VAPNIK V N.The nature of statistical learning theory［M］.New