svm(上)支持向量机课件

SupportVectorMachines支持向量机第三讲引子23相关参考资料•统计学习理论的本质，VladimirN.Vapnik著，张学工译，清华大学出版社，2000.094•••BernhardScholkopf,AlexJ.Smola,CHRISTOPHERJ.C.BURGES•支持向量机导论，N.Cristianini,J.Shawe-Taylor著，电子工业出版社，2004.03•SupportVectorClassification.StevenGunn.(518/54.29)模式识别领域权威期刊与会议•IEEETrans.PatternAnalysisandMachineIntelligence•IEEETrans.NeuralNetworks•IEEEConferenceonComputerVisionandPatternRecognition(CVPR)•InternationalConferenceonPatternRecognition(ICPR)•InternationalConferenceonComputerVision(ICCV)支持向量机的应用之一：手写体数字识别1、支持向量机可以做什么？NIST手写体数字的前100个目前最好的识别水平：•LeNet4•多项式支持向量机（错误率0.7%）6（错误率0.8%）1、支持向量机可以做什么？支持向量机的应用之二：性别识别SVMSVM男或女男或女SVM男或女71、支持向量机可以做什么？支持向量机的应用之三：行人检测82、支持向量机的提出问题1：支持向量机为什么会有如此好的性能？问题2：何为最优分类面？9它追求的不仅仅是得到一个能将两类样本分开的分类面，而是要得到一个最优的分类面。TobeNo.12、支持向量机的提出参考标准：使错分样本数目最少缺陷1：错分训练样本数目对判别函数的好坏评估不够精细错分样本数最少错分训练样本数最少10缺陷2：拥有较少的错分训练样本数的判别函数未必就是一个好的判别函数2、支持向量机的提出11margin2、支持向量机的提出支持向量机的标准：使margin尽可能大:两类样本到分类面的最短距离之和12a.线性支持向量机的数学模型3、支持向量机的数学模型设所求的分类面表达式为：该分类面若能将训练样本线性分开，则：(),gxwxb(,)0iiywxb13对于有限个数的样本，存在(,)iiywxb上式可简写为：,s.t.,0when1,0when1iiiiwxbywxby即：(,)1,iiywxbi其中，/,/wwbbll在上述约束条件下，SVM的求解则是最大化margin的过程。问题：若将分类面（w,b）对应的margin记为，则(,)wb14(,)?wb优化目标1min(,),2wbww约束条件(,)1iiywxb1,2,,ilL2w11(,),,(,)llxyxyL{1,1}iy利用线性SVM求解线性分类面本质上是求解如下优化问题：15综上所述，线性SVM的数学模型可以描述为：给定训练样本集b.支持向量机的求解161min(,),2wbww(,)1iiywxb1,2,,ilL支持向量机的优化模型：一般的优化问题模型：min()fx..()01,2,,istcxipL()0,1,2,,jcxjpppqLStep1：构造Lagrange函数11(,;),[(,)1]2niiiiLwbwwywxbStep2:求解Lagrange函数的鞍点求解L(w,b;α)关于w和b的最小值，关于α的最大值，即：Lagrange乘子b.支持向量机的求解：拉格朗日对偶法17****1*****1(,,)00(,,)0liiiliiiiLwbybLwbwyxwStep3代入Lagrange函数，得到原始问题的对偶问题：对L(w,b;α)关于w和b求偏导，得：18***11max(,;)..0lliiiiiiiLwbstwyxy19**11(,;),[(,)1]2liiiiLwbwwywxb****11111,[(,)1]2lllliiijjjiijjjiijijyxyxyyxxb******,1,1111(,),2llllijijijijijijiiiijijiiyyxxyyxxyb***1,11,2lliijijijiijyyxx1,11max(),2lliijijijiijWyyxx**1liiiiwyx0i10liiiy原始问题与对偶问题解的关系：1min(,),2wbww(,)1iiywxb1,2,,ilL原始问题对偶问题20支持向量机的判别函数：****1(),,liiiifxwxbyxxb1,2,,ilLKarush-Kuhn-Tucker（KKT）条件与支持向量*[(,)1]01,2,,iiiywxbil对于这样的样本，我们称为支持向量（SupportVectors）(,)1iiywxbi，它将使得对于取值不为零的KKT条件21对偶问题的解是最优解的条件：*(1,2,,)iil**1liiiiwyx**iiiwyx支持向量最优超平面是支持向量的线性组合SVM的解的表达式可以重写为：***1[,,]2bwxwx**()sgn(,)iiifxyxxb支持向量支持向量机的判别函数：22SupportVectorMachine支持向量机的编程实现23一、Matlab图像编程概要1.读入图像：RGB=imread(‘1.jpg’);该函数的返回值RGB是一个三维的数组，分别代表像素点所在的行号、列号和像素点的R、G、B三个通道的值。例：RGB(1,1,1);%图像第一行第一列的R值；RGB(1,3,2);%图像第一行第三列的G值；RGB(2,4,3);%图像第二行第四列的B值；RR=RGB(:,:,1);%彩色图像的红色像素通道GG=RGB(:,:,2);%彩色图像的绿色像素通道BB=RGB(:,:,3);%彩色图像的蓝色像素通道2.鼠标输入：[xx,yy,button]=ginput;接受鼠标输入直到敲回车键结束。其中：xx、yy：记录鼠标按下时横坐标和纵坐标值；button:记录鼠标按下时的状态。1表示左键，2表示中间键，3表示右键。3.绘制图形：plot(x,y,‘b*’)；plot(x,y,‘b*’)：在坐标(x,y)处绘制一个蓝色的”*”注意：进行图形绘制前，首先运行figure。如果要绘制多个点，需要首先运行holdon。等绘制结束，再运行holdoff。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在图像上采集训练样本的示例程序Figure,subplot(1,2,1);imshow('S3a.bmp');Title(‘鼠标左键点印章,鼠标右键点纸面,回车结束’)[xx,yy,button]=ginput;RGB=imread('S3a.bmp');RR=RGB(:,:,1);GG=RGB(:,:,2);BB=RGB(:,:,3);050100150200250300050100150200250300RGS3a.bmp1.训练SVM:[nsv,alpha,b0]=svc(X,Y,ker,C)二、SVM的Matlab工具箱使用指南X：训练样本的输入特征，X的行数为训练样本的个数，X的列数代表训练样本的特征维数；Y：训练样本对应的标号，为一个列矩阵。矩阵的行数为样本的个数。Y的值只能是1或者-1；Ker:核函数类型，常用的包括:’linear’，’poly’，’rbf’C：经验风险与结构风险的权衡参数，详见SVM的数学优化模型。nsv：支持向量的个数；alpha：对偶问题的解；b0：svm表达式中的偏移量。2.测试SVM:preY=svcoutput(trnX,trnY,tstX,ker,alpha,bias)trnX-训练样本的输入特征；trnY-训练样本的标号；tstX-测试样本的输入特征；ker-核函数alpha-SVM的求解结果bias-SVM的偏移量svkernel.m3.核函数参数的设置: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';end4.在二维坐标中绘制SVM的训练和测试结果:svcplot(X,Y,ker,alpha,bias)其中：X-训练样本的输入特征Y-训练样本的标号ker-核函数alpha-SVM的求解结果bias-SVM的偏移量ker=‘linear’;%选择线性核函数[nsvalphabias]=svc(trnx,trny,ker,10);%训练SVMsvcplot(trnx,trny,ker,alpha,bias);%显示分类器效果利用SVM的Matlab工具箱进行印签提取的示例程序050100150200250300050100150200250300RGtstnum=1;fori=1:size(RGB,1)forj=1:size(RGB,2)testx=double(RGB(i,j,1:2));preY=svcoutput(trnx,trny,testx,ker,alpha,bias);tstnum=tstnum+1;if(preY==1)resIm(i,j)=255;elseresIm(i,j)=0;endendendimshow(resIm);利用SVM的Matlab工具箱进行印签提取的示例程序S3a.bmp050100150200250300050100150200250300RGS3a.bmp三、SVM的C语言编程介绍1.求解SVM的两个开源开发包：•Libsvm:~cjlin•SVM-light：~thorsten/svm_lightlabelindex1:value1index2:value2...2.利用SVM的C语言程序直接进行分类器的训练和测试：例：11:672:663:724:725:596:717:548:679:79-11:1012:1083:1004:995:1026:957:938:969:89使用说明训练结果3.利用SVM的C语言开发包编写自己的SVM分类器：svm_model*svm_train(constsvm_problem*prob,constsvm_parameter*param)doublesvm_predict(constsvm_model*model,constsvm_nod