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

1、11G Rm、 n應(yīng)有y = 1 ；若X屬于七類，則對(duì)應(yīng)有y對(duì)于任給的未知模式，有I g(X)0, X G C1? (X)0, X G C2式中sgn ()為符號(hào)函數(shù)，g(X)稱為決策或者s g (X)= 1, s g n?( x)= -1,(分類)函數(shù)。X G C1X G C2支持向量機(jī)原理與實(shí)驗(yàn)支持向量機(jī)分類問題支持向量機(jī)是基于統(tǒng)計(jì)的學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化(SRM )原則的機(jī)器學(xué) 習(xí)。而(SRM )原則是針對(duì)二值分類問題(兩類的分類問題)提出的，因此，關(guān)于 SVM的基本問題是二值分類問題。設(shè)有兩類模式C和C，T = (X ,y )(X , y )(X , y )是從模式C121122N

2、N1和C中抽樣得到的訓(xùn)練集，其中X G Rm、y G l, -1。若X屬于C類，則對(duì)2nnn1=-1 ；。尋求rm上的一個(gè)實(shí)函數(shù)g(x)，我們稱解決上述問題的方法為“分類機(jī)”。當(dāng)g(X )為線性函數(shù)時(shí)，稱為線性 分類機(jī)；當(dāng)g(X )為非線性函數(shù)時(shí)，稱為非線性分類機(jī)。對(duì)于這個(gè)二維問題，線 性分類機(jī)的作用就是要在匕和C2之間尋找一條分類線l，其表達(dá)式為g(X )。我 們已經(jīng)熟知，在高維情況下g (X 1是一個(gè)超平面。對(duì)于線性可分的兩類模式C1和C2而言，能夠準(zhǔn)確將其分開的直線不是唯一 的。假設(shè)有直線l可以無誤地將C和C2兩類模式分開，另有直線lL和直線l2與l之 間的間距為k，與l2之間形成一個(gè)沒

3、有學(xué)習(xí)樣本的帶狀區(qū)域，不妨稱該帶狀區(qū) 域?yàn)椤斑厧?M arg in) ”:而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 = 1X g C1 gX ) 1, y = 1 g(X )= (W X) + b 1上式對(duì)于任何學(xué)習(xí)樣本都必須成立。在此前提下尋在選擇分類線的過程中找最寬邊界的問題，最后可以表示成一個(gè)約束優(yōu)化問題: TOC o 1-5

4、h z min1-WW b2s.t.y . (W X.) + b 1, i = 1,2,., m1WW 2y. (W X.) + b 1,i = 1,2,.,m這里目標(biāo)函數(shù)中的1沒有其他意義，只是為了下一步導(dǎo)出求解方法時(shí)方便。即 2minW .bs.t.求得最優(yōu)解W *和b * ；分類函數(shù)為g（X） = （W * - X） + b*從以上分析過程可知，對(duì)于任意學(xué)習(xí)樣本X，有ng（X ） 1,貝uX. G Cg（x） -1,貝X G C2學(xué)習(xí)樣本是實(shí)際模式的抽樣或特例，工作中的實(shí)際模式可能超過學(xué)習(xí)樣本的 分布范圍。如果能夠預(yù)測(cè)到實(shí)際模式的分布，并且根據(jù)其分布確定分類函數(shù)，我 們稱之為“預(yù)測(cè)最優(yōu)”

5、。但實(shí)際上是很難做到的，無論我們得到多大規(guī)模的樣本都 總是實(shí)際問題的抽樣或特例，以這些數(shù)據(jù)所做的任何估計(jì)都只是以局部推測(cè)全 局。以上得到的“支持向量機(jī)”取兩類樣本之間最大邊帶的中心為分類函數(shù)，顯然 是對(duì)現(xiàn)有學(xué)習(xí)樣本的最佳分類。盡管這樣的分類函數(shù)未必是“預(yù)測(cè)最優(yōu)”，但這種 方法比器硬“限幅函數(shù)單個(gè)神經(jīng)元”只能得到一個(gè)可行的分類函數(shù)來說，有更強(qiáng)的 合理性。我們稱支持向量機(jī)獲得的分類函數(shù)具有“結(jié)構(gòu)最優(yōu)”性。從結(jié)構(gòu)上還可以看出，最寬邊界只取決于個(gè)別樣本，大量位于直線/和直線 112外邊的樣本對(duì)最寬邊界并沒有影響。稱恰好位于直線1和直線12上的樣本為“支 持向量”。這正是這種算法稱為“支持向量機(jī)”的原因

