用于不平衡數據分類的模糊支持向量機算法

鞠 　 哲，　曹 雋 喆，　顧 　 宏

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

?

用于不平衡數據分類的模糊支持向量機算法

鞠 哲，曹 雋 喆，顧 宏*

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

作為一種有效的機器學習技術，支持向量機已經被成功地應用于各個領域．然而當數據不平衡時，支持向量機會產生次優的分類模型；另一方面，支持向量機算法對數據集中的噪聲點和野點非常敏感．為了克服以上不足，提出了一種新的用于不平衡數據分類的模糊支持向量機算法．該算法在設計樣本的模糊隸屬度函數時，不僅考慮訓練樣本到其類中心距離，而且考慮樣本周圍的緊密度．實驗結果表明，所提模糊支持向量機算法可以有效地處理不平衡和噪聲問題．

支持向量機；模糊支持向量機；模糊隸屬度；不平衡數據；分類

0　引　言

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

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

1　SVM簡介

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

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

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

(1)

求解優化問題(1)的對偶問題：

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

(2)

2　用于不平衡數據分類的FSVM算法

傳統的SVM算法認為，每一個樣本的重要性是相同的，算法分配給每一個樣本相同的權值．在實際應用中，數據往往是不平衡的，而且包含噪聲．因此，一個合理的做法是根據樣本不平衡性和樣本重要性來分配不同的權值．對于二分類問題，給定訓練集(X，T)={(xi，ti)，i=1，2，…，l}，其中xi為樣本，ti為樣本xi的標簽，ti∈{-1，1}．不失一般性，假設前p個樣本是正類樣本(即ti=1，i=1，2，…，p)，剩下后l-p個樣本是負類樣本(即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模糊隸屬度設計

在文獻[4]中模糊隸屬度被定義為

(4)

(5)

圖1　帶有一個噪聲點的橢圓分布數據示意圖

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

(6)

(7)

i=1，2，…，p

(8)

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

(9)

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

2.2懲罰因子設置

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

3　實驗與結果分析

表1　UCI數據集及其相關屬性

采用3個常用的分類器性能評價指標用來評價算法的表現，分別是敏感性Sn、特異性Sp和幾何平均值Gm，定義如下：

(10)

(11)

(12)

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

表2　8個UCI數據集上的分類結果比較

表3　各種算法在8個UCI數據集上的最優參數

4　結　語

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

[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]. 軟件學報, 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]杜 喆,劉三陽,齊小剛. 一種新隸屬度函數的模糊支持向量機[J]. 系統仿真學報, 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]許翠云,業 寧. 基于類向心度的模糊支持向量機[J]. 計算機工程與科學, 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]楊 揚,李善平. 基于實例重要性的SVM解不平衡數據分類[J]. 模式識別與人工智能, 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]. 計算機應用, 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．

國家自然科學基金資助項目(61502074,U1560102)；高等學校博士學科點專項科研基金資助項目(20120041110008).

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

TP181

A

10.7511/dllgxb201605013