实验三、 SVM 用于模式识别一、实验目的1. 理解SVM 的基本原理；2. 研究SVM 的分类效果；3. 了解混淆均值的应用,熟悉MATLAB 工具箱。
二、实验原理支持向量机在统计学习理论的基础上发展了一种新的机器学习方法。
如果仅从分类的角度来说，它是一种广义的线性分类器，它是在线性分类器的基础上，通过引入结构风险最小化原则、最优化理论和核函数演化而成的。
该方法根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折中，以期获得最好的推广能力。
而且，只要定义不同的核函数，就可以实现其它现有的学习算法。
因此，支持向量机己经在众多领域取得了成功的应用。
1.最优分类面SVM 方法是从线性可分情况下的最优分类面提出的，图1给出了二维两类线性可分情况的最优分类面示意图。
图中实心点和空心点分别表示两类的样本，H 为分类线，1H 和1H 分别为过各类样本中离分类线最近的点且平行于分类线的直线，它们之间的距离叫做分类空隙或分类间隔(margin)。
所谓最优分类线就是要求分类线不但能将两类正确分开，而且要使分类间隔最大。
前者是保证经验风险最小(为0)，分类间隔最大实际上就是使推广性的界中的置信范围最小，从而使真实风险最小。
推广到高维，最优分类线就成为最优分类面。
图1 最优分类面示意图设线性可分样本集(,)i i y X ，1,i =…,n ，d x R ∈，{1,1}y ∈+-是类别标号。
d 维空间中线性判别函数的一般形式为()g b =⋅+x W X ，分类面方程为()0g b =⋅+=x W X (1)为了描述分类面，使用下面的形式将判别函数进行归一化:()1g b =⋅+≥x W X ，若1i y = (2)()1g b =⋅+≤-x W X ，若1i y =- (3)即使两类所有样本都满足()1g ≥x 离分类面最近的样本的()1g =x ，这样分类间隔就等于2w，因此使间隔最大等价于使w (或2w )最小；而要求分类线对所有样本正确分类，就是要求它满足：[]10i y b ⋅+-≥w x ，1,i =…,n (4)因此满足条件式(3一13)且使2w 最小的分类面就是最优分类面。
过两类样本中离分类面最近的点且平行于最优分类面的超平面1H 、2H 上的训练样本就是式(4)中使等号成立的那些样本，称之为支持向量(Support Vectors)。
因为它们支撑了最优分类面，如图3.4中用圆圈标出的点所示。
根据上面的讨论，最优分类面问题可以表示成如下的二次规划问题，即在条件(4)的不等式约束下，求函数：2()0.50.5(,)Φ=⨯=⨯W w w w (5)的最小值。
为此，可以定义如下的Lagrange 函数1(,,)0.5(,){[]1}ni i i i L b y b αα==⨯-⋅+-∑W w w W X (6)其中0i α≥为Lagrange 系数，我们的问题是对w 和b 求Lagrange 函数的极小值。
把式（6）分别对w 和b 求偏微分并令它们等于0，就可以把原问题转化为如下这种较为简单的对偶问题：在约束条件10ni ii yα==∑ (7)0i α≥，1,i =…,n (8)之下对i α求解下列函数的最大值： 若i α*为最优解，则**1ni i i i y α==∑w x (9)由此可见，最优分类面的权函数向量是训练样本向量的线性组合。
这是一个不等式约束下二次函数极值问题，存在唯一解。
且根据Kuhn-Tucker 条件，这个优化问题的解须满足{[]1}0i i i y b α⋅+-=W X ，1,i =…,n (10)因此，对多数样本*i α将为零，取值不为零的*i α对应于式子（4）等号成立的样本即支持向量，它们通常只是全体样本的很少一部分。
求解上述问题后得到的最优分类函数式：****1()sgn{()}sgn{()}ni i i i i f b y b α==⋅+=⋅+∑x w x x x (11)sgn()为符号函数。
由于非支持向量对应的i α均为零，因此式中的求和实际上之对支持向量进行。
而b *是分类的阈值，可以由任意一个支持向量用式（4）求得，或通过两类中任意一对支持向量取中值求得。
三、实验要求编写一个SVM 算法的程序。
按下面方式用下表的数据训练一个SVM 分类器。
对每个样本进行预处理得到新的向量：22121122[1,,,,,]x x x x x x 。
(1) 只用第一个样本训练分类器并给出超平面及间隔。
(2) 用前2个样本（共4个点）重复（1），给出分类超平面方程、间隔及支持向量。
(3) 用前3个样本（共6个点）重复（2）。
然后再用前4个点，……，直到变换后的样本在变换后的空间中不再是线性可分的。
四、评价参数总体精度(Overall Accuracy)指混淆矩阵主对角线上所有元素之和除以参与计算混淆矩阵计算的所有像元个数所得到的百分数。
使用者精度(User ’s Accuracy)指分类后的土地覆盖类别，对应到地面真实参考时，真正为该种类别的像元素的百分比，即依据每一种分类，将对角线元素除以该行的列所有元素相加之和，所产生的百分比数。
生产者精度(Producer ’s Accuracy)(也称制图精度)指属于某一真实地面参考资料类别的检验点，有部分检验点被错误分类，而被正确分类的像元数的百分比，即将混淆矩阵中对一种分类，对角元素除以行中所有元素相加的和，所产生的百分比，本实验采用总体精度进行分析。
五、实验结果及分析初始样本的空间分布图如下：the scatter of initial data图1 初始样本的空间分布由此可见，这两类样本是线性可分的。
但是为了进一步研究支持向量机在高维空间的分类效果，本实验将原始数据映射到高维空间，即把数据先进行预处理。
对每个样本进行预处理得到新的向量：22121122[1,,,,,]x x x x x x 。
当然这样预处理只是为了简单分析SVM 对高维数据的处理状况，并不影响数据的线性可分特性。
下面我们对三种情况进行讨论及研究。
预处理后的样本为：采用这种映射方式，可使本来线性不可分的数据在新的特征空间变为线性可分，当然这数据自身已经线性可分了，在原始的特征空间中本身就线性可分，所以有点多此一举，不过也让我们熟悉广义线性判别函数方式。
表2 第二组样本映射后的结果分类超片面方程为22012345121122[,,,,,][1,,,,,]TY d x x x x x x d =+=⋅+WX w w w w w w (12)因此，以下实验给出权重w 和截距d ，通过(12)式可以获取超片面。
1、实验一，仅采用这两类中的第一个样本作为训练样本，然后求取超片面和间隔。
在此过程，我们采用每类的第一个样本作为训练样本，其余的18个样本作为测试样本，对训练结果进一步验证。
每个特征的权重矢量为w=[0.0000 0.0005 -0.0028 -0.0025 0.0041 0.0312]；偏差b=-1.2816；间隔为1.9922*1000；拉格朗日系数为[5.109，5.109]*0.0001； 支持向量为训练样本本身。
2、实验二，采用每类中的前两个样本作为训练样本，然后求取超平面和间隔。
在此过程，我们采用每类的第一个样本作为训练样本，其余的16个样本作为测试样本，对训练结果进一步验证。
每个特征的权重矢量为w=[0.0000 -0.0121 -0.0739 0.0414 0.0534 0.0222]；偏差b=-2.2743；间隔为187.5741；拉格朗日系数为[0.0012 0.0042 0.0049 0.0004]；支持向量为训练样本本身。
分类的总体精度为100%表5 混淆矩阵3、实验三，采用每类中的前三个样本作为训练样本，然后求取超平面和间隔。
每个特征的权重矢量为w=[0.0000 -0.0121 -0.0739 0.0414 0.0534 0.0222]；偏差b=-2.2743；间隔为187.5741；拉格朗日系数为[0.0012 0.0042 0.0049 0.0004]；第一类的支持向量为前两个训练样本，第二类的支持向量也是前两个训练样本。
即表2的前两行和表3的前两行样本。
分类的总体精度为100%表6 混淆矩阵4、实验四，采用每类中的前三个样本作为训练样本，然后求取超平面和间隔。
每个特征的权重矢量为w=[0.0000 -0.0121 -0.0739 0.0414 0.0534 0.0222]；偏差b=-2.2743；间隔为187.5741；拉格朗日系数为[0.0012 0.0042 0.0049 0.0004]；第一类的支持向量仍为前两个训练样本，第二类的支持向量也是前两个训练样本。
即表2的前两行和表3的前两行样本。
分类的总体精度为100%表7 混淆矩阵当采用前五个样本作为训练样本时，实验结果和实验二也一致。
直至到采用前六个样本时，支持向量的数目为3。
测试样本的识别率仍为100%。
六、实验程序clear allclose allclcx1(:,1)=[-3,0.5,2.9,-0.1,-4,-1.3,-3.4,-4.1,-5.1,1.9]';x1(:,2)=[-2.9,8.7,2.1,5.2,2.2,3.7,6.2,3.4,1.6,5.1]';x2(:,1)=[-2,-8.9,-4.2,-8.5,-6.7,-0.5,-5.3,-8.7,-7.1,-8]';x2(:,2)=[-8.4,0.2,-7.7,-3.2,-4,-9.2,-6.7,-6.4,-9.7,-6.3]';sampleji.firstsort(1:2,:)=x1';sampleji.secondsort(1:2,:)=x2';% sampleji=load('E:\ sampleji.mat');% sampleji is a struct that contains two sample datas(firstsort and % secondsort). For example,firstsort is a 2*10 matrixscatter(sampleji.firstsort(1,:)',sampleji.firstsort(2,:)','b');%imshow the initial datahold onscatter(sampleji.secondsort(1,:)',sampleji.secondsort(2,:)','r');hold offtitle('the scatter of initial data')%%%%%%%%%%%%%%%mapmapfirst(:,1)=ones(10,1);mapsecond(:,1)=ones(10,1);%have 10 samples in each classmapfirst(:,2)=sampleji.firstsort(1,:)';mapsecond(:,2)=sampleji.se condsort(1,:)';mapfirst(:,3)=sampleji.firstsort(2,:)';mapsecond(:,3)=sampleji.se condsort(2,:)';mapfirst(:,4)=(sampleji.firstsort(1,:).^2)';mapsecond(:,4)=(sampl eji.secondsort(1,:).^2)';mapfirst(:,5)=(sampleji.firstsort(1,:).*sampleji.firstsort(2,:))' ;mapsecond(:,5)=(sampleji.secondsort(1,:).*sampleji.secondsort(2,: ))';mapfirst(:,6)=(sampleji.firstsort(2,:).^2)';mapsecond(:,6)=(sampl eji.secondsort(2,:).^2)';%%%%%%%%%%%%%the train sample number is NN=2;train_sample=[mapfirst(1:N,:);mapsecond(1:N,:)];[nx,ny]=size(train_sample);y=[ones(nx/2,1);-1*ones(nx/2,1)];my_struct=svmtrain(train_sample,y);%%%%%%%%%the text sampletext_sample=[mapfirst(N+1,:);mapsecond(N+1,:)];class=svmclassify(my_struct,text_sample);%%%%%%%%%%%%5alpha=abs(my_struct.Alpha);% Lagragian multiplier%%%%%%my_Struct.Alpha is that alpha multiply with the label of suppervectorw=diag(alpha)*my_struct.SupportVectors;w=sum(w);% weight vector of optimal hyperplanemargin=2/(w*w');% margin between two classes。