基于ν－最大間隔超球體支持向量機(jī)的非平衡數(shù)據(jù)分類

李秋林

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

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

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

1 超球體支持向量機(jī)

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

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

其中x為支持向量。

2 ν－最大間隔超球體支持向量機(jī)

2.1 ν－最大間隔超球體支持向量機(jī)

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

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

建立的數(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，記

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

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

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

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

顯然式(16)成立。

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

3 實(shí)驗(yàn)仿真

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

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

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

圖2 ν=0.5時(shí)最大間隔超球體支持向量機(jī)

圖3 ν=5時(shí)最大間隔超球體支持向量機(jī)

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

圖4 ν=0.5，σ=0.5時(shí)最大間隔超球體支持向量機(jī)

圖5 ν=5，σ=0.5時(shí)最大間隔超球體支持向量機(jī)

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

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

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

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

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

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

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

其中:TP、TN表示正確分類的正類和負(fù)類;FN、FP錯(cuò)誤分類的正類和負(fù)類;Recall+、Recall－表示2個(gè)類的查全率。

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

表2 不同算法的分類精度

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

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

4 結(jié)束語

基于ν－MMHSSVM的非平衡數(shù)據(jù)分類既能提高正類的聚類性，也能保證正負(fù)類類間間隔的距離最大，進(jìn)而提高了模型分類器的性能，且模型的算法復(fù)雜度與其他算法是同級(jí)的。通過上面的實(shí)驗(yàn)仿真可以得出結(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ī)［J］.重慶理工大學(xué)學(xué)報(bào):自然科學(xué)版，2011(10):66－70.

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

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

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

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

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

［8］唐曉芬，趙秉新.基于支持向量機(jī)的農(nóng)村勞動(dò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ī)［J］.控制與決策，2010，25(1):79 －83.

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

［13］王娟，胡文軍，王士同.最大邊界模糊核超球分類方法［J］.計(jì)算機(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.