用于不平衡數(shù)據(jù)分類的模糊支持向量機(jī)算法

鞠 　 哲，　曹 雋 喆，　顧 　 宏

( 大連理工大學(xué) 控制科學(xué)與工程學(xué)院， 遼寧 大連　116024 )

?

用于不平衡數(shù)據(jù)分類的模糊支持向量機(jī)算法

鞠 哲，曹 雋 喆，顧 宏*

( 大連理工大學(xué) 控制科學(xué)與工程學(xué)院， 遼寧 大連116024 )

作為一種有效的機(jī)器學(xué)習(xí)技術(shù)，支持向量機(jī)已經(jīng)被成功地應(yīng)用于各個(gè)領(lǐng)域．然而當(dāng)數(shù)據(jù)不平衡時(shí)，支持向量機(jī)會(huì)產(chǎn)生次優(yōu)的分類模型；另一方面，支持向量機(jī)算法對(duì)數(shù)據(jù)集中的噪聲點(diǎn)和野點(diǎn)非常敏感．為了克服以上不足，提出了一種新的用于不平衡數(shù)據(jù)分類的模糊支持向量機(jī)算法．該算法在設(shè)計(jì)樣本的模糊隸屬度函數(shù)時(shí)，不僅考慮訓(xùn)練樣本到其類中心距離，而且考慮樣本周圍的緊密度．實(shí)驗(yàn)結(jié)果表明，所提模糊支持向量機(jī)算法可以有效地處理不平衡和噪聲問題．

支持向量機(jī)；模糊支持向量機(jī)；模糊隸屬度；不平衡數(shù)據(jù)；分類

0　引　言

支持向量機(jī)(support vector machine，SVM)是建立在統(tǒng)計(jì)學(xué)習(xí)中的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則基礎(chǔ)上的一種機(jī)器學(xué)習(xí)方法，能有效地處理小樣本、高維數(shù)據(jù)、非線性等問題．作為一種常用的機(jī)器學(xué)習(xí)技術(shù)，SVM[1-2]已經(jīng)被成功地應(yīng)用到各種實(shí)際分類問題中．然而，真實(shí)的數(shù)據(jù)集常常含有噪聲或野點(diǎn)．傳統(tǒng)的SVM算法等同地對(duì)待所有訓(xùn)練樣本并賦予它們統(tǒng)一的權(quán)值，因此SVM算法對(duì)訓(xùn)練樣本中噪聲和野點(diǎn)非常敏感[3]．為了克服噪聲數(shù)據(jù)對(duì)SVM分類結(jié)果的影響，Lin等[4]首次提出了模糊支持向量機(jī)(FSVM) 算法．在FSVM算法中，訓(xùn)練集中不同的訓(xùn)練樣本被賦予不同的模糊隸屬度(即權(quán)值)來衡量樣本對(duì)分類器的重要程度．Lin等[4]認(rèn)為如果一個(gè)樣本離其類中心越近，那么它就越有可能屬于該類，需分配給該樣本一個(gè)較高的模糊隸屬度；相反，如果這個(gè)樣本遠(yuǎn)離其類中心，那么它就越有可能是噪聲或野點(diǎn)，需分配給該樣本一個(gè)較小的模糊隸屬度．FSVM算法是對(duì)傳統(tǒng)SVM算法的一種改進(jìn)，在一定程度上降低了SVM算法對(duì)噪聲或野點(diǎn)的敏感度．然而，F(xiàn)SVM算法在設(shè)計(jì)模糊隸屬度時(shí)只考慮了樣本到其類中心的距離作為衡量樣本的重要性指標(biāo)．對(duì)于不規(guī)則分布的數(shù)據(jù)集，這種方法可能會(huì)將噪聲樣本當(dāng)作正常樣本進(jìn)行訓(xùn)練，因而影響了算法的精度．隨后，一些改進(jìn)的FSVM算法被相繼提出，如文獻(xiàn)[5]利用核方法將FSVM算法在核空間中實(shí)現(xiàn)；文獻(xiàn)[6]提出了一種基于樣本間緊密度的FSVM算法；文獻(xiàn)[7]提出了一種利用樣本到其類內(nèi)超平面來設(shè)計(jì)模糊隸屬度的FSVM 算法；文獻(xiàn)[8]提出了一種基于類向心度的改進(jìn)FSVM算法，算法在設(shè)計(jì)模糊隸屬度時(shí)不僅考慮到樣本到類中心的距離，而且考慮到樣本之間的內(nèi)在聯(lián)系．

