任建華　劉曉帥　孟祥福　王　偉

(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院　遼寧 葫蘆島 125105)

?

基于可變隸屬度的模糊雙支持向量機研究

任建華劉曉帥孟祥福王偉

(遼寧工程技術(shù)大學(xué)電子與信息工程學(xué)院遼寧 葫蘆島 125105)

摘要雙支持向量機是一種新的非平行二分類算法。其處理速度比傳統(tǒng)支持向量機快很多，但是雙支持向量機沒有考慮不同輸入樣本點會對最優(yōu)分類超平面產(chǎn)生不同的貢獻(xiàn)。在測試階段測試點到兩類超平面的距離相等時，雙支持向量機也沒有明確給出對這些等距點的處理方法。針對這些情況，提出一種可變隸屬度的模糊雙支持向量機。距離類中心較近的樣本點隸屬度由其到類中心的距離決定，距離類中心較遠(yuǎn)的樣本點隸屬度由其到類中心的距離和它的緊密度共同決定。在測試階段出現(xiàn)等距點時，根據(jù)等距點與各類訓(xùn)練點的等價性比例進(jìn)行分類。實驗結(jié)果表明，與支持向量機、標(biāo)準(zhǔn)雙支持向量機、雙邊界支持向量機、混合模糊雙支持向量機相比，這種可變隸屬度模糊雙支持向量機分類精度最高。

關(guān)鍵詞雙支持向量機支持向量機等距點等價性比例模糊隸屬度分類

RESEARCH ON OPTIONAL MEMBERSHIP-BASED FUZZY TWIN SUPPORT VECTOR MACHINE

Ren JianhuaLiu XiaoshuaiMeng XiangfuWang Wei

(School of Electronics and Information Engineering,Liaoning Technical University,Huludao 125105,Liaoning,China)

AbstractTwin support vector machine is a novel nonparallel binary classification algorithm, and its processing speed is much faster than the traditional support vector machines, but the twin support vector machine does not consider that different input sample points will have different contribution on optimal classification hyperplanes. When the distances between test points and two kinds of hyperplanes are equal in test phase, the twin support vector machine does not explicitly give the treatment approach for these equidistant points. In view of this, this paper proposes an optional membership-based fuzzy twin support vector machine. The membership of sample point closer to the class centre is determined by the distance between the point and the class centre, while the membership of sample point farther to the class centre is jointly determined by the distance of the point to class centre and the affinity of point. During the testing phase, if the equidistant points appear, they can be classified according to the equivalence ratio of equidistant points with various test points. Experimental results show that compared with the support vector machine, standard twin support vector machine, twin-bounder support vector machine and fuzzy twin support vector machine, this optional membership-based fuzzy twin support vector machine has highest classification accuracy.

KeywordsTwin support vector machineSupport vector machineEquidistant pointsEquivalence proportionFuzzy membershipClassification

0引言

支持向量機[1-3]SVM是Vapnik等人提出的一種用于解決二類問題的監(jiān)督學(xué)習(xí)方法。它建立在結(jié)構(gòu)風(fēng)險小化原則基礎(chǔ)之上，具有很強的學(xué)習(xí)能力和泛化能力，所以支持向量機已經(jīng)被廣泛地應(yīng)用于現(xiàn)實的場景中[4,5]。SVM的核心原理是通過解一個二次規(guī)劃問題來得到一對平行的最大間隔超平面，從而將兩類樣本盡可能地分開。近年來一些基于不平行超平面的分類算法被提出，例如，2006年Mangasarian[6]等人提出了廣義特征值近似支持向量機GEPSVM(Proximal Support Vector Machine via generated Eigenvalues)和2007年Jayadeva[7]提出了雙支持向量機[8,9]TWSVM(Tw -in Support Vector Machine)。

