李秋林

(西南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院，重慶 400715)

經(jīng)典的支持向量機(SVM)［1］通過構(gòu)造最優(yōu)超平面來分隔兩類樣本，由于其簡單和良好的泛化能力使得其在眾多領(lǐng)域得到廣泛應(yīng)用［2－8］。Tax和 Duin［9－10］受支持向量機的啟發(fā)，提出了超球體支持向量機(HSSVM)，用于支持向量數(shù)據(jù)描述分類，其主要思想是建立包含樣本的最小超球體。HSSVM已廣泛應(yīng)用于人臉識別、預(yù)警技術(shù)、故障檢測等方面。在此基礎(chǔ)上，有學(xué)者相繼提出了最大間隔最小體積球形支持向量機［11］、不等距超球體支持向量機［12］、最大邊界模糊核超球分類方法［13］等。

非平衡數(shù)據(jù)集是指數(shù)據(jù)集中某些類的樣本數(shù)量比其他類的樣本數(shù)量大很多，其中樣本少的類為少數(shù)類(稱為正類)，樣本多的類為多數(shù)類(稱為負類)。非平衡數(shù)據(jù)集普遍存在于機器學(xué)習(xí)的許多實際應(yīng)用領(lǐng)域中。利用傳統(tǒng)的機器學(xué)習(xí)方法分類，對于正類來說分類精度很低，而對于負類則相對較高。若少數(shù)類別的數(shù)據(jù)有很大的分類代價，少數(shù)類樣本被錯誤分類所帶來的危害要比多數(shù)類樣本被錯誤分類大得多。如何有效地提高分類器對非平衡數(shù)據(jù)集的分類性能是目前機器學(xué)習(xí)和模式識別領(lǐng)域的一個熱點研究問題。本文通過直接采用最大化間隔，并引入?yún)?shù)ν來建立一種新的模型，稱之為ν－最大間隔超球體支持向量機(ν－MMHSSVM)，即構(gòu)造2個同心超球，并使其間隔最大，小超球?qū)⒄惏渲校蟪驅(qū)⒇擃悩颖九懦谕?。實驗仿真結(jié)果表明，該算法對非平衡數(shù)據(jù)集的分類效果明顯好于傳統(tǒng)的算法。

1 超球體支持向量機

對于超球體支持向量機(HSSVM)，以a為中心、R為半徑的圓可以包含所有的樣本點，并且要求這個圓盡可能地小。不失一般性，超球體算法為了解決非線性問題，通過核函數(shù)把訓(xùn)練樣本映射到高維特征空間。設(shè)初始訓(xùn)練樣本集合X={xi|xi∈RN，i=1，…，l}，則原始優(yōu)化問題為:

其中 K(xi，xj)=(Φ(xi)，Φ(xj))。通過求解對偶問題(2)，最終可以得到判決函數(shù)為

其中x為支持向量。

2 ν－最大間隔超球體支持向量機

2.1 ν－最大間隔超球體支持向量機

HSSVM是通過構(gòu)造最小超球半徑為目標(biāo)進行分類，因此，在處理非平衡數(shù)據(jù)集時容易降低正類分類準(zhǔn)確率，從而導(dǎo)致其泛化能力有限，所以，本文以最大化間隔、最小化超球半徑為目標(biāo)來建立一種新的超球體SVM算法，并引入?yún)?shù)ν，用于調(diào)節(jié)間隔和超球半徑，得到ν－最大間隔超球體支持向量機(ν－MMHSSVM)。如圖1所示，記“+”正類樣本為，記“－”負類樣本為，正負類間間隔為ρ，得到2個同心超球S1和S2，其中:S1半徑為R;S2半徑為R+ρ。

圖1 ν－最大間隔超球體支持向量機

建立的數(shù)學(xué)優(yōu)化模型為:

下面求解原始問題(4)的對偶問題，其Lagrange函數(shù)為:

其中α≥0，β≥0，為 Lagrange乘子向量。由 KKT條件可得:

通過求解式(12)，得到最優(yōu)解α，代入式(8)可得超球球心。

