模糊支持向量機(jī)的偏移量計算方法

1、計 算 機(jī) 工 程 第 35 卷 第19期Vol.35 No.19 Computer Engineering ·人工智能及識別技術(shù)·文章編號：10003428(2009)19018103文獻(xiàn)標(biāo)識碼：A2009年10月October 2009中圖分類號：TP391.4模糊支持向量機(jī)的偏移量計算方法陳家德，吳小俊(江南大學(xué)信息工程學(xué)院，無錫 214122)摘 要：偏移量確定了支持向量機(jī)和模糊支持向量機(jī)(FSVM)的最優(yōu)分類面位置，對分類性能具有較大影響。為提高模糊支持向量機(jī)的識別率，基于Fisher判別分析方法提出一種新的偏移量計算方法，將其用于FSVM多類分類器設(shè)計。對3種數(shù)

2、據(jù)集的測試結(jié)果表明，使用新偏移量的FSVM識別率高于使用標(biāo)準(zhǔn)偏移量的FSVM識別率。 關(guān)鍵詞：偏移量；支持向量機(jī)；模糊支持向量機(jī)；機(jī)器學(xué)習(xí)Offset Calculation Method for Fuzzy Support Vector MachineCHEN Jia-de, WU Xiao-jun(School of Information Technology, Jiangnan University, Wuxi 214122)【Abstract】Offset determines the position of optimal separating planeof Support Ve

3、ctor Machine(SVM) and Fuzzy Support VectorMachine(FSVM) and affects the performance of classification greatly. In order to improve the recognition rate of FSVM, this paper proposesa newcalculation approach for offset based on Fisher discriminant analysis method and uses it to design FSVM multi-class

4、ification. Test results of threedata sets show that the recognition rate of FSVM using new offset is higher than the one using normal offset. 【Key words】offset; Support Vector Machine(SVM); Fuzzy Support Vector Machine(FSVM); machine learning1 概述支持向量機(jī)(Support Vector Machine, SVM)是基于統(tǒng)計學(xué)習(xí)的機(jī)器學(xué)習(xí)新方法1，它具有

5、良好的數(shù)學(xué)形式、直觀的幾何解釋和良好的泛化能力，解決了模型選擇與欠學(xué)習(xí)、過學(xué)習(xí)問題以及非線性問題，避免局部最優(yōu)解，有效克服了“維數(shù)災(zāi)難”。由于SVM中人為設(shè)定的參數(shù)較少，因此便于使用，已被成功用于各種分類問題。SVM方法可以解決兩類問題，而處理多類問題時，如果一些輸入樣本不能被確切歸為某一類，則普通SVM將無法順利運行。針對該問題，文獻(xiàn)2提出模糊支持向量機(jī)(Fuzzy Support Vector Machine, FSVM)，并引入模糊隸屬度函數(shù)，在一定程度上避免了傳統(tǒng)SVM的局限性。SVM和FSVM的分類性能由求解二次規(guī)化問題得到的權(quán)重和偏移量確定，偏移量過大或過小將直接影響最優(yōu)分類面位置

6、和分類性能。因此，本文采用一種新的偏移量求解方法。1圖1 線性可分情況下的最優(yōu)分類面此時分類間隔等于小。滿足式(1)且2，使間隔最大等價于使|w|2最w|w|2最小的分類面即最優(yōu)分類面，H1, H222 兩類支持向量機(jī)支持向量機(jī)訓(xùn)練時，多類問題被轉(zhuǎn)化為n個兩類問題進(jìn)行訓(xùn)練。在一個兩類問題中，m(m<1)維訓(xùn)練集被映射到一維特征空間Z中。兩類的最優(yōu)分類超平面基于特征空間中的二次優(yōu)化問題進(jìn)行求解。2.1 最優(yōu)超平面SVM由線性可分情況下的最優(yōu)分類面發(fā)展而來，其基本思想如圖1所示。在圖1中，空心點和方格點代表2類樣本；H為分類線，H1, H2分別為經(jīng)過各個類中離分類線最近的樣本且平行于分類線的

