SVM原理及應(yīng)用舉例

1、SVM原理及應(yīng)用舉例陳朝虹 碩班 201220109072SVM例子% 四個(gè)樣本-2,2,2,-2,-2,-2,2,2%構(gòu)造輸入data=1 1 -1 -1;-2 2 -2 2;2-2 -2 2;%quadprogH=zeros(4,4);tag=data(1,:);for i=1:4for j=1:4k=(1+data(2:end,i)'*data(2:end,j)A2;,前兩個(gè)屬第一類，后兩個(gè)屬第二類求解二次優(yōu)化問題%多項(xiàng)式kernal徑向基RBF kernal%k=exp(-norm(data(2:end,i)-data(2:end,j)A2/2); %H(i,j)=tag(i)

2、*tag(j)*k; endendC = 1;咆個(gè)權(quán)重設(shè)置最大的允許值f = -1*ones(4,1);%二次規(guī)劃中的 fA =;b =;Aeq = tag;beq = 0;lb = zeros(4,1);%lb和 ub表示 sum (alpha*yi ) =0ub = C*ones(4,1);a0 = zeros(4,1);%所有權(quán)重的初值% 下使用二次規(guī)劃算法調(diào)用quadprog a,fval,eXitflag,output,lambda=%quadprog(H,f,A,b,Aeq,beq,lb,ub,a0,options)力求解min1/2xT*H*x+fT*x由此我們把對偶問題加上一個(gè)

3、負(fù)號原來求最大變成求最小值options = optimset;% Options是用來控制算法的選項(xiàng)參數(shù)的向量options.LargeScale = 'off'options.Display ='off'a,fval,eXitflag,output,lambda=quadprog(H,f,A,b,Aeq,beq,lb,ub,a0,options);% 求解bb=zeros(1,4);for i=1:4for j=1:4k=(1+data(2:end,i)'*data(2:end,j)A2;% 多項(xiàng)式 kernal%k=exp(-norm(data(2

4、:end,j)-data(2:end,i)A2/2); %徑向基 RBF kernalb(i)=b(i)+a(i)*tag(i)*k; end end b=mean(b);% 輸出分類結(jié)果result=zeros(1,4); for i=1:4for j=1:4k=(1+data(2:end,i)'*data(2:end,j)A2;% 多項(xiàng)式 kernal%k=exp(-norm(data(2:end,j)-data(2:end,i)A2/2); %徑向基 RBF kernalresult(i)=result(i)+a(i)*tag(i)*k+b; end end程序運(yùn)行結(jié)果米用多項(xiàng)式

5、核：系數(shù)為a=0.00780.00780.00780.0078分類結(jié)果：result =1.03121.0312-1.0313-1.0313采用徑向基RBF核：系數(shù)為a =1.00001.00001.00001.0000分類結(jié)果:result =1.00071.0007-1.0007-1.0007SVM理論基礎(chǔ)如上圖所示，有一堆訓(xùn)練數(shù)據(jù)的正負(fù)樣本，標(biāo)記為:（與M，"1/ M e 1，玉£衣成假設(shè)有一個(gè)超平面 H:3, M+ 3=0可以把這些樣本正確無誤地分割開來，同時(shí)存在兩個(gè)平行于H的超平面 H1和H2:使離H最近的正負(fù)樣本剛好分別落在H1和H2上，這樣的樣本就是支持向量。

6、那么其他所有的訓(xùn)練樣本都將位于 H1和H2之外，也就是滿足如下約束：州西 1 for 盟-1州西+3K-1 = -1寫成統(tǒng)一的式子就是:yj (w +&)-1之0(1)而超平面H1和H2的距離可知為:M argjw = 2/MSVM的任務(wù)就是尋找這樣一個(gè)超平面H把樣本無誤地分割成兩部分，并且使 H1和H2的距離最大。要找到這樣的超平面，只需最大化間隔Margin ,也就是最小化。于是可以構(gòu)造如下的條件極值問題：min囪1 之0 （2）對于不等式約束的條件極值問題，可以用拉格朗日方法求解。而拉格朗日方程的構(gòu)造規(guī)則是：用約束方程乘以非負(fù)的拉格朗日系數(shù)，然后再從目標(biāo)函數(shù)中減去。于是得到拉格朗

7、日方程如下：其中： 3 (4) 那么我們要處理的規(guī)劃問題就變?yōu)?min max £ （用瓦 珥）"上叫“ '/（5）上式才是嚴(yán)格的不等式約束的拉格朗日條件極值的表達(dá)式。對于這一步的變換，很多文章都沒有多做表述，或者理解有偏差，從而影響了讀者后續(xù)的推演。在此我將詳細(xì)地一步步推導(dǎo)，以解困惑。（5）式是一個(gè)凸規(guī)劃問題，其意義是先對“求偏導(dǎo)，令其等于 0消掉a ,然后再對w和b求L的最小值。要直接求解（5）式是有難度的，通過消去拉格朗日系數(shù)來化簡方程，為此我們把（5）對我們的問題無濟(jì)于事。 所幸這個(gè)問題可以通過拉格朗日對偶問題來解決, 式做一個(gè)等價(jià)變換：=max minin

8、£ （叫瓦科）wj>上式即為對偶變換，這樣就把這個(gè)凸規(guī)劃問題轉(zhuǎn)換成了對偶問題:max min口 wf （6）其意義是：原凸規(guī)劃問題可以轉(zhuǎn)化為先對 對a求L的最大值。下面我們就來求解（ 式有：w和b求偏導(dǎo)，令其等于 0消掉w和b,然后再6）式，為此我們先計(jì)算 w和b的偏導(dǎo)數(shù)。由（3）肛dw龍（的,瓦內(nèi)）db為了讓L在w和b上取到最小值，令（7）式的兩個(gè)偏導(dǎo)數(shù)分別為 0,于是得到:Z%乂= 0z（8）將（8）代回（3）式，可得:1 口f吧i £（電瓦q）=彳同-w2叩3-匯玨M 十二? /i-ii-i-i3二一聞I -楂.-匕-0+£鳴2 j-i上喝-刎i-i

9、i 工 工二 !一萬二工巧丐兇為卜弓）I E Z37（9）再把（9）代入（6）式有:max mm £ （網(wǎng)友 0；） = max<輯額>0i工二%一5工工當(dāng)必匕（不勺） i-11i-l j-1考慮到（8）式，我們的對偶問題就變?yōu)?L工m招2一不工匯烏叩必卜勺卜鼻 j-i -j-i、寸一£ sl-二q,=02«1%之0、（11）上式這個(gè)規(guī)劃問題可以直接從數(shù)值方法計(jì)算求解。需要指出的一點(diǎn)是，（2）式的條件極值問題能夠轉(zhuǎn)化為（ 含著一個(gè)約束，即：叫G一1）=。（這個(gè)約束是這樣得來的，如果（2）和（5）等效，必有:m把（3）式代入上式中，得到：片M n m跨7|洲一£ R （普1不+方） 11）= ：；H -m鬲/ 西，InJ化簡得到：j'm討Z% （無卜口卜0'一 g（13）又因?yàn)榧s束（1）式和（4）式，有：（10）5）式的凸規(guī)劃問題，其中隱所以要使（13）式成立，只有令由此得到（12）式的約束。該約束的意義是：如果一個(gè)