支持向量機(jī)原理與實(shí)驗(yàn)

11GRm、n11GRm、n應(yīng)有y=1；若X屬于七類，則對(duì)應(yīng)有y對(duì)于任給的未知模式，有Ig(X)〉0,XGC1[?(X)〉0,XGC2式中sgn()為符號(hào)函數(shù)，g(X)稱為決策或者sg"(X)}=1,sgn?(x)}=-1,(分類)函數(shù)。XGC1XGC2支持向量機(jī)分類問(wèn)題支持向量機(jī)是基于統(tǒng)計(jì)的學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化(SRM)原則的機(jī)器學(xué)習(xí)。而(SRM)原則是針對(duì)二值分類問(wèn)題(兩類的分類問(wèn)題)提出的，因此，關(guān)于SVM的基本問(wèn)題是二值分類問(wèn)題。設(shè)有兩類模式C和C，T={(X,y)(X,y)(X,y)}是從模式C121122NN1和C中抽樣得到的訓(xùn)練集，其中XGRm、yG{l,-1}。若X屬于C類，則對(duì)2nnn1=-1；。尋求rm上的一個(gè)實(shí)函數(shù)g(x)，我們稱解決上述問(wèn)題的方法為“分類機(jī)”。當(dāng)g(X)為線性函數(shù)時(shí)，稱為線性分類機(jī)；當(dāng)g(X)為非線性函數(shù)時(shí)，稱為非線性分類機(jī)。對(duì)于這個(gè)二維問(wèn)題，線性分類機(jī)的作用就是要在匕和C2之間尋找一條分類線l，其表達(dá)式為g(X)。我們已經(jīng)熟知，在高維情況下g(X1是一個(gè)超平面。對(duì)于線性可分的兩類模式C1和C2而言，能夠準(zhǔn)確將其分開的直線不是唯一的。假設(shè)有直線l可以無(wú)誤地將C和C2兩類模式分開，另有直線lL和直線l2與l之間的間距為k，〈與l2之間形成一個(gè)沒(méi)有學(xué)習(xí)樣本的帶狀區(qū)域，不妨稱該帶狀區(qū)域?yàn)椤斑厧?Margin)”:而l是邊帶的中分線。顯然，最合理的分類線應(yīng)該具有最寬的邊帶。假設(shè)，已知分類線l的法線矢量為W。，則分類線的表達(dá)式為:g(X)=(W-X)+b=0式中(.)表示矢量點(diǎn)積。顯然，g(X)到原點(diǎn)距離為b町對(duì)于給定的所有N個(gè)學(xué)習(xí)樣本^<X,y)}：，g(X)應(yīng)滿足:g(X)〉0,y=1XgC1g\X)<0,y.=-1XGC2

y=sgn{g(X)}y=sgn{g(X)}=1J=sgn{g(X)}=-1直線l和直線l與分類線l之間的間隔距離為*,則這兩條邊界線的表達(dá)式分12別為:l:(W-X)+b=kl:(W-X)+b=-k直線l和直線l之間的間距為2.k，"尋找最大帶寬的問(wèn)題，轉(zhuǎn)化為在保證所12有學(xué)習(xí)樣本滿足條件的前提下，尋找g()使k達(dá)到最大的問(wèn)題了。k是一個(gè)標(biāo)量，因此，可以取W=匕；b=匕。于是，分類線l的表達(dá)式可以改寫成：kkl:g(X)=(W.X)+b=0直線l和直線l的表達(dá)式可以改寫成：12l:(W-X)+b=1七:(Wo.X)+b°=-1當(dāng)k增大時(shí)，|W||=^kl變小。于是，尋找最大帶寬k的問(wèn)題，變成了尋找最小IWII的問(wèn)題，為了計(jì)算上的方便，取目標(biāo)函數(shù)為^IWII2。211對(duì)于任意學(xué)習(xí)樣本(Xnyn)，其分布必然在直線l之上或直線l之下。即有g(shù)(X)=(W?X)+b>1,y^=1g(X)=(W?X)+b<-1,y=-1將以上兩式合并，有y..[(W.X.)+b]>1上式對(duì)于任何學(xué)習(xí)樣本都必須成立。在此前提下尋在選擇分類線的過(guò)程中找最寬邊界的問(wèn)題，最后可以表示成一個(gè)約束優(yōu)化問(wèn)題:上式對(duì)于任何學(xué)習(xí)樣本都必須成立。在此前提下尋TOC\o"1-5"\h\zmin1——-WWb2s.t.y^.[(W?X.)+b]>1,i=1,2,...,m1—W『W2y.?[(W?X.1—W『W2y.?[(W?X.)+b]>1,i=1,2,...,m求得最優(yōu)解W*和b*；分類函數(shù)為

g（X）=（W*-X）+b*從以上分析過(guò)程可知，對(duì)于任意學(xué)習(xí)樣本X，有ng（X）＞1,貝uX.GCg（x\）＜-1,貝XGC2學(xué)習(xí)樣本是實(shí)際模式的抽樣或特例，工作中的實(shí)際模式可能超過(guò)學(xué)習(xí)樣本的分布范圍。如果能夠預(yù)測(cè)到實(shí)際模式的分布，并且根據(jù)其分布確定分類函數(shù)，我們稱之為“預(yù)測(cè)最優(yōu)”。但實(shí)際上是很難做到的，無(wú)論我們得到多大規(guī)模的樣本都總是實(shí)際問(wèn)題的抽樣或特例，以這些數(shù)據(jù)所做的任何估計(jì)都只是以局部推測(cè)全局。以上得到的“支持向量機(jī)”取兩類樣本之間最大邊帶的中心為分類函數(shù)，顯然是對(duì)現(xiàn)有學(xué)習(xí)樣本的最佳分類。盡管這樣的分類函數(shù)未必是“預(yù)測(cè)最優(yōu)”，但這種方法比器硬“限幅函數(shù)單個(gè)神經(jīng)元”只能得到一個(gè)可行的分類函數(shù)來(lái)說(shuō)，有更強(qiáng)的合理性。我們稱支持向量機(jī)獲得的分類函數(shù)具有“結(jié)構(gòu)最優(yōu)”性。從結(jié)構(gòu)上還可以看出，最寬邊界只取決于個(gè)別樣本，大量位于直線/和直線112外邊的樣本對(duì)最寬邊界并沒(méi)有影響。稱恰好位于直線1和直線12上的樣本為“支持向量”。這正是這種算法稱為“支持向量機(jī)”的原因。12兩類線性可分支持向量機(jī)的求解現(xiàn)在回到兩類線性可分的分類機(jī)問(wèn)題上。兩類線性可分的支持向量機(jī)問(wèn)題是一個(gè)二次規(guī)劃問(wèn)題(目標(biāo)函數(shù)上多了一個(gè)平方)，二次規(guī)劃問(wèn)題是典型的凸優(yōu)化問(wèn)題，可以轉(zhuǎn)換成拉格朗日(Lagrange)問(wèn)題求解。定義拉格朗日函數(shù)L(w,b,a)=i|W||2-亳a(y-((工-w)+b)-1)其中，a>0為L(zhǎng)agrange乘子。由KKT1條件，函數(shù)在按點(diǎn)位只滿足：

丈七七丈七七i=1將上式帶入月拉格朗日函數(shù)，max

as.t.=0w=^ayxi=1得到問(wèn)題的Wolf對(duì)偶問(wèn)題：V1w乙a——乙乙yyaaX-Xi2ijijiji=1i=1j=1&a=0iii=1a.>0,i=1,2,...,m這是一個(gè)標(biāo)準(zhǔn)的二次規(guī)劃問(wèn)題(QP)，是在一個(gè)不等式約束條件下進(jìn)行二次函數(shù)尋優(yōu)。該問(wèn)題存在唯一解?？汕蟪觯簃W*=2ya*尤ib*=y-(W*)tx,kgSV，根據(jù)已經(jīng)得到的W和支持向量求出b并構(gòu)造分類函數(shù)，并得到最優(yōu)分類超平面：f(x,W*,b*)=sgn((W*)Tx+b*)k從線性約束凸優(yōu)化問(wèn)題的幾何意義可知，只有與a“〉0相對(duì)應(yīng)的那些約束條件才是有效的。對(duì)應(yīng)于支持向量機(jī)問(wèn)題，這些a.所對(duì)應(yīng)的學(xué)習(xí)樣本yn)是支持向量，它們恰好位于分類邊帶線上，兩條邊帶線為：""l:(W-X)+b=1l::(W-X)+b=-1其余與ak=0對(duì)應(yīng)的約束條件中的樣本點(diǎn)，都位于上邊帶〈之上或下邊帶I?之下，這些點(diǎn)的存在并不影響分類函數(shù)的位置。1廣義線性支持向量機(jī)(近似線性可分情況)近似線性可分支持向量機(jī)，又叫軟間隔支持向量機(jī)(SoftmarginSVM)，是在線性可分的情況下建立起來(lái)的.在最優(yōu)化問(wèn)題上添加松弛因子&i>0和懲罰因子C，允許有錯(cuò)分樣本存在.在這里我們考慮一次損失函數(shù)的SVM，原始問(wèn)題構(gòu)造為：min—W2+C黨&w.b2is.t.y-[(W-X)+b]-1+&>0,i=1,2,...,m&.>0ii

