支持向量机分析.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,内容提要,1 引言,2,统计学习理论,3,线性支持向量机,4 非,线性支持向量机,5,支持向量回归,6 支持向量聚类,1,引言,一.SVM,(,Support Vector Machine),的历史,神经网络分类器,，,Bayes分类器等是基于,大样本,学习的分类器,。,Vapnik 等从,1960,年开始关于,统计学习理论,的研究,。,统计学习理论,是关于,小样本,的机器学习理论,。,1992,年,支持向量机,首次被引入,。1995,年Vapnik发展了,支持向量机,理论,。,支持向量机,是基于,统计学习理论,的一种实用的,机器学习,方法,。,二.SVM 的发展,SVM理论的发展:,最小二乘,支持向量机(,LS SVM),多分类支持向量机(M-SVM),支持向量回归(SVR),支持向量聚类(SVC),SVM与计算智能的融合:,神经网络+支持向量机,模糊逻辑+支持向量机,遗传算法+支持向量机,小波分析+支持向量机,主分量分析+支持向量机,粗糙集理论+支持向量机,三.SVM的应用,数据与文本分类,系统建模及预测,模式识别(图像及语音识别,，,生物特征识别),异常检测(入侵检测,，,故障诊断),时间序列预测,2,统计学习理论,一.两分类问题,给定,l,个观测值:,i=1,2,.,l,R,n,每个,观测值与一个标记相连:,i=1,2,.,l,土1,对于,(2-,类)分类,建立一个函数:,:,表示函数的参数,使得,f,能正确地分类未学习过的样本,第 2 类,第 1 类,二.,期望风险与实验风险,期望风险最小化,其中,x,y,的联合概率,P(x,y),是未知的,实验风险最小化,实验风险是由在训练集上测得的平均误差所确定的,如果训练样本的个数是有限的,则实验风险最小化的方法不保证有高推广能力,三.VC理论,VC(V,apnik-Chervonenkis)维数,分类函数,的集合F的VC维数,p=VCdim(F),定义,(VapnikChervonenkis).,函数 的集合F的,VC,维数是,p当且仅当存在点集,x,i,p,i,=1,使得这些点能够被所有,2,p,种可能的,分类方式分开,且不存在集合,x,i,q,i,=1,(,q p),满足这一性质,。,在,n 维空间中,超平面集合的VC维数等于n,+1,。,VC维数刻画了“可能近似正确”,意义上的学习能力,。,例:VC维数,四.结构风险最小化,VC,理论引入期望风险的边界,它依赖于实验风险与,F,的能力,。,这些边界的最小化导出,结构风险最小化原理:,实验风险与 VC 可信度之和为最小,其中,h,与VC 维数有关,是能力概念的一种测度,支持向量机是基于结构风险最小化原理,构造的一种学习机,3,线性支持向量机,一.两分类问题:线性分割情形,第 1 类,第 2 类,许多决策边界可以分割这些数据点出为两类,我们选取哪一个?,坏的决策边界的例子,第 1 类,第 2 类,第 1 类,第 2 类,好的决策边界:间隔大,决策边界离两类数据应尽可能远,最大化间隔 m,第 1 类,第 2 类,m,二.最优化问题,设 x,1,.,x,n,为数据集,y,i,1,-1 为,xi,的类标记,要求决策边界正确地分类所有的点,于是得到一个带有约束的优化问题,将上述最优化问题转换成其,对偶问题,:,取Lagrange函数,(w,b;)=1/2,w,2,n,i=1,i,(y,i,(w,x,i,)+b,1),则,对偶问题,由,max,W()=max,(min,w,b,(w,b;),给出,。,由,min,w,b,(w,b;),得,/b=0,n,i=1,i,y,i,=0,/,w,=0,w,=,n,i=1,i,y,i,x,i,于是得到,对偶问题,这是一个,二次规划(QP)问题,a,i,的全局最大值总可以求得,W的计算,解得,*=argmin,1/2,n,i=1,n,i=1,i,j,y,i,y,j,n,k,=1,k,w,*,=,n,i=1,i,y,i,x,i,b,*=1/2,其中,X,r,与,x,s,满足,x,r,x,s,0,y,r,=1,y,s,=1,则,f(x)=sgn(+b),三.解的性质,许多的,a,i,为零,w 只是少数数据的线性组合,具有非零,a,i,的 x,i,称为,支持向量(SV),决策边界仅由SV确定,设 t,j,(j=1,.,s)为支持向量的指标,于是,为了检测一个新数据 z,计算 如果 W,T,Z+b,0,则 z 属于第一类;否则,属于第二类,。,a,6,=1.4,四.几何解释,第1类,第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,4 非,线性支持向量机,一.非线性分割问题,关键思想:,为了解决非线性分割问题,将 x,i,变换到一个高维空间,。,输入空间:x,i,所在的空间,特征空间:变换后,f,(x,i,)的空间,如何变换?,利用一个适当的变换,f,使分类变得容易些,。,特征空间中的线性算子等价于输入空间中的非线性算子,。,变换可能出现的问题,难以得到一个好的分类且计算开销大,SVM同时解决这两个问题,最小化|,w,|,2,能得到好的分类,利用核函数技巧可以进行有效的计算,f,(),f,(),f,(),f,(),f,(),f,(),f,(),f,(),f,(,),f,(),f,(),f,(),f,(),f,(),f,(),f,(),f,(),f,(),f,(),特征空间,输入空间,变换举例,定义核函数 K(x,y)如下,考虑下列变换,内积可由 K 计算,不必通过映射,f,(,)计算,二.核函数技巧,核函数 K 与映射,f,(.)之间的关系是,作为核函数技巧这是已知的,在应用中,我们指定K,从而间接地确定,f,(,),，,以代替选取,f,(,),。,直观地,K(x,y)表示我们对数据 x 和 y 之间相似性的一种描述,，,且来自我们的先验知识,。,为了,f,(,)存在,，,K(x,y)需要满足 Mercer 条件,。,核函数举例,d 阶多项式核,具有宽度,s的径向基函数核,相当接近于径向基函数神经网络,具有参数,k,and,q,的,Sigmoid,核,对所有的,k,和,q,，,它不满足 Mercer 条件,三.非线性SVM算法,将所有的,内积改为核函数,训练算法:,线性的,非线性的,检测算法:,线性的,非线性的,对于一个新数据,z,，,如果,f,0,，,则分到第,1,类,；,如果,f0,，,则分到第,2,类,。,例题,设有 5个 1 维数据点:,x,1,=1,x,2,=2,x,3,=4,x,4,=5,x,5,=6,其中1,2,6 为第1类,而4,5 为第2类,y,1,=1,y,2,=1,y,3,=-1,y,4,=-1,y,5,=1,。,利用 2 阶多项式核,K(x,y)=(xy+1),2,C 取为 100,先求,a,i,(i=1,5):,利用 QP 求解,得到,a,1,=0,a,2,=2.5,a,3,=0,a,4,=7.333,a,5,=4.833,注意到确实满足约束条件,支持向量为 x,2,=2,x,4,=5,x,5,=6,描述函数为,确定b,当 x,2,x,4,x,5,位于 上时,f(2)=1,f(5)=-1,f(6)=1,由此解得,b=9,描述函数的值,1,2,4,5,6,第2类,第1类,第1类,5,支持向量回归,一.,最小二乘法,x,f(x),i,求,解,:,二.线性支持向量回归,(SVR),约束,:,+,-,0,求解,:,x,f(,x,),线性,支持向量回归,(SVR),最小化,:,x,f(,x,),+,-,0,*,约束,:,Lagrange 最优化,目标函数,约束条件,回归公式,回归,公式:,性质:,冗余性,全局的且唯一的,非线性推广,三.非线性,支持向量回归,f(x),x,+,-,0,f(x),(,x),+,-,0,输入空间,特征空间,回归公式,线性的:,非线性的:,一般的:,多项式型:,核函数的类型,线性型:,径向基函数型:,指数径向基函数型:,几点说明,SVM 基本上是一个两分类器,修改 QP 公式,以允许多类别分类,。,常用的方法:以不同的方式智能地将数据集分为两部分,对每一种分割方式用 SVM训练,多类别分类的结果,由所有的SVM分类器的输出经组合后得到(多数规则),。,“一对一”策略,这种方法对,N,类训练数据两两组合,构建,C,2,N,=N(N-1)/2,个支持向量机。最后分类的时候采取“投票”的方式决定分类结果。,“一对其余”策略,这种方法对,N,分类问题构建,N,个支持向量机,每个支持向量机负责区分本类数据和非本类数据。最后结果由输出离分界面距离,w,x+b,最大的那个支持向量机决定。,软件,关于 SVM 的实现可以在下列网址找到www.kernelmachines.org/software.html,SVM,Light,是最早的 SVM 软件之一,SVM 的各种 Matlab toolbox 也是可利用的,LIBSVM,可以进行多类别分类,CSVM,用于,SVM,分类,rSVM,用于,SVM,回归,mySVM,用于,SVM,分类与回归,M-SVM,用于,SVM多类别,分类,6 支持向量聚类,一.发展简介,Vapnik(1995):,支持向量机,Tax&Duin(1999):,利用,SV,表示高维分布的特征,Scholkopf et al.(2001):,利用,SV,计算封闭数据点的轮廓线的集合,Ben-Hur et al.(2001):,利用,SV,系统地搜索聚类解,二.方法的基本思想,利用高斯核函数将数据点映射到高维特征空间,在特征空间内寻找封闭数据点的像点的最小球面,将球面映射回数据空间,，,构成封闭数据点的轮廓线的集合,被每条轮廓线所封闭的点即属于与同一个聚类,减小高斯核函数的宽度，增加轮廓线的数目,用一个大的软间隙值处理重迭的聚类,映射到高维特征空间,三.主要步骤,球分析,聚类分析,设 为一具有,N个点的数据集,用一个非线性变换,映射到高维特征空间,寻求,由,限制的中心为,a,且半径为,R,的最小闭球,球分析,引入,Lagrangian,函数:,引入松弛变量,j,0,给出:,j,0 与,j,0 为,Lagrange,乘子,C 为常数,，,C,j,为惩罚项,利用KKT(Karush-Kuhn-Tucker)完备性条件给出:,球,由球心到像点的距离:,当 R=D(x,j,)时，则 x,j,为支持向量,在数据空间中封闭点的,轮廓线为集合,x|D(x)=R,支持向量,满足,i,=0 的点,x,i,的像点位于特征空间之外或在边界上,如果 0,i,R的点y的弧段。,所有点的邻接矩阵 A,ij,A,ij,=1,，,如果对于弧段上所有的y，D(y),R,A,ij,=0，如果对于弧段上至少1个y，D(y)R,聚类分析:邻接矩阵,计算主要部分的伪代码,Get Adjacent Matrix,(,A),初始化矩阵A,各元素清零,for,i,2 to,n,for,j,1 to,i,-1,if,j,R,则跳出循环,if,d,R,then,a(i,j),=,a(j,i),1,end,end,end,end,参数,聚类水平由两个参数控制:,1)q,Gaussian 核的宽度参数。q 增加,，不相连的轮廓线增加，聚类的个数增加。,2)C,软间隙常数。它允许特征空间中的球不封闭所有的点。,没有BSV的例,有BSV的例,.外点的个数由参数,C,控制,n,bsv,=1/C,其中 n,bsv,为 BSV的个数,，,C 为,软间隙常数,。,p=1/NC,1/NC 为,BSV一部分的上界,。,支持向量,图4说明没有,BSV轮廓线分开的数据与要求利用BSV的数据之间的不同。,如果不存在BSV,，两个概率分布之间的小的重迭所产生的数据足以防止轮廓线分开。,例,Iris,数据,数据集考虑,150 个实例，每个实例由iris 花的4个测量数据组成。,存在3种类型的花，每一种由50个实例描述。,变动,p,与,q,从,q 的初始值开始，在这一尺度所有的点对生成所得到的单一聚类中可估计的核值。在这个值没有外点是需要的，于是选取,C=1.,如果 q 是增加的,，则单个或一些点的聚类破坏或者聚类边界变的很粗糙。为了研究BSV什么时候允许出现，则让p增加。,较低个数的 SV 保证光滑的边界。,当 q增加时，SV的个数也增加。如果SV的个数太多，则让 p 增加，其中许多 SV可能转入BSV,，并且光滑的聚类或核边界就显现出来，如图3b。,沿着一个方向系统地增加 q 与 p,就能保证最小个数的SV。,关于,Iris,的结果,问题,计算复杂度,(O(n,2,m),),最优,q,值对于每个数据库是不同的，并且很难调好。,聚类分析中:,计算邻接矩阵,分配标记到,BSV,也存在某些问题。,谢谢大家!,