支持向量机实验报告

人工智能课程项目报告姓名：班级：44?K?K?K?K?IC?K?K?IOICTIC^K?K?K?K目录TOC\o"1-5"\h\z一、实验背景1二、实验目的1三、实验原理13.1线性可分：13.2线性不可分：43.3坐标上升法：7SMO算法：8四、实验内容10五、实验结果与分析125.1实验环境与工具125.2实验数据集与参数设置125.3评估标准13实验结果与分析13一、实验背景本学期学习了高级人工智能课程，对人工智能的各方面知识有了新的认识和了解。为了更好的深入学习人工智能的相关知识，决定以数据挖掘与机器学习的基础算法为研究对象，进行算法的研究与实现。在数据挖掘的各种算法中，有一种分类算法的分类效果，在大多数情况下都非常的好，它就是支持向量机（SVM）算法。这种算法的理论基础强，有着严格的推导论证，是研究和学习数据挖掘算法的很好的切入点。二、实验目的对SVM算法进行研究与实现，掌握理论推导过程，培养严谨治学的科研态度。三、实验原理支持向量机基本上是最好的有监督学习算法。SVM由Vapnik首先提出（Boser,GuyonandVapnik,1992;CortesandVapnik,1995;Vapnik,1995,1998*它的主要思想是建立一个超平面作为决策曲面，使得正例和反例之间的隔离边缘被最大化。SVM的优点：通用性（能够在各种函数集中构造函数）鲁棒性（不需要微调）有效性（在解决实际问题中属于最好的方法之一）计算简单（方法的实现只需要利用简单的优化技术）理论上完善（基于VC推广理论的框架）3.1线性可分：首先讨论线性可分的情况，线性不可分可以通过数学的手段变成近似线性可分。基本模型：

-判定函数形式：g3)=wlx+b—因此，y((wtxi+b)>mVi一裕量(margin)-令2ml|w||这里的裕量是几何间隔。一裕量(margin)-令2ml|w||这里的裕量是几何间隔。我们的目标是最大化几何间隔，但是看过一些关于SVM的论文的人一定记得什么优化的目标是要最小化llwlI这样的说法，这是怎么回事呢？原因来自于对间隔和几何间隔的定义(数学基础)：间隔：6=y(wx+b)=lg(x)l几何间隔：llwll叫做向量w的范数，范数是对向量长度的一种度量。我们常说的向量长度其实指的是它的2-范数，范数最一般的表示形式为p-范数，可以写成||*||=++_4-w^如下表达式：11另外，注意我们的目标：最大化几何间隔，而不是求出这个间隔。即，在什么情况下间隔最大，我们要得到的是这个“情况”（W和b取什么值，因为所有X和y是已知的）所以，我们可以把目标转换：“爵E==》Mil刨1==：*『miHy||切||"钥他于驾+时＞1盘=L…点在这个问题中，自变量就是可，而目标函数是w的二次函数，所有的约束条件都是w的线性函数（不要把Xi当成变量，它代表样本，是已知的）这种规划问题有个很有名气的称呼一一二次规划（QuadraticProgramming，QP），而且可以更进一步的说，由于它的可行域是一个凸集，因此它是一个凸二次规划。拉格朗日乘子法可以求解这个问题。1"/，，£（叫8心）=-IH*一，2叫（切（方％+3）—1问题1:-J-实际上就是目标函数减去，ai乘上约束条件的累加和。将问题转化为拉格朗日乘子待定问题。经过数学计算（求导），可以发现：样本确定了w，用数学的语言描述，就是w可以表示为样本的某种组合：w=a1y1x1+a2y2x2+•••+anynxn式子中的ai是一个一个的数，而xi是样本点，因而是向量，n就是总样本点的个数。w的表达式可以简写如下:£5头=o另外可以得到约束条件：■-把问题1写成其对偶形式，可转化成问题2：蜜x}%—Y°，ajyiy）xixjsubjectto〉atyi=0;>0Vi这样就可以解了，而且方法很多，如SMO。解出来得到的是a，然后可以得到w和b，进而得到分类超平面。（事实上，不需要求出可，非线性下求出w也无意义）3.2线性不可分：在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。那是否意味着，每当我们解决一个问题，都需要找一个函数，从低维映射到高维？这个函数是什么样子的呢？首先观察一下线性下的目标函数（转化后的）。（注：之所以观察这个公式，是因为转化到高维后，就线性可分了，最后推导得到的还是这个式子）