7、直線，它們之間的距離稱為分類間隔margin。最優(yōu)分類線能將2個類正確分開，并使分類間隔最大3。設(shè)樣本集為(xi,yi),i=1,2,",n,xR,y+1,1，且d上的訓(xùn)練樣本點稱為支持向量。利用Lagrange優(yōu)化方法可以把上述最優(yōu)分類面問題轉(zhuǎn)化為其對偶問題，即在約束條件aiyi=0,ai0,i=1,2,",n下i=1n對ai求解下列函數(shù)的最大值：Q(a)=aii=1n1naiajyiyj(xi,xj) (2) 2i,j=1ai為原問題中與式(1)對應(yīng)的Lagrange乘子。上述問題是一個不等式約束下二次函數(shù)尋優(yōu)的問題，存在唯一解。容易基金項目：2006年教育部新世紀(jì)優(yōu)秀

8、人才計劃基金資助項目(NCEG- 06-0487)；國家自然科學(xué)基金資助項目(60472060, 60572034)；江蘇省自然科學(xué)基金資助項目(BK2006081)作者簡介：陳家德(1980)，男，碩士，主研方向：模式識別，模糊支持向量機(jī)；吳小俊，教授、博士生導(dǎo)師滿足：yi(wxi)b10(1)181證明，解中只有一部分ai不為零，它們對應(yīng)的樣本即支持向量。求解上述問題得到最優(yōu)超平面的w*和b*，此時最優(yōu)分類函數(shù)為D(x)=sgn(w*x)b*=sgn(ai*yi(xix)b*) (3)i=1n4 偏移量模糊支持向量機(jī)的最優(yōu)分類面由權(quán)重w和偏移量b同時決定，權(quán)重確定其形態(tài)，偏移量確定最優(yōu)分類

9、面的位置。通過適當(dāng)改變偏移量b，可以平滑地移動分類面而不改變其形狀，但對分類結(jié)果會產(chǎn)生一定影響。在特征空間的線性可分兩類問題中，令 =minzZ1(w,xi)i其中，求和部分只對支持向量進(jìn)行；b*是偏移量。2.2 核函數(shù)對于非線性問題，可以通過非線性變換將其轉(zhuǎn)化為某個高維空間中的線性問題，并在變換空間中求最優(yōu)分類面。在高維空間中只要進(jìn)行內(nèi)積運算，此類內(nèi)積運算可以用原空間中的函數(shù)實現(xiàn)3。根據(jù)泛函分析的相關(guān)理論，只要一種核函它就對應(yīng)某一變換空間中的內(nèi)積。 數(shù)(xi,yj)滿足Mercer條件，可以用特征空間的(x)代替x，則式(3)轉(zhuǎn)化為Q(a)=maxzZ2(w,xi)i其中，Z1和Z2分別為標(biāo)

10、記“+1”和“-1”的兩類；w為權(quán)重；此時，分類間隔轉(zhuǎn)換為:(w,xi)=0xi(Z1Z2)；>。和:(w,xi)=0兩面之間的距離。在多類問題中，可以利用和來調(diào)整偏移量大小。對多類問題中的每個類分別用式(3)轉(zhuǎn)化為練數(shù)據(jù)的個數(shù)記為N2。D(x)=sgn(aiyi(xi,x)b*) (5)支持向量FSVM的標(biāo)準(zhǔn)偏移量為+3 “一對一”多類FSVM bS= (12) 23.1 多類SVM它與上文用二次規(guī)化問題求解的偏移量b*一致，且與每在k類問題中，該方法共構(gòu)建k(k-1)/2個SVM，其中每對兩類問題中的數(shù)據(jù)個數(shù)相獨立。該偏移量不一定是最佳選個SVM分開2個類別，分類函數(shù)如下：2Dij=