由KKT條件得:

引入核函數(shù)，令 K(xi·xj)=(φ(xi)·φ(xj))，其間隔為ρ=‖φ()－a‖－‖φ()－a‖，并記，則原問題的判決規(guī)則為:對于測試樣本 x，若‖x －a‖≤R1，記

則判定其為正類，反之判定其為負類。決策函數(shù)為

2.2 算法復(fù)雜度分析

算法復(fù)雜度由規(guī)劃中變量和約束方程的個數(shù)決定。SVM、HSSVM、ν－MMHSSVM求解的都是凸二次規(guī)劃問題。用Q(d，s)表示一個凸二次規(guī)劃問題，CQ(d，s)表示對應(yīng)的復(fù)雜度，其中d為變量個數(shù)，s為約束方程的個數(shù)。若訓(xùn)練樣本數(shù)為n，則SVM、HSSVM、ν－MMHSSVM 算法的復(fù)雜度分別表示為 CQ(n，2n+1)、CQ(n，2n+1)、CQ(n，2n+2)。SVM在時間和空間上的復(fù)雜度為O(n2)［14］，即

令式(14)中的n取值n+1，則有

顯然式(16)成立。

由式(14)～(16)可得 CQ(n，2n+2)=O(n2)，故各個算法復(fù)雜度同級。

3 實驗仿真

3.1 人工數(shù)據(jù)集

先通過人造數(shù)據(jù)集來驗證ν-MMHSSVM的有效性。隨機產(chǎn)生容量為100的訓(xùn)練集，其中正類點5個，負類點各95個，這樣就構(gòu)造出了一組人工非平衡數(shù)據(jù)集。用ν-MMHSSVM進行訓(xùn)練，并調(diào)節(jié)參數(shù)ν來調(diào)節(jié)超球分割，分類結(jié)果見圖2、3。

若正負類超球線性可分，從圖2、3可知:參數(shù)ν越小，則包裹正類的超球半徑就越大;參數(shù)ν越大，則包裹正類的超球半徑就越小。故通過調(diào)節(jié)參數(shù)ν，就可以提高正類的分類準(zhǔn)確率。

圖2 ν=0.5時最大間隔超球體支持向量機

圖3 ν=5時最大間隔超球體支持向量機

若正負類超球線性不可分，通過核函數(shù)映射到高維空間超球可分，其參數(shù)ν的變化、超球分割面變化的情況與線性情形下類似，結(jié)果如圖4、5所示。

圖4 ν=0.5，σ=0.5時最大間隔超球體支持向量機

圖5 ν=5，σ=0.5時最大間隔超球體支持向量機

從上面的模擬可知，隨著參數(shù)ν的變化，ν－MMHSSVM對線性和非線性情況都進行了正確分類。

3.2 真實數(shù)據(jù)集

從UCI公共數(shù)據(jù)庫中選取了5組數(shù)據(jù)集進行了實驗。表1中列出了本次實驗所用的數(shù)據(jù)。為了方便，這里的實驗數(shù)據(jù)都是正樣本數(shù)相對于負樣本數(shù)極其稀少的情況。表1中對正負類的情況進行了標(biāo)號，并給出了正負類各占整個數(shù)據(jù)集的比例情況，然后通過徑向基核函數(shù)映射后，并采用HSSVM、MMHSSVM進行訓(xùn)練，最后給出訓(xùn)練對比的結(jié)果。

表1 實驗中使用的數(shù)據(jù)集

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

類準(zhǔn)確率是評價模型分類器最常用的標(biāo)準(zhǔn)，它可以反映分類器對于數(shù)據(jù)集的整體分類性能。但是，它不能正確評價非均衡數(shù)據(jù)集的分類結(jié)果。例如，100個樣本中，正類樣本數(shù)為5，負類樣本數(shù)為95。如果將所有樣本分為負類樣本，分類的正確度仍為95%，這個評價結(jié)果顯然是不合理的，若此時正類分類代價較高，誤判帶來結(jié)果就比較嚴(yán)重。因此，對于非均衡數(shù)據(jù)集分類需要一個合理的評價標(biāo)準(zhǔn)。