6、。12兩類線性可分支持向量機(jī)的求解現(xiàn)在回到兩類線性可分的分類機(jī)問題上。兩類線性可分的支持向量機(jī)問題是 一個(gè)二次規(guī)劃問題(目標(biāo)函數(shù)上多了一個(gè)平方)，二次規(guī)劃問題是典型的凸優(yōu)化 問題，可以轉(zhuǎn)換成拉格朗日(Lagrange )問題求解。定義拉格朗日函數(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ù)，maxas.t.=0 w = a y xi=1得到問題的Wolf對(duì)偶問題：V 1 w乙a乙乙yy a a X - Xi 2 i j i j i j i=1i=1

7、j =1& a = 0iii=1a. 0, i = 1, 2, ., m這是一個(gè)標(biāo)準(zhǔn)的二次規(guī)劃問題(QP)，是在一個(gè)不等式約束條件下進(jìn)行二次 函數(shù)尋優(yōu)。該問題存在唯一解?？汕蟪觯簃W * = 2 y a * 尤ib * = y - (W *) t x , k g SV，根據(jù)已經(jīng)得到的W和支持向量求出b并構(gòu)造分類函數(shù)，并得到最優(yōu)分類超平面：f (x, W *, b *) = sgn( W *)T x + b *)k從線性約束凸優(yōu)化問題的幾何意義可知，只有與a “0相對(duì)應(yīng)的那些約束條 件才是有效的。對(duì)應(yīng)于支持向量機(jī)問題，這些a.所對(duì)應(yīng)的學(xué)習(xí)樣本yn)是支 持向量，它們恰好位于分類邊帶線上，兩條邊帶

8、線為：l :(W - X) + b = 1l : (W - X) + b = -1其余與a k =0對(duì)應(yīng)的約束條件中的樣本點(diǎn)，都位于上邊帶之上或下邊帶I? 之下，這些點(diǎn)的存在并不影響分類函數(shù)的位置。1廣義線性支持向量機(jī)(近似線性可分情況)近似線性可分支持向量機(jī)，又叫軟間隔支持向量機(jī)(SoftmarginSVM)，是在 線性可分的情況下建立起來的.在最優(yōu)化問題上添加松弛因子&i 0和懲罰因子 C，允許有錯(cuò)分樣本存在.在這里我們考慮一次損失函數(shù)的SVM，原始問題構(gòu)造 為：min W 2 + C 黨 &w .b2is.t. y - (W - X ) + b -1 + & 0,i = 1,2,.,m&

9、. 0ii該問題的Wolf對(duì)偶問題如下:max%V 1VV “ “ Ea EE y y a a X X i 2 i j i j i j i=1i=1 j =1s.t.Y.y a = 0 ii0 C, i = 1, 2, m模型與求解過程同標(biāo)準(zhǔn)方法相似。線性不可分支持向量機(jī)實(shí)際應(yīng)用中，一般分類問題在定義的特漲空間中不一定線性可分，把問題轉(zhuǎn) 為已知問題，降低維空間中的數(shù)據(jù)特征X映射到高維線性特征空間F中， X T中(X )然后在高位空間中求線性最優(yōu)超平面。這時(shí)對(duì)偶形式的目標(biāo)函數(shù)變 為:Q (a) = E a -1E E y y a a 甲(X ) 甲(X ) i 2 . i j i j i.j對(duì)偶

10、形式中出現(xiàn)兩向量的內(nèi)積運(yùn)算，Vapnik等人提出采用滿足Mercer條件 的核函數(shù)K(X , X .)來替換內(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)7 0，滿足:J K (X Y )g (X )g (Y )dXdY 0，f g (x )2dx vs常用的核函數(shù)有: 多項(xiàng)式內(nèi)核：K(X, X .) = (X - X. ) + 1)d，所得到的是d階多項(xiàng)式分類器f (X, a) = sgn( E a y (X X . +1) d

11、 + b)i徑向基函數(shù)內(nèi)核RBF：經(jīng)典徑向基函數(shù)使用線面的判定規(guī)則:f (X, a) = sgn( E a Kg (I X X . I) - b)i其中K5(IX,. . X)取決于兩個(gè)向量之間的距離，其為非負(fù)單調(diào)函數(shù)，通用的 判定規(guī)則采用高斯徑向基函數(shù)：K (I X - X I) = exp(* X)，參數(shù)由SW 訓(xùn)5jC 2練算法自動(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 ) o