11、wijxbij (6) 擇。根據(jù)Fisher判別分析方法可以得到如下偏移量：N+N2(13) bN=d1其中，wij為權(quán)重；bij為偏移量；Dij(x)=Dji(x)。對于輸入向量x，計算Di(x)=sgn(Dij(x)。n1n ," 2 , , k ( k 2)標(biāo)記。本文采用FSVM多類問題中的一對aiajyiyj(xi)(xj) (4) 12i,j=1一算法，k類問題分為k(k1)/2個兩類問題。將分別標(biāo)記為若(x,y)滿足Mercer條件，則令(x,y)=(x)(y)，+1,1的兩類中的第1類訓(xùn)練數(shù)據(jù)的個數(shù)記為N1，另一類訓(xùn)N1+N2此偏移量是,以及每類N1和N2的凸組合。如果

12、出FSVM的多類算法，在多個類別滿足式(8)而造成相同分類結(jié)果的情況下，引入模糊隸屬度函數(shù)。在“一對一”分類模式下，假設(shè)最優(yōu)決策面方程為Dij(x)=0(ji,i,j=1,2,",k)，在垂直于Dij(x)=0方向上定義如下一維隸屬函數(shù)：N2>N1，則偏移量離數(shù)據(jù)為N2的一類較遠(yuǎn)，反之則離數(shù)據(jù)1x>0 (7)sign(x)=為N1的一類較遠(yuǎn)。當(dāng)N2=N1時，式(13)可以簡化為 0x0+將x劃入如下類別：bN=d=dbS (14)argmaxDi(x) (8) 2 i=1,2,",k其中，0.5<d<1.5，是新偏項的參數(shù)，一般根據(jù)數(shù)據(jù)和先驗采用上述

13、方法時，會出現(xiàn)不確定區(qū)域。3.2 多類FSVM 為了解決多類SVM中的不確定區(qū)域問題，文獻(xiàn)4-5提其中，ji,i,j=1,2,",k。利用mij(x)定義第i類隸屬函數(shù)為mi(x)=ifDij(x)11 (9)mij(x)=Dij(x)else圖3 最優(yōu)分類面中不同偏移量的最優(yōu)分類線mij(x) (10) 方框空心點代表另一個類，空心圓點類數(shù)據(jù)多于方框空心點 ji,j=1,2,",kmin圖3以Iirs二維數(shù)據(jù)為例，其中，空心圓點代表一個類；類數(shù)據(jù)；H1,H2分別為經(jīng)過各類中離分類線最近的樣本且平一個未知的待識樣本x隸屬于以下類別：argmaxmi(x) (11) 行與分類

14、線的直線， 線上的點為支持向量點； H3為標(biāo)準(zhǔn)偏移i=1,2,",k圖2描述了“一對一”方法對不可分區(qū)域的劃分結(jié)果。量的分類線；H4為新偏移量的分類線。圖3描述了N2>N1的情形，可以看到分類線由于偏移量不同而發(fā)生的位置變化。由權(quán)重和偏移量構(gòu)成的最優(yōu)分類面函數(shù)在對測試集進(jìn)行測試前已經(jīng)確定，因此，無論標(biāo)準(zhǔn)偏移量或新偏移量，在SVM和FSVM中的求法相同，且參數(shù)的選取一致。5 實驗與結(jié)果分析圖2 “一對一”方法對不可分區(qū)域的劃分結(jié)果為了驗證本文方法的性能，利用PCA方法提取ORL人臉庫數(shù)據(jù)與水仙花數(shù)據(jù)進(jìn)行實驗比較。取壓縮后維數(shù)為46×56的每類人臉中的前5幅作為訓(xùn)練集，后

15、5幅作為測試數(shù)據(jù)，182并用PCA方法提取人臉特征數(shù)據(jù)。以水仙花數(shù)據(jù)每類中的前25個作為訓(xùn)練集，后25個作為測試數(shù)據(jù)。Wine數(shù)據(jù)集的每類數(shù)據(jù)各不相同。各種數(shù)據(jù)特征如表1所示。表1 實驗數(shù)據(jù)的特征數(shù)據(jù)集 人臉 水仙花 Wine類別數(shù)維數(shù)每類數(shù)據(jù)個數(shù)10總個數(shù) 400 150 17840 10由表2可以看出，對于人臉數(shù)據(jù)和水仙花數(shù)據(jù)，因為每類數(shù)據(jù)都相同，即N1=N2，所以新偏移量由標(biāo)準(zhǔn)偏移量通過適當(dāng)調(diào)整參數(shù)d得到。對于Wine數(shù)據(jù)，雖然其每類數(shù)據(jù)各不同，但通過改變偏移量的求法，即使用新偏移量，其識別率得到了一定提高。表2 標(biāo)準(zhǔn)偏移量和新偏移量數(shù)據(jù)集 人臉d bS/(%) 0.9 94.50bN/

16、(%) 95.00 100.00 98.893 4 50 3 1359, 71, 48用上述“一對一”多類FSVM算法，選用多項式核函數(shù)，懲罰因子C100。實驗計算機(jī)配置為奔騰雙核1.86 GHz CPU, 1 GB RAM，仿真程序用Matlab 7.0編寫。由圖4圖6可知，對于人臉數(shù)據(jù)、水仙花數(shù)據(jù)和Wine數(shù)據(jù)，最高識別率分別在新偏移量參數(shù)d為0.9, 1.1, 1.0時取得。1.1 98.67 水仙花Wine 1.0 94.44在水仙花數(shù)據(jù)中雖然存在交叉點，但由于訓(xùn)練時選取的每類中的前25個數(shù)據(jù)已經(jīng)包括了交叉點，即指定了其類別，因此識別率可以達(dá)到100%。由圖圖6可以看出，不同參數(shù)求出的

17、偏移量對識別率有一定影響。通過參數(shù)調(diào)整，對每種數(shù)據(jù)分類時可以取得一個峰值，其值高于采用原標(biāo)準(zhǔn)偏移量進(jìn)行分類時的峰值。6 結(jié)束語本文使用一種新的偏移量計算方法，得到的偏移量對最優(yōu)分類面的位置進(jìn)行了適當(dāng)調(diào)整，不會影響FSVM的學(xué)習(xí)能力和外推能力。該方法為偏移量的獲取提供了新思路，但仍然需要人工設(shè)置參數(shù)值而沒有實現(xiàn)自適應(yīng)，有待進(jìn)一步完善。參考文獻(xiàn)1 邊肇祺, 張學(xué)工. 模式識別M. 北京: 清華大學(xué)出版社, 2000. 2 Tsujinishi D, Shigeo A. Fuzzy Lest Squares Support VectorMachines for Multiclass ProblemJ

18、. Neural Networks, 2003, 16(5/6): 785-792.3 Vapnik V N. 統(tǒng)計學(xué)習(xí)理論的本質(zhì)M. 2版. 北京: 清華大學(xué)出版社, 2000.4 Shigeo A, Inoue T. Fuzzy Support Vector Machines for MulticlassProblemsC/Proc. of ESANN02. Bruges, Belgium: s. n., 2002. 5 Inoue T, Shigeo A. Fuzzy Support Vector Machines for Pattern圖4 人臉數(shù)據(jù)識別率ClassificationC/Proc. of IJCNN01. Washington D. C., USA: s. n., 2001.圖5 水仙花數(shù)據(jù)識別率 圖6 Wine數(shù)據(jù)識別率 編輯 陳 暉（上接第整數(shù)倍，從而減小時間驅(qū)動方式對時延的放大作用?？紤]到系統(tǒng)具有外部干擾，設(shè)計基于切換系統(tǒng)的魯棒故障觀測器，將故障檢測閾值的選取歸結(jié)為具有線性矩陣不等式約束的最小化