郭亞偉,白治江

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

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

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

0引言

　　支持向量機(SVM)［1］因其能夠有效地避免維數(shù)災(zāi)難，實現(xiàn)全局最優(yōu)，具有嚴謹?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ù)(負)類的分類準(zhǔn)確率，總的分類效果也受到了極大的影響［2］。數(shù)據(jù)重采樣技術(shù)主要是過采樣和欠采樣。過采樣主要包括隨機過采樣、SMOTE［2］算法、BorderlineSMOTE［3］技術(shù)等。這些過采樣方法雖然可以確保原始分類信息的完整性，但是由于新合成的正類樣本不能準(zhǔn)確表達原始樣本集的信息，從而導(dǎo)致過擬合，同時也會增加計算復(fù)雜度。欠采樣主要包括隨機欠采樣、基于聚類欠采樣的極端學(xué)習(xí)機［4］等。單一的欠采樣技術(shù)雖然可以降低計算復(fù)雜度，但是在刪除樣本時通常會導(dǎo)致負類樣本中部分信息缺失，影響分類準(zhǔn)確性。

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

1基本的分類方法

　　1.1SMOTE算法

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

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

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

　?。?)對每一個近鄰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，主要思想是對錯分的正類和負類樣本分別賦予不同的懲罰系數(shù)C+和C-，約束表達式變?yōu)椋?/p>

2混合重采樣方法

　　2.1RU_SMOTE算法

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

　　2.2HB_SMOTE(Hyperplane Based SMOTE)算法

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

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

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

　　（6）可以選取不同γ、n和m重復(fù)步驟（4）以獲取合適的新負類樣本集。其中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。真實負類FPTN對于非平衡數(shù)據(jù)集而言，用準(zhǔn)確率來評價分類器的性能是不合理的。因為很多情況下雖然總的分類精度很高，但實際上正類的分類精度卻可能很低。如果正類樣本數(shù)占總樣本數(shù)的1%，即使正類樣本全部分錯，分類精度還是會達到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)同時兼顧了正負類樣本的分類性能，只有二者的值都大時，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ù)作為正類，將其余的類合并作為負類。而對Vowel和Segment數(shù)據(jù)集分別選取類標(biāo)為“hed”和“brickface”的數(shù)據(jù)作為正類。這3個數(shù)據(jù)集的詳細描述詳見表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種算法，這是因為該算法剔除了負類樣本集中的噪聲樣本和無用樣本，從而增加了有效樣本的比率。結(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ù)此刪除那些負類樣本集中越界和靠近超平面的樣本以及那些遠離超平面的樣本，從而減少負類樣本集中的噪聲點和無效點。而通過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