此外，盡管SVM算法在平衡數(shù)據(jù)集上具有良好的性能表現(xiàn)，但當(dāng)數(shù)據(jù)不平衡時(shí)SVM算法的分類效果不佳．SVM算法偏向于保證多數(shù)類的分類精度，而在少數(shù)類上分類效果往往較差．目前，許多算法被用來處理基于不平衡數(shù)據(jù)的分類問題，以便提高SVM算法在不平衡數(shù)據(jù)集上的分類性能．從數(shù)據(jù)層面，將SVM算法和欠采樣或過采樣技術(shù)相結(jié)合來平衡正負(fù)類的樣本比例[9]．但采樣方法實(shí)際上通過增加少數(shù)類樣本或減少多數(shù)類樣本來調(diào)整數(shù)據(jù)集的不平衡性，具有一定的盲目性，結(jié)果的穩(wěn)定性難以得到保證，而且不適用于不平衡比例較大的數(shù)據(jù)集．從算法層面，對(duì)SVM算法本身進(jìn)行改進(jìn)來處理不平衡數(shù)據(jù)分類．如文獻(xiàn)[10]提出了一種基于實(shí)例重要性的不平衡SVM分類算法．算法首先將數(shù)據(jù)按其重要性排序，選擇最重要的數(shù)據(jù)訓(xùn)練初始分類器，然后算法循環(huán)迭代．該算法在數(shù)據(jù)樣本太大或太小時(shí)效果較差．文獻(xiàn)[11]通過賦予正負(fù)類樣本不同的懲罰因子(different error costs，DEC)來降低不平衡數(shù)據(jù)給SVM算法帶來的影響．一個(gè)簡單有效的處理方法是將懲罰因子直接設(shè)置為正負(fù)類數(shù)據(jù)的不平衡比率[12]．文獻(xiàn)[13]提出了一種改進(jìn)近似支持向量機(jī)算法，該算法不僅賦予正負(fù)類樣本以不同的懲罰因子，且在約束條件中增加新的參數(shù)，使分類面更具靈活性，提高了算法精度．

1　SVM簡介

對(duì)于二分類問題，SVM的基本思想就是在樣本(核)空間尋找一個(gè)最優(yōu)超平面，使得兩類樣本的分類間隔達(dá)到最大．給定訓(xùn)練集(X，T)={(xi，ti)，i=1，2，…，l}，其中xi為樣本，ti為樣本xi的標(biāo)簽，ti∈{-1，1}；引入非線性映射Φ(x)，將訓(xùn)練集映入高維空間(Φ(X)，T)={(Φ(xi)，ti)，i=1，2，…，l}；選取適當(dāng)?shù)暮撕瘮?shù)K(x，y)=Φ(x)TΦ(y)；引入松弛變量ξi≥0，i=1， 2， …，l．標(biāo)準(zhǔn)支持向量機(jī)的一般形式可以表示為

s.t.ti(ωTΦ(xi)+b)≥1-ξi

ξi≥0，i=1，2，…，l

(1)

求解優(yōu)化問題(1)的對(duì)偶問題：

0≤αi≤C， i=1，2，…，l

(2)

2　用于不平衡數(shù)據(jù)分類的FSVM算法

傳統(tǒng)的SVM算法認(rèn)為，每一個(gè)樣本的重要性是相同的，算法分配給每一個(gè)樣本相同的權(quán)值．在實(shí)際應(yīng)用中，數(shù)據(jù)往往是不平衡的，而且包含噪聲．因此，一個(gè)合理的做法是根據(jù)樣本不平衡性和樣本重要性來分配不同的權(quán)值．對(duì)于二分類問題，給定訓(xùn)練集(X，T)={(xi，ti)，i=1，2，…，l}，其中xi為樣本，ti為樣本xi的標(biāo)簽，ti∈{-1，1}．不失一般性，假設(shè)前p個(gè)樣本是正類樣本(即ti=1，i=1，2，…，p)，剩下后l-p個(gè)樣本是負(fù)類樣本(即ti=-1，i=p+1，p+2，…，l)．不平衡FSVM的一般形式可以表示為

s.t.ti(ωTΦ(xi)+b)≥1-ξi

ξi≥0，i=1，2，…，l

(3)

2.1模糊隸屬度設(shè)計(jì)

在文獻(xiàn)[4]中模糊隸屬度被定義為

(4)

(5)

圖1　帶有一個(gè)噪聲點(diǎn)的橢圓分布數(shù)據(jù)示意圖