MXVat-iVtiiajy^jXiXj1-1iJ/、我们发现它关注的不是函数本身，而是函数结果的内积。即，我不在乎你把x（二维），转化为了x几维，也不在乎转化后的值是多少，我在乎的是转化之后，两个x再求内积（一个数）是多少。幸运的是，数学中有这样一些函数，他们叫核函数，计算效果相当于转化到高维后的内积。百度百科的解释：核函数将m维高维空间的内积运算转化为n维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾难”等问题，从而为在高维特征空间解决复杂的分类或回归问题奠定了理论基础。几个核函数：多项式核：'cn任】壬立）=exp高斯核:它能将原始空间映射为无穷维空间。不过，如果sita选得很大的话，就相当于一个低维的子空间；反过来，如果选得很小，则可以将任意的数据映射为线性可分一一当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。同样，经过数学推导，非线性SVM的目标函数为:maxn]i-I■>03i—15.r.max»乾疆=oi—1同样，可以用SMO求解。如上图：如果转化到高维还是不可分呢？或者转的维数不够，或者存在TOC\o"1-5"\h\z1M血耳脚『噪声点？这个时候怎么办？引入松弛变量：-其中称为松弛变量，C是一个参数。同样，经过转化：max凶一；£叫丐力为©（»。（勺）.（i接，s.t.ya^yt=OrO<at<Cyt此时，我们发现没有了参数矿，与之前模型唯一不同在于c的限制条件。为了不失一般性，我们使用引入松弛变量的模型。也就是需要求解的目max.2一叫勺V2力少（*D'。（易）•奁iiJ,s.t./aiyt=0,0<（X£<C,Vi标问题。根据KKT条件可以得出目标函数中取值的意义：Q=0=加,>1,

0<ai<C<^>=La-C<=>y-u.<1.这里的还是拉格朗日乘子：对第1种情况，表明是正常分类，在边界内部(我们知道正确分类的点)；对第2种情况，表明了是支持向量，在边界上；对第3种情况，表明了是在两条边界之间；3.3坐标上升法：在最后讨论W(a)的求解之前，我们先看看坐标上升法的基本原理。假inaxW(Q\…Km)*设要求解下面的优化问题：这里W是a向量的函数(也就是前面转化后的目标函数)。求最优解的方法有多种：一种是梯度下降法，一种是牛顿法，还有一种是坐标上升法。Looj>untileoiivcrgeiiee!(Fori—1..…{Ct,=HTg矿U(cqcir^_),d；,1....,arF,),}方法过程：坐标上升法可以用一张图来表示:

3.4SMO算法：SMO算法由MicrosoftResearch的JohnC.Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的论文《SequentialMinimalOptimizationAFastAlgorithmforTrainingSupportVectorMachine》。算法框架：fori=1:iter根据预先设定的规则，从所有样本中选出两个保持其他拉格朗日乘子不变，更新所选样本对应的拉格朗日乘子end样本选取规则：第一个参数是违反kkt条件的。第二个参数：选择使得I二—上：（实际输出和期望输出的误差）最大的参数。情况比较复杂，原算法分了很多情况。当所有变量都满足kkt条件时，算法结束，求得a。选出了参数就要进行计算。其中一个参数是可以求导等于0然后解出来（不失一般性，记为a2）。另一个参数随之发生变化（记为a1）。解之前要先确定取值范围：根据y1和y2异号或同号，可得出a2的上下界分别为：a^),H=】nin(GC+口羿二雄俨)ifVi产»

