支持向量機分類算法在MATLAB環(huán)境下的實現(xiàn)-

1、收稿日期:20080418作者簡介:董婷(1981,女,陜西岐山人,助教,在讀研究生,研究方向為機器學習和計算機視覺研究。E-m a i :l do ng ti ng 163.co m支持向量機分類算法在MATLAB 環(huán)境下的實現(xiàn)董 婷(榆林學院計算機與網(wǎng)絡(luò)工程系,陜西榆林719000摘 要:支持向量機算法SVM (SupportV ectorM ach i n e做為新一代機器學習算法近年來被成功的應用到很多模式識別問題中,其在數(shù)學上表示為求解一個二次規(guī)劃問題。主要論述了支持向量機分類算法在MATLAB 環(huán)境下的具體實現(xiàn)方法,為支持向量機算法的學習者和非計算機專業(yè)的廣大研究人員提供一種簡單、

2、方便、高效、可行實現(xiàn)方法。關(guān)鍵詞:SVM;二次歸劃;MATL AB中圖分類號:TP181 文獻標識碼:A 文章編號:1008-3871(200804-0094-03 V.V apnik 等人從二十世紀六、七十年代致力于小樣本的機器學習研究,到二十世紀九十年代中期,統(tǒng)計學習理論受到越來越廣泛的重視1,研究如何從一些觀察數(shù)據(jù)(樣本出發(fā),模擬目前為止尚不能通過原理或?qū)嶒灠l(fā)現(xiàn)的規(guī)律;利用這些規(guī)律分析客觀對象,對未來數(shù)據(jù)或無法觀測的數(shù)據(jù)進行預測,這就是機器學習的統(tǒng)計方法2。支持向量機SVM (Support VectorM achine是在統(tǒng)計學習理論基礎(chǔ)上發(fā)展起來的一種新的機器學習方法,是結(jié)構(gòu)風險最小

3、化原理的實現(xiàn)3。算法實現(xiàn)需具有深厚的數(shù)學功底和計算機編程技術(shù),對非計算機專業(yè)的廣大研究人員來說,一種簡單高效的實現(xiàn)環(huán)境和方法是迫切的需要。支持向量機算法在MATLAB 環(huán)境下易于實現(xiàn)和靈活應用的特點,很好的提供這一技術(shù)平臺。1 支持向量機及MATLAB1.1 最優(yōu)超平面 SVM 方法是從線性可分的情況下的最優(yōu)分類面(Opti m aH l yperplane提出的。設(shè)線性可分樣本集為(x i ,y i ,i=1,n ;y =+1,-1是類別標號,分類面方程為:w #x +b=0(1這個平面將兩類樣本沒有錯誤的分開,并且使得離分類面最近的樣本到分類面的距離最大,即分類間隔最大,等價于使+w +2

4、最小,w 為分類面的法向量。而要求分類面對所有樣本正確分類,約束條件為:y i (w #x i +b-1E 0,i=1,2,L ,n(2因此,滿足上述條件且使得+w +2最小的分類面就是最優(yōu)分類面。過兩類樣本中離分類面最近的點且平行于最優(yōu)分類面的超平面H 1、H 2上的訓練樣本就是式(2中使等號成立的那些樣本叫做支持向量。最優(yōu)分類面可以表示為如下約束的優(yōu)化問題,即在式(2的約束下,求函數(shù)U (w =12+w +2=12(w #w (3的最小值。為此,可以定義如下的拉格朗日函數(shù):L(w,b ,a=12+w +2-r ni=1a i y i (w #x+b-1(4(4式中,a i >0為拉格

5、朗日系數(shù)。把原問題轉(zhuǎn)化為如下較簡單的對偶問題:m ax Q (a=r ni=1a i -12r ni=1,j=1a i a j y i y j (x i #x j s .t r n i=1y i a i =0a i E 0,i=1,n 。1.2 非線性SVM 上面討論的是最優(yōu)和廣義線性分類函數(shù),要解決一個特征空間中的最優(yōu)線性分類問題,我們只需知道這個空間中的內(nèi)積運算即可。按照廣義線性判別函數(shù)的思路,要解決一個非線性問題,我們可以設(shè)法將它通過非線性變換轉(zhuǎn)換為另一個空間的線性問題,在這個變換空間求最優(yōu)或最廣義分類面?？紤]M ercer 條件:對于任意的對稱函數(shù)K(x ,x c ,它是某個特征空間的

6、內(nèi)積運算的充分必要條件是,對與任意的U (x恒不為0,且Q U 2(xdx <,有2008年7月第18卷 第4期榆林學院學報J O URNAL OF Y UL I N COLLEGE July .2008Vo.l 18No .4k K(x ,yU (xU (ydxdy 40,顯然這一條件不難滿足4。如果用內(nèi)積K (x ,y 代替最優(yōu)分類面的點積,就相當于把原特征空間變換到了某一新的特征空間,此時的支持向量機為:MAX Q(a=r ni=1a i -12r ni=1j=1a i a j y i y jK(x i ,x j s .t r ni=1y i a i =00F a ,F C i=1

7、,n 。相應的判別函數(shù)也應變?yōu)?f(x=sgn r ni=1a i *y i K (x i ,x+b *。其它的條件不變,這就是支持向量機。支持向量機的思想可以概括為:首先通過非線性變換將輸入空間變換到一個高維空間,然后就這個新空間中求取最優(yōu)線性分類面,而這種非線性變換是通過定義適當?shù)暮瘮?shù)實現(xiàn)的,這些函數(shù)叫做核函數(shù)。選擇不同的核函數(shù)就構(gòu)成不同的支持向量機,常用的有以下三類核函數(shù):li n ear :K (x ,y=x #y ;ploy :K (x ,y=(x #y+1q;rb:f K (x ,y=exp -|x-y |2R2。1.3 MATLAB MATLAB 是美國M ath W ork 公

8、司推出的一種用于工程計算的高性能程序設(shè)計語言。其代碼編寫過程與數(shù)學推導過程的格式很接近。應用主要集中在數(shù)值計算、算法開發(fā)、數(shù)學建模等方面,以矩陣為運算單元進行計算。MATLAB 作為一種計算工具和科技資源,可以擴大科學研究的范圍、縮短開發(fā)周期。該軟件的特點語言簡潔,代碼靈活,被稱為第四代計算機語言2。其最突出的特點就是提供了更為直觀、符合人們思維習慣的的代碼,易學易用,被國際學術(shù)界確認為準確、可靠的計算標準軟件。2 支持向量機分類算法的實現(xiàn)支持向量機算法是在訓練樣本的特征空間求取能把兩類樣本沒有錯誤分開的最大間隔超平面,在數(shù)學上表示為一個凸二次規(guī)劃的問題。也可以說算法求解的主要內(nèi)容是通過求解二

9、次規(guī)劃(QP問題,這個優(yōu)化問題的求解是支持向量機算法的核心,可以說支持向量機的算法就得到了實現(xiàn)。前面所述支持向量機算法可以表示為在式(6和式(7的約束下求式(5取最小值時的拉格朗日乘子A=(51,52,5n T,為訓練樣本的個數(shù)。Q (A=-A TI+1/2A TDA (50F A F C(6A Ty=0(7其中:A =(51,52,5n T為n 元列向量,是要求的拉格朗日乘子;D ij =y i y j K (x i ,x j 是一個正定矩陣;y =(y 1,y 2,y n T是樣本的所屬類別,由1或-1組成的列向量;x i 為訓練樣本?？梢钥闯?求解支持向量機就是求解上述的一個二次規(guī)劃問題

10、,求解后得到拉格朗日乘子A =(51,52,5n T,也就求得了最大間隔超平面。求解這個二次規(guī)劃問題需要深厚的數(shù)學功底數(shù)值計算方面的技能,在主流程序語言中實現(xiàn)算法又需要專業(yè)的計算機程序設(shè)計的知識。在MATLAB 環(huán)境下求解這一問題會變得非常簡單,這得益于MATLAB 軟件強大的優(yōu)化工具箱,提供了一個求解二次規(guī)劃的函數(shù),可以直接調(diào)用。二次規(guī)劃問題(quadratic pr ogra mm ing的標準形式為:m i n f c x+12x c H xsub .to Ax F b Aeqx=beq lb F x F ub其中,H 、A 、A eq 為矩陣;f 、b 、beq 、lb 、ub 、x

11、為向量,其它形式的二次規(guī)劃問題都可轉(zhuǎn)化為標準形式。MATLAB5.x 版中的qp 函數(shù)已被6.0版中的函數(shù)quadprog 取代。函數(shù)quadprog 格式如下:x ,fva l=quadprog(H,f A,b,A eq ,beq ,lb ,ub ,x0其中H 、f 、A 、b 、Aeq 、beq 、l b 、ub 為標準形中的參數(shù);x 為求解得到的最優(yōu)值,也就是二次規(guī)劃的解析解;lb 、ub 分別為x 的下界與上界,滿足不等式約&b F x F ub ;A eq 、beq 滿足等約束條件Aeq #x=beq ;x0為設(shè)置的初值,這個值是人為賦予x 的值,一般x 為零;fval 為目

12、標函數(shù)最小值,可以看出,支持向量機算法是一個標準的二次規(guī)劃問題;H =D ij =y i y j K (x i ,x j ,根據(jù)訓練樣本數(shù)據(jù)求出;f=-1;支持向量機算法沒形式的不等式約束條件,所以A 、b 為空矩陣;Aeq=A T ,beq=y ,實現(xiàn)A Ty=0等式約束;Lb =0、ub=C ,實現(xiàn)0F A F C 不等式約束;x0=0,賦予A 的初始值為零。樣本數(shù)據(jù)已知,C 是人工賦于的值?，F(xiàn)在支持向量機的求解需要一個公式就可以完成了,主要MATLAB 代碼如下:functi o n nsv ,a l p ha ,b=svc(X,Y,ker ,C% X -訓練樣本% Y -訓練樣本類別%

13、 ker -核函數(shù)類型% C -正則系數(shù)% nsv -支持向量個數(shù)#95#董 婷:支持向量機分類算法在MATLAB 環(huán)境下的實現(xiàn)% a l p ha -拉格朗日乘子% b -偏置值H =zeros(n,n;for i=1:n for j=1:nH (,i j=Y (i*Y (j*svkerne l(ker ,X (,i :,X(,j :; end end%D ij =y y j K (x i ,x j f=-ones(n ,1;l b =zeros(n ,1; %a l p has >=0ub =C *ones(n ,1; %alphas <=C x0=zeros(n ,1; %賦

14、初值0000A =Y c ,b =0; %Ax =b a l p ha la m bda ho w =qp(H,c ,A,b ,v l b ,vub,x0,neqcstr %調(diào)用qp 函數(shù)其中的svker nel 函數(shù)為核函數(shù),容易實現(xiàn),參照核函數(shù)的公式編寫代碼就成。我們調(diào)用函數(shù)svc 得到拉格朗日乘子(51,52,5n T和偏置b ,對于任何一個未知樣本x ,用判別函數(shù)f (x =sgnE ni=1a *i y i K (x i ,x+ b *就可以得到其類別預測值,sgn 函數(shù)為判別函數(shù),sgn(x=1 x>0-1 x<0。3 結(jié)論MATLAB 軟件是數(shù)學類應用軟件,在數(shù)值計算

15、方面尤為突出,被認為是進行高效研究、開發(fā)的首選軟件工具。加上其語言簡單自由,易于學習和掌握,是很多非計算機類專業(yè)的科研人員首選開發(fā)工具。支持向量機算法在MATLAB 環(huán)境下的實現(xiàn)的核心內(nèi)容是優(yōu)化工具箱的應用。基于MATALAB 環(huán)境下支持向量機算法的實現(xiàn)具有方便簡單、代碼編寫和移植快捷、性能可靠、程序運行易于控制等特點。尤其為非計算機專業(yè)的科研工作者提供了一種簡單、快捷的支持向量機算法研究和應用的技術(shù)平臺。參考文獻:1(英克里斯特安尼.支持向量機導論M .李國正,王猛,曾華軍譯.北京:電子工業(yè)出版社,2004.2張瑞豐.精通MATLAB 6.5M .北京:中國水利水電出版社,2004.3V l

16、andi m ir N.Vapnik .統(tǒng)計學習理論的本質(zhì)M .張學工譯.北京B 清華大學出版社,1999.4邊肇祺,張學工.模式識別M .北京:清華大學出版社,1988.(責任編輯:王瑞斌S V M A lgorith m R ealized i n MABLABDONG T ing(Depart m ent of Co m puter and N et w ork Eng i n eer i n g ,Yu li n College ,Yuli n 719000,Shaanx iAbst ract :A s a novel generation-m achine lear n i n g-m et h od ,Suppo rtV ectorM ach i n e has caughtm uch a-t tention i n recent years,and successfu lly used i n so m e top ics of patter n recogn iti o n .I n m athe m atics it presents a quadratic prog ra mm i n g .The w ays and