支持向量机ppt课件

,9.3,支持向量机,9.3 支持向量机,支持向量机，一种线性和非线性数据有前途的新划分类方法。巧妙利用向量内积的回旋，通过将非线性核函数将问题变为高维特征空间与低维输入空间的相互转换，解决了数据挖掘中的维数灾难。由于计算问题最终转化为凸二次规划问题，因此挖掘算法是无解或有全局最优解,。,支持向量机，一种线性和非线性数据有前途的新划分类方法。巧妙利,支持向量机定义,所谓支持向量机，顾名思义，分为两个部分了解：,一，什么是支持向量（简单来说，就是支持或支撑平面上把两类类别划分开来的超平面的向量点）,二，这里的“机（,machine,，机器）”便是一个算法。在机器学习领域，常把一些算法看做是一个机器，如分类机（当然，也叫做分类器），而支持向量机本身便是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。,支持向量机定义所谓支持向量机，顾名思义，分为两个部分了解：,SVM,的描述,目标：,找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。,解决方法：,构造一个在约束条件下的优化问题，具体的说是一个约束二次规划问题,(constrained quadratic programing),求解该问题，得到分类器。,SVM的描述目标：找到一个超平面，使得它能够尽可能多的将两类,概 述,概 述,1.,线性可分情形,1.线性可分情形,线性可分情形,最大边缘超平面,(MMH),边缘：从超平面到其边缘的侧面的最短距离等于到其边缘的另一个侧面的最短距离，边缘侧面平行于超平面,线性可分情形最大边缘超平面(MMH),分类面与边界距离,(margin),的数学表示,:,分类超平面表示为：,Class 1,Class 2,m,数学语言描述,分类面与边界距离(margin)的数学表示:分类超平面表示为,一、线性可分的支持向量,(,分类,),机,首先考虑线性可分情况。设有如下两类样本的训练集：,线性可分情况意味着存在,超平面,使训练点中的正类和,负类样本分别位于该超平面的两侧。,如果能确定这样的参数对（,w,b,）,的话,就可以构造,决策函数,来进行,识别新样本。,一、线性可分的支持向量(分类)机首先考虑线性可分情况。设有如,9,线性可分的支持向量,(,分类,),机,问题是,：这样的参数对（,w,b,）有许多。,解决的方法是采用最大间隔原则。,最大间隔原则,：选择使得训练集,D,对于线性函数,(w,x)+b,的几何间隔取最大值的,参数对,(w,b),，并,由此构造决策函数。,在规范化下，超平面的几何间隔为,于是，找最大,几何间隔的超平面,表述成如下的最优化问题：,(1),线性可分的支持向量(分类)机问题是：这样的参数对（w,b）有,线性可分的支持向量,(,分类,),机,为求解问题,(1),使用,Lagrange,乘子法,将其转化为对偶问题。于是引入,Lagrange,函数,：,其中，称为,Lagrange,乘子。,首先求,Lagrange,函数关于,w,b,的极小值。由,极值条件有：,得到：,(2),(3),(4),线性可分的支持向量(分类)机 为求解问题(1),使用Lag,11,线性可分的支持向量,(,分类,),机,将,(3),式代入,Lagrange,函数，并利用,(4),式，则原始,的优化问题转化为如下的,对偶问题,(,使用极小形式,),：,这是一个凸二次规划问题,有唯一的最优解,(5),求解问题,(5),，得,。则参数对,(w,b),可由下式计算：,线性可分的支持向量(分类)机将(3)式代入Lagrange函,12,线性可分的支持向量,(,分类,),机,支持向量：,称训练集,D,中的样本,x,i,为支持向量，如,果它对应的,i,*0,。,根据原始最优化问题的,KKT,条件，有,于是，支持向量正好在间隔边界上,于是，得到如下的决策函数：,线性可分的支持向量(分类)机 支持向量：称训练集D中的样本x,几何意义：超平面法向量是支持向量的线性组合。,几何意义,a,6,=1.4,Class 1,Class 2,a,1,=0.8,a,2,=0,a,3,=0,a,4,=0,a,5,=0,a,7,=0,a,8,=0.6,a,9,=0,a,10,=0,几何意义：超平面法向量是支持向量的线性组合。几何意义a6=1,对于线性不可分的样本怎么办？,非线性可分情形,如何找到正确的分类曲线和正确的超平面对此类情况分类,?,对于线性不可分的样本怎么办？非线性可分情形 如何找到正确,非线性可分情形,关键点,:,把,x,i,变换到高维的特征空间,为什么要变换？,通过加入一个新的特征,x,i,，使得样本变成线性可分的，此时特征空间维数变高,Transform,x,(x),非线性可分情形关键点:把 xi 变换到高维的特征空间,例子,a,x,1,2,+,b,x,2,2,=1,w,1,z,1,+w,2,z,2,+w,3,z,3,+,b,=0,例子a x12+b x22=1,设训练集 ，其中,假定可以用 平面上的二次曲线来划分：,现考虑把,2,维空间 映射到,6,维空间的变换,上式可将,2,维空间上二次曲线映射为,6,维空间上的一个超平面：,非线性分类,设训练集,可见，只要利用变换，把,x,所在的,2,维空间的两类输入点映射,x,所在的,6,维空间，然后在这个,6,维空间中，使用,线性学习机求出分划超平面：,最后得出原空间中的二次曲线：,非线性分类,可见，只要利用变换，把 x 所在的2维空间的两类输入点映射x,如何选择到较高维空间的非线性映射？给定的检验元组，必须计算与每个支持向量的点积，出现形如 可以引入,核函数（,内积的回旋）来替代,如何选择到较高维空间的非线性映射？给定的检验元组，必须计算与,需要求解的最优化问题,非线性分类,最后得到决策函数,或,为此，引进函数,需要求解的最优化问题非线性分类最后得到决策函数或为此，引进函,实现非线性分类的思想,给定训练集后，决策函数仅依赖于,而不需要再考虑非线性变换,如果想用其它的非线性分划办法，则可以考虑选择其它形式,的函数 ，一旦选定了函数，就可以求解最优化问题,实现非线性分类的思想 给定训练集后，决策函数仅依赖于 如果想,实现非线性分类的思想,其中,解得 ，而决策函数,实现非线性分类的思想其中解得,目前研究最多的核函数主要有三类：,核函数的选择,多项式内核,得到,q,阶多项式分类器,包含一个隐层的多层感知器，隐层节点数是由算法自动确定,Sigmoid,内核,每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定,高斯径向基函数内核,RBF,目前研究最多的核函数主要有三类：核函数的选择多项式内核得到q,几个典型的核函数,几个典型的核函数,核的比较,核的比较,现有,5,个一维数据,x,1,=1,x,2,=2,x,3,=4,x,4,=5,x,5,=6,其中,1,2,6,为,class 1,，,4,5,为,class 2,y,1,=1,y,2,=1,y,3,=-1,y,4,=-1,y,5,=1,选择,polynomial kernel of degree 2,K(x,y)=(xy+1),2,C=100,求解,a,i,(,i,=1,5),1,2,4,5,6,例子,现有5个一维数据12456例子,例子,通过二次规划求解，得到,支持向量为,x2=2,x4=5,x5=6,判别函数为,b,满足,f,(2)=1,f,(5)=,-,1,f,(6)=1,得到,b=9,例子通过二次规划求解，得到,结果,判别函数,1,2,4,5,6,class 2,class 1,class 1,结果判别函数12456class 2class 1class,SVM,应用,分类、回归、密度估计,手写字符识别,文本自动分类,人脸识别,时间序列预测,蛋白质识别,DNA,排列分析,SVM 应用分类、回归、密度估计,