基于上述觀察，本文除了考慮樣本到類中心的距離，還將樣本周圍的緊密度作為設(shè)計(jì)模糊隸屬度的依據(jù)．一個(gè)簡單的K-近鄰準(zhǔn)則用來衡量樣本的緊密度．如圖1所示，噪聲點(diǎn)x5到其3-近鄰{x6，x7，x8}的平均距離要遠(yuǎn)遠(yuǎn)大于正常樣本點(diǎn)x1到其3-近鄰{x2，x3，x4}的平均距離．因此，對(duì)于一個(gè)正樣本xi，它周圍的緊密度可以定義為

(6)

(7)

i=1，2，…，p

(8)

i=p+1，p+2，…，l

(9)

其中α∈[0，1]，m>0，δ是一個(gè)很小的正數(shù)來保證分母大于0．在本文中，δ取值為0.000 1，α的選擇范圍是{0，0.1，…，1.0}，m的選擇范圍是{0.1，0.2，…，1.0}．此外，為了節(jié)省算法的訓(xùn)練時(shí)間，本文模糊隸屬度中K統(tǒng)一設(shè)置為10．

2.2懲罰因子設(shè)置

一般來說，DEC算法[11]通過賦給少數(shù)類以較大的權(quán)值、多數(shù)類以較小的權(quán)值，可以有效地減小不平衡性對(duì)SVM算法的影響．然而DEC算法中，沒有根據(jù)樣本的重要性對(duì)類內(nèi)樣本加以區(qū)分，使得DEC算法很容易受到噪聲或野點(diǎn)的影響．而本文將模糊隸屬度和懲罰因子結(jié)合起來，不僅可以較好地處理不平衡數(shù)據(jù)分類問題，而且可以克服噪聲數(shù)據(jù)對(duì)SVM分類結(jié)果的影響．根據(jù)文獻(xiàn)[11-12]的結(jié)果，當(dāng)C+/C-設(shè)置為多數(shù)類與少數(shù)類樣本個(gè)數(shù)的比值時(shí)，SVM算法可以得到較好的分類結(jié)果．本文中懲罰因子C+設(shè)置為C(l-p)/p，C-設(shè)置為C(C> 0)．

3　實(shí)驗(yàn)與結(jié)果分析

表1　UCI數(shù)據(jù)集及其相關(guān)屬性

采用3個(gè)常用的分類器性能評(píng)價(jià)指標(biāo)用來評(píng)價(jià)算法的表現(xiàn)，分別是敏感性Sn、特異性Sp和幾何平均值Gm，定義如下：

(10)

(11)

(12)

其中Tp、Tn、Fp和Fn分別表示真陽性樣本個(gè)數(shù)、真陰性樣本個(gè)數(shù)、假陽性樣本個(gè)數(shù)和假陰性樣本個(gè)數(shù)．Sn和Sp分別反映了分類器正確預(yù)測正負(fù)類樣本的比率，顯然Sn和Sp的值越大表明分類器性能越好．然而Sn和Sp相互制約，尤其當(dāng)數(shù)據(jù)不平衡時(shí)，很難同時(shí)用這兩個(gè)指標(biāo)反映分類器的性能．于是引入它們的幾何平均值Gm來反映分類器在不均衡數(shù)據(jù)上的性能．Gm的值越大，表明分類器的綜合性能越好．

表2　8個(gè)UCI數(shù)據(jù)集上的分類結(jié)果比較

表3　各種算法在8個(gè)UCI數(shù)據(jù)集上的最優(yōu)參數(shù)

4　結(jié)　語

本文提出了一種新的用于不平衡數(shù)據(jù)的FSVM 算法．該算法不僅可以有效地降低不平衡數(shù)據(jù)對(duì)SVM造成的影響，而且可以降低數(shù)據(jù)中噪聲和野點(diǎn)的干擾，進(jìn)而提高分類器精度．UCI數(shù)據(jù)集上的數(shù)值實(shí)驗(yàn)驗(yàn)證了該分類方法的有效性．然而需要指出的是，該算法在提升分類精度的同時(shí)，需要優(yōu)化的參數(shù)也隨之增多．下一步的研究工作是設(shè)計(jì)有效的參數(shù)選擇策略來縮短算法的訓(xùn)練時(shí)間．

[1]Vapnik V N. The Nature of Statistical Learning Theory [M]. New York:Springer, 1995.

[2]Cristianini N, Shawe-Taylor J. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods [M]. Cambridge:Cambridge University Press, 2000.

[3]ZHANG Xue-gong. Using class-center vectors to build support vector machines [C] // Proceedings of the 1999 IEEE Signal Processing Society Workshop. Madison:IEEE, 1999:3-11.

[4]LIN Chun-fu, WANG Sheng-de. Fuzzy support vector machines [J]. IEEE Transactions on Neural Networks, 2002, 13(2):464-471.