對于雙支持向量機，其核心思想是尋找一對非平行的超平面，其中的一個超平面離一類盡可能的近而離另一類盡可能的遠(yuǎn)。雙支持向量機與傳統(tǒng)支持向量機根本的區(qū)別是雙支持向量機解決兩個規(guī)模相對更小的二次規(guī)劃問題。而傳統(tǒng)支持向量機解決一個規(guī)模較大的二次規(guī)劃問題，所以雙支持向量機能將訓(xùn)練時間約減到傳統(tǒng)SVM的1/4[10]。后來不同的學(xué)者對雙支持向量機進(jìn)行了不同的改進(jìn)，例如2011年Shao Y H等人提出了一種有邊界的雙支持向量機，即雙邊界支持向量機TBSVM(Twin Bounded Support Vector Machine)[11]。通過增加規(guī)則化條件，采用結(jié)構(gòu)風(fēng)險最小原則在一定程度上提高了模型的識別率；同年P(guān)eng X J[12]等人提出了一種雙參數(shù)雙支持向量機，在一定程度上解決了樣本分布不平衡問題；2013年丁勝峰[13]等人提出了一種混合模糊雙支持向量機HFTSVM(Hybrid Fuzzy Twin Support Vector Machine)，其隸屬度函數(shù)是距離與緊密度的結(jié)合，在一定程度上減少了野點和噪聲的影響。以上雙支持向量都沒有考慮到測試點到兩個分類超平面的距離相等的現(xiàn)象，所以會出現(xiàn)一些錯分點，影響分類精度。為解決以上不足，進(jìn)一步提高分類精度和分類效率，簡化計算，本文在雙邊界支持向量機和模糊雙支持向量機的基礎(chǔ)上提出一種可變隸屬度模糊雙支持向量機OFTSVM(Optional Fuzzy Twin Support Vector Machine)。該算法根據(jù)樣本點到對應(yīng)類中心距離的不同確定不同類別的隸屬度函數(shù)，距離類中心較近的樣本點隸屬度由其到類中心的距離決定，距離類中心較遠(yuǎn)的樣本點隸屬度由其到類中心的距離和它的緊密度共同決定。由此為不同的樣本點賦予不同的隸屬度，即減少了一定量的計算也減小了噪聲或野點對分類結(jié)果的影響，抑制過學(xué)習(xí)現(xiàn)象的發(fā)生。在測試階段出現(xiàn)等距測試點時，根據(jù)測試點屬性與各類訓(xùn)練點屬性相同的比例(等價性比例)對這些等距測試點分類，減少錯分現(xiàn)象的發(fā)生，提高分類精度。實驗結(jié)果表明，這種可變模糊雙支持向量機在分類時間可行的情況下，分類性能最好。

1雙支持向量機

對于二分類問題，雙支持向量機是一種效率很高的算法。它基于GEPSVM思想，通過求解兩個規(guī)模更小的二次規(guī)劃問題來獲得到一對非平行超平面，使得每一個超平面離一類盡可能的近而離另一類盡可能的近。其訓(xùn)練學(xué)習(xí)的目的就是尋找兩個非平行超平面，并且規(guī)定樣本點只屬于兩類中的一類。

雙支持向量機分線性和非線性兩種情況，但求解原理是一樣的。線性情況比較簡單，本文給出的雙支持向量機都是在非線性情況下的，給定樣本集{xi,yi}，i=1,2,…,l，只能有yi=+1或yi=-1。假設(shè)矩陣A∈Rl1×n表示屬于+1類的樣本點，矩陣B∈Rl2×n表示屬于-1類的樣本點，l1、l2分別為樣本數(shù)目，l1+l2=l，則雙支持向量機的訓(xùn)練學(xué)習(xí)過程轉(zhuǎn)化為優(yōu)化問題：

(1)

(2)

其中e為全為1的列向量，b+、b-為偏移量，c1、c2為對錯分樣本的懲罰因子，ξ+、ξ-為懲罰因子，C=[AB]，K為滿足Mercer條件的核函數(shù)[14]。通過拉格朗日函數(shù)把優(yōu)化問題轉(zhuǎn)化為它的對偶問題：

(3)

(4)

其中S=[K(A,CT)e]，R=[K(B,CT)e]，所以決策函數(shù)為：

(5)

假如輸入一個新的樣本點，就可以根據(jù)這個樣本點到兩個分類超平面的垂直距離來判斷其屬于那一類。如果該樣本點到+1類超平面的垂直距離大于它到-1類超平面的垂直距離，則該樣本點被分到-1類中；如果該樣本點到+1類超平面的垂直距離小于它到-1類超平面的垂直距離，則該樣本點被分到+1類中。

2模糊雙支持向量機