12、ffset)，其中，scale和offset是事先確定的參數(shù)，這里支持向量對(duì)應(yīng)于第一城，而 Lagrange乘子對(duì)應(yīng)于相應(yīng)的權(quán)值。MLP的優(yōu)點(diǎn)是不存在困擾神經(jīng)網(wǎng)絡(luò)局部極小 問題。雙曲正弦核函數(shù)：K(X - X.) = tanh(XX - X. - 5)，確定核函數(shù)后，此時(shí)的對(duì)偶問 題目標(biāo)為：1無力, i=12i=1 j =1利用核函數(shù)，兩類非線性可分問題轉(zhuǎn)化成了線性問題。相應(yīng)的分類函數(shù)為g(X )= Il a y K(X , X )尤 a y K(X , X )+ yi i ii i i k ki=1i=1可見，正因?yàn)樵谥С窒蛄繖C(jī)的Wolfe對(duì)偶表達(dá)形式中，只出現(xiàn)了學(xué)習(xí)樣本的 點(diǎn)積運(yùn)算，才使得

13、我們有可能運(yùn)用核函數(shù)的方法解決非線性分類問題。這正是支 持向量機(jī)引起人們廣泛關(guān)注的意義所在。K,X .)成立的Mercer條件。多類情況支持向量機(jī)方法最初是針對(duì)二類別的分類而提出的，如何將其有效的推廣到 多類別分類仍是當(dāng)前支持向量機(jī)研究的重要內(nèi)容之一.目前，對(duì)于多類分類問 題,SVM的解決途徑有兩種:一種是通過構(gòu)造多個(gè)SVM二值分類器并將它們組合 起來實(shí)現(xiàn)多類分類，例如one2against2rest,one2against2one和DAG-SVM.雖然這三 種方法是當(dāng)前最常用且性能較優(yōu)的，但one2against2rest和one2against2one方法的 泛化誤差是無界的.再者,one

14、2against2one所需構(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)將趨于過學(xué) 習(xí).DAGSVM方法解決了不可分區(qū)域問題，而且不一定要計(jì)算所有的子分類判決函數(shù)，但各個(gè)子分類器在有向無環(huán)圖中的位置也會(huì)對(duì)分類系統(tǒng)產(chǎn)生較大的影響。常見的支持向量機(jī)實(shí)現(xiàn)技術(shù)上面只是討論了 SVM的原理和一般模型，但這只是理論上的數(shù)學(xué)模型，要 想應(yīng)用，要知道它的實(shí)現(xiàn)技術(shù)，通常有：Chunking塊算法Decom

15、posing 算法SMO算法實(shí)驗(yàn)實(shí)驗(yàn)一、兩類線性可分的SVM算法給定學(xué)習(xí)樣本：| Xi X 2X J，其中，X e R m是已知類別M維特征矢 量，七e -1是X .的類別值。這里介紹兩類可分情況下的SVM算法的MatLab 語言編程實(shí)現(xiàn)方法。利用MatLab計(jì)算，使用SMO算法訓(xùn)練學(xué)習(xí)樣本步驟如下:生成學(xué)習(xí)樣本數(shù)據(jù)部分代碼如下：randn(seed,50);m=0 0;1.2 1.2;S=0.2*eye(2);points_per_class=200 200;X1=mvnrnd(m(:,1),S,points_per_class(1);X1=X1 mvnrnd(m(:,2),S,points

16、_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);% compute the classification error on the training set, X1%計(jì)算錯(cuò)誤分類數(shù)Pe_tr=su

17、m(2*(w*X1-w00)-1).*y10)% compute the maring計(jì)算分類間隔marg=2/sqrt(sum(w.A2)分類效果圖如下上圖為兩類近似線性可分學(xué)習(xí)樣本的分類結(jié)果，紅色為-1類，藍(lán)色為1類， 圈起來的為松弛的樣本點(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ù)的情況，也不考慮推廣條件下引入 Penalty Loss 的情況。問題描述：平面上有如下點(diǎn) A = 1 1.5

18、;2 1.5;3 1.5;4 1.5;1 0.5;2 0.5;3 0.5;4 0.5 及其對(duì)應(yīng)的標(biāo)號(hào)flag = 1 1 1 1 -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)單的線性可分問題。 實(shí)現(xiàn)方法，用SVM的對(duì)偶問題，轉(zhuǎn)換為Matlab的有約束非線性規(guī)劃問題。結(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)很好的分類。 代碼如下function f

