支持向量机实验报告

人工智能课程项目报告姓名：班级：卜4工4工工土4土卜4工4工4工4工4工 ?K?K?K?K?IC?K?K?IOICTICK?K?K?K目录一、实验背景1二、实验目的1三、实验原理13.1线性可分：13.2线性不可分：43.3坐标上升法：73.4 SMO 算法：8四、实验内容10五、实验结果与分析125.1实验环境与工具125.2实验数据集与参数设置125.3评估标准135.4 实验结果与分析13一、实验背景本学期学习了高级人工智能课程，对人工智能的各方面知识有了新的认 识和了解。为了更好的深入学习人工智能的相关知识，决定以数据挖掘与机 器学习的基础算法为研究对象，进行算法的研究与实现。在数据挖掘的各种算法中，有一种分类算法的分类效果，在大多数情况 下都非常的好，它就是支持向量机（SVM）算法。这种算法的理论基础强， 有着严格的推导论证，是研究和学习数据挖掘算法的很好的切入点。二、实验目的对SVM算法进行研究与实现，掌握理论推导过程，培养严谨治学的科 研态度。三、实验原理支持向量机基本上是最好的有监督学习算法。SVM由Vapnik首先提出 （Boser,Guyon and Vapnik,1992;Cortes and Vapnik,1995;Vapnik, 1995,1998* 它 的主要思想是建立一个超平面作为决策曲面，使得正例和反例之间的隔离边 缘被最大化。SVM的优点：1. 通用性（能够在各种函数集中构造函数）2. 鲁棒性（不需要微调）3. 有效性（在解决实际问题中属于最好的方法之一）4. 计算简单（方法的实现只需要利用简单的优化技术）5. 理论上完善（基于VC推广理论的框架）3.1线性可分：首先讨论线性可分的情况，线性不可分可以通过数学的手段变成近似线 性可分。基本模型：-判定函数形式：g3) = wlx + b因此，y(wtxi + b) m V i一裕量 (margin)-令2ml|w|这里的裕量是几何间隔。我们的目标是最大化几何间隔，但是看过一些关于SVM的论文的人一 定记得什么优化的目标是要最小化llwl I这样的说法，这是怎么回事呢？原因来自于对间隔和几何间隔的定义(数学基础)：间隔：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当成变量，它代表样本，是已知的）这种规划问题有个很有名气的称呼一一二次规划（Quadratic Programming，QP），而且可以更进一步的说，由于它的可行域是一个凸集， 因此它是一个凸二次规划。拉格朗日乘子法可以求解这个问题。1 /，（叫8心）=-IH* 一，2叫（切（方 +3） 1问题1:-J -实际上就是目标函数减去，ai乘上约束条件的累加和。将问题转化为 拉格朗日乘子待定问题。经过数学计算（求导），可以发现：样本确定了 w，用数学的语言描述， 就是w可以表示为样本的某种组合：w= a 1y1x1+ a 2y2x2+ a nynxn式子中的a i是一个一个的数，而xi是样本点，因而是向量，n就是总 样本点的个数。w的表达式可以简写如下:5 头=o另外可以得到约束条件：-把问题1写成其对偶形式，可转化成问题2：蜜x% Y ，ajyiy）xixjsubject to atyi = 0; 0 Vi这样就可以解了，而且方法很多，如SMO。解出来得到的是a，然后可 以得到w和b，进而得到分类超平面。（事实上，不需要求出可，非线性下求 出w也无意义）3.2线性不可分：在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后 通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出 最优分离超平面，从而把平面上本身不好分的非线性数据分开。那是否意味着，每当我们解决一个问题，都需要找一个函数，从低维映射到高维？这个函数是什么样子的呢？首先观察一下线性下的目标函数（转化后的）。（注：之所以观察这个公式，是因为转化到高维后，就线性 可分了，最后推导得到的还是这个式子）MX V at - i V tii ajyjXiXj1-1 iJ/、我们发现它关注的不是函数本身，而是函数结果的内积。即，我不在乎 你把x（二维），转化为了 x几维，也不在乎转化后的值是多少，我在乎的是 转化之后，两个x再求内积（一个数）是多少。幸运的是，数学中有这样一 些函数，他们叫核函数，计算效果相当于转化到高维后的内积。百度百科的解释：核函数将m维高维空间的内积运算转化为n维低维输 入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾 难”等问题，从而为在高维特征空间解决复杂的分类或回归问题奠定了理论 基础。几个核函数：多项式核：c n任】壬立）=exp高斯核:它能将原始空间映射为无穷维空间。不过，如果sita选得很大的话，就相 当于一个低维的子空间；反过来，如果选得很小，则可以将任意的数据映射为线性可分一一当然，这并不一定是好事，因为随之而来的可能是非常严重 的过拟合问题。不过，总的来说，通过调控参数，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。同样，经过数学推导，非线性SVM的目标函数为:maxni-I 03 i 15. r.乾疆=oi 1同样，可以用SMO求解。如上图：如果转化到高维还是不可分呢？或者转的维数不够，或者存在1M血耳脚噪声点？这个时候怎么办？引入松弛变量：-其中称为松弛变量，C是一个参数。同样，经过转化：max凶一；叫丐力为（。（勺）.（i接，s.t.y ayt = OrO at Cyt此时，我们发现没有了参数矿，与之前模型唯一不同在于c的限制条件。为了不失一般性，我们使用引入松弛变量的模型。也就是需要求解的目max . 2 一叫勺V2力少（*D。（易）奁 i iJ,s. t. / aiyt = 0,0 （X 1,0ai C=La - C y-u. until eoiivcrgeiiee! (For i 1. Ct, = HTg 矿 U (cqcir_), d；,1. ., arF,),方法过程：坐标上升法可以用一张图来表示:3.4 SMO 算法：SMO 算法由 Microsoft Research 的 John C. Platt 在 1998 年提出，并 成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更 优。关于SMO最好的资料就是他本人写的论文 Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machine。算法框架：for i=1:itera. 根据预先设定的规则，从所有样本中选出两个b. 保持其他拉格朗日乘子不变，更新所选样本对应的拉格朗日乘子 end样本选取规则：第一个参数是违反kkt条件的。第二个参数：选择使得I二上：（实际输出和期望输出的误差）最大的参 数。情况比较复杂，原算法分了很多情况。当所有变量都满足kkt条件时， 算法结束，求得a。选出了参数就要进行计算。其中一个参数是可以求导等于0然后解出来 （不失一般性，记为a2）。另一个参数随之发生变化（记为a1）。解之前 要先确定取值范围：根据y1和y2异号或同号，可得出a2的上下界分别为：a), H =】nin(GC +口羿二雄俨)if Vi 产 砰“ 一Cl H = mm(C,呻 + 甘j if =桃如果是极值点，二阶导应该大于0,关于a2的二阶导为:71 = X（xt jXi） +,x2） - 2X（xt ,x3 y经过数学计算，在二阶导大于0的情况下，结合取值范围:-niewclipped 、_if ar H;if L ihif L.然后得到al: 1二+S（在 2一。广血网）一在一些情况下，二阶导不是正数，这时候需要用到目标函数在取最小值和最大值时候的值： f =凹（耳 + 6） - 0（X1 !）- sa2K（xx2）, = y2（E2 + 6） - s%K（X ,巳）- a2K（x2tx2 = %L）,H = %（仁 _/）,% = LJ + 晶 +捉；K（WK）+? L2K（x.，走）+, x2% =弓儿 +/；次（E,扁）庄）.计算出al和a2后，相应的更新b。而b在满足下述条件；也 ifO 0 | amineAl1) (numChanged = 0;i f (examineA_l)loop I aver all trailing examples numChanged += examineExample(I)Iseloop I over exampiss where alpjia is not 0 & not C numChanged += examineExample(I)if (examineAl1 = 1) exarnineAl_ Lelse if | (numChanged = 0) examJ neA = 1参数选择：procedure examineExample(12)y2 = target12alph2 = Lagrange multipiier for 12E2 = SVM output on point12 - y2 (check in error cache) r2 = E2*y2if ( (r2 -tQ.l & alph2 to 1 & alph2 0)Lf (number of non-zeo & non-C Ipha 1)(i 1 = resul t. q t second choice heur 1st ic (sect-： on 2,2) if takeStep (ilf i2) return 1loop over al1 non-zero 3nd ncrn-C Iphar starting 旦一 a randcun point :11 = identity of current alphai f takeStep ( lf ：.2) return 1)loop aver all possible 11, star-J ng at a random poin- :i1 = Loop variableif (takeStep(1H2) return 1)return 0 endprocedure参数更新：procedure takeStep (i1,i2) if (il = i2) return 0 alphl = Lagrange muItiplier for i yl = ta rget n 1 El = SUM output on pointi11 - yl (check in error cache) s = yl*y2Compute L, H via. equations (13) and (14) if (L = H) return 0kl 1 = kernel (point il f po.i nt il ) kl2 = kernel(pointilfpoint i2) k22 = kernel(pointi2f point2) eta = kll+k22-2+kl2 if (eta 0) a2 = alph2 + y2*(E1-E2/eta if U2 H) a2 = H)elseLobj = objective function at a2=L Hobj = object.ive function at a2=H if (Lobj Hobj+eps) a2 = Helse a2 = alph2 if (|a2-aiph2| avcijr -i n ji i ej k-i i i u h jr开始训练,18 56 300.12680138791642032 4.658191 3.5073960.2402438674811237 3.457096 -0,0822160.3670452553975438 6*080573 9.4188860.8106342724751081 -0.271240G721112174 -3.8247408239349932训练结束开始预测一.预测正确率为：1.032msCycle.txt：Cycle2.txt：支持向量是少数，分类超平面在中间。2.5超片面映射 至U2维21.50.5 0-1-1.5-2.5510152025303540-2.5-2-1.5-1-0.50O.&11.522 5不规则图形.txt：40 -35 -30 -25 -20 -15 -10 -5 -0 -0分类超平面是比较优秀的，并不是在图像的点上，而是大约在中间。存 在容错点：人脸.txt：同样的处理。人脸图像更复杂一些，同一类是不连在一起的。能正确分 类同样存在容错点。m-nrEd-i|而青 Insert IQo-5IQms-ktop15-ndQE tle-pheart_scale：核函数为线性的时候:预测正确率为：0-79 109ms非线性（高斯核，sita=1）：预测正确率为：0.8494ms非线性（高斯核，sita=0.5）：（过小存在过度拟合的情况）预测正确率为：0-95112msBigdata.txt：总共10000条，主要用来测试运行时间。发现数据量大就很难进行训练。训练数据运行时间500167ms1000219ms1500546ms20001297ms25001843ms30004410ms35005429ms40005815ms45007402ms500010857msSVM算法分析:不适合于大数据，因为需要进行大量的核函数等运算。如果对核函数进 行缓存，则需要缓存一个N*N的矩阵（N是训练样本的个数），会占用大 量的空间。相应的，linear svm可以解决这个问题。