該問(wèn)題的Wolf對(duì)偶問(wèn)題如下:max

%?V1VV““Ea——EEyyaaX?Xi2ijijiji=1i=1j=1s.t.Y.ya=0ii0<a>C,i=1,2,,max

%?s.t.模型與求解過(guò)程同標(biāo)準(zhǔn)方法相似。線性不可分支持向量機(jī)實(shí)際應(yīng)用中，一般分類問(wèn)題在定義的特漲空間中不一定線性可分，把問(wèn)題轉(zhuǎn)為已知問(wèn)題，降低維空間中的數(shù)據(jù)特征X映射到高維線性特征空間F中，XT中(X)然后在高位空間中求線性最優(yōu)超平面。這時(shí)對(duì)偶形式的目標(biāo)函數(shù)變?yōu)?Q(a)=Ea-1EEyyaa甲(X)?甲(X)^i2..ijiji.j對(duì)偶形式中出現(xiàn)兩向量的內(nèi)積運(yùn)算，Vapnik等人提出采用滿足Mercer條件的核函數(shù)K(X,X.)來(lái)替換內(nèi)及運(yùn)算，即K(X,X.)=(甲(X).甲(X.))實(shí)現(xiàn)非線性軟間隔分類，成立的Mercer條件：影射中。以及和表達(dá)式：K(X?Y)=Ep(X)p(r)i存在的條件是，當(dāng)且僅當(dāng)對(duì)于任意的g(x)70，滿足:JK(X?Y)g(X)g(Y)dXdY>0，fg(x)2dxvs常用的核函數(shù)有:多項(xiàng)式內(nèi)核：K(X,X.)=((X-X.)+1)d，所得到的是d階多項(xiàng)式分類器f(X,a)=sgn(Eay(X?X.+1)d+b)i徑向基函數(shù)內(nèi)核RBF：經(jīng)典徑向基函數(shù)使用線面的判定規(guī)則:f(X,a)=sgn(EaKg(IX?X.I)-b)i