在實際分類中，由于數(shù)據(jù)本身的不確定性(主要是包括噪聲和孤立點)，往往分類精度不高。針對這個問題，有學(xué)者根據(jù)模糊理論提出了模糊隸屬度，再將其引入到支持向量機中，進(jìn)而有了模糊支持向量機。這樣根據(jù)樣本點對分類的影響不同而為其賦予不同的隸屬度，從而抑制噪聲對分類的影響。雙支持向量機同樣可以為每個樣本點賦予不同的隸屬度來提高分類精度，這就是模糊雙支持向量機。

2.1可變模糊隸屬度

自從模糊支持向量機提出以后，隸屬度函數(shù)的設(shè)計方法層出不窮，并且沒有可遵循的規(guī)律。有的學(xué)者基于距離[2],有的基于緊密度[15],但這兩種隸屬度設(shè)計方法都比較單一，對樣本的隸屬度描述不是很準(zhǔn)確。后來又有學(xué)者又提出了基于距離和緊密度的隸屬度設(shè)計方法[13]。但是在此算法中把每個樣本點的緊密度都計算出來，計算量是非常大的，并且在距離類中心較近的樣本點是比較緊密的，所以再計算其緊密度是沒有太大意義。在此提出一種可變模糊隸屬度，距離類中心較近的樣本點隸屬度由其到類中心的距離決定，距離類中心較遠(yuǎn)的樣本點隸屬度由其到類中心的距離和它的緊密度共同決定。

定義1樣本點在在特征空間的中心

(6)

其中，Φ是從原始空間到高維空間的非線性映射。

定義2樣本點到各自類中心的距離

di+=‖Φ(xi)-O+‖di-=‖Φ(xi)-O-‖

(7)

定義3樣本到各自類中心的最遠(yuǎn)距離為類半徑

(8)

定義4樣本點之間的距離

dij=‖Φ(xi)-Φ(xj)‖

(9)

則基于距離的隸屬度為：

(10)

δ>0且足夠小，取離xi最近的k個樣本點：

(11)

M=max(m1,m2,…,ml)

(12)

則基于緊密度的隸屬度為：

(13)

則可變隸屬度為：

其中0<θ<1。

2.2可變隸屬度模糊雙支持向量機

給定樣本集{xi,yi}，為每個樣本點計算其隸屬度si，把si作為權(quán)值加入到樣本集中，這時樣本集就變?yōu)閧xi,si,yi}，則優(yōu)化問題：

(14)

(15)

其中c1、c2、c3、c4都為懲罰因子，SA、SB表示正負(fù)樣本的隸屬度組成的向量，采用拉格朗日乘子法求解優(yōu)化問題，則其對偶問題為：

(16)

(17)

其中，H=[K(B,CT)e],G=[K(A,CT)e]。

[u+,b+]T=-(GTG+c3I)-1HTα

(18)

[u-,b-]T= (HTH + c4I)-1GTγ

(19)

從對偶問題中可以看出，變量α、γ不同于標(biāo)準(zhǔn)雙支持向量機的變量。此處的α、γ的上界是隨隸屬度變化的，相當(dāng)于不同的樣本點使用不同的懲罰因子，這樣使得分類面對重要數(shù)據(jù)的分類精度明顯提高。

只要解出式(18)、式(19)就能可以求出決策函數(shù)：

(20)

此決策函數(shù)與式(5)看起來是一樣的，但實際上[u±,b±]T的值是不一樣的，只是形式一樣。假如輸入一個新的樣本點，就可以根據(jù)這個樣本點到兩個分類超平面的垂直距離來判斷其屬于那一類了。但是如果當(dāng)樣本點到兩個分類超平面距離相等時，標(biāo)準(zhǔn)雙支持向量機沒有給出明確的分類方法，在此稱這樣的點為等距點。

2.3等距點的處理

由于數(shù)據(jù)的不確定性，在分類過程中會出現(xiàn)等距點。雙支持向量機又規(guī)定樣本點只能屬于兩類中的其中一類，對于這些等距點，雙支持向量機進(jìn)入一個盲區(qū)，影響分類精度。如果是隨機分類，有可能屬于+1類的點被隨機分到了+1類。但是也有可能屬于+1類的點被分到-1類，屬于-1類的點被分到+1類，這樣就會出現(xiàn)錯分現(xiàn)象。針對這種現(xiàn)象，為進(jìn)一步提高分類精度，本文根據(jù)等距點與各類訓(xùn)練點的屬性等價性比例[16]對這些等距點進(jìn)行再分類。

