支持向量机(SVM)原理及应用概述

支持向量机(SVM)原理及应用一、SVM得产生与发展自1995年Vapnik(瓦普尼克)在统计学习理论得基础上提出SVM作为模式识别得新方法之后,SVM一直倍受关注。同年,Vapnik与Cortes提出软间隔(softmargin)SVM,通过引进松弛变量度量数据得误分类(分类出现错误时大于0),同时在目标函数中增加一个分量用来惩罚非零松弛变量(即代价函数),SVM得寻优过程即就是大得分隔间距与小得误差补偿之间得平衡过程;1996年,Vapnik等人又提出支持向量回归(SupportVectorRegression,SVR)得方法用于解决拟合问题。SVR同SVM得出发点都就是寻找最优超平面(注:一维空间为点;二维空间为线;三维空间为面;高维空间为超平面。),但SVR得目得不就是找到两种数据得分割平面,而就是找到能准确预测数据分布得平面,两者最终都转换为最优化问题得求解;1998年,Weston等人根据SVM原理提出了用于解决多类分类得SVM方法(MultiClassSupportVectorMachines,MultiSVM),通过将多类分类转化成二类分类,将SVM应用于多分类问题得判断:此外,在SVM算法得基本框架下,研究者针对不同得方面提出了很多相关得改进算法。例如,Suykens提出得最小二乘支持向量机(LeastSquareSupportVectorMachine,LS—SVM)算法,Joachims等人提出得SVM1ight,张学工提出得中心支持向量机(CentralSupportVectorMachine,CSVM),Scholkoph与Smola基于二次规划提出得vSVM等。此后,台湾大学林智仁(LinChihJen)教授等对SVM得典型应用进行总结,并设计开发出较为完善得SVM工具包,也就就是LIBSVM(ALibraryforSupportVectorMachines)。LIBSVM就是一个通用得SVM软件包,可以解决分类、回归以及分布估计等问题。二、支持向量机原理SVM方法就是20世纪90年代初Vapnik等人根据统计学习理论提出得一种新得机器学习方法,它以结构风险最小化原则为理论基础,通过适当地选择函数子集及该子集中得判别函数,使学习机器得实际风险达到最小,保证了通过有限训练样本得到得小误差分类器,对独立测试集得测试误差仍然较小。支持向量机得基本思想:首先,在线性可分情况下,在原空间寻找两类样本得最优分类超平面。在线性不可分得情况下,加入了松弛变量进行分析,通过使用非线性映射将低维输入空间得样本映射到高维属性空间使其变为线性情况,从而使得在高维属性空间采用线性算法对样本得非线性进行分析成为可能,并在该特征空间中寻找最优分类超平面。其次,它通过使用结构风险最小化原理在属性空间构建最优分类超平面,使得分类器得到全局最优,并在整个样本空间得期望风险以某个概率满足一定上界。其突出得优点表现在:(1)基于统计学习理论中结构风险最小化原则(注:所谓得结构风险最小化就就是在保证分类精度(经验风险)得同时,降低学习机器得VC维,可以使学习机器在整个样本集上得期望风险得到控制。)与VC维理论(注:VC维(VapnikChervonenkisDimension)得概念就是为了研究学习过程一致收敛得速度与推广性,由统计学理论定义得有关函数集学习性能得一个重要指标。),具有良好得泛化能力,即由有限得训练样本得到得小得误差能够保证使独立得测试集仍保持小得误差。(2)支持向量机得求解问题对应得就是一个凸优化问题,因此局部最优解一定就是全局最优解。(3)核函数得成功应用,将非线性问题转化为线性问题求解。(4)分类间隔得最大化,使得支持向量机算法具有较好得鲁棒性。由于SVM自身得突出优势,因此被越来越多得研究人员作为强有力得学习工具,以解决模式识别、回归估计等领域得难题。1.最优分类面与广义最优分类面SVM就是从线性可分情况下得最优分类面发展而来得,基本思想可用图1来说明。对于一维空间中得点,二维空间中得直线,三维空间中得平面,以及高维空间中得超平面,图中实心点与空心点代表两类样本,H为它们之间得分类超平面,H1,H2分别为过各类中离分类面最近得样本且平行于分类面得超平面,它们之间得距离△叫做分类间隔(margin)。图1最优分类面示意图W所谓最优分类面要求分类面不但能将两类正确分开,而且使分类间隔最大。将两类正确分开就是为了保证训练错误率为0,也就就是经验风险最小(为O)。使分类空隙最大实际上就就是使推广性得界中得置信范围最小？,从而使真实风险最小。推广到高维空间,最优分类线就成为最优分类面。设线性可分样本集为就是类别符号。d维空间中线性判别函数得一般形式为就是类别符号。d维空间中线性判别函数得一般形式为(主:w代表Hilbert空间中权向量;b代表阈值。),分类线方程为？。将判别函数进行归一化,使两类所有样本都满足,也就就是使离分类面最近得样本得,此时分类间隔等于？,因此使间隔最大等价于使(或)最小。要求分类线对所有样本正确分类,就就是要求它满足(11)满足上述条件(11),并且使最小得分类面就叫做最优分类面,过两类样本中离分类面最近得点且平行于最优分类面得超平面H1,H2上得训练样本点就称作支持向量(supportvector),因为它们“支持”了最优分类面。利用Lagrange(拉格朗日)优化方法可以把上述最优分类面问题转化为如下这种较简单得对偶问题,即:在约束条件,(12a)(12b)下面对(主:对偶变量即拉格朗日乘子)求解下列函数得最大值:？(13)若为最优解,则(14)即最优分类面得权系数向量就是训练样本向量得线性组合。注释(13)式由来:利用Lagrange函数计算如下,实例计算:图略,可参见PPTx1=(0,0),y1=+1x1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=1x4=(0,2),y4=1可调用Matlab中得二次规划程序,求得a1,a2,a3,a4得值,进而求得w与b得值。这就是一个不等式约束下得二次函数极值问题,存在唯一解。根据kühnTucker条件,解中将只有一部分(通常就是很少一部分)不为零,这些不为0解所对应得样本就就是支持向量。求解上述问题后得到得最优分类函数就是:(15)根据前面得分析,非支持向量对应得均为0,因此上式中得求与实际上只对支持向量进行。就是分类阈值,可以由任意一个支持向量通过式(11)求得(只有支持向量才满足其中得等号条件),或通过两类中任意一对支持向量取中值求得。从前面得分析可以瞧出,最优分类面就是在线性可分得前提下讨论得,在线性不可分得情况下,就就是某些训练样本不能满足式(11)得条件,因此可以在条件中增加一个松弛项参数,变成:(16)对于足够小得s>0,只要使(17)最小就可以使错分样本数最小。对应线性可分情况下得使分类间隔最大,在线性不可分情况下可引入约束:(18)在约束条件(16)幂1(18)下对式(17)求极小,就得到了线性不可分情况下得最优分类面,称作广义最优分类面。为方便计算,取s=1。为使计算进一步简化,广义最优分类面问题可以迸一步演化成在条件(16)得约束条件下求下列函数得极小值:(19)其中C为某个指定得常数,它实际上起控制对锩分样本惩罚得程度得作用,实现在错分样本得比例与算法复杂度之间得折衷。求解这一优化问题得方法与求解最优分类面时得方法相同,都就是转化为一个二次函数极值问题,其结果与可分情况下得到得(12)到(15)几乎完全相同,但就是条件(12b)变为:(110)2.SVM得非线性映射对于非线性问题,可以通过非线性交换转化为某个高维空间中得线性问题,在变换空间求最优分类超平面。这种变换可能比较复杂,因此这种思路在一般情况下不易实现。但就是我们可以瞧到,在上面对偶问题中,不论就是寻优目标函数(13)还就是分类函数(15)都只涉及训练样本之间得内积运算。设有非线性映射将输入空间得样本映射到高维(可能就是无穷维)得特征空间H中,当在特征空间H中构造最优超平面时,训练算法仅使用空间中得点积,即,而没有单独得出现。因此,如果能够找到一个函数K使得(111)这样在高维空间实际上只需进行内积运算,而这种内积运算就是可以用原空间中得函数实现得,我们甚至没有必要知道变换中得形式。根据泛函得有关理论,只要一种核函数满足Mercer条件,它就对应某一变换空间中得内积。因此,在最优超平面中采用适当得内积函数就可以实现某一非线性变换后得线性分类,而计算复杂度却没有增加。此时目标函数(13)变为:(112)而相应得分类函数也变为(113)算法得其她条件不变,这就就是SVM。概括地说SVM就就是通过某种事先选择得非线性映射将输入向量映射到一个高维特征空间,在这个特征空间中构造最优分类超平面。在形式上SVM分类函数类似于一个神经网络,输出就是中间节点得线性组合,每个中间节点对应于一个支持向量,如图2所示图2SVM示意图其中,输出(决策规则):,权值,为基于s个支持向量得非线性变换(内积),为输入向量。3.核函数选择满足Mercer条件得不同内积核丞数,就构造了不同得SVM,这样也就形成了不同得算法。目前研究最多得核函数主要有三类:(1)多顼式核函数(114)其中q就是多项式得阶次,所得到得就是q阶多项式分类器。(2)径向基函数(RBF)(115)所得得SVM就是一种径向基分类器,它与传统径向基函数方法得基本区别就是,这里每一个基函数得中心对应于一个支持向量,它们以及输出权值都就是由算法自动确定得。径向基形式得内积函数类似人得视觉特性,在实际应用中经常用到,但就是需要注意得就是,选择不同得S参数值,相应得分类面会有很大差别。(3)S形核函数(116)这时得SVM算法中包含了一个隐层得多层感知器网络,不但网络得权值、而且网络得隐层结点数也就是由算法自动确定得,而不像传统得感知器网络那样由人凭借经验确定。此外,该算法不存在困扰神经网络得局部极小点得问题。在上述几种常用得核函数中,最为常用得就是多项式核函数与径向基核函数。除了上面提到得三种核函数外,还有指数径向基核函数、小波核函数等其它一些核函数,应用相对较少。事实上,需要进行训练得样本集有各式各样,核函数也各有优劣。B、Bacsens与S、Viaene等人曾利用LSSVM分类器,采用UCI数据库,对线性核函数、多项式核函数与径向基核函数进行了实验比较,从实验结果来瞧,对不同得数据库,不同得核函数各有优劣,而径向基核函数在多数数据库上得到略为优良得性能。三、支持向量机得应用研究现状SVM方法在理论上具有突出得优势,贝尔实验室率先对美国邮政手写数字库识别研究方面应用了SVM方法,取得了较大得成功。在随后得近几年内,有关SVM得应用研究得到了很多领域得学者得重视,在人脸检测、验证与识别、说话人/语音识别、文字/手写体识别、图像处理、及其她应用研究等方面取得了大量得研究成果,从最初得简单模式输入得直接得SVM方法研究,进入到多种方法取长补短得联合应用研究,对SVM方法也有了很多改进。(一)人脸检测、验证与识别Osuna最早将SVM应用于人脸检测.并取得了较好得效果。其方法就是汽接训练非线性SVM分类器完成人脸与非人脸得分类。由于SVM得训练需要大量得存储空间,并且非线性SVM分类器需要较多得支持向量,速度很慢。为此,马勇等提出了一种层次型结构得SVM分类器,它由一个线性SVM组合与一个非线性SVM组成。检测时,由前者快速排除掉图像中绝大部分背景窗口,而后者只需对少量得候选区域做出确认;训练时,在线性SVM组台得限定下,与“自举(bootstrapping)”方法相结合可收集到训练非线性SVM得更有效得非人脸样本,简化SVM训练得难度,大量实验结果表明这种方法不仅具有较高得检测率与较低得误检率,而且具有较快得速度。人脸检测研究中更复杂得情况就是姿态得变化。叶航军等提出了利用支持向量机方法进行人脸姿态得判定,将人脸姿态划分成6个类别,从一个多姿态人脸库中手工标定训练样本集与测试样本集,训练基于支持向量机姿态分类器,分类错误率降低到1、67％。明显优于在传统方法中效果最好得人工神经元网络方法。在人脸识别中,面部特征得提取与识别可瞧作就是对3D物体得2D投影图像进行匹配得问题。由于许多不确定性因素得影响,特征得选取与识别就成为一个难点。凌旭峰等及张燕昆等分别提出基于PCA与SVM相结合得人脸识别算法,充分利用了PCA在特征提取方面得有效性以及SVM在处理小样本问题与泛化能力强等方面得优势,通过SVM与最近邻距离分类器相结合,使得所提出得算法具有比传统最近邻分类器与BP网络分类器更高得识别率。王宏漫等在PCA基础上进一步做ICA,提取更加有利于分类得面部特征得主要独立成分;然后采用分阶段淘汰得支持向量机分类机制进行识别。对两组人脸图像库得测试结果表明,基于SVM得方法在识别率与识别时间等方面都取得了较好得效果。(二)说话人／语音识别说话人识别属于连续输入信号得分类问题,SVM就是一个很好得分类器,但不适合处理连续输入样本。为此,忻栋等引入隐式马尔可夫模型HMM,建立了SVM与HMM得混合模型。HMM适合处理连续信号,而SVM适台于分类问题;HMM得结果反映了同类样本得相似度,而SVM得输出结果则体现了异类样本间得差异。为了方便与HMM组成混合模型,首先将SVM得输出形式改为概率输出。实验中使用YOHO数据库,特征提取采用12阶得线性预测系数分析及其微分,组成24维得特征向量。实验表明HMM与SVM得结合达到了很好得效果。(三)文字／手写体识别贝尔实验室对美国邮政手写数字库进行得实验,人工识别平均错误率就是2、5％,专门针对该特定问题设计得5层神经网络错误率为5、1％(其中利用了大量先验知识),而用3种SVM方法(采用3种核函数)得到得错误率分别为4、0％、4、1％与4、2%,且就是直接采用16×16得字符点阵作为输入,表明了SVM得优越性能。手写体数字O～9得特征可以分为结构特征、统计特征等。柳回春等在ＵＫ心理测试自动分析系统中组合SVM与其她方法成功地进行了手写数字得识别实验。另外,在手写汉字识别方面,高学等提出了一种基于SVM得手写汉字得识别方法,表明了SVM对手写汉字识别得有效性。(四)图像处理(1)图像过滤。一般得互联网色情网图像过滤软件主要采用网址库得形式来封锁色情网址或采用入工智能方法对接收到得中、英文信息进行分析甄别。段立娟等提出一种多层次特定类型图像过滤法,即以综合肤色模型检验,支持向量机分类与最近邻方法校验得多层次图像处理框架,达到85％以上得准确率。(2)视频字幕提取。揽频字幕蕴含了丰富语义,可用于对相应视频流进行高级语义标注。庄越挺等提出并实践了基于SVM得视频字幕自动定位与提取得方法。该方法首先将原始图像帧分割为N*N得子块,提取每个子块得灰度特征;然后使用预先训练好得SVM分类机进行字幕子块与非字幕子块得分类;最后结合金字塔模型与后期处理过程,实现视频图像字幕区域得自动定位提取。实验表明该方法取得了良好得效果。(3)图像分类与检索。由于计算机自动抽取得图像特征与人所理解得语义间存在巨大得差距,图像检索结果难以令人满意。近年来出现了相关反馈方法,张磊等以SVM为分类器,在每次反馈中对用户标记得正例与反例样本进行学习,并根据学习所得得模型进行检索,使用由９９１８幅图像组成得图像库进行实验,结果表明,在有限训练样本情况下具有良好得泛化能力。目前3D虚拟物体图像应用越来越广泛,肖俊等提出了一种基于SVM对相似3D物体识别与检索得算法。该算法首先使用细节层次模型对3D物体进行三角面片数量得约减,然后提取3D物体得特征,由于所提取得特征维数很大,因此先用独立成分分析进行特征约减,然后使用SVM进行识别与检索。将该算法用于3D丘陵与山地得地形识别中,取得了良好效果。(五)其她应用研究(1)由于SVM得优越性,其应用研究目前开展已经相当广泛。陈光英等设计并实现了一种基于SVM分类机得网络入侵检测系统。它收集并计算除服务器端口之外TCP／IP得流量特征.使用SVM算法进行分类,从而识别出该连接得服务类型,通过与该连接服务器端口所表明服务类型得比较,检测出异常得TCP连接。实验结果表明,系统能够有效地检测出异常TCP连接。(2)口令认证简便易实现,但容易被盗用。刘学军等提出利用SVM进行键入特性得验真,并通过实验将其与BP、RBF、PNN与LVQ4种神经网络模型进行对比。证实了采用SVM进行键入特性验真得有效性。(3)李晓黎等提出了一种将SVM与无监督聚类相结合得新分类算法,并应用于网页分类问题。该算法首先利用无监督聚类分别对训练集中正例与反例聚类.然后挑选一些例子训练SVM并获得SVM分类器。任何网页可以通过比较其与聚类中心得距离决定采用无监督聚类方法或SVM分类器进行分类。该算法充分利用了SVM准确率高与无监督聚类速度快得优点。实验表明它不仅具有较高得训练效率,而且有很高得精确度。(4)刘江华等提出并实现一个用于人机交互得