数据挖掘导论--第5章-分类-5.5-SVM-2017

5.5支持向量机支持向量机支持向量机(SupportVectorMachines,SVM)源于Vapnik和Chervonenkis的统计学习理论的早期工作第一篇论文是Boser,Guyon和Vapnik[BGV92]的文章优点对复杂的非线性边界的建模能力与其它模型相比,它们不太容易过分拟合支持向量机还提供了学习模型的紧凑表示广泛的使用范围SVM可以用来预测和分类它们已经用在许多领域,包括手写数字识别、对象识别、演说人识别,以及基准时间序列预测检验支持向量机两个线性可分的类找到这样一个超平面，使得所有的方块位于这个超平面的一侧，而所有的圆圈位于它的另一侧可能存在无穷多个那样的超平面“最大边缘”原理：即追求分类器的泛化能力最大化。即希望所找到的决策边界，在满足将两类数据点正确的分开的前提下,对应的分类器边缘最大。这样可以使得新的测试数据被错分的几率尽可能小。◇如下图所示的情况(b)就比情况(a)与(c)的泛化能力强,其原因在于其分界面与两类样本中的最近邻的样本的距离最大.Class1Class2Class1Class2Class1Class2(a)(b)(c)决策边界的边缘denotes+1denotes-1直观而言，如何分类这些样本？即给出一个决策超平面更多的例子：要考虑以下因素：◆经验风险最小(已知的样本错分最少)◆泛化能力最大(可能出现的新样本错分最少)决策边界的边缘denotes+1denotes-1更多的例子：决策边界的边缘denotes+1denotes-1更多的例子：决策边界的边缘denotes+1denotes-1更多的例子：决策边界的边缘denotes+1denotes-1所有的决策超平面都是可行的。但是应该选择哪一个为最优决策超平面呢？更多的例子：决策边界的边缘ClassifierMargindenotes+1denotes-1Definethemarginofalinearclassifierasthewidththattheboundarycouldbeincreasedbybeforehittingadatapoint.更多的例子：决策边界的边缘MaximumMargindenotes+1denotes-1Themaximummarginlinearclassifieristhelinearclassifierwiththe,um,maximummargin.ThisisthesimplestkindofSVM(CalledanLSVM)LinearSVM更多的例子：决策边界的边缘denotes+1denotes-1Themaximummarginlinearclassifieristhelinearclassifierwiththemaximummargin.ThisisthesimplestkindofSVM(CalledanLSVM)SupportVectorsLinearSVM更多的例子：决策边界的边缘SVM的决策边界和边缘一个线性分类器的决策边界可以写成如下形式：wx+b=0其中，w和b是模型的参数B1b11b120bxw1bxw1bxw边缘方块的类标号为+1，圆圈的类标号为1z的类标号y调整决策边界的参数w和b，两个平行的超平面bi1和bi2可以表示如下bi1：wx+b=1bi2：wx+b=1可以证明,边缘d0bif10bif1zwzwy||||2wd边缘推导w的方向垂直于决策边界如果xa和xb是任意两个位于决策边界上的点，则wxa+b=0,wxb+b=0于是w(xbxa)=0.由于xbxa是决策超平面中任意向量,于是w的方向必然垂直于决策边界令x1是bi1上的数据点，x2是bi2上的数据点.代入bi1和bi2相减得到w(x1x2)=2由令u=w,v=x1x2,得到||w||||x1x2||cos(w,x1x2)=2),cos(||||||||||||||||),cos(vuvuvuvuvuvu即边缘推导(续)||w||||x1x2||cos(w,x1x2)=2同时||x1x2||cos(w,x1x2)=d于是||w||d=2，即2||||dwSVMSVM的训练阶段从训练数据中估计决策边界的参数w和b最大化边缘d，并满足wxi+b≥1如果yi=1wxi+b≤1如果yi=1即yi(wxi+b)≥1最大化d等价于最小化这是一个凸二次优化问题，可以通过标准的拉格朗日乘子（Lagrangemultiplier）方法求解Nibyii,...,2,1,1)(||||21min2wxw约束条件SVM(续)拉格朗日算子其中，参数i称为拉格朗日乘子对Lp关于w和b求偏导，并令它们等于零因为拉格朗日乘子i是未知的，因此仍然不能得到w和b的解211||||()12NpiiiiLybwwx11000NpiiiiNpiiibLyLywxw(5-38)(5-39)(5-40)SVM(续)使用Karuch-Kuhn-Tucher（KKT）条件：i≥0i[yi(wxi+b)1]=0（5.42）除非训练实例满足方程yi(wxi+b)=1,否则拉格朗日乘子i必须为零i0的训练实例位于超平面bi1或bi2上，称为支持向量（5.39）和（5.40）代入到公式（5.38）中这是Lp的对偶问题(最大化问题).可以使用数值计算技术,如二次规划来求解1,12NDiijijiijLyyijxx(5-43)SVM(续)解出i后,用(5.39)求w,再用(5.42)求b决策边界为z可以按以下的公式来分类如果f(z)=1，则检验实例z被分为到正类，否则分到负类10Niiiiybxx1()()()Niiiifsignbsignybzwzxz对于许多实际问题,前面讨论的最优决策超平面的条件过于严格。◇对存在数据污染、近似线性分类的情况,可能并不存在一个最优的线性决策超平面◇存在噪声数据时，为保证所有训练数据的准确分类，可能会导致过拟合nibxwyxgyiTiii,...,2,11)()(不可分情况：软边缘(softmargin)SVMClass1Class2分类面不可分情况：软边缘(softmargin)SVMClass1Class2分类面不可分情况：软边缘(softmargin)SVM因此，需要允许有一定范围内的“错分”,又有较大分界区域的最优分类面软边缘（softmargin）SVM通过引入松弛变量、惩罚因子，在一定程度上允许错误分类样本，以增大间隔距离。在分类准确性与泛化能力上寻求一个平衡点不可分情况：软边缘(softmargin)SVM引入松驰变量i其中C和k是用户指定的参数，对误分训练实例加罚取k=1，C根据模型在确认集上的性能选择NibyCiiikNii,...,2,1,1)()(||||21min12wxw约束条件拉格朗日算子其中，前面两项是需要最小化的目标函数，第三项表示与松弛变量相关的不等式约束，而最后一项是要求i的值非负的结果KKT条件i≥0,i≥0,i≥0i{yi(wxi+b)1+i}=0ii=021111||||{()1}2NNNiiiiiiiiiLCybiwwx不可分情况：软边缘(softmargin)SVM其中，C为惩罚因子，C越大,表示分类越严格,允许错分的样本受到的限制越大,错分的样本数少,越容易产生过拟合。虚线与实线为C=1和104所解得的决策超平面不可分情况：软边缘(softmargin)SVM软边缘(softmargin)SVM的基本工作原理：对存在数据污染、近似线性分类的情况,可能并不存在一个最优的线性决策超平面；当存在噪声数据时，为保证所有训练数据的准确分类，可能会导致过拟合。因此，需要允许有一定程度“错分”,又有较大分界区域的最优决策超平面，即软间隔支持向量机。软间隔支持向量机通过引入松弛变量、惩罚因子，在一定程度上允许错误分类样本，以增大间隔距离。在分类准确性与泛化能力上寻求一个平衡点。不可分情况：软边缘(softmargin)SVM非线性SVM使用非线性变换例:)1,2,2,2,,(),(:2121222121xxxxxxxx样本非线性可分，将其映射到高维空间，可使样本线性可分非线性SVM：从低维空间到高维空间的映射0x2x0x样本非线性可分，将其映射到高维空间，可使样本线性可分Φ:x→φ(x)非线性SVM：从低维空间到高维空间的映射因此对非线性问题,可以把样本x映射到某个高维特征空间H,并在H中使用线性分类器.非线性SVM非线性SVM的优化问题约束条件:yi(w(xi)+b)≥1,i=1,2,...,N对偶拉格朗日问题参数w和b2||||min2ww=1,1()()2nDiijijijiijLyyxx(){()())1}0iiiiiijjjijyyybwxxx非线性支持向量机的基本工作原理对非线性可分的问题，可以利用核变换，把原样本映射到某个高维特征空间，使得原本在低维特征空间中非线性可分的样本，在新的高维特征空间中变得线性可分，并使用线性支持向量机进行分类。非线性SVM核技术Mercer定理:核函数K可以表示为K(u,v)=(u)(v),当且仅当对于任意满足g(x)2dx为有限值的函数g(x)，则K(x,y)g(x)g(y)dxdy≥0满足定理5.1的核函数称为正定（positivedefinite）核函数常用核函数(,)(+1)pKxyxy22/(2)(,)Kexyxy(,)tanh()KkxyxySVM的特点SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值SVM通过最大化决策边界的边缘来控制模型的能力需要提供其他参数，如使用的核函数类型、为了引入松弛变量所需的代价函数C等分类属性处理每个分类属性值引入一个哑变量,转化为二元变量例如，如果婚姻状况有3个值{单身，已婚，离异}，可以对每一个属性值引入一个二元变量可以推广到多类问题多类问题SVM是对二类问题设计的还有一些方法也是针对二类问题的如何处理多类问题?训练令Y={y1,y2,...,yK}是类标号的集合1-r方法:分解成K个二类问题每一个类yiY创建一个二类问题,其中所有属于yi的样本都被看作正类,而其他样本作为负类1-1方法:构建K(K1)/2个二类分类器每一个分类器用来区分一对类(yi,yj)为类(yi,yj)构建二类分类器时,不属于yi或yj的样本被忽略掉常用的SVM程序LIBSVM：~cjlin/mySVMSVM-Light……matlab的SVM函数使用1、数据预处理2、数据载入、归一化3、训练SVM分类器（svmtrain）4、分类可选的步骤：交叉检验，选择最优的核函数和参数svmtrain和svmclassify函数Svmtrain：Trainsupportvectormachineclassifier（训练SVM分类器）语法及调用参数：SVMStruct=svmtrain(Training,Group)SVMStruct=svmtrain(...,'Kernel_Function',Kernel_FunctionValue,...)