支持向量機(jī)及其編程實(shí)現(xiàn)

支持向量機(jī)及其編程實(shí)現(xiàn)第1頁，課件共35頁，創(chuàng)作于2023年2月SupportVectorMachine支持向量機(jī)2第2頁，課件共35頁，創(chuàng)作于2023年2月相關(guān)參考資料統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)，VladimirN.Vapnik著，張學(xué)工譯，清華大學(xué)出版社，2000.093

BernhardScholkopf,AlexJ.Smola,CHRISTOPHERJ.C.BURGES支持向量機(jī)導(dǎo)論，N.Cristianini,J.Shawe-Taylor著，電子工業(yè)出版社，2004.03SupportVectorClassification.StevenGunn.第3頁，課件共35頁，創(chuàng)作于2023年2月1、支持向量機(jī)可以做什么？4第4頁，課件共35頁，創(chuàng)作于2023年2月支持向量機(jī)的應(yīng)用之一：手寫體數(shù)字識(shí)別1、支持向量機(jī)可以做什么？NIST手寫體數(shù)字的前100個(gè)目前最好的識(shí)別水平：LeNet4

多項(xiàng)式支持向量機(jī)（錯(cuò)誤率<0.7%）5（錯(cuò)誤率<0.8%）第5頁，課件共35頁，創(chuàng)作于2023年2月貝爾實(shí)驗(yàn)室對美國郵政手寫數(shù)字庫進(jìn)行的實(shí)驗(yàn)分類器錯(cuò)誤率人工表現(xiàn)2.5%決策樹C4.516.2%最好的兩層神經(jīng)網(wǎng)絡(luò)5.9%SVM4.0%第6頁，課件共35頁，創(chuàng)作于2023年2月SVM與神經(jīng)網(wǎng)絡(luò)（NN）的對比SVM的理論基礎(chǔ)比NN更堅(jiān)實(shí)，更像一門嚴(yán)謹(jǐn)?shù)摹翱茖W(xué)”（三要素：問題的表示、問題的解決、證明）SVM——嚴(yán)格的數(shù)學(xué)推理NN——強(qiáng)烈依賴于工程技巧推廣能力取決于“經(jīng)驗(yàn)風(fēng)險(xiǎn)值”和“置信范圍值”，NN不能控制兩者中的任何一個(gè)。NN設(shè)計(jì)者用高超的工程技巧彌補(bǔ)了數(shù)學(xué)上的缺陷——設(shè)計(jì)特殊的結(jié)構(gòu)，利用啟發(fā)式算法，有時(shí)能得到出人意料的好結(jié)果。第7頁，課件共35頁，創(chuàng)作于2023年2月“我們必須從一開始就澄清一個(gè)觀點(diǎn)，就是如果某事不是科學(xué)，它并不一定不好。比如說，愛情就不是科學(xué)。因此，如果我們說某事不是科學(xué)，并不是說它有什么不對，而只是說它不是科學(xué)?！蓖恚cSVM相比，NN不像一門科學(xué)，更像一門工程技巧，但并不意味著它就一定不好！第8頁，課件共35頁，創(chuàng)作于2023年2月1、支持向量機(jī)可以做什么？支持向量機(jī)的應(yīng)用之二：性別識(shí)別SVMSVM男或女男或女SVM男或女9第9頁，課件共35頁，創(chuàng)作于2023年2月1、支持向量機(jī)可以做什么？支持向量機(jī)的應(yīng)用之三：行人檢測10第10頁，課件共35頁，創(chuàng)作于2023年2月2、支持向量機(jī)的提出問題1：支持向量機(jī)為什么會(huì)有如此好的性能？問題2：何為最優(yōu)分類面？11