[5]JIANG Xiu-feng, YI Zhang, LV Jian-cheng. Fuzzy SVM with a new fuzzy membership function [J]. Neural Computing & Applications, 2006, 15(3):268-276.

[6]張 翔,肖小玲,徐光祐. 基于樣本之間緊密度的模糊支持向量機(jī)方法[J]. 軟件學(xué)報(bào), 2006, 17(5):951-958.

ZHANG Xiang, XIAO Xiao-ling, XU Guang-you. Fuzzy support vector machine based on affinity among samples [J]. Journal of Software, 2006, 17(5):951-958. (in Chinese)

[7]杜 喆,劉三陽,齊小剛. 一種新隸屬度函數(shù)的模糊支持向量機(jī)[J]. 系統(tǒng)仿真學(xué)報(bào), 2009, 21(7):1901-1903.

DU Zhe, LIU San-yang, QI Xiao-gang. Fuzzy support vector machine with new membership function [J]. Journal of System Simulation, 2009, 21(7):1901-1903. (in Chinese)

[8]許翠云,業(yè) 寧. 基于類向心度的模糊支持向量機(jī)[J]. 計(jì)算機(jī)工程與科學(xué), 2014, 36(8):1623-1628.

XU Cui-yun, YE Ning. A novel fuzzy support vector machine based on the class centripetal degree [J]. Computer Engineering and Science, 2014, 36(8):1623-1628. (in Chinese)

[9]Estabrooks A, Jo T, Japkowicz N. A multiple resampling method for learning from imbalanced data sets [J]. Computational Intelligence, 2004, 20(1):18-36.

[10]楊 揚(yáng),李善平. 基于實(shí)例重要性的SVM解不平衡數(shù)據(jù)分類[J]. 模式識(shí)別與人工智能, 2009, 22(6):913-918.

YANG Yang, LI Shan-ping. Instance importance based SVM for solving imbalanced data classification [J]. Pattern Recognition and Artificial Intelligence, 2009, 22(6):913-918. (in Chinese)

[11]Veropoulos K, Campbell C, Cristianini N. Controlling the sensitivity of support vector machines [C] // International Joint Conference on AI. Stockholm:IJCAI Press, 1999:55-60.

[12]Batuwita R, Palade V. Class imbalance learning methods for support vector machines [M] // HE Hai-bo, MA Yun-qian, eds. Imbalanced Learning:Foundations, Algorithms, and Applications. Hoboken:Wiley-IEEE Press, 2013:83-99.

[13]劉 艷,鐘 萍,陳 靜,等. 用于處理不平衡樣本的改進(jìn)近似支持向量機(jī)新算法[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(6):1618-1621.

LIU Yan, ZHONG Ping, CHEN Jing,etal. Modified proximal support vector machine algorithm for dealing with unbalanced samples [J]. Journal of Computer Applications, 2014, 34(6):1618-1621. (in Chinese)

[14]Batuwita R, Palade V. FSVM-CIL:Fuzzy support vector machines for class imbalance learning [J]. IEEE Transactions on Fuzzy Systems, 2010, 18(3):558-571.

[15]Chang C C, Lin C J. LIBSVM:A library for support vector machines [J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3):27.

A fuzzy support vector machine algorithm for imbalanced data classification

JUZhe,CAOJun-zhe,GUHong*

( School of Control Science and Engineering, Dalian University of Technology, Dalian 116024, China )

As an effective machine learning technique, support vector machine (SVM) has been successfully applied to various fields. However, when it comes to imbalanced datasets, SVM produces suboptimal classification models. On the other hand, the SVM algorithm is very sensitive to noise and outliers present in the datasets. To overcome the disadvantages of imbalanced and noisy training datasets, a novel fuzzy SVM algorithm for imbalanced data classification is proposed. When designing the fuzzy membership function, the proposed algorithm takes into account not only the distance between the training sample and its class center, but also the tightness around the training sample. Experimental results show that the proposed fuzzy SVM algorithm can effectively handle the imbalanced and noisy problem.

support vector machine (SVM); fuzzy support vector machine; fuzzy membership; imbalanced data; classification

1000-8608(2016)05-0525-07

2016-03-30；

2016-04-11．

國家自然科學(xué)基金資助項(xiàng)目(61502074,U1560102)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20120041110008).

鞠 哲(1986-)，男，博士生，E-mail:juzhe1120@hotmail.com；顧 宏*(1961-)，男，教授，博士生導(dǎo)師，E-mail:guhong@dlut.edu.cn.

TP181

A

10.7511/dllgxb201605013