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

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

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

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

4、最小,w 為分類面的法向量。而要求分類面對所有樣本正確分類,約束條件為:y i (w #x i +b-1E 0,i=1,2,L ,n(2因此,滿足上述條件且使得+w +2最小的分類面就是最優(yōu)分類面。過兩類樣本中離分類面最近的點(diǎn)且平行于最優(yōu)分類面的超平面H 1、H 2上的訓(xùn)練樣本就是式(2中使等號(hào)成立的那些樣本叫做支持向量。最優(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ù),要解決一個(gè)特征空間中的最優(yōu)線性分類問題,我們只需知道這個(gè)空間中的內(nèi)積運(yùn)算即可。按照廣義線性判別函數(shù)的思路,要解決一個(gè)非線性問題,我們可以設(shè)法將它通過非線性變換轉(zhuǎn)換為另一個(gè)空間的線性問題,在這個(gè)變換空間求最優(yōu)或最廣義分類面?？紤]M ercer 條件:對于任意的對稱函數(shù)K(x ,x c ,它是某個(gè)特征空間的

6、內(nèi)積運(yùn)算的充分必要條件是,對與任意的U (x恒不為0,且Q U 2(xdx <,有2008年7月第18卷 第4期榆林學(xué)院學(xué)報(bào)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)分類面的點(diǎn)積,就相當(dāng)于把原特征空間變換到了某一新的特征空間,此時(shí)的支持向量機(jī)為: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 。相應(yīng)的判別函數(shù)也應(yīng)變?yōu)?f(x=sgn r ni=1a i *y i K (x i ,x+b *。其它的條件不變,這就是支持向量機(jī)。支持向量機(jī)的思想可以概括為:首先通過非線性變換將輸入空間變換到一個(gè)高維空間,然后就這個(gè)新空間中求取最優(yōu)線性分類面,而這種非線性變換是通過定義適當(dāng)?shù)暮瘮?shù)實(shí)現(xiàn)的,這些函數(shù)叫做核函數(shù)。選擇不同的核函數(shù)就構(gòu)成不同的支持向量機(jī),常用的有以下三類核函數(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、司推出的一種用于工程計(jì)算的高性能程序設(shè)計(jì)語言。其代碼編寫過程與數(shù)學(xué)推導(dǎo)過程的格式很接近。應(yīng)用主要集中在數(shù)值計(jì)算、算法開發(fā)、數(shù)學(xué)建模等方面,以矩陣為運(yùn)算單元進(jìn)行計(jì)算。MATLAB 作為一種計(jì)算工具和科技資源,可以擴(kuò)大科學(xué)研究的范圍、縮短開發(fā)周期。該軟件的特點(diǎn)語言簡潔,代碼靈活,被稱為第四代計(jì)算機(jī)語言2。其最突出的特點(diǎn)就是提供了更為直觀、符合人們思維習(xí)慣的的代碼,易學(xué)易用,被國際學(xué)術(shù)界確認(rèn)為準(zhǔn)確、可靠的計(jì)算標(biāo)準(zhǔn)軟件。2 支持向量機(jī)分類算法的實(shí)現(xiàn)支持向量機(jī)算法是在訓(xùn)練樣本的特征空間求取能把兩類樣本沒有錯(cuò)誤分開的最大間隔超平面,在數(shù)學(xué)上表示為一個(gè)凸二次規(guī)劃的問題。也可以說算法求解的主要內(nèi)容是通過求解二

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

10、,求解后得到拉格朗日乘子A =(51,52,5n T,也就求得了最大間隔超平面。求解這個(gè)二次規(guī)劃問題需要深厚的數(shù)學(xué)功底數(shù)值計(jì)算方面的技能,在主流程序語言中實(shí)現(xiàn)算法又需要專業(yè)的計(jì)算機(jī)程序設(shè)計(jì)的知識(shí)。在MATLAB 環(huán)境下求解這一問題會(huì)變得非常簡單,這得益于MATLAB 軟件強(qiáng)大的優(yōu)化工具箱,提供了一個(gè)求解二次規(guī)劃的函數(shù),可以直接調(diào)用。二次規(guī)劃問題(quadratic pr ogra mm ing的標(biāo)準(zhǔn)形式為: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)化為標(biāo)準(zhǔ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 為標(biāo)準(zhǔn)形中的參數(shù);x 為求解得到的最優(yōu)值,也就是二次規(guī)劃的解析解;lb 、ub 分別為x 的下界與上界,滿足不等式約&b F x F ub ;A eq 、beq 滿足等約束條件Aeq #x=beq ;x0為設(shè)置的初值,這個(gè)值是人為賦予x 的值,一般x 為零;fval 為目

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

13、 ker -核函數(shù)類型% C -正則系數(shù)% nsv -支持向量個(gè)數(shù)#95#董 婷:支持向量機(jī)分類算法在MATLAB 環(huán)境下的實(shí)現(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ù),容易實(shí)現(xiàn),參照核函數(shù)的公式編寫代碼就成。我們調(diào)用函數(shù)svc 得到拉格朗日乘子(51,52,5n T和偏置b ,對于任何一個(gè)未知樣本x ,用判別函數(shù)f (x =sgnE ni=1a *i y i K (x i ,x+ b *就可以得到其類別預(yù)測值,sgn 函數(shù)為判別函數(shù),sgn(x=1 x>0-1 x<0。3 結(jié)論MATLAB 軟件是數(shù)學(xué)類應(yīng)用軟件,在數(shù)值計(jì)算

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

16、andi m ir N.Vapnik .統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)M .張學(xué)工譯.北京B 清華大學(xué)出版社,1999.4邊肇祺,張學(xué)工.模式識(shí)別M .北京:清華大學(xué)出版社,1988.(責(zé)任編輯:王瑞斌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