其中K5(IX,..X「)取決于兩個(gè)向量之間的距離，其為非負(fù)單調(diào)函數(shù)，通用的判定規(guī)則采用高斯徑向基函數(shù)：K(IX-XI)=exp(―"*—X』')，參數(shù)由SW訓(xùn)5jC2練算法自動(dòng)確定。多層感知機(jī)：支持向量機(jī)采用Sigmoid函數(shù)作為內(nèi)及運(yùn)算，這時(shí)就實(shí)現(xiàn)了包好一個(gè)隱層的多層感知機(jī)，隱層節(jié)點(diǎn)數(shù)目有訓(xùn)練蘇三發(fā)自動(dòng)確定，媽祖Mercer條件的Sigmoid函數(shù)為：K(X.,X.)=tanh(scalex(X.-X)—offset)，其中，scale和offset是事先確定的參數(shù)，這里支持向量對(duì)應(yīng)于第一城，而Lagrange乘子對(duì)應(yīng)于相應(yīng)的權(quán)值。MLP的優(yōu)點(diǎn)是不存在困擾神經(jīng)網(wǎng)絡(luò)局部極小問(wèn)題。雙曲正弦核函數(shù)：K(X-X.)=tanh(XX-X.-5)，確定核函數(shù)后，此時(shí)的對(duì)偶問(wèn)題目標(biāo)為：''—1無(wú)力,i=12i,i=1利用核函數(shù)，兩類非線性可分問(wèn)題轉(zhuǎn)化成了線性問(wèn)題。相應(yīng)的分類函數(shù)為g(X)=IlayK(X,X)—尤ayK(X,X)+yiiiiiikki=1i=1可見，正因?yàn)樵谥С窒蛄繖C(jī)的Wolfe對(duì)偶表達(dá)形式中，只出現(xiàn)了學(xué)習(xí)樣本的點(diǎn)積運(yùn)算，才使得我們有可能運(yùn)用核函數(shù)的方法解決非線性分類問(wèn)題。這正是支持向量機(jī)引起人們廣泛關(guān)注的意義所在。K?,,X.)成立的Mercer條件。多類情況支持向量機(jī)方法最初是針對(duì)二類別的分類而提出的，如何將其有效的推廣到多類別分類仍是當(dāng)前支持向量機(jī)研究的重要內(nèi)容之一.目前，對(duì)于多類分類問(wèn)題,SVM的解決途徑有兩種:一種是通過(guò)構(gòu)造多個(gè)SVM二值分類器并將它們組合起來(lái)實(shí)現(xiàn)多類分類，例如one2against2rest,one2against2one和DAG-SVM.雖然這三種方法是當(dāng)前最常用且性能較優(yōu)的，但one2against2rest和one2against2one方法的泛化誤差是無(wú)界的.再者,one2against2one所需構(gòu)造的子分類器的數(shù)量關(guān)于類別數(shù)k成超線性增長(zhǎng)，共k(k—1)/2個(gè),且在測(cè)試階段，都必須計(jì)算所有子分類判據(jù)函數(shù).One2against2one方法還有一個(gè)最明顯的缺點(diǎn)就是,每個(gè)子分類器必須都要非常仔細(xì)地調(diào)整，如果某個(gè)子分類器不規(guī)范化,則整個(gè)分類系統(tǒng)將趨于過(guò)學(xué)習(xí).DAGSVM方法解決了不可分區(qū)域問(wèn)題，而且不一定要計(jì)算所有的子分類判決函數(shù)，但各個(gè)子分類器在有向無(wú)環(huán)圖中的位置也會(huì)對(duì)分類系統(tǒng)產(chǎn)生較大的影響。常見的支持向量機(jī)實(shí)現(xiàn)技術(shù)上面只是討論了SVM的原理和一般模型，但這只是理論上的數(shù)學(xué)模型，要想應(yīng)用，要知道它的實(shí)現(xiàn)技術(shù)，通常有：Chunking塊算法Decomposing算法SMO算法實(shí)驗(yàn)實(shí)驗(yàn)一、兩類線性可分的SVM算法給定學(xué)習(xí)樣本：|XiX2…XJ，其中，XeRm是已知類別M維特征矢…'量，七e"-1｝是X.的類別值。這里介紹兩類可分情況下的SVM算法的MatLab語(yǔ)言編程實(shí)現(xiàn)方法。利用MatLab計(jì)算，使用SMO算法訓(xùn)練學(xué)習(xí)樣本步驟如下:生成學(xué)習(xí)樣本數(shù)據(jù)部分代碼如下：randn('seed',50);m=[00;1.21.2]';S=0.2*eye(2);points_per_class=[200200];X1=mvnrnd(m(:,1),S,points_per_class(1))';X1=[X1mvnrnd(m(:,2),S,points_per_class(2))'];y1=[ones(1,points_per_class(1))-ones(1,points_per_class(2))];樣本圖示如下：kpar1=0;kpar2=0;C=0.1;tol=0.001;steps=100000;eps=10A(-10);method=0;[alpha,w0,w,evals,stp,glob]=SMO2(X1',y1',kernel,kpar1,kpar2,C,tol,steps,eps,method);%%computetheclassificationerroronthetrainingset,X1%計(jì)算錯(cuò)誤分類數(shù)Pe_tr=sum((2*(w*X1-w0>0)-1).*y1<0)/length(y1)%%toplottheclassifierhyperplaneaswellasthemarginlinesglobalfigt4;繪圖figt4=2;svcplot_book(X1',y1',kernel,kpar1,kpar2,alpha,-w0);%%counttheSV計(jì)算支持向量數(shù)sup_vec=sum(alpha>0)%%computethemaring計(jì)算分類間隔marg=2/sqrt(sum(w.A2))分類效果圖如下上圖為兩類近似線性可分學(xué)習(xí)樣本的分類結(jié)果，紅色為-1類，藍(lán)色為1類，圈起來(lái)的為松弛的樣本點(diǎn)，計(jì)算結(jié)果得錯(cuò)誤分率為0.0225；支持向量個(gè)數(shù)為82個(gè)（共400學(xué)習(xí)樣本）；實(shí)驗(yàn)數(shù)據(jù)表明SMO2算法用較好的分類效果，最大分類間隔為0.9410。實(shí)驗(yàn)二、使用matlab自帶函數(shù)fmincon求解的簡(jiǎn)單例子對(duì)于，不考慮非線性分類引入核函數(shù)的情況，也不考慮推廣條件下引入PenaltyLoss的情況。問(wèn)題描述：平面上有如下點(diǎn)A=[11.5;21.5;31.5;41.5;10.5;20.5;30.5;40.5]及其對(duì)應(yīng)的標(biāo)號(hào)flag=[1111-1-1-1-1];用SVM方法構(gòu)造一個(gè)決策函數(shù)實(shí)現(xiàn)正確分類。如果我們?cè)诙S坐標(biāo)上描點(diǎn)，就會(huì)發(fā)現(xiàn)這是個(gè)很簡(jiǎn)單的線性可分問(wèn)題。實(shí)現(xiàn)方法，用SVM的對(duì)偶問(wèn)題，轉(zhuǎn)換為Matlab的有約束非線性規(guī)劃問(wèn)題。結(jié)果分析：實(shí)驗(yàn)數(shù)據(jù)給的是線性可分析情況，且數(shù)據(jù)樣本點(diǎn)較少，這里不再畫圖表示，求得w=[0,2];b=-2;即最終的決策函數(shù)為：f=sign([0,2]*xT-2)可以驗(yàn)證，這個(gè)學(xué)習(xí)到的決策函數(shù)能夠?qū)@些平面上的點(diǎn)實(shí)現(xiàn)很好的分類。代碼如下functionf=ffsvm(x)A=[11.5;21.5;31.5;41.5;10.5;20.5;30.5;40.5];flag=[1111-1-1-1-1];fori=1:1:length(A)forj=1:1:length(A)normA(i,j)=A(i,:)*A(j,:)';normFlag(i,j)=flag(1,i)*flag(1,j);endendf=0;fori=1:1:length(A)forj=1:1:length(A)f=f+1/2*(normA(i,j)*x(i)*x(j)*normFlag(i,j));endf=f-x(i);end在命令窗口輸入：Aeq=[1111-1-1-1-1];beq=0;lb=[00000000];調(diào)用MatLab內(nèi)置優(yōu)化函數(shù)fmincon；[x,favl,exitflag]=fmincon(@ffsvm,x0,[],[],Aeq,beq,lb,[])得到如下結(jié)果：Optimizationterminatedsuccessfully:Magnitudeofdirectionalderivativeinsearchdirectionlessthan2*options.TolFunandmaximumconstraintviolationislessthanoptions.TolConActiveConstraints:1x=0.50000.50000.50000.50000.50000.50000.50000.5000favl=-2.0000exitflag=1結(jié)果：x的分量都不為0,說(shuō)明這些點(diǎn)都是支持向量；計(jì)算w；w=[00];fori=1:length(A)w=w+flag(i)*x(i)*A(i,:);end計(jì)算b；b=0;fori=1:8b=b-flag(i)*x(i)*normA(i,1);endb=flag(1)+b；實(shí)驗(yàn)三、支持向量機(jī)多類分類使用實(shí)驗(yàn)數(shù)據(jù)為“鳶尾屬植物數(shù)據(jù)集”，核函數(shù)為徑向基核函數(shù)(RBF)，其參數(shù)由訓(xùn)練得到。誤差評(píng)測(cè)標(biāo)準(zhǔn)為K折交叉確認(rèn)誤差。用quadprog函數(shù)(matlab中一個(gè)求解二次規(guī)劃的函數(shù))實(shí)現(xiàn)C-SVC來(lái)進(jìn)行分類，通過(guò)適當(dāng)?shù)膮?shù)設(shè)置，可以利用quadprog函數(shù)實(shí)現(xiàn)C-SVC三類問(wèn)題的分類方法——將三類問(wèn)題轉(zhuǎn)化為三個(gè)兩類問(wèn)題，使用一對(duì)多法(one-against-rest)，分別求出相應(yīng)的決策函數(shù)即可(優(yōu)點(diǎn)：方法簡(jiǎn)單易行；缺點(diǎn)：容易形成死區(qū))；結(jié)果分析：因使用四維數(shù)據(jù)，這里不再圖示，對(duì)于兩兩分類，效果較明顯，但每個(gè)分類器的訓(xùn)練都是將全部的樣本作為訓(xùn)練樣本(一部分測(cè)試樣本)，這樣需要求解K個(gè)二次規(guī)劃問(wèn)題，因?yàn)槊總€(gè)支持向量機(jī)的訓(xùn)練速度隨著訓(xùn)練樣本的數(shù)量的增加急劇減慢，估測(cè)是這種尋來(lái)呢的時(shí)間較長(zhǎng)；第二個(gè)缺點(diǎn)是如果以兩類分類器的輸出去符號(hào)函數(shù)，則有可能存在測(cè)試樣本同時(shí)屬于多類或不屬于任何一類的區(qū)域，本次實(shí)驗(yàn)驗(yàn)中，選取80%的樣本為訓(xùn)練樣本，20%的樣本為測(cè)試樣本；單個(gè)分類器的錯(cuò)誤率分別為0；0.2；0.2左右，整體分類率在0.96左右，分類效果較好。代碼如下：functionclass3clear,clcloadfisheriris.mat;%Loadthedataandselectfeaturesforclassificationdata=meas;%GetthesizeofthedataN=size(data,1);%ExtracttheSetosaclassspe={'Iris-setosa','Iris-versicolor','Iris-virginica'};fori=1:3groups_temp=ismember(species,spe(i));%versicolor,virginica,setosa[misCla(i),RR(i)]=fenlei(groups_temp,data,N);endmisCla,RRsum(misCla)endfunction[miscla,R]=fenlei(groups_temp,data,N)%convertthegroupto1&-1groups=2*groups_temp-ones(N,1);indices=crossvalind('Kfold',groups);ErrorMin=1;forr=1:1:5forC=1:1:5ErrorNum=0;forii=1:5%UseK-foldtogettraindataandtestdatatest=(indices==ii);train=?test;traindata=data(train,:);%NpA-Ey%Ytraingroup=groups(train,:);%NpA-Ey%YAa±dtrainlength=length(traingroup);%NpA-Ey%YoDjtestdata=data(test,:);%^i2aEy%Ytestgroup=groups(test,:);%^i2aEy%YAa±dtestlength=length(testgroup);%^i2aEy%Y'0Dj%GetmatrixHoftheproblemiBE1%^Id?u°~Ey%0OOkfun=[];fori=1:1:trainlengthforj=1:1:trainlength%rbfkernelkfun(i,j)=exp(-1/(rA2)*(traindata(i,:)-traindata(j,:))*(traindata(i,:)-traindata(j,:))');endend%countparametersofquadprogfunctionH=(traingroup*traingroup').*kfun;xstart=zeros(trainlength,1);f=-ones(trainlength,1);Aeq=traingroup';beq=0;lb=zeros(trainlength,1);ub=C*o