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

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

2、據(jù)集的測(cè)試結(jié)果表明，使用新偏移量的FSVM識(shí)別率高于使用標(biāo)準(zhǔn)偏移量的FSVM識(shí)別率。 關(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)計(jì)學(xué)習(xí)的機(jī)器學(xué)習(xí)新方法1，它具有

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

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

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

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

9、面的位置。通過(guò)適當(dāng)改變偏移量b，可以平滑地移動(dòng)分類面而不改變其形狀，但對(duì)分類結(jié)果會(huì)產(chǎn)生一定影響。在特征空間的線性可分兩類問(wèn)題中，令 =minzZ1(w,xi)i其中，求和部分只對(duì)支持向量進(jìn)行；b*是偏移量。2.2 核函數(shù)對(duì)于非線性問(wèn)題，可以通過(guò)非線性變換將其轉(zhuǎn)化為某個(gè)高維空間中的線性問(wèn)題，并在變換空間中求最優(yōu)分類面。在高維空間中只要進(jìn)行內(nèi)積運(yùn)算，此類內(nèi)積運(yùn)算可以用原空間中的函數(shù)實(shí)現(xiàn)3。根據(jù)泛函分析的相關(guān)理論，只要一種核函它就對(duì)應(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)重；此時(shí)，分類間隔轉(zhuǎn)換為:(w,xi)=0xi(Z1Z2)；>。和:(w,xi)=0兩面之間的距離。在多類問(wèn)題中，可以利用和來(lái)調(diào)整偏移量大小。對(duì)多類問(wèn)題中的每個(gè)類分別用式(3)轉(zhuǎn)化為練數(shù)據(jù)的個(gè)數(shù)記為N2。D(x)=sgn(aiyi(xi,x)b*) (5)支持向量FSVM的標(biāo)準(zhǔn)偏移量為+3 “一對(duì)一”多類FSVM bS= (12) 23.1 多類SVM它與上文用二次規(guī)化問(wèn)題求解的偏移量b*一致，且與每在k類問(wèn)題中，該方法共構(gòu)建k(k-1)/2個(gè)SVM，其中每對(duì)兩類問(wèn)題中的數(shù)據(jù)個(gè)數(shù)相獨(dú)立。該偏移量不一定是最佳選個(gè)SVM分開2個(gè)類別，分類函數(shù)如下：2Dij=

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

12、出FSVM的多類算法，在多個(gè)類別滿足式(8)而造成相同分類結(jié)果的情況下，引入模糊隸屬度函數(shù)。在“一對(duì)一”分類模式下，假設(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時(shí)，式(13)可以簡(jiǎn)化為 0x0+將x劃入如下類別：bN=d=dbS (14)argmaxDi(x) (8) 2 i=1,2,",k其中，0.5<d<1.5，是新偏項(xiàng)的參數(shù)，一般根據(jù)數(shù)據(jù)和先驗(yàn)采用上述

13、方法時(shí)，會(huì)出現(xiàn)不確定區(qū)域。3.2 多類FSVM 為了解決多類SVM中的不確定區(qū)域問(wèn)題，文獻(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) 方框空心點(diǎn)代表另一個(gè)類，空心圓點(diǎn)類數(shù)據(jù)多于方框空心點(diǎn) ji,j=1,2,",kmin圖3以Iirs二維數(shù)據(jù)為例，其中，空心圓點(diǎn)代表一個(gè)類；類數(shù)據(jù)；H1,H2分別為經(jīng)過(guò)各類中離分類線最近的樣本且平一個(gè)未知的待識(shí)樣本x隸屬于以下類別：argmaxmi(x) (11) 行與分類

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

15、5幅作為測(cè)試數(shù)據(jù)，182并用PCA方法提取人臉特征數(shù)據(jù)。以水仙花數(shù)據(jù)每類中的前25個(gè)作為訓(xùn)練集，后25個(gè)作為測(cè)試數(shù)據(jù)。Wine數(shù)據(jù)集的每類數(shù)據(jù)各不相同。各種數(shù)據(jù)特征如表1所示。表1 實(shí)驗(yàn)數(shù)據(jù)的特征數(shù)據(jù)集 人臉 水仙花 Wine類別數(shù)維數(shù)每類數(shù)據(jù)個(gè)數(shù)10總個(gè)數(shù) 400 150 17840 10由表2可以看出，對(duì)于人臉數(shù)據(jù)和水仙花數(shù)據(jù)，因?yàn)槊款悢?shù)據(jù)都相同，即N1=N2，所以新偏移量由標(biāo)準(zhǔn)偏移量通過(guò)適當(dāng)調(diào)整參數(shù)d得到。對(duì)于Wine數(shù)據(jù)，雖然其每類數(shù)據(jù)各不同，但通過(guò)改變偏移量的求法，即使用新偏移量，其識(shí)別率得到了一定提高。表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用上述“一對(duì)一”多類FSVM算法，選用多項(xiàng)式核函數(shù)，懲罰因子C100。實(shí)驗(yàn)計(jì)算機(jī)配置為奔騰雙核1.86 GHz CPU, 1 GB RAM，仿真程序用Matlab 7.0編寫。由圖4圖6可知，對(duì)于人臉數(shù)據(jù)、水仙花數(shù)據(jù)和Wine數(shù)據(jù)，最高識(shí)別率分別在新偏移量參數(shù)d為0.9, 1.1, 1.0時(shí)取得。1.1 98.67 水仙花Wine 1.0 94.44在水仙花數(shù)據(jù)中雖然存在交叉點(diǎn)，但由于訓(xùn)練時(shí)選取的每類中的前25個(gè)數(shù)據(jù)已經(jīng)包括了交叉點(diǎn)，即指定了其類別，因此識(shí)別率可以達(dá)到100%。由圖圖6可以看出，不同參數(shù)求出的

17、偏移量對(duì)識(shí)別率有一定影響。通過(guò)參數(shù)調(diào)整，對(duì)每種數(shù)據(jù)分類時(shí)可以取得一個(gè)峰值，其值高于采用原標(biāo)準(zhǔn)偏移量進(jìn)行分類時(shí)的峰值。6 結(jié)束語(yǔ)本文使用一種新的偏移量計(jì)算方法，得到的偏移量對(duì)最優(yōu)分類面的位置進(jìn)行了適當(dāng)調(diào)整，不會(huì)影響FSVM的學(xué)習(xí)能力和外推能力。該方法為偏移量的獲取提供了新思路，但仍然需要人工設(shè)置參數(shù)值而沒(méi)有實(shí)現(xiàn)自適應(yīng)，有待進(jìn)一步完善。參考文獻(xiàn)1 邊肇祺, 張學(xué)工. 模式識(shí)別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)計(jì)學(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ù)識(shí)別率ClassificationC/Proc. of IJCNN01. Washington D. C., USA: s. n., 2001.圖5 水仙花數(shù)據(jù)識(shí)別率 圖6 Wine數(shù)據(jù)識(shí)別率 編輯 陳 暉（上接第整數(shù)倍，從而減小時(shí)間驅(qū)動(dòng)方式對(duì)時(shí)延的放大作用?？紤]到系統(tǒng)具有外部干擾，設(shè)計(jì)基于切換系統(tǒng)的魯棒故障觀測(cè)器，將故障檢測(cè)閾值的選取歸結(jié)為具有線性矩陣不等式約束的最小化