文档介绍：SVM分类器中的最优化问题电子工程学院周娇201622021121摘要支持向量机(SupportVectorMachines,SVM)是一种分类方法,它通过学会一个分类函数或者分类模型,该模型能把数据库中的数据项映射到给定类别中的某一个,从而可以用于预测未知类别数据的类别。所谓支持向量机,顾名思义,分为两个部分了解:一,什么是支持向量(简单来说,就是支持或支撑平面上把两类类别划分开来的超平面的向量点);二,这里的“机(machine,机器)”便是一个算法。支持向量机是基于统计学****理论的一种机器学****方法,通过寻求结构化风险最小来提高学****机泛化能力,实现经验风险和置信范围的最小化,从而达到在统计样本量较少的情况下,亦能获得良好统计规律的目的。在本文中,主要介绍了如何通过求解最优化问题来得到SVM分类器的最佳参数,使得SVM分类器的性能最好。线性分类如图(1),在二维平面上有两种不同的数据点,分别用红色和蓝色来表示,红颜色的线就把这两种不同颜色的数据点分开来了。这些数据点在多维空间中就是向量,红颜色的线就是一个超平面。图(1)图(2)假设是维空间中的一个数据点,其中是这个数据点的个特征,令, 1,z≥0-1,z<0()在图(1)中,处在红线左边的数据点,其y值为-1,反之,处在红线右边的数据点其y值为1。这样,根据y的值就把这个数据点分类了。那么分类的重点就在如何构造这个函数。设图(1)中的超平面(即红线)其表达式为,则=()直观上表示数据点到超平面的几何间隔,去掉分子的绝对值就有了正负性,是法向量,是截距。表示了数据点到超平面的函数间隔,如图(2)所示。由于是这个数据点的个特征,就是对特征进行线性组合,即给每一个特征加上一个权重。因为1,z≥0-1,z<0,=,=1或-1分别表示两个类别,而的正负决定它该分到哪个类别,所以我们以和符号是否一致来判断分类是否正确。令 γi=yi()()则γ>0表示分类正确,否则分类错误。那么我们需要求解出和这两个参数。最大间隔分类器对一个数据点进行分析,当它到超平面的几何间隔越大的时候,分类正确的把握率越大。对于一个包含n个点的数据集x(x1,x2,……,xn),我们可以很自然地定义它的间隔为所有这n个点的间隔中最小的那个。于是,为了使得分类的把握尽量大,我们希望所选择的超平面能够最大化这n个间隔值。令γ=minγi,i=1,2,……,n()所以最大间隔分类器的目标函数为maxγ()条件为γi=yi≥γ,i=1,2,……,n()即yi≥γ,i=1,2,……,n()其中γ=γ,即γ=γ,由于ω和的值可以缩放,令γ=1,则最优化问题转为:max1()≥1,i=1,2,……,n()通过求解这个最优化问题,我们可以得到一个最大间隔分类器,如图(2)所示,中间的红线为最优超平面,另外两条虚线到红线的距离都等于1,即γ=1。从原始问题到对偶问题及求解。原规划即:max1()≥1,i=1,2,……,n()由于求1的最大值相当于求122的最小值,所以上述问题等价于:min122()-1≥0,i=1,2,……,n()容易证明这是个凸优化问题。构造Lagrange函数将其变为无约束的最优化问题,给每一个约束条件加上一个Lagran