19、 = ffsvm(x)A = 1 1.5;2 1.5;3 1.5;4 1.5;1 0.5;2 0.5;3 0.5;4 0.5;flag = 1 1 1 1 -1 -1 -1 -1;for i=1:1:length(A)for j=1:1:length(A)normA(i,j) = A(i,:)*A(j,:);normFlag(i,j) = flag(1,i)*flag(1,j);endendf = 0;for i=1:1:length(A)for j=1:1:length(A)f = f + 1/2*(normA(i,j)*x(i)*x(j)*normFlag(i,j);endf = f -

20、x(i);end在命令窗口輸入：Aeq = 1 1 1 1 -1 -1 -1 -1;beq = 0;lb = 0 0 0 0 0 0 0 0;調(diào)用MatLab內(nèi)置優(yōu)化函數(shù)fmincon；x,favl,exitflag = fmincon(ffsvm,x0,Aeq,beq,lb,)得到如下結(jié)果：Optimization terminated successfully:Magnitude of directional derivative in search direction less than 2*options.TolFun and maximum constraint violation

21、is less than options.TolCon Active Constraints: 1x = 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 favl = -2.0000 exitflag = 1結(jié)果：x的分量都不為0,說明這些點(diǎn)都是支持向量；計(jì)算w；w = 0 0;for i = 1:length(A)w = w + flag(i)*x(i)*A(i,:);end計(jì)算b；b = 0;for i=1:8b = b-flag(i)*x(i)*normA(i,1);endb = flag(1) + b；實(shí)驗(yàn)三、支持向量機(jī)多

22、類分類使用實(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來進(jìn)行分類，通過適當(dāng)?shù)膮?shù)設(shè)置， 可以利用quadprog函數(shù)實(shí)現(xiàn)C-SVC三類問題的分類方法將三類問題轉(zhuǎn)化為 三個(gè)兩類問題，使用一對(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è)試樣本)，這樣需

23、要 求解K個(gè)二次規(guī)劃問題，因?yàn)槊總€(gè)支持向量機(jī)的訓(xùn)練速度隨著訓(xùn)練樣本的數(shù)量 的增加急劇減慢，估測(cè)是這種尋來呢的時(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左右，分類效果 較好。代碼如下：function class3clear ,clcload fisheriris.mat;% Load the data and select features for classification da

24、ta = meas;%Get the size of the dataN = size(data,1);% Extract the Setosa classspe=Iris-setosa,Iris-versicolor,Iris-virginica;for i=1:3groups_temp = ismember(species,spe(i);%versicolor,virginica,setosamisCla(i),RR(i)=fenlei(groups_temp,data,N);endmisCla,RRsum(misCla)endfunction miscla,R=fenlei(groups

25、_temp,data,N)%convert the group to 1 & -1groups = 2*groups_temp - ones(N,1);indices = crossvalind(Kfold, groups);ErrorMin = 1;for r=1:1:5for C=1:1:5ErrorNum = 0;for ii=1:5%Use K-fold to get train data and test data test = (indices = ii); train =test;traindata = data(train,:);%NpA-Ey%Ytraingroup = gr

26、oups(train,:);%NpA-Ey%YAadtrainlength = length(traingroup);%NpA-Ey%Y oDjtestdata = data(test,:);%i2aEy%Ytestgroup = groups(test,:);%i2aEy%YAadtestlength = length(testgroup);%i2aEy%Y0Dj%Get matrix H of the problem iBE1%Idu Ey%0OO kfun =;for i=1:1:trainlengthfor j=1:1:trainlength%rbf kernelkfun(i,j)=e

27、xp(-1/(rA2)*(traindata(i,:)-traindata(j,:)*(traindata(i,:)-traindata(j,:);endend%count parameters of quadprog functionH = (traingroup*traingroup).*kfun;xstart = zeros(trainlength,1);f = -ones(trainlength,1);Aeq = traingroup;beq = 0;lb = zeros(trainlength,1);ub = C*ones(trainlength,1);options=optimset(La