支持向量机分析

第五章支持向量机内容提要§1引言§2统计学习理论§3线性支持向量机§4非线性支持向量机§5支持向量回归§6支持向量聚类§1引言一.SVM(SupportVectorMachine)的历史神经网络分类器，Bayes分类器等是基于大样本学习的分类器。Vapnik等从1960年开始关于统计学习理论的研究。统计学习理论是关于小样本的机器学习理论。1992年支持向量机首次被引入。1995年Vapnik发展了支持向量机理论。支持向量机是基于统计学习理论的一种实用的机器学习方法。二.SVM的发展⒈SVM理论的发展:最小二乘支持向量机(LS–SVM)多分类支持向量机(M-SVM)支持向量回归(SVR)支持向量聚类(SVC)⒉SVM与计算智能的融合:神经网络+支持向量机模糊逻辑+支持向量机遗传算法+支持向量机小波分析+支持向量机主分量分析+支持向量机粗糙集理论+支持向量机三.SVM的应用数据与文本分类系统建模及预测模式识别(图像及语音识别，生物特征识别)异常检测(入侵检测，故障诊断)时间序列预测§2统计学习理论一.两分类问题给定l个观测值:,i=1,2,...,l∊Rn每个观测值与一个标记相连:,i=1,2,...,l∊{土1}对于(2-类)分类,建立一个函数::表示函数的参数使得f能正确地分类未学习过的样本iy1R:nfixixiy第2类第1类二.期望风险与实验风险期望风险最小化其中x,y的联合概率P(x,y)是未知的实验风险最小化实验风险是由在训练集上测得的平均误差所确定的如果训练样本的个数是有限的,则实验风险最小化的方法不保证有高推广能力liiiempxfylfR121yxdPxfyfR,21三.VC理论VC(Vapnik-Chervonenkis)维数分类函数的集合F的VC维数p=VCdim(F)定义(Vapnik–Chervonenkis).函数的集合F的VC维数是p,当且仅当存在点集{xi}pi=1使得这些点能够被所有2p种可能的分类方式分开,且不存在集合{xi}qi=1(qp)满足这一性质。在n维空间中,超平面集合的VC维数等于n+1。VC维数刻画了“可能近似正确”意义上的学习能力。ff例:VC维数四.结构风险最小化VC理论引入期望风险的边界,它依赖于实验风险与F的能力。这些边界的最小化导出结构风险最小化原理:实验风险与VC可信度之和为最小其中h与VC维数有关,是能力概念的一种测度支持向量机是基于结构风险最小化原理构造的一种学习机))4/(log)1)/2((log()()(lhlhfRfRemp§3线性支持向量机一.两分类问题:线性分割情形第1类第2类许多决策边界可以分割这些数据点出为两类我们选取哪一个?坏的决策边界的例子第1类第2类第1类第2类好的决策边界:间隔大决策边界离两类数据应尽可能远最大化间隔m第1类第2类m二.最优化问题设{x1,...,xn}为数据集,yi{1,-1}为xi的类标记要求决策边界正确地分类所有的点于是得到一个带有约束的优化问题将上述最优化问题转换成其对偶问题:取Lagrange函数Φ(w,b;α)=1/2‖w‖2–∑ni=1αi(yi[(w,xi)+b]–1)则对偶问题由maxαW(α)=maxα(minw,bΦ(w,b;α))给出。由minw,bΦ(w,b;α)得əΦ/əb=0⇒∑ni=1αiyi=0əΦ/əw=0⇒w=∑ni=1αiyixi于是得到对偶问题这是一个二次规划(QP)问题i的全局最大值总可以求得W的计算解得α*=argminα1/2∑ni=1∑ni=1αiαjyiyjxi,xj–∑nk=1αkw*=∑ni=1αiyixi,b*=–1/2w*,xr+xs其中Xr与xs满足xr,xs0,yr=–1,ys=1则f(x)=sgn(w*,x+b)三.解的性质许多的i为零w只是少数数据的线性组合具有非零i的xi称为支持向量(SV)决策边界仅由SV确定设tj(j=1,...,s)为支持向量的指标,于是为了检测一个新数据z计算如果WTZ+b0,则z属于第一类;否则,属于第二类。6=1.4四.几何解释第1类第2类1=0.82=03=04=05=07=08=0.69=010=0§4非线性支持向量机一.非线性分割问题关键思想:为了解决非线性分割问题,将xi变换到一个高维空间。输入空间:xi所在的空间特征空间:变换后f(xi)的空间如何变换?利用一个适当的变换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的径向基函数核相当接近于径向基函数神经网络具有参数kandq的Sigmoid核对所有的k和q，它不满足Mercer条件三.非线性SVM算法将所有的内积改为核函数训练算法:线性的非线性的检测算法:线性的非线性的对于一个新数据z，如果f0，则分到第1类；如果f0，则分到第2类。例题设有5个1维数据点:x1=1,x2=2,x3=4,x4=5,x5=6,其中1,2,6为第1类,而4,5为第2类y1=1,y2=1,y3=-1,y4=-1,y5=1。利用2阶多项式核K(x,y)=(xy+1)2C取为100先求i(i=1,…,5):利用QP求解,得到1=0,2=2.5,3=0,4=7.333,5=4.833注意到确实满足约束条件支持向量为{x2=2,x4=5,x5=6}描述函数为确定b当x2,x4,x5位于上时,f(2)=1,f(5)=-1,f(6)=1,由此解得b=9描述函数的值12456第2类第1类第1类§5支持向量回归一.最小二乘法YXwXXTT0dwdLossxf(x)bwxxf2YbwXLossi•求解:二.线性支持向量回归(SVR)•约束:iiTiTiybxwbxwy+-0wwMinT21•求解:xf(x)bwxxf线性支持向量回归(SVR)NiiiTCww1*21•最小化:xf(x)bwxxf+-0*•约束:0,**iiiiiTiiTiybxwbxwyLagrange最优化NiiiTCwwL1*21NiiTiiibxwy1NiiTiiibxwy1**Niiiii1**目标函数约束条件回归公式回归公式:性质:冗余性全局的且唯一的非线性推广bxxααxyNiiii1*,三.非线性支持向量回归f(x)x+-0f(x)(x)+-0输入空间特征空间回归公式线性的:bxxααxyNiiii1*,非线性的:bxxααxyNiiii1*,一般的:bxxKααxyNiiii1*,多项式型:核函数的类型线性型:径向基函数型:iixxxxK,),(diixxxxK,),(222exp),(siixxxxK指数径向基函数型:22exp),(siixxxxK几点说明SVM基本上是一个两分类器,修改QP公式,以允许多类别分类。常用的方法:以不同的方式智能地将数据集分为两部分,对每一种分割方式用SVM训练,多类别分类的结果,由所有的SVM分类器的输出经组合后得到(多数规则)。“一对一”策略这种方法对N类训练数据两两组合,构建C2N=N(N-1)/2个支持向量机。最后分类的时候采取“投票”的方式决定分类结果。“一对其余”策略这种方法对N分类问题构建N个支持向量机,每个支持向量机负责区分本类数据和非本类数据。最后结果由输出离分界面距离w·x+b最大的那个支持向量机决定。软件关于SVM的实现可以在下列网址找到SVMLight是最早的SVM软件之一SVM的各种Matlabtoolbox也是可利用的LIBSVM可以进行多类别分类CSVM用于SVM分类rSVM用于SVM回归mySVM用于SVM分类与回归M-SVM用于SVM多类别分类§6支持向量聚类一.发展简介Vapnik(1995):支持向量机Tax&Duin(1999):利用SV表示高维分布的特征Scholkopfetal.(2001):利用SV计算封闭数据点的轮廓线的集合Ben-Huretal.(2001):利用SV系统地搜索聚类解二.方法的基本思想利用高斯核函数将数据点映射到高维特征空间在特征空间内寻找封闭数据点的像点的最小球面将球面映射回数据空间，构成封闭数据点的轮廓线的集合被每条轮廓线所封闭的点即属于与同一个聚类减小高斯核函数的宽度，增加轮廓线的数目用一个大的软间隙值处理重迭的聚类映射到高维特征空间三.主要步骤⒈球分析⒉聚类分析•设为一具有N个点的数据集•用一个非线性变换Φ映射到高维特征空间•寻求由限制的中心为a且半径为R的最小闭球⒈球分析{}ixd22||()||jxaRj22||()||jjxaRj引入Lagrangian函数:引入松弛变量ξj＞0给出:βj＞0与µj＞0为Lagrange乘子,C为常数，C∑ξj为惩罚项利用KKT(Karush-Kuhn-Tucker)完备性条件给出:球由球心到像点的距离:当R=D(xj)时，则xj为支持向量在数据空间中封闭点的轮廓线为集合{x|D(x)=R}22()||()||jjDxxa支持向量满足ξi=0的点xi的像点位于特征空间之外或在边界上如果0βiC,它的像点位于特征空间球的曲面上这些都是支持向量有界支持向量满足ξi＞0及βi＞0的点xi的像点位于特征空间之外，这样的点有µi=0，因此βi=C这些是有界支持向量(BSVs)当C＞1时，不存在有界支持向量支持向量小结SVs位于聚类边界上BSVs位于聚类边界之外所有其它的点位于聚类边界之内数据空间⒉聚类分析聚类分配观察:给定不同聚类中的一对数据点，任一连接它们的轨线必定走出特征空间中的球，即这条轨线包含使得D(y)R的点y的弧段。所有点的邻接矩阵﹛Aij﹜Aij=1，如果对于弧段上所有的y，D(y)≤RAij=0，如果对于弧段上至少1个y，D(y)R聚类分析:邻接矩阵计算主要部分的伪代码GetAdjacentMatrix(A)初始化矩阵A,各元素清零fori←2tonforj←1toi-1ifjithenifa(i,j)=1theni、j两行合并为第i行elseifa(i,j)=0then计算xi和xj之间各样点x与球心距离d,一旦有样点满足dR,则跳出循环ifd≤Rthena(i,j)=a(j,i)←1endendendend参数聚类水平由两个参数控制:1)q—Gaussian核的宽度参数。q增加，不相连的轮廓线增加，聚类的个数增加。2)C—软间隙