它追求的不僅僅是得到一個(gè)能將兩類樣本分開的分類面，而是要得到一個(gè)最優(yōu)的分類面。TobeNo.1第11頁，課件共35頁，創(chuàng)作于2023年2月2、支持向量機(jī)的提出參考標(biāo)準(zhǔn)：使錯(cuò)分樣本數(shù)目最少缺陷1：錯(cuò)分訓(xùn)練樣本數(shù)目對判別函數(shù)的好壞評(píng)估不夠精細(xì)錯(cuò)分樣本數(shù)最少錯(cuò)分訓(xùn)練樣本數(shù)最少12第12頁，課件共35頁，創(chuàng)作于2023年2月缺陷2：擁有較少的錯(cuò)分訓(xùn)練樣本數(shù)的判別函數(shù)未必就是一個(gè)好的判別函數(shù)2、支持向量機(jī)的提出13第13頁，課件共35頁，創(chuàng)作于2023年2月margin2、支持向量機(jī)的提出支持向量機(jī)的標(biāo)準(zhǔn)：使margin盡可能大:兩類樣本到分類面的最短距離之和14第14頁，課件共35頁，創(chuàng)作于2023年2月a.線性支持向量機(jī)的數(shù)學(xué)模型3、支持向量機(jī)的數(shù)學(xué)模型設(shè)所求的分類面表達(dá)式為：該分類面若能將訓(xùn)練樣本線性分開，則：15對于有限個(gè)數(shù)的樣本，存在上式可簡寫為：即：其中，第15頁，課件共35頁，創(chuàng)作于2023年2月在上述約束條件下，SVM的求解則是最大化margin的過程。問題：若將分類面（w,b）對應(yīng)的margin記為，則16第16頁，課件共35頁，創(chuàng)作于2023年2月優(yōu)化目標(biāo)約束條件利用線性SVM求解線性分類面本質(zhì)上是求解如下優(yōu)化問題：17綜上所述，線性SVM的數(shù)學(xué)模型可以描述為：給定訓(xùn)練樣本集第17頁，課件共35頁，創(chuàng)作于2023年2月b.支持向量機(jī)的求解18支持向量機(jī)的優(yōu)化模型：一般的優(yōu)化問題模型：第18頁，課件共35頁，創(chuàng)作于2023年2月Step1：構(gòu)造Lagrange函數(shù)Step2:求解Lagrange函數(shù)的鞍點(diǎn)求解L(w,b;α)關(guān)于w和b的最小值，關(guān)于α的最大值，即：Lagrange乘子b.支持向量機(jī)的求解：拉格朗日對偶法19第19頁，課件共35頁，創(chuàng)作于2023年2月Step3代入Lagrange函數(shù)，得到原始問題的對偶問題：對L(w,b;α)關(guān)于w和b求偏導(dǎo)，得：20第20頁，課件共35頁，創(chuàng)作于2023年2月21第21頁，課件共35頁，創(chuàng)作于2023年2月原始問題與對偶問題解的關(guān)系：原始問題對偶問題22第22頁，課件共35頁，創(chuàng)作于2023年2月KKT條件與支持向量對于這樣的樣本，我們稱為支持向量（SupportVectors），它將使得對于取值不為零的KKT條件23對偶問題的解是最優(yōu)解的前提條件是：第23頁，課件共35頁，創(chuàng)作于2023年2月最優(yōu)超平面是支持向量的線性組合SVM的解的表達(dá)式可以重寫為：支持向量機(jī)的判別函數(shù)：24第24頁，課件共35頁，創(chuàng)作于2023年2月SupportVectorMachine支持向量機(jī)的編程實(shí)現(xiàn)25第25頁，課件共35頁，創(chuàng)作于2023年2月一、Matlab圖像編程概要1.讀入圖像：

RGB=imread(‘1.jpg’);

該函數(shù)的返回值RGB是一個(gè)三維的數(shù)組，分別代表像素點(diǎn)所在的行號(hào)、列號(hào)和像素點(diǎn)的R、G、B三個(gè)通道的值。例：