定義5屬性等價性比例是描述樣本點之間有效聯(lián)系的參數(shù)：

(21)

其中，a表示樣本點屬性集合，Ci(a)表示樣本點與其他樣本點屬性相等的個數(shù)，Ni(a)該樣本點總的屬性個數(shù)。

當(dāng)分類中出現(xiàn)等距點時，分別計算該等距樣本點與各類所有訓(xùn)練樣本點的屬性等價性比例，記為qi+，qi-。等價性比例越高說明該等距點與該類的訓(xùn)練樣本點聯(lián)系性越高，越有可能屬于該類。即如果qi+>qi-，則該等距點就會被分到+1類，如果qi+

3實驗與分析

3.1實驗數(shù)據(jù)與實驗環(huán)境

為了驗證本文算法的性能，在此選用兩種數(shù)據(jù)集進(jìn)行實驗，即人工數(shù)據(jù)集和標(biāo)準(zhǔn)數(shù)據(jù)集。人工數(shù)據(jù)集是由計算機隨機長生的500個二維空間樣本點，記為D；標(biāo)準(zhǔn)數(shù)據(jù)集是在UCI[17]數(shù)據(jù)庫中選擇的幾組數(shù)據(jù)，如表1所示，記為U。

表1　標(biāo)準(zhǔn)數(shù)據(jù)集

實驗環(huán)境是在Intel(R) Core(TM) i5-3230M CPU @2.6 GHz, 4 GB內(nèi)存, 500 GB硬盤和Microsoft Windows7操作系統(tǒng)，使用Matlab V7R14工具實現(xiàn)算法。

3.2含噪聲的人工數(shù)據(jù)實驗

表2　人工數(shù)據(jù)集分類結(jié)果

從實驗結(jié)果可以看出，本文算法的分類精度最高，分類精度比標(biāo)準(zhǔn)雙支持向量機(TWSVM)高5個百分點，比雙邊界支持向量機(TBSVM)高3個百分點，也比混合模糊雙支持向量機(HFTSVM)高一個百分點。這是由于本算法為每個樣本點賦予不同的隸屬度。同時對等距點進(jìn)行再分類，這樣提高了分類精度。分類時間與TWSVM幾乎相同，遠(yuǎn)少于SVM，比混合雙支持向量機(HFTSVM)有所減小。這是由于本文算法采用可變隸屬度，比HFTSVM節(jié)省了一定的計算量，即為核參數(shù)和懲罰參數(shù)的確定節(jié)省一定的計算開銷，本算法對等距點的處理也增加了少量的計算量，但本文算法的總體分類性能是最好的。

3.3標(biāo)準(zhǔn)數(shù)據(jù)集實驗

與人工數(shù)據(jù)集的實驗一樣，本算法與其他四種分類算法進(jìn)行比較。在標(biāo)準(zhǔn)數(shù)據(jù)集中取前10%的數(shù)據(jù)集作為訓(xùn)練樣本，其余的作為測試樣本，依然采用高斯核函數(shù)作為本實驗的核函數(shù)，最終確定最佳參數(shù)σ=5,c1=50,c2=80,c3=40,c4=75，θ=41%,分類精度如表3所示，分類時間如表4所示。從表3可以看出，在Sonar數(shù)據(jù)集上，本文算法與HFTSVM算法的分類精度幾乎相等，但比TWSVM高3個百分點；在Pima-Indian數(shù)據(jù)集上，本文算法分類精度最高，比HFTSVM算法高3個百分點，比TWSVM高5個百分點。從表4可以看出，在Sonar數(shù)據(jù)集上，本文算法分類時間與HFTSVM的分類時間幾乎相等，但比TWSVM多4.2 s；在Pima-Indian數(shù)據(jù)集上的，本文算法分類時間比HFTSVM少2.6 s，比TWSVM多1.4 s，可以看出本文算法在分類時間可行的情況下，分類精度有一定的提高，所以本文算法是有效的。

表3　所選數(shù)據(jù)集的分類精度結(jié)果(%)

表4　所選數(shù)據(jù)集的分類時間結(jié)果(s)

3.4擴展分析