砰“一ClH=mm(C,呻+甘jif»=桃

如果是极值点，二阶导应该大于0,关于a2的二阶导为:71=X（xtjXi）+,x2）-2X（xt,x3y经过数学计算，在二阶导大于0的情况下，结合取值范围:-^niew^clipped、_ifar>H;ifL<<ihif<L.结合取值范围:-^niew^clipped、_然后得到al:1二％+S（在2一。广血网）一在一些情况下，二阶导不是正数，这时候需要用到目标函数在取最小值和最大值时候的值：f\=凹（耳+6）-0^（X1^!）-sa2K（x^x2）,£=y2（E2+6）-s%K（X,巳）-a2K（x2tx2\£=%L）,H[=%（仁_//）,%=LJ\+晶+捉；K（WK）+?L2K（x.，走）+,x2\%=弓儿+///；次（E,扁）庄）.计算出al和a2后，相应的更新b。而b在满足下述条件；「也ifO<«^<C[0+如）/2otherwise下更新艮陟*-El功血件一呻闹趴函）职F血・切F血严■借）枪E）F血严・样）轮有2〕更新完a和b，一个周期结束，进入下一次循环。当所有的参数符合kkt条件，循环结束。四、实验内容SVM算法步骤：读入训练数据。用SMO算法求解，得到分类预测模型。根据预测模型进行预测。我们发现SVM算法的难点和重点是SMO算法。算法流程图：SMO主循环部分:mainroutine:numChanged=0;examineAll=1;while(numChanged>0|amineAl1)(numChanged=0;if(examineA_l)loopIaveralltrailingexamplesnumChanged+=examineExample(I)^IseloopIoverexampisswherealpjiaisnot0¬CnumChanged+=examineExample(I)if(examineAl1==1)exarnineAl_—Lelseif|(numChanged==0)examJneA]'=1参数选择：procedureexamineExample(12)y2=target[12]alph2=Lagrangemultipiierfor12E2=SVMoutputonpoint[12]-y2(checkinerrorcache)r2=E2*y2if((r2<-tQ.l&&alph2<C)||(r2>to1&&alph2>0)){Lf(numberofnon-ze±o&non-C^Ipha>1)(i1=result.qtsecondchoiceheur1stic(sect-：on2,2)iftakeStep(ilfi2)return1}loopoveral1non-zero3ndncrn-C^Ipharstarting旦一arandcunpoint■:11=identityofcurrentalphaiftakeStep("lf：.2)return1)loopaverallpossible11,star-Jngatarandompoin-■:i1=Loopvariableif(takeStep('1H\2)return1})return0endprocedure参数更新：proceduretakeStep(i1,i2)if(il==i2)return0alphl=LagrangemuItiplierfori\yl=target[n1]El=SUMoutputonpoint[i11-yl(checkinerrorcache)s=yl*y2ComputeL,Hvia.equations(13)and(14)if(L==H)return0kl1=kernel(point[il][il])kl2=kernel(point[il]fpoint[i2])k22=kernel(point[i2]fpoint[±2])eta=kll+k22-2+kl2if(eta>0){a2=alph2+y2*(E1-E2}/etaifU2<L)己2=Lelseif(a2>H)a2=H)else{Lobj=objectivefunctionata2=LHobj=object.ivefunctionata2=Hif(Lobj<Hobj-eps)a2=Lelseif(Lobj>Hobj+eps)a2=Helsea2=alph2}if(|a2-aiph2|<eps*(a2+aiph2+eps))return0a_=cilphl+s+(c.lph2-a2)Upd&t$thresholdtoreflectchangeinLagrarig硅multipliersUpdateweightvectortoreflectchangeinal&3.2fifSVHisLinearUpdateerrorcacheusingnewLagrangemultipliersStorealinthealphaarrayStorea2inthealphaarrayreturn_endprocedure五、实验结果与分析5.1实验环境与工具Windows7旗舰版（ServicePack1）MyEclipse2014。5.2实验数据集与参数设置bigdata.txt==》线性可分（y=x程序产生）cycle.txt==》线性不可分（xA2+yA2=1，程序生成）cycle2.txt==》线性不可分（乂八2+娑2=0~2.5）heart_scale==》线性不可分实际数据testSet.txt==》线性可分不规则图形.txt==》线性不可分（图像数据）人脸.txt==》线性不可分（图像数据）5・3评估标准算法经过训练集的训练之后，在测试集上的分类准确率。通过实际图像也可以看到分类效果。5.4实验结果与分析testSet.txt实验结果：hI11i_rv|r■i_riIIbtuvuj—■Rvljiliu11iijj・*iihurjhuihh■irs-i■>^avcijr^-i■n■‘jiiej■^k-^iiiuhjr开始训练,…1856300.126801387916420324.6581913.5073960.24024386748112373.457096-0,0822160.36704525539754386*0805739.4188860.8106342724751081-0.271240G721112174-3.8247408239349932训练结束开始预测一.预测正确率为