SVM原理及应用举例

1、SVM原理及应用举例陈朝虹 硕班 201220109072SVM例子% 四个样本-2,2,2,-2,-2,-2,2,2%构造输入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;,前两个属第一类，后两个属第二类求解二次优化问题%多项式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;咆个权重设置最大的允许值f = -1*ones(4,1);%二次规划中的 fA =;b =;Aeq = tag;beq = 0;lb = zeros(4,1);%lb和 ub表示 sum (alpha*yi ) =0ub = C*ones(4,1);a0 = zeros(4,1);%所有权重的初值% 下使用二次规划算法调用quadprog a,fval,eXitflag,output,lambda=%quadprog(H,f,A,b,Aeq,beq,lb,ub,a0,options)力求解min1/2xT*H*x+fT*x由此我们把对偶问题加上一个

3、负号原来求最大变成求最小值options = optimset;% Options是用来控制算法的选项参数的向量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;% 多项式 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);% 输出分类结果result=zeros(1,4); for i=1:4for j=1:4k=(1+data(2:end,i)'*data(2:end,j)A2;% 多项式 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程序运行结果米用多项式

5、核：系数为a=0.00780.00780.00780.0078分类结果：result =1.03121.0312-1.0313-1.0313采用径向基RBF核：系数为a =1.00001.00001.00001.0000分类结果:result =1.00071.0007-1.0007-1.0007SVM理论基础如上图所示，有一堆训练数据的正负样本，标记为:（与M，"1/ M e 1，玉£衣成假设有一个超平面 H:3, M+ 3=0可以把这些样本正确无误地分割开来，同时存在两个平行于H的超平面 H1和H2:使离H最近的正负样本刚好分别落在H1和H2上，这样的样本就是支持向量。

6、那么其他所有的训练样本都将位于 H1和H2之外，也就是满足如下约束：州西 1 for 盟-1州西+3K-1 = -1写成统一的式子就是:yj (w +&)-1之0(1)而超平面H1和H2的距离可知为:M argjw = 2/MSVM的任务就是寻找这样一个超平面H把样本无误地分割成两部分，并且使 H1和H2的距离最大。要找到这样的超平面，只需最大化间隔Margin ,也就是最小化。于是可以构造如下的条件极值问题：min囱1 之0 （2）对于不等式约束的条件极值问题，可以用拉格朗日方法求解。而拉格朗日方程的构造规则是：用约束方程乘以非负的拉格朗日系数，然后再从目标函数中减去。于是得到拉格朗

7、日方程如下：其中： 3 (4) 那么我们要处理的规划问题就变为:min max £ （用瓦 珥）"上叫“ '/（5）上式才是严格的不等式约束的拉格朗日条件极值的表达式。对于这一步的变换，很多文章都没有多做表述，或者理解有偏差，从而影响了读者后续的推演。在此我将详细地一步步推导，以解困惑。（5）式是一个凸规划问题，其意义是先对“求偏导，令其等于 0消掉a ,然后再对w和b求L的最小值。要直接求解（5）式是有难度的，通过消去拉格朗日系数来化简方程，为此我们把（5）对我们的问题无济于事。 所幸这个问题可以通过拉格朗日对偶问题来解决, 式做一个等价变换：=max minin

8、£ （叫瓦科）wj>上式即为对偶变换，这样就把这个凸规划问题转换成了对偶问题:max min口 wf （6）其意义是：原凸规划问题可以转化为先对 对a求L的最大值。下面我们就来求解（ 式有：w和b求偏导，令其等于 0消掉w和b,然后再6）式，为此我们先计算 w和b的偏导数。由（3）肛dw龙（的,瓦内）db为了让L在w和b上取到最小值，令（7）式的两个偏导数分别为 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 £ （网友 0；） = max<辑额>0i工二%一5工工当必匕（不勺） i-11i-l j-1考虑到（8）式，我们的对偶问题就变为:L工m招2一不工汇乌叩必卜勺卜鼻 j-i -j-i、寸一£ sl-二q,=02«1%之0、（11）上式这个规划问题可以直接从数值方法计算求解。需要指出的一点是，（2）式的条件极值问题能够转化为（ 含着一个约束，即：叫G一1）=。（这个约束是这样得来的，如果（2）和（5）等效，必有:m把（3）式代入上式中，得到：片M n m跨7|洲一£ R （普1不+方） 11）= ：；H -m鬲/ 西，InJ化简得到：j'm讨Z% （无卜口卜0'一 g（13）又因为约束（1）式和（4）式，有：（10）5）式的凸规划问题，其中隐所以要使（13）式成立，只有令由此得到（12）式的约束。该约束的意义是：如果一个