基于Python的支持向量机分类算法研究分析计算机科学与技术专业.docx

摘要在大数据盛行的时代背景下，机器学习这门学科的广泛应用。并且列举运用PythOn语言进行数据处理的优势，将其与传统语言进行对比，充分体现了PythOn语言在语言简洁，效率高等方面的优势。这也是本文最后选择PythOn语言实现SVM算法的主要原因。本文主体内容阐述了支持向量机算法(SVM)的基本内涵，并且用图示和数学方法形象具体讲解了SVM的基本原理。具体分析了SVM算法中线性可分数据、线性不可分数据和含有。Utlier点的数据集的分类方式。通过对偶问题求解法、核函数、及SMO算法等实现了对最优超平面的求解。并且完成了二分类问题向多标签分类问题的推广。文章通过，使用手写数字数据集在PythOn上进行SVM模型的训练与测试，体会SVM算法如何解决实际问题。具体的表现了用Python语言实现SVM算法的优势，直观的展现了实验成果。关键字：机器学习PythonSVM最优超平而核函数AbstractIntheeraoftheprevalenceofbigdata,machinelearningiswidelyusedinthisdiscipline.AndenumeratetheadvantagesofusingPythonlanguagefordataprocessing,compareitwithtraditionallanguages,andfullyembodytheadvantagesofPythonlanguageintermsofsimplelanguageandhighefficiency.ThisisthemainreasonwhythisarticlechoosesthePythonlanguagetoimplementtheSVMalgorithm.ThemaincontentofthispaperexpoundsthebasicconnotationofSupportVectorMachine(SVM),andexplainsthebasicprincipleofSVMconcretelywithgraphicandmathematicalmethods.TheclassificationOfIinearlyseparabledata,linearlyindivisibledata,anddatasetswithoutlierpointsintheSVMalgorithmisspecificallyanalyzed.Thesolutiontotheoptimalhyperplaneisachievedthroughthedualproblemsolvingmethod,kernelfunction,andSMOalgorithm.Andithascompletedthepromotionofthetwo-classificationproblemtothemulti-labelclassificationproblem.Passingtheendofthearticle,usingthehand-writtendigitaldatasettotrainandtesttheSVMmodelinPython,tounderstandhowtheSVMalgorithmsolvespracticalproblems.ThespecificperformanceoftheSVMalgorithmusingPythonlanguageadvantages,intuitivedisplayoftheexperimentalresults.Keywords:machinelearning,Python,SVM,optimalhyperplane,kernelfunction第一章绪论1.1 机器学习随着互联网计算机技术的普及应用与发展，随处可见的数据信息数量日益庞大,数据与信息与人们的生活愈发的息息相关。数据量的不断扩大和信息获取方式的不断增多，带来了信息处理日益困难的问题。伴随着硬件性能的快速增长，人们寄希望于计算机可以帮助人类处理越来越庞大的数据。因此，机器学习在近年来得以迅速兴起与发展。机器学习(MaChineLeaming,ML)是集合了多种领域知识的一门学科，涵盖统计学、概率论、算法复杂度理论等多个领域。用于研究计算机通过模拟人类的学习行为，并且由此去的新知识和技能的能力。机器学习是计算机人工智能的核心，被应用于人工智能的多个领域。顾名思义，机器学习是使用机器来模拟人类学习行为的一项技术。具体来说，机器学习是一门训练机器获取新知识或新技能，包括获取现有知识的学科。这里所说的“机器”，指的就是计算机、电子计算机、中子计算机、光子计算机或神经计算机等等。机器学习已经在很多领域进行了广泛应用，例如：计算机视觉、DNA序列测序、语音识别、手写识别、医学诊断。机器学习算法是一种能够从数据中进行持续学习的算法。MitChen(1997)为其提供了一个简洁的定义：对于某类任务T和性能度量P,一个计算机程序被认为可以从经验E中学习是指，通过经验E改进后，它在任务T上由性能度量P衡量的性能有所提升。其中任务T指的是人们希望机器可以实现的功能。在分类、回归、异常检测、转录、机器翻译等任务上，机器学习已经有了广泛的应用。而获取经验E的过程可以分为无监督算法和有监督算法。两者的区别在于是否对数据集中的数据样本给予标签。1.2 支持向量机在监督学习中，支持向量机是影响力最大的机器学习方法之一。支持向量机由CorinnaCortes和Vapnik等人于1995年提出，其创新的核技术使其不再局限于对线性数据的处理，在对于非线性数据的分类上也有了良好的表现，并已被广泛应用于文本识别、手写字体识别、及时间序列预测等小型分类任务中。支持向量机(SUPPortVectorMachines,SVM)这种机器学习方法是以统计学理论、VC维理论和结构风险最小化原理为基础的。在解决特定问题，如小样本、非线性和高维模式问题时表现优异，并且大大优化克服了机器学习中会遇到的“维数灾难”问题与“过学习”问题。SVM具有如下特点：(1)以非线性映射为理论基础，利用内积核函数实现由低维空间到高维空间的非线性映射。(2)以寻找最优超平面为目标，核心思想为最大化分类间隔。(3)以少数支持向量为训练结果，去除了大量冗余样本，具有良好的鲁棒性。(4)理论基础坚实、数学模型简单明了，可以归结为一个受约束的二次型规划(QuadraticProgramming,QP)的求解问题。(5)可以运用牛顿法、内点法等经典优化算法，方便快捷地求得最优解。SVM作为一类二分类模型，可以处理以下三类数据：(1)线性可分数据。使硬间隔最大化，进行线性分类器学习(2)近似线性可分数据。使软间隔最大化，进行线性分类器学习(3)线性可分数据。使核函数与软间隔最大化，进行非线性分类器学习。平面内的直线，对应线性分类器；平面上的曲线，对应非线性分类器。硬间隔虽然可以将线性可分数据集中的样本正确分类，但是受到OUuier样本的很大影响，不推荐使用。软间隔可以对近似线性可分数据和非线性可分数据进行分类，离超平面很近的outlier点可以允许被错误分类，从而可以更广泛的应用。1.3 Python语言PythOn这门语言已经产生并发展了30余年，是目前最受欢迎的程序设计语言，也是通用编程语言中最接近自然语言的。Python侧重于求解计算问题，其具有语法简单，语言表达层次高等特点，这与计算机问题解决中的思维理念相吻合。Python语言将问题和问题的解决方案进行简化，从而达到问题的自动化求解，是当下最直观的利用计算机解决复杂信息系统的工具。Python语言的适用群体广泛，任何需要使用计算机来解决计算问题的人群都可以使用，即使是非计算机专业从业人员。Python语言是一种轻化语法，弱化类型的计算机语言，同C语言等相比较，不需要指针和地址等计算机系统内必须的结构元素；可以不定义变量就直接使用(解释器会自动匹配)；语言内部通过UTF-8编码来实现，字符串类型独立，操作多语言文本时，语言大大简化，可以优秀的支持中文；运用变长列表代替定长数组，可以将多种数据类型进行兼容并可以灵活地表示集合长度。PythOn语言除了有基本语法，还是一个脚本语言，直接运行源代码便可以执行，这可以让程序运行和源代码相融合。这种模式的优势在于：(1)有利于源代码维护。(2)可以跨操作系统操作。(3)可以实现代码的交流与设计。Python具有简洁的语言代码，能支持两种设计方法，即：面向过程与面向对象这两种设计方法，且不需要通过函数封装程序，因此代码长度仅为C语言代码长度的十分之一到五分之一。综合以上所谈，总结PythOn语言的优点如下：(I)PythOn这种解释语言可大大方便编程。解释语言具有先天优势，即：不需要编译时间，可以大大提高工作效率。(2)PythOn有很多非常成熟的库可以利用，开发生态优秀。如：NumPy(存储和处理大型矩阵)、SciPy(高效的数学运算)、pandas(处理数据的函数和方法)、matplotlib(数据操作、聚合和可视化)等。(3)PythOn的运行效率不低。与PythOn友好的库可以提高程序运行的速度，在团队的有力支撑下，库的效率可比程序员用C语言调试优化一个月的效率还高。在本文中，介绍了支持向量机可解决的线性数据分类、近似线性数据分类和非线性数据分类这三类问题，并且通过使用具有编写效率高、语言简洁和可直接使用的第三方支持库种类全面等特点的Python来实现SVM算法，快捷便利地实现数据样本的分类问题，展现了SVM与Python在机器学习方面的优势所在。1.4 论文主要研究内容本文分析了在信息化飞速发展的大数据背景下，运用Python语言处理数据的优势与可行性，重点讲解了SVM算法的基本原理，和在面临不同数据集的分类问题时所用的具体方法，对此进行了详尽的数学分析和原理阐述。并最终用PythOn语言实现了多标签的SVM分类训练。第二章支持向量机的原理2.1 线性可分问题对于一个给定的数据样本集D=O,yJ,(冗2，、2)，,Qn,%)，支持向量机的基本原理就是要在给定的样本空间中找到一个超平面将不是同一类型类型的数据样本分开。如图2.1所示，在如下的二维平面中，将两种不是同一类型的数据分别用图形0和X进行表示，对于线性可分的两类数据，可以用一条直线将两类数据分开。这样的直线就是一个超平面。将这条直线一侧的数据点标记为y=-l,另一侧的数据点标记为y=lo如图2.2所示，在一个给定样本空间中，超平面可由式(21)表示：Wx+b=0(2-1)式中，用W=(W1；1%；Wd)表示超平面的法向量，位移项则用常数人表示。由法向量W和位移项人确定的划分超平面记为(W/)。对于数据集里任意数据点，当为二1时，有W7+b>0,当时，有Wxi+b<0,即：(Wxi+bltyi=1(Wxi+b-1,%=-1当式中等号成立的时候，项为距离超平面最近的样本点，这些样本点被称为支持向量。2.2 函数间隔与几何间隔通过观察卬/勺+b的符号与力的符号一致与否可判断分类超平面是否选取正确，所以，可以用%(W0i+b)的正负性来判断分类的正确性，由此，定义函数间(Functionalmargin)为:Yf=y(Wx+b)(2-3)据此，在超平面(W,b)中关于样本集D中的所有样本点(看,)的最小函数间隔值便是超平面(W,b)对于样本集D的函数间隔：Yf = minyF£(i=l,.,n)(2-4)但是，当卬和成比例改变时，函数间隔的值也会成比例变化，如卬和b变化为3W和3人时，函数间隔的值也会变为原值的3倍，所以如此定义的函数间隔是不完全正确的，还需要引入几何间隔(GeometriCaImargin)这一定义。样本集D中任一点九到超平面(W/)的距离，定义为几何间隔。如图2.3所示，在二维空间上有一点Xi和超平面(W/)(在此为直线)，)为Xi在超平面上的垂直投影点，4为点勺到该超平面的距离，则有：(2-5)图2.3式(2-6)中的Ilwll为向量W的L2范数，即将向量W中的各元素求平方和后开根号所得的值。将点项代入超平面方程式(21),可得：Wx0=-b(2-6)将式(2-6)两边同时乘上W7又由=IIWll2及式(2-7)可推出：由于间隔一般为正值，因此将几何距离与类别y的乘积定义为几何间隔，即：YG=(2-8)ygIwll'f由式(2-8)可看出，函数间隔乘向量卬的L2范数就可以得到几何间隔。2.3 最大间隔分类器如图2.4所示，对于一个样本集D,存在多个满足分类条件的超平面，这些超平面与数据点之间的间隔不一，甚至部分几乎紧贴数据点。对数据点进行分类的时候，为了提高分类的可靠性，需要寻找最优超平面(C)PtimalHyPerPIane),使得超平面的两侧的数据点与超平面的间隔，即图2.5中的GAP的值尽可能大。图2.4图2.5如图2.5所示，最优超平面用图中的实线来表示，此条实线到位于其两侧的虚线的距离相等，此距离等于几何间隔，两虚线之间的距离为几何间隔的2倍。在超平面确定之后，再等比例地放大或缩小卬和从WG+b的值也会随之放大或缩小，所以函数间隔对于使间隔值最大化没有意义。而几何间隔为函数的间隔的IlWlI,可以使得几何间隔在放大或缩小W和人的时候保持不变，几何间隔只因超平面的改变而改变。综上所述，用于寻找最优超平面的最大间隔指几何间隔。为了方便公式的推导，令式(28)中的函数间隔YF为1,可得：目标即为求在约束条件力(勿。i+b)l(i=l,2,n)下，几何间隔的最大值,即：(2-10)2.4 用拉格朗日乘数法求最大值由上文可知，SVM的原目标函数为几何间隔的两倍，即:(2-11)(2-12)C2max2Yg=max而为了求解方便，将目标函数转换为：m42s.t.y(Wxi+b)l(i=l,2,.,n)原命期：IImin2Kf微博：碘说工作室网站 微信公众号：数说工作室si.K(WrX：+b)NLi=L2,.n构造函数：尸(w,b,a)=4m'-方心(WTXj+b)Tr三l公.C(W)=max尸(wb.a)al>Q这个函数意味着通过调整a的大小，使得F函数最大。当约束不满足时，即>NX-b)<l,一定可以调整a使得C(W)无限大(令3等于正无须呵。当约束满足时，我们能让F函数最大的，也就是取到了因此约束满足时，有：C(W)JIlwf那么原命题就等价于：minC(w)=minmaxF(v.b,a)=pw.w.bat>0图2.6现有的目标函数式(212)为二次函数，约束条件为线性条件，该问题可以使用拉格朗日对偶性(LagrangeDUaIity)转换为优化对偶变量(DUalVariabIe)的问题。在约束条件前乘以拉格朗日乘子从而将目标函数与约束条件融合为一个函数表达式：L(Wt b, )=Iwll2n-W %(yt(w7*%t + 力)- 1) i=i(2-13)(2-14)令:(IV)=maxL(W,bta)«iao当约束条件不被满足，即yt(W7+b)-IVO时，显然，B(W)=+8；当约束条件得到满足时，即yi(WGi+b)l0时，6(卬)=等，因此：(IV)=<嘤，满足约束条件1+8,不满足约束条件(2-15)由式(2-14),目标函数可转换为:minQ(W)=minmaxL(W,b,)=p*W,bW,bai>0r(2-16)其中，户为问题的最优解，为方便求解，根据对偶性，将式(2-15)转换为:maxminL(W,b,)=dt,W,bo(2-17)其中，产为新式的最优值，且d*<p*,当满足一定条件时等号成立，/为p*的近似解。2.5对偶问题求解假设为定值，求minL(W,b,a)oW,b首先对卬、b,分别求偏导数，且令偏导数值为0：(2-18)将式(2-18)的结果代入式(213),得：Inn1.(W,b,)=2W0ti%yj%勺一W四。必才引勺i,j=li=li=l推导过程如下:=Wai-BWaiaJyiyJ*Xii=lL(W,bta) =IwIl2n-WaMyi(W,阳+")T)i=l+w% i=li=ln=-WW-aiyiWxii=ln=泮/WaiyKii=lnWaiyW阳-I=Inn四为+W°ti=li=lnnni=li=li=l(n、丁HnnW四为阳)W四%勺一匕W%+WOCii=l)i=li=li=lInnn=一5W%(修)7%与jb4%+W%i,j=li=li=lnn=Wai-2W%'%Xbj(2)根据(1),变量W和已被消去，只有未知，由式QJ9),求TnmL(W,b,)WtD对的极大值：TnyWai-BW(Xiajyiyj4xji=lij=lns.t.Watyt=0i=l(2-20)aiO求得最优解%,记作6*。根据KKT条件解得:(2-21)w*=W6*yii=l.n6=%-Wai*%冷勺)Ii=l求得最优超平面为：Wx+b“=O(2-22)第三章线性不可分3.1 核函数在实际应用的求解中，原始数据往往是线性不可分的。如图3.1所示的二维空间内，有若干红球与篮球，显然，无法找到一个超平面(直线)将这两类小球进行分类。对于这种线性不可分的情况，在SVM中，可以使用核函数和松弛变量来求解这类问题。图3.1数据在原始空间内不线性可分的问题，可以通过将其投射到高维空间这一办法来解决。其原理是当数据线性不可分时，SVM会优先在低维空间中进行计算，然后使用核函数将原始空间映射到高维空间，达到在高维空间中找到最优超平面的效果，成功地实现在低维空间本身将不能分类的非线性数据分类。如图3.2所示，这些数据在二维空间中无法进行线性分类，因此将原始数据投射到三维空间中进行分类。图3.2然而，若一遇到非线性数据就将其投射到高维空间，那么一个原始二维空间经映射将成为一个五维空间；一个原始三维空间经映射将成为一个19维度空间。新空间的维数呈爆炸式增长，带来了庞大而困难的计算量。并且，在无穷维的情况下，无法进行计算。核函数的优势在于，由于在SVM的求解过程中只用到内积计算，而核函数的值恰好等于其在高维空间内的内积值，因此可以大大简化SVM的计算过程。此外，与传统算法LogiStiC回归算法、DeCiSionTree算法相比，利用核函数进行数据分类时，效果更加完美。在图3.3中的三种分类方式效果对比图可以很直观的体现这一优势。图3.3如表3.1所示，常用的核函数有多项式核函数、高斯核RBF函数、SigmOid核函数。表3.1常用核函数核函数名称核函数式多项式核函数K(XpX2)=(X1X2+c)d高斯核RBF函数K(Xl,力)=exp(-yx1-X2II2)Sigmoid核函数K(x1,x2)=tanh(x1x2÷c)在选择核函数时，需要依靠先验领域知识或交叉验证等方法，若没有更多信息、，普遍选用高斯核函数。3.2 松弛变量在前文中，已经讨论了线性可分数据和非线性可分数据的处理方式，即当数据为线性可分时，可找到一个超平面将数据直接进行分类；当处理非线性数据时，可以使用核函数将原始数据投射到更高维空间后进行分类。然而，还是存在一些特殊情况对于以上两种方法都不适用。如图3.4所示有若干蓝色小球与粉色小球，其中有一个蓝色小球(OUHier)M偏向于粉色小球堆。黑色虚线为根据数据计算得到的超平面，此时该超平面严格地将红色小球与蓝色小球进行了分类，然而GAP的值却变得很小。甚至在某些情况下，当蓝色小球M混入粉色小球堆中，SVM无法找到一个合适的超平面将两类小球进行分离。如果将偏离的蓝色小球忽略后进行分类，可以获得图中的GAP更宽的红色超平面。为了应对这样的由于个别数据点严重偏离大多数数据点所在区域的情况,SVM允许有个别数据点偏离超平面，即某些数据点的函数间隔小于Io在实际应用中，引入松弛变量(SIaCkVariable)SO,考虑OUuier后的约束条件为:(Wxi+bl-ityi=lkWxi+b-1+i,yi=-1式(3-1)亦可表不为：yi(Wxi+b)l-i(i=l,2,.,n)(3-2)由式(3-2),显然当&取无限大值时，所有超平面都可以满足条件，因此，在原目标函数上添加一项，使8的和也取得最小值。随之，SVM的目标函数由式(2-13)转化为式(3-3)：.r19、min-+C2Ji,(=l,2t.fn)i=ls.t.yi(Wxi+b)1-fj,(i=1,2,n)(3-3)iO,(i=1,2,.,n)其中，C为权重值，用于在最大化GAP和最小化数据偏差之间平衡。同样，在约束条件前乘以拉格朗日乘子a,从而将目标函数与约束条件融合为一个函数表达式，构造得到新的拉格朗日函数：IlWlI2v",1.(W,btaffry)=-ai(yi(Wxi+/?)-1+j->r总i=1=1为求得最优解,的偏导数都为0,即:(W = 1aiyixi F= % = O (C i = O(3-5)将解代入式(3-4)得目标函数:nW WaiTW孙 XPi=lnst1=1% = ° i = 1,2, .,n将式(36)与式(220)对比可知，含有outlier的分类问题中的火多了上限C的约束条件。而在核函数中也只需把孙勺替换成Kai,专)即可。综上所述，可以解决线性可分、线性不可分和含有outlier点的三种SVM问题。3.3 高斯核函数与松弛变量的综合应用综合核函数与松弛变量的使用，可以更好的解决分类问题。如图3-5所示有若干红球与绿球，且个别红色小球混入了绿色小球堆中，而个别绿色小球混入了红色小球中。通过使用高斯核，获得超平面后映射回原空间中，得到曲线将两类小球分离，而通过引入松弛变量，允许有个别小球偏离超平面。在已经使用高斯核的基础上，选择不同的。和f可以获得不同的分类效果，观察图3.5(a)和图3.5(e)、图3.5(b)和图3.5、图3.5(C)和图3.5(g)、图3.5(d)和图3.5(h)四组图片可知，惩罚因子C越大，意味着对OUtIier点约重视，越不愿意放弃OUtlier点；而观察图3.5(a)、图3.5(d)和图3.5(e)、图3.5(h)两组图片可知，。值越大，意味着outlier点的数量和GAP值越小。在实际应用中，需要选择合适的核函数、惩罚因子C与松弛变量的值以获得合适的超平面。30图 3.5(a)602图 3.5(b)高斯楂，C=1 0,高斯核，C=1.0, =100 0图 3.5(c)图 3.5(d)图 3.5(e)图 3.5(f)高斯核，C=5.0, =10.0高斯核.C=5.0, =100.0图 3.5(h)图3.5(g)相关代码如下所示。data-np.Ioadtxt('bipartition.txt',dtype-np.float,delimiter-'t,)×,y-np.split(dataj(2,)ja×is*l)y=y.ravel()clf-para*('linear.l),('linear',.5),('linear,1),('linear',2)j(,rbf,f1,0.1),(,rbfI91),1.10),(,rbf'f1.Iee)I(rbf,5,"1),(rbf',5,1),Crbf,5,10),(,rbf,5,Iee)XIJVinl×lsaa×三×:0.ain()j×:,0.ma×()×2jin,×2jb×=x:>ladn(),×:jl.ma×()二二百×1,×2-np.grid×1-in:×ima×:2j1x2-in:×2-a×:2j"/6Wgridtestnp.stack(×1.flat,×2.flat),a×isl)*d'c三-light,up!.colors.ListedColornap(,t77EA*j,¢FFA0AO,)Cjdark=mpl.colors.ListedColoraap('g>>'r'J)pircParams'fornams"if'三SimHei,mpl.rcParams,axes.unicodc_minus'-Falseplt.figure(figsize(18,14J,facecolor-,w,)forijparaainenumerate(clf_para«):clf三sv三.SVC(C=paraml,kernel三para0)ifpara0*«,rbf,:cH.garna-paran2title-高盛核，C三X.lf$xi$%.lf,%(paratnl/param2)else:title>线性核,C三X.lfXparamlclf.fit(×jy)y-hat=clf.predict(×)showaccuracy(yhat,y)W演“三prit(title)Print('支IJ向里的数目：，clf.n-support)PrirVt('支IT向里的系数：，clf.dualcoef)Print('支II向里：；clf.supportJpit.subplot(3%i+l)gridhat«clf.predict(gridtest)grid-hot三grid-hat.reshape(xl.shope)pit.pcolormesh(×l,×2,grid-hat,Ce叩=CLlight,alpha>0.8)pit.scatter(x:#0,x:f1,cy,edgecolors-,k',s40,cmap«c«i_dark)pit.scatter(xclf.supports,×clf.support-,1,edgecolors三'k',facecolors*,none,s«100,marker，。')z=cIf.decision-function(grid_test)prit(,zz)print('clf.decision,function(x)-',clf.decision-function(×)print(,clf.predict(x)三,clf.predict(×)z三z.reshape(×l.shape)pit.contour(×1fx2,z»colors三list(,kbrbk'),Iinestyles,-,-,',-linewidths-lf.5,1.5,.S,1,levels-(-l>-0.5,g.5,1)pitxli(xljnin,×1-a×)plt.yli(x2-mij×2-ma×)plt.title(title,fontsie三14)pl±suptile('SVM不同爹数的分类,fontsize2)plt<tIghtsIayout(14)pit,subplots_adjust(top.92)plt.savefig(,l.png)3.4 多标签分类(multilabelclassification)多标签分类可以转换为单标签分类。其中一种方法是将每个多标记实例的所属标记联合起来创建为一个新的标记。这种方法被称Label-PoWerset。由此，多标签分类问题转换为了单标签分类问题。转换后的分类问题可以使用任何分类器进行分类。另一种方法是采用一对多(OAA)策略：训练针对类别i的二元分类器，将类别i训练样本与其他样本分离。在分类过程中，X被分为了多标签类。其中"为类别数。这种方法称为二元相关方法，此方法是单标签一对多策略的扩展。3.5 SMO求解对偶问题在第三章中得到了SVM的目标函数式(3-6),为了实求解结果同时适用于线性可分与线性不可分问题，首先将目标函数式(36)中的阳,勺)替换为核函数K(/*2)并取负得到新的目标函数：in()=mm)匕岑=Iaiajy仍Kai,巧)一£仁Iais.t.WctM=°(»=12,11)i=l0%C(3-7)该目标函数需要求解向量的n个参数(1,a2,a3,a),有多种算法可以求解该目标函数，但序列最小优化算法SMO将求解N个参数的二次规划问题分解成了多个二次规划问题分别求解，每次只求解两个变量，同时将其他变量看作常量，不断循环直到获得最优值。该方法虽然迭代次数较多，但每次迭代的计算量小，因此在求解效率和内存需求上都有了显著的进步。假设已经固定了n-2个参数(a3,a4,a5,，an),求解与a2,则目标函数转换为：11minW(Xl,o)=oua2÷ok22a22+七2%为一(«1一。2)+YiaiV1+y2«2v2+MaZL(3-8)其中M为常量，Kij=K(xpXz),Vi=y=3a;y;K(Xpxy),i=1,2。为了求解该子问题，首先将目标函数中的等式约束转换为：«iyi+«2y2=-W=(3-9)i=3则%=yi(一。2丫2)，将其代入式(3-8),对。2求导并令其为0：=(C11+C22-2K12)a2-K11y2+y1y2-1-v1y2+v2y2=0(3-10)0CL2可求解得到。2,带入式(3-9)得,分别记作。271'!/。由于的值难以计算，对式(310)进行变形，使得(X27iew可以用更新前的。2。以表示。根据式(2-21)的超平面表达式可知，新的数据点的预测值为：/(x)=afyiKxbxj)+b(3-11)则VI与V2的值为：(V1=/(Xi)-b-a1y1K11-a2y2K12(312)Iv2=/(x2)-b-a1y1K12-a2y2K22将其带入式(3-10),并令(Kll+K22-2K12)=,预测值与真实值之差Ei=f(xi)-得：2nevv=a20ld+(3-13)由于此时获得的(l27iew在计算中未考虑约束条件，将(X2ziew记作。2海卬山neaped,而约束条件在二维平面中的表示为图3.6,最优解必须在图中的线段上取得，因此La2newH,L与”的取值预决于力与力是否相等，具体取值为：(=max0,1-a2=minC,C+%a2'以”1.=maxO,a1+a2-CH=minGa1+a2>yi=y2经过上述约束条件的修剪即可获得最优解。2襁卬：newHq2new,unclipped>Hnew,undippedL<new,unclippedVH1.q2new,unclipped<L获得new后，根据。2海卬与a/ew的关系可以求得ajew的值:图36而b的值首先需满足如下条件：(3-16)Q,0<a1new<Cb=b2,0<a2eu,<C<E+b2)2,其他更新格式为：b1new=bozd-E1-y1(a1evv-a1ozd)K(xnx1)-y2(a2new-a2oid)K(xn%2)(3-17)b2new=b°zd-F2-y1(a1-a1ofd)K(xnx2)-y2(a2n-a20id)K(%2,%2)(3-18)当与(X2更新后，匕和E的值也同时需要更新，当所有都更新后，即可获得分类平面函数式(3-11)。以上所述为已选择两个乘子后，对两乘子的求解过程。而乘子的选择的步骤为:(1)扫描所有乘子，将第一个不满足KKT条件的乘子进行更新。(2)在所有满足KKT条件的乘子中寻找满足条件TnMEL助乘子作为第二个乘子进行更新。第四章SVM分类实例4.1使用Python运行SVM分类实例在前文中介绍了SVM分类算法的基本理论。SVM的基本思想为寻找样本空间的超平面并在最大化数据间隔的基础上进行分类。当处理非线性问题时，SVM引入了核函数，将低维数据映射至高维数据后使其变为线性可分后进行分类。考虑到数据样本中可能存在“噪声”，引入了松弛变量，使分类器有一定的容错能力。本章通过使用mnist手写数字数据集在Python上进行SVM模型的训练与测试，体会SVM算法如何解决实际问题。Mnist手写数字数据集是机器学习的一个典型数据集，其数据来源于250个不同的人的手写数字，共包含70000张28*28像素的图片。如图4/所示为一个典型的手写数字，对于人眼而言可以轻易地识别出该数字为“0”一一高度比宽度稍长的一个椭圆。然而对于计算机而言很难将人类的这种直观感受用算法表达出来。O图4.1手写数字图表4.1分类器结果实际值预测值PositiveNegative正TPFN负FPTN机器学习通过大量样本学习认知规律这一方法与人类类似，但其具体地学习认知规律的过程与人类有所不同。对于SVM,解决本问题的思路是首先读取大量带有标签的手写数字，之后寻找出可将不同标签数据进行分类的超平面，即获得了预测函数可以识别出新的手写数字的规则。此外，随着样本数量的增加，SVM可以学习到更准确地认知规律。然而，当样本数过多时，也可能出现过拟合的情况，即模型过度地拟合了训练数据，而对于测试数据而言，其分类效果却较差。图4.2为样本集中的部分图像，由于mnist手写数字数据集原始数据为图像，而SVM无法识别图像，因此首先对数据进行预处理。原始图像为28X28灰度图，其每一个像素为一个0255的灰度值，O为纯黑，255为纯白。因此将读取灰度图的每一个像素的灰度值，并将其存入一个1X785的一维数组中（第一个元素为标签），则数据就由图像转为了数据，之后将所有训练数据与测试数据分别保存至CSV文件中。训练图片：0O010201020训练图片2IIO 10 20训练图片6IIIO20O 1020测试图片 010 2001020