支持向量机分类器

支持向量机分类器1支持向量机的提出与发展支持向量机（SVM,supportvectormachine）是数据挖掘中的一项新技术，是借助于最优化方法来解决机器学习问题的新工具，最初由 V.Vapnik等人在1995年首先提出，近几年来在其理论研究和算法实现等方面都取得了很大的进展， 开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。根据Vapnik&Chervonenkis的统计学习理论，如果数据服从某个（固定但未知的）分布,要使机器的实际输出与理想输出之间的偏差尽可能小 ，则机器应当遵循结构风险最小化（SRM,structuralriskminimization） 原则，而不是经验风险最小化原则，通俗地说就是应当使错误概率的上界最小化。 SVME是这一理论的具体实现。与传统的人工神经网络相比 ，它不仅结构简单，而且泛化（generalization） 能力明显提高。2问题描述2.1问题引入假设有分布在Rd空间中的数据，我们希望能够在该空间上找出一个超平面 （Hyper-pan）,将这一数据分成两类。属于这一类的数据均在超平面的同侧， 而属于另一类的数据均在超平面的另一侧。如下图。比较上图，我们可以发现左图所找出的超平面（虚线） ，其两平行且与两类数据相切的超平面（实线）之间的距离较近，而右图则具有较大的间隔。 而由于我们希望可以找出将两类数据分得较开的超平面，因此右图所找出的是比较好的超平面。可以将问题简述如下：设训练的样本输入为xi,i=1,•••,l，对应的期望输出为yi€{+1,-1},其中+1和-1分别代表两类的类别标识，假定分类面方程为 3-x+b=0。为使分类面对所有样本正确分类并且具备分类间隔，就要求它满足以下约束条件:for+1for-1而是要得到一个最优的分类面。它追求的不仅仅是得到一个能将两类样本分开的分类面,而是要得到一个最优的分类面。2.2问题的数学抽象将上述问题抽象为:根据给定的训练集T={（X］侃）,（3）…,（旳加）}£（XxY）1,

其中hW二_R,X称为输入空间，输入空间中的每一个点 Xi由n个属性特征组成，VjVjeY={-LI}」=l…jo寻找Rn上的一个实值函数g(x)，以便用分类函数f(x)=sgn(g(x)),推断任意一个模式x相对应的y值的问题为分类问题。判别函数g(x)是特征空间中某点x到超平面的距离的一种代数度量。如果g(x)>0，则判定x属于C1,如果g(x)<0，则判定x属于C2，如果g(x)=0，则可以将x任意分到某一类或者拒绝判定。3支持向量机分类算法3.1线性可分支持向量分类机3.1.1基础理论与定理I—考虑训练集了「若beR和止数厂使得対所有使x=1的卜标f有佃巧)+A>e(这里(炉迅)我示向虽少和叫的内积).而対所仃f史h--1的卜标M(妙町)+张则称训练集7■线性叮分.称相应的分类何题宦线性町分的「记两类样本集分别为人厂=讥|”=1,兀总乃，』厂=｛斗|片=一人迅£了八定义W的凸包conv(AZ*)为TOC\o"1-5"\h\zf皿 A+ ]conv(A/^)=^x= x,a-;|=1,Aj>0,j= ©芒A厂*[j-i JA/~的凸包conv(j\/_)为(.V_ ,V. rconv(A/_)-|x-》心V』|A.」LA,>0.y-LTN~:©e』厂”.\o"CurrentDocument"[M /=i" J冀中M表示+1类样本集中样本点的个败■忙衣示一1类样本集中样本点的个数*定站给出了训练集丁线性町分〒两类样木集凸包之间的关甌定理1训练集T线性叮分的允要条件足.厂的两类样本佻』厂和4厂的凸包相如F图所示阳1训乳集7■址性可分时两类样本云集的凸包证明：①必要件若厂是线性町分的,Ar={xf\yi=i.xleT}.A/-=mv^-L^er},由线

性可分的定义可知,存在超平面H={xcRn:（coxUb=0}和£>0,使得（co^xf）+b>£9Va-zeA厂且（co^x^+b<—e,Vx;eW.而正类点集的凸包中的任意点X和负类点集的凸包中的任总•点x'町分别及示为兀匹乞兀/-I jTTOC\o"1-5"\h\zNt N.其中a,>0,/?;>0且£的=1,三0丿=1。21 /si丁是可以得到< \ N. "♦（e・x）+b二e•工a占+b二工匕（（0・耳）+3»£乞％二£>0、 i—i ） /—1 /—1，N.，N.（Q・f）+b=。•工0八：+"=工0（（。•巧）+"）*-£工0丿=-£<0/=! 7=1由此可见，止负两类点集的凸包位于趙平面（e・x）+—0的两侧，故两个凸包相离・②充分性设两类点集Ar,3厂的凸包相离。冈为两个凸包那是闭凸集.R.有界，根据凸集强分离定理，可知存在个超平向H二{xw/T:（eT）+b=0}強分离这两个凸包，即存在正数占>0,使得对MSAT的凸包中的任意点X和才分别有（6?-.r）+5>（cox'）^b<-€显然特别的，对于任总的a;eA/+,^（（ox^+b>s,対于任总的齐G厂，有9巧）+比-£,由训练集线性叮分的定义町知Z•是线性町分的。由于空间用中超'匕血都町以写为9・对+5=0的形式,参数（ob）乘以任童一个非零常数厉得到的足同一个超平而，定义满足条件兀（（e•兀）+b）20,i=L…」min|（gj«x,）+ZJ=Ij—L-••J的超平面为规范超平面。定理2当训练集样本为线性叮分时，存任唯-・的规范超平面（Q・x）+b=0.便（fox,）+6>ly,=1; ⑴（ry-xz）+6<-1yf=-l.讦明：规范超平面的存衣件是显然的.HiiFH唯一件。假设其规范超平面有两个：（e“）+F=0和胪=0。由丁规范超平血满

足条件內K也(仙・兀)+6)NO*i-L…上由第二个条內K也(仙・兀)+6)NO*i-L…上由第二个条件町知C91—<y"-br—bn,或者妙二-少，F二一/第一个条fT说明少二―V=-b"不可能成匕故I唯叽得iiF。3.1.2最优超平面的求解式【I）中满址0•叶）+办二七1成走的兀称为普通支持向呈'时「线杵町分的情况来说.只有它们在建立分类超平血的时候起到了作用，普通支持向呈通常只占申扣LI!小的一祁分，故而也说明5VM艮仃稀疏性”肘于旳-1类的样冰点・Jt与规范超平面的何隔为则普通支持向量间的间隔为亠.兹优超平面即总味首最人化二.如图2所示I训 训nr对fi类时样本点,其与规范超平面的间隔为3■码）+可1】山） o_