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

任建華　劉曉帥　孟祥福　王　偉

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

?

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

任建華劉曉帥孟祥福王偉

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

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

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

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

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

1雙支持向量機

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

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

(1)

(2)

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

(3)

(4)

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

(5)

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

2模糊雙支持向量機

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

2.1可變模糊隸屬度

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

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

(6)

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

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

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

(7)

定義3樣本到各自類中心的最遠距離為類半徑

(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作為權值加入到樣本集中，這時樣本集就變為{xi,si,yi}，則優化問題：

(14)

(15)

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

(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)

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

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

(20)

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

2.3等距點的處理

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

定義5屬性等價性比例是描述樣本點之間有效聯系的參數：

(21)

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

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

3實驗與分析

3.1實驗數據與實驗環境

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

表1　標準數據集

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

3.2含噪聲的人工數據實驗

表2　人工數據集分類結果

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

3.3標準數據集實驗

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

表3　所選數據集的分類精度結果(%)

表4　所選數據集的分類時間結果(s)

3.4擴展分析

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

4結語

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

參考文獻

[1] Vladimir N Vapnik.統計學習理論的本質[M].張學工,譯.北京:清華大學出版社,2000.

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

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

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

[5] 靳玉萍,張兵,高凱.球形支持向量機在煤自燃預測中的應用[J].計算機應用與軟件,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].計算機應用研究,2013,30(2):432-435.

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

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

[16] 梁宏霞,閆得勤.粗糙支持向量機[J].計算機科學,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.數據挖掘概念與技術[M].范明,孟小峰,譯.北京:機械工業出版社,2012.

中圖分類號TP3

文獻標識碼A

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

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