文档介绍：、引言?支持向量机(Support Vector Machine,简称SVM)是在统计学****理论的基础上发展起来的一种新的机器学****方法,它是建立在统计学****理论的VC维理论和结构风险最小化原则上的,避免了局部极小点(支持向量机算法是一个凸二次优化问题,能够保证找到的极值解就是全局最优解),并能有效地解决过学****问题,具有良好的推广性能和较好的分类精确性(由有限训练样本得到的决策规则对独立的测试集仍能够得到小的误差)。?支持向量机在解决小样本、非线性及高维模式识别问题中表现出的许多特有的优势,使它成为一种优秀的机器学****算法。目前,支持向量机已经成为国际上人工智能领域和机器学****领域新的研究热点。、基于二次规划的支持向量机分类?线性可分情况先考虑二维情况下的线性可分的两类样本(○,×),如图所示,存在很多条可能的分类线能够将训练样本分开。显然分类线a最好,因为它更远离每一类样本,风险小。而其他的分类线离样本较近,只要样本有较小的变化,将会导致错误的分类结果。因此分类线a是代表一个最优的线性分类器。所谓最优分类线就是要求分类线不但能将两类无误地分开,而且要使两类的分类间隔最大。图中H是最优分类线,H1和H2分别为过各类样本中离分类线最近的点且平行于分类线的直线,H1和H2之间的距离叫做两类的分类空隙或者分类间隔(margin)。将二维推广到高维,最优分类线就成为最优分类超平面。、基于二次规划的支持向量机分类?线性可分情况(续)设线性可分样本集为(xi,yi),i=1,2,…n,x∈Rd,y∈{+1,-1}是类别号。d维空间中线性判别函数的一般形式为g(x)=w?x+b,则分类超平面方程为:w?x+b=0其中,w为分类超平面的法线,是可调的权值向量;b为偏置,决定相对原点的位置。当两类样本是线性可分时,满足条件:(w?xi)+b≥+1yi=+1(w?xi)+b≤-1yi=-1超平面(w?xi)+b=+1距离原点的垂直距离为,而超平面(w?xi)+b=-1距离原点的垂直距离为,因此分类间隔就等于,所以使间隔最大等价于使 (或 )最小。若要求分类线对所有样本正确分类,则要求它满足:yi[(w?xi)+b]-1≥0,i=1,2,…,n因此满足该条件且使最小的分类超平面就是最优分类超平面。过两类样本中离分类超平面最近点且平行于最优分类面的超平面的训练样本就是使等号成立的哪些样本,它们叫做支持向量(Support Vectors)。wb?1wb??1wwbb211????、基于二次规划的支持向量机分类?线性可分情况(续)最优分类超平面问题可以表示成如下约束优化问题其约束条件为yi[(w?xi)+b]-1≥0,i=1,2,…,n定义Lagrange函数:其中,αi>0为Lagrange系数。分别对w和b求偏微分并令它们等于0,得带入原始Lagrange函数,得)(21min21min)(min,2,??????????????????niiiibxwywwbwL11)(21),,(?????????????niiiiniiiixywxywwbwL110),,(???00),,(11??????????niiiniiiyybbwL??????????njijijijiniixxyyQ1,1)(21)(????、基于二次规划的支持向量机分类?线性可分情况(续)因此,原问题转换为对偶问题:在约束条件:之下对αi求解下列函数的最大值:对偶问题完全是根据训练数据来表达的。所得到的解αi只有一部分(通常是少部分)不为零,对应的样本就是支持向量。若为最优解,则其中,xs为任一支持向量。最后得到的最优分类函数为:niyiniii,,2,1,001???????????????njijijijiniixxyyQ1,1)(21)(?????i?ssniiiixwybxyw??????????1,1???????????????????????niiiibxxybxwxf1)(sgnsgn)(?、基于二次规划的支持向量机分类?线性不可分情况对于线性不可分(非线性)问题:采用一个非线性变换φ(x)把输入数据映射到一个高维特征空间,然后在高维特征空间进行线性分类,最后再映射回到原空间就成为输入空间的非线性分类。考虑到可能存在一些样本不能被分离超平面分离,增加一个松弛变量,优化问题为:约束为其中,C为一常数,起控制对错分样本惩罚的程度的作用,实现在错分样本的比例与算法复杂度之间的折衷。C值越大,表示主要把重点放在减少分类错误上,C值越小,表示主要把重点放在分离超平面