RGB(1,1,1);%圖像第一行第一列的R值；RGB(1,3,2);%圖像第一行第三列的G值；RGB(2,4,3);%圖像第二行第四列的B值；RR=RGB(:,:,1);%彩色圖像的紅色像素通道GG=RGB(:,:,2);%彩色圖像的綠色像素通道BB=RGB(:,:,3);%彩色圖像的藍(lán)色像素通道第26頁，課件共35頁，創(chuàng)作于2023年2月2.鼠標(biāo)輸入：[xx,yy,button]=ginput;接受鼠標(biāo)輸入直到敲回車鍵結(jié)束。其中：xx、yy：記錄鼠標(biāo)按下時(shí)橫坐標(biāo)和縱坐標(biāo)值；button:記錄鼠標(biāo)按下時(shí)的狀態(tài)。1表示左鍵，2表示中間鍵，3表示右鍵。3.繪制圖形：plot(x,y,‘b*’)；plot(x,y,‘b*’)：在坐標(biāo)(x,y)處繪制一個(gè)藍(lán)色的”*”注意：進(jìn)行圖形繪制前，首先運(yùn)行figure。如果要繪制多個(gè)點(diǎn)，需要首先運(yùn)行holdon。等繪制結(jié)束，再運(yùn)行holdoff。第27頁，課件共35頁，創(chuàng)作于2023年2月xlabel('R')ylabel('G')holdoff[count,asd]=size(xx);subplot(1,2,2);holdon;fori=1:counttrnx(i,:)=[RR(yy(i),xx(i)),GG(yy(i),xx(i))];switchbutton(i)case1trny(i,:)=-1;plot(trnx(i,1),trnx(i,2),‘r*');case2trny(i,:)=-1;plot(trnx(i,1),trnx(i,2),‘b+');otherwiseendend利用Matlab在圖像上采集訓(xùn)練樣本的示例程序Figure,subplot(1,2,1);imshow('S3a.bmp');Title(‘鼠標(biāo)左鍵點(diǎn)印章,鼠標(biāo)右鍵點(diǎn)紙面,回車結(jié)束’)[xx,yy,button]=ginput;RGB=imread('S3a.bmp');RR=RGB(:,:,1);GG=RGB(:,:,2);BB=RGB(:,:,3);第28頁，課件共35頁，創(chuàng)作于2023年2月1.訓(xùn)練SVM:[nsv,alpha,b0]=svc(X,Y,ker,C)二、SVM的Matlab工具箱使用指南X：訓(xùn)練樣本的輸入特征，X的行數(shù)為訓(xùn)練樣本的個(gè)數(shù)，X的列數(shù)代表訓(xùn)練樣本的特征維數(shù)；Y：訓(xùn)練樣本對應(yīng)的標(biāo)號(hào)，為一個(gè)列矩陣。矩陣的行數(shù)為樣本的個(gè)數(shù)。Y的值只能是1或者-1；Ker:核函數(shù)類型，常用的包括:’linear’，’poly’，’rbf’C：經(jīng)驗(yàn)風(fēng)險(xiǎn)與結(jié)構(gòu)風(fēng)險(xiǎn)的權(quán)衡參數(shù)，詳見SVM的數(shù)學(xué)優(yōu)化模型。nsv：支持向量的個(gè)數(shù)；alpha：對偶問題的解；b0：svm表達(dá)式中的偏移量。第29頁，課件共35頁，創(chuàng)作于2023年2月2.測試SVM:preY=svcoutput(trnX,trnY,tstX,ker,alpha,bias)trnX-訓(xùn)練樣本的輸入特征；trnY-訓(xùn)練樣本的標(biāo)號(hào)；tstX-測試樣本的輸入特征；ker-核函數(shù)alpha-SVM的求解結(jié)果bias-SVM的偏移量第30頁，課件共35頁，創(chuàng)作于2023年2月svkernel.m3.核函數(shù)參數(shù)的設(shè)置:switchlower(ker)case'linear'k=u*v';case'poly'p1=2;k=(u*v'+1)^p1;case'rbf‘p1=1;k=exp(-(u-v)*(u-v)'/(2*p1^2));case'sigmoid‘p1=1;p2=1;k=tanh(p1*u*v'/length(u)+p2);otherwisek=u*v';end第31頁，課件共35頁，創(chuàng)作于2023年2月4.在二維坐標(biāo)中繪制SVM的訓(xùn)練和測試結(jié)果:

svcplot(X,Y,ker,alpha,bias)其中：X-訓(xùn)練樣本的輸入特征Y-訓(xùn)練樣本的標(biāo)號(hào)ker-核函數(shù)alpha-SVM的求解結(jié)果bias-SVM的偏移量第32頁，課件共35頁，創(chuàng)作于2023年2月ker=‘linear’;%選擇線性核函數(shù)[nsvalphabias]=svc(trnx,trny,ker,10);%訓(xùn)練SVMsvcplot(trnx,trny,ker,alpha,bias);%顯示分類器效果利用SVM的Matlab工具箱進(jìn)行印簽提取的示例程序第33頁，課件共35頁，創(chuàng)作于2023年2月tstnum=1;fori=1:size(RGB,1)forj=1:size(RGB,2)testx=double(RGB(i,j,1:2));pr