支持向量机及其编程实现

支持向量机及其编程实现第1页，课件共35页，创作于2023年2月SupportVectorMachine支持向量机2第2页，课件共35页，创作于2023年2月相关参考资料统计学习理论的本质，VladimirN.Vapnik著，张学工译，清华大学出版社，2000.093

BernhardScholkopf,AlexJ.Smola,CHRISTOPHERJ.C.BURGES支持向量机导论，N.Cristianini,J.Shawe-Taylor著，电子工业出版社，2004.03SupportVectorClassification.StevenGunn.第3页，课件共35页，创作于2023年2月1、支持向量机可以做什么？4第4页，课件共35页，创作于2023年2月支持向量机的应用之一：手写体数字识别1、支持向量机可以做什么？NIST手写体数字的前100个目前最好的识别水平：LeNet4

多项式支持向量机（错误率<0.7%）5（错误率<0.8%）第5页，课件共35页，创作于2023年2月贝尔实验室对美国邮政手写数字库进行的实验分类器错误率人工表现2.5%决策树C4.516.2%最好的两层神经网络5.9%SVM4.0%第6页，课件共35页，创作于2023年2月SVM与神经网络（NN）的对比SVM的理论基础比NN更坚实，更像一门严谨的“科学”（三要素：问题的表示、问题的解决、证明）SVM——严格的数学推理NN——强烈依赖于工程技巧推广能力取决于“经验风险值”和“置信范围值”，NN不能控制两者中的任何一个。NN设计者用高超的工程技巧弥补了数学上的缺陷——设计特殊的结构，利用启发式算法，有时能得到出人意料的好结果。第7页，课件共35页，创作于2023年2月“我们必须从一开始就澄清一个观点，就是如果某事不是科学，它并不一定不好。比如说，爱情就不是科学。因此，如果我们说某事不是科学，并不是说它有什么不对，而只是说它不是科学。”同理，与SVM相比，NN不像一门科学，更像一门工程技巧，但并不意味着它就一定不好！第8页，课件共35页，创作于2023年2月1、支持向量机可以做什么？支持向量机的应用之二：性别识别SVMSVM男或女男或女SVM男或女9第9页，课件共35页，创作于2023年2月1、支持向量机可以做什么？支持向量机的应用之三：行人检测10第10页，课件共35页，创作于2023年2月2、支持向量机的提出问题1：支持向量机为什么会有如此好的性能？问题2：何为最优分类面？11

它追求的不仅仅是得到一个能将两类样本分开的分类面，而是要得到一个最优的分类面。TobeNo.1第11页，课件共35页，创作于2023年2月2、支持向量机的提出参考标准：使错分样本数目最少缺陷1：错分训练样本数目对判别函数的好坏评估不够精细错分样本数最少错分训练样本数最少12第12页，课件共35页，创作于2023年2月缺陷2：拥有较少的错分训练样本数的判别函数未必就是一个好的判别函数2、支持向量机的提出13第13页，课件共35页，创作于2023年2月margin2、支持向量机的提出支持向量机的标准：使margin尽可能大:两类样本到分类面的最短距离之和14第14页，课件共35页，创作于2023年2月a.线性支持向量机的数学模型3、支持向量机的数学模型设所求的分类面表达式为：该分类面若能将训练样本线性分开，则：15对于有限个数的样本，存在上式可简写为：即：其中，第15页，课件共35页，创作于2023年2月在上述约束条件下，SVM的求解则是最大化margin的过程。问题：若将分类面（w,b）对应的margin记为，则16第16页，课件共35页，创作于2023年2月优化目标约束条件利用线性SVM求解线性分类面本质上是求解如下优化问题：17综上所述，线性SVM的数学模型可以描述为：给定训练样本集第17页，课件共35页，创作于2023年2月b.支持向量机的求解18支持向量机的优化模型：一般的优化问题模型：第18页，课件共35页，创作于2023年2月Step1：构造Lagrange函数Step2:求解Lagrange函数的鞍点求解L(w,b;α)关于w和b的最小值，关于α的最大值，即：Lagrange乘子b.支持向量机的求解：拉格朗日对偶法19第19页，课件共35页，创作于2023年2月Step3代入Lagrange函数，得到原始问题的对偶问题：对L(w,b;α)关于w和b求偏导，得：20第20页，课件共35页，创作于2023年2月21第21页，课件共35页，创作于2023年2月原始问题与对偶问题解的关系：原始问题对偶问题22第22页，课件共35页，创作于2023年2月KKT条件与支持向量对于这样的样本，我们称为支持向量（SupportVectors），它将使得对于取值不为零的KKT条件23对偶问题的解是最优解的前提条件是：第23页，课件共35页，创作于2023年2月最优超平面是支持向量的线性组合SVM的解的表达式可以重写为：支持向量机的判别函数：24第24页，课件共35页，创作于2023年2月SupportVectorMachine支持向量机的编程实现25第25页，课件共35页，创作于2023年2月一、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);%彩色图像的蓝色像素通道第26页，课件共35页，创作于2023年2月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。第27页，课件共35页，创作于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在图像上采集训练样本的示例程序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);第28页，课件共35页，创作于2023年2月1.训练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表达式中的偏移量。第29页，课件共35页，创作于2023年2月2.测试SVM:preY=svcoutput(trnX,trnY,tstX,ker,alpha,bias)trnX-训练样本的输入特征；trnY-训练样本的标号；tstX-测试样本的输入特征；ker-核函数alpha-SVM的求解结果bias-SVM的偏移量第30页，课件共35页，创作于2023年2月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';end第31页，课件共35页，创作于2023年2月4.在二维坐标中绘制SVM的训练和测试结果:

svcplot(X,Y,ker,alpha,bias)其中：X-训练样本的输入特征Y-训练样本的标号ker-核函数alpha-SVM的求解结果bias-SVM的偏移量第32页，课件共35页，创作于2023年2月ker=‘linear’;%选择线性核函数[nsvalphabias]=svc(trnx,trny,ker,10);%训练SVMsvcplot(trnx,trny,ker,alpha,bias);%显示分类器效果利用SVM的Matlab工具箱进行印签提取的示例程序第33页，课件共35页，创作于2023年2月tstnum=1;fori=1:size(RGB,1)forj=1:size(RGB,2)testx=double(RGB(i,j,1:2));pr