對于本次實驗，采用文獻［16］中正負查全率(Recall)和g均值方法來評價實驗結(jié)果:

其中:TP、TN表示正確分類的正類和負類;FN、FP錯誤分類的正類和負類;Recall+、Recall－表示2個類的查全率。

表2是不同算法對各個數(shù)據(jù)集的正負查全率，表3為不同算法對各個數(shù)據(jù)集的g均值及平均值。

表2 不同算法的分類精度

表3 不同數(shù)據(jù)集的g均值及平均值

從表2可以看出，HSSVM有較高的負查全率，且遠高于正查全率，但正查全率較低。而ν－M MHSSVM不但有較高的正查全率，而且還有較高的負查全率。通過表3可以看出，ν－MMHSSVM的各個數(shù)據(jù)集上的g均值均高于HSSVM在各個數(shù)據(jù)集上的g均值，ν－MMHSSVM的g均值平均值也明顯高于HSSVM的g均值平均值。

4 結(jié)束語

基于ν－MMHSSVM的非平衡數(shù)據(jù)分類既能提高正類的聚類性，也能保證正負類類間間隔的距離最大，進而提高了模型分類器的性能，且模型的算法復(fù)雜度與其他算法是同級的。通過上面的實驗仿真可以得出結(jié)論:與傳統(tǒng)的HSSVM算法相比，本文提出的ν－MMHSSVM分類算法大大提高了對正類的查全率，從而有效地提高了對非平衡數(shù)據(jù)集的分類性能。

［1］Vapnik V N.The Nature of Statistical Learning Theory［M］.London，UK:Springer-Verlag，1995.

［2］鄔嘯，魏延，吳瑕.基于混合核函數(shù)的支持向量機［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2011(10):66－70.

［3］余珺，鄭先斌，張小海.基于多核優(yōu)選的裝備費用支持向量機預(yù)測法［J］.四川兵工學(xué)報，2011(6):118－119.

［4］萬輝.一種基于最小二乘支持向量機的圖像增強算法［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，2011(6):53－57.

［5］羅沛清，梁青陽，江欽龍，等.基于分層聚類的支持向量機模擬電路故障診斷［J］.四川兵工學(xué)報，2011(9):92 －95..

［6］崔建國，李明，陳希成.基于支持向量機的飛行器健康診斷方法［J］.壓電與聲光，2009(2):266－269.

［7］張宏蕾，張立亭，羅亦泳，等.基于支持向量機的土地利用預(yù)警研究［J］.安徽農(nóng)業(yè)科學(xué)，2010(35):20503－20504.

［8］唐曉芬，趙秉新.基于支持向量機的農(nóng)村勞動力轉(zhuǎn)移預(yù)測［J］.安徽農(nóng)業(yè)科學(xué)，2011(11):6837－6838.

［9］Tax D，Duin R.Support vector domain description［J］.Pattern Recognition Letters，2003，20:11 －13.

［10］Tax D，Duin R.Support vector domain description［J］.Machine Leaning，2004(1):45 －66.

［11］文傳軍，詹永照，陳長軍.最大間隔最小體積球形支持向量機［J］.控制與決策，2010，25(1):79 －83.

［12］張慧敏，柴毅.不等距超球體支持向量機［J］.計算機工程與應(yīng)用，2011，47(11):19 －22.

［13］王娟，胡文軍，王士同.最大邊界模糊核超球分類方法［J］.計算機應(yīng)用 2011，31(9):2542 －2545.

［14］Collobert R，Bengio S.SVMTorch:Support vector machine for large-scale regression problems［J］.J of Machine Learning Research，2001，1(2):143 － 160.

［15］Frank A.Asuncion A UCI repository of machine learning databases［EB/OL］.［2012 － 06 － 18］.http://archive.ics.uci.edu/ml.

［16］Joshi M V.On Evaluating Performance of Classifiers for Rare Classes［C］//Proc of the 2nd IEEE International Conference on Data Mining.Maebishi，Japan:［s.n.］，2002:641－644.