從表3中可以看出，隨著數(shù)據(jù)集的增大分類精度越來越高，但是隨著數(shù)據(jù)集的增大，本文算法分類精度增長率最大。同時從表4可以看出隨著數(shù)據(jù)集的增大分類時間也相應(yīng)的增加，但隨著數(shù)據(jù)集的增大，本文算法分類時間增長的相對較小，這說明本文算法在數(shù)據(jù)集較大時有很大的優(yōu)勢。

4結(jié)語

本文在引進(jìn)可變隸屬度的同時也對等距點進(jìn)行再分類，簡化了少量計算，為不同的樣本點賦予不同的隸屬度，提高了抗噪性能，減少錯分現(xiàn)象的發(fā)生，提高了分類精度。實驗結(jié)果表明，在分類時間可行的同時，分類精度值也比標(biāo)準(zhǔn)雙支持向量機也有了提高，因此本算法優(yōu)于標(biāo)準(zhǔn)雙支持向量機。由于在本文算法中涉及了多個參數(shù)，參數(shù)之間的聯(lián)系是以后需要研究的問題。

參考文獻(xiàn)

[1] Vladimir N Vapnik.統(tǒng)計學(xué)習(xí)理論的本質(zhì)[M].張學(xué)工,譯.北京:清華大學(xué)出版社,2000.

[2] 李凱,李娜,盧霄霞.一種模糊加權(quán)的孿生支持向量機算法[J].計算機工程與應(yīng)用,2013,49(4):162-165.

[3] 王曉丹,王積勤.支持向量機訓(xùn)練和實現(xiàn)算法綜述[J].計算機工程與應(yīng)用,2004,40(13):75-78.

[4] 余輝,趙暉.支持向量機多類分類算法新研究[J].計算機工程與應(yīng)用,2008,44(7):185-189.

[5] 靳玉萍,張兵,高凱.球形支持向量機在煤自燃預(yù)測中的應(yīng)用[J].計算機應(yīng)用與軟件,2013,30(9):57-60.

[6] Mangasarian O L,Wild E W.Multisurface proximal support vector machine classification via generalized eigenvalues[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(1):69-74.

[7] Khemchandni R,Suresh C.Twin support vector machine for pattern classification[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2007,29(5):905-910.

[8] Tian Y J,Shi Y,Liu X H.Recent advances on support vector machines research[J].Tech Econ Develop Econ,2012,18(3):5-33.

[9] Qi Z Q,Tian Y J,Shi Y.Robust twin support vector machine for pattern classification[J].Pattern Recognition,2013,46(1):305-316.

[10] Ye Qiaolin,Zhao Chunxia,Ye Ning.Least squares twin support vector machine classification via maximum one-class within class variance[J].Optimization Methods & Software,2012,27(1):53-69.

[11] Shao Y H.Improvements on twin support vector machines[J].IEEE Transactions on Neural Networks,2011,22(6):962-968.

[12] Peng X J.A novel twin parametric-margin support vector machine for pattern recognition[J].Pattern Recognition,2011,44(10):2678-2692.

[13] 丁勝峰,孫勁光.基于混合模糊隸屬度的模糊雙支持向量機研究[J].計算機應(yīng)用研究,2013,30(2):432-435.

[14] 劉華富.支持向量機Mercer核的若干性質(zhì)[J].北京聯(lián)合大學(xué)學(xué)報,2005,19(1):40-42.

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

[16] 梁宏霞,閆得勤.粗糙支持向量機[J].計算機科學(xué),2009,36(4):208-210.

[17] Blake C L,Merz C J.UCI Repository for machine learning databases[EB/OL].(1998-01-12).IrvineCA: University of California,Department of Information and Computer Sciences.http://www.ics.uci.edu /mlearn /MLRepository.html.

[18] Han Jiawei,Micheline Kamber,Jian Pei.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰,譯.北京:機械工業(yè)出版社,2012.

中圖分類號TP3

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.033

收稿日期：2014-08-07。國家自然科學(xué)基金青年科學(xué)基金項目(61003162)；遼寧省教育廳項目(L2013131)。任建華，副教授，主研領(lǐng)域：數(shù)據(jù)庫系統(tǒng)，數(shù)據(jù)挖掘等。劉曉帥，碩士生。孟祥福，副教授。王偉，講師。