支持向量机(数学建模)

第三十一章支持向量机支持向鼠机是数据挖掘中的一项新技术，是借助j:最优化方法來解决机器学习问题的新工具，最初由V.Vapmk等人提出，近儿年來在其理论研究和算法实现等方而都取得了很人的进展，开始成为克服“维数灾难”和过学习等困难的强有力的手段，它的理论基础和实现途径的基本框架都已形成。1支持向磧分类机的基本原理根据给定的训练集T=(x),(X2)，(x)e(XxY)1,其中xtE：X=Rn9X称为输入空间，输入空间中的每一个点兀由n个属性特征组成,开丘丫=-1,1=1,丿。寻找R1上的一个实值函数如,以便用分类函数f(x)=Sgll(g(x),推断任意一个模式工相対应的y值的问题为分类问题。1.1线性可分支持向量分类机考虑训练集T,若mgR”,bwR和正数,使得对所有使儿=1的卜标!有(a)xt)+b：(这里(a)X.)表示向鼠co和旺的内积)，而対所有使儿=-1的F标i有+贝IJ称训练集T线性可分，称相应的分类问题是线性可分的。记两类样本集分别为M+=x1.|iy.=lA1eT,M-=xJy.=-l,x1eTo定义M+的凸包conv(M+)为人az；亏conv(M+)=ij=iAj20,丿=1,M;XjwM_-761-其中必表示+1类样本集中样本点的个数，M表示-1类样本集中样本点的个数，定理1给出了训练集:T线性可分与两类样本集凸包之间的关系。定理1训练集:T线性可分的充耍条件是，：T的两类样本集M+和的凸包相离。如卜图所示训练集7线性可分时两类样木点集的凸包-#-#-证明：必耍性-#-#-若T是线性可分的，M+=x.|);=Lx.er,M=xiyi=xiT,由线性可分的定义可知，存在超平H=xeRn:（x）+b=0和0,使得+bS,VxfGM+且（69X.）+Z?=1(cox)+b=q工兀+J：是可以得到b=工(x.)+d)f工at=0i=ii=iN.M(a)x)+b=o工0产；+b=0j(ox；)+b)0,使得对M+,M-的凸包中的任意点才和弋分别有（69X）+b8（G）-XV）+b8,炖于任意的咅WM_,有（0Xj+bSY,由训练集线性可分的定义可知丁是线性可分的。由J：空间Rn中超平面都可以写为（co-x）+b=0的形式，参数（6）乘以任意一个非零常数后得到的是同一个超平面，定义满足条件.（69-）+/?）0,1=1,-,11）1111|（OX.）+|=1的超平面为规范超平面。定理2当训练集样本为线性可分时，存在唯一的规范超平面（a）x）+b=0,使得（69X,）+dl儿=1；11?（d9Xf）+d-l兀=一1证明：规范超平面的存在性是显然的，下证其唯一性。假设其规范超平面有两个：（血匕）+夕=0和（血玄）+方=0。由J：规范超平面满足条件d（9xj+b）no,1=1,millxj+b=1.5=11z=1,丿该问题的特点是目标函数*11创是的凸函数，并且约束条件都是线性的。引入Lagrange函数2/厶(血,a)=-|2+工ax(1一儿(。x.)+b)Li=i/1=1务儿=02=1=带入Lagrange函数化为原问题的Lagrange对偶问题1771一厅工工儿儿务勺(兀)+工a./f=i=1i=iS兀4=0!=1%0,z=lr-J求解上述最优化问题，得到最优解a=(a；,-a；)7，计算力=ah兀1=1iwaxas.t.(3)其中Q=(0,QjTgRl+为Lagrange乘子。根据wolfe对偶的定义，通过対原问题中各变量的偏导置零可得匹=0dcodb由KKT互补条件知g(i-儿(3)+/)=o可得，只有当兀为支持向量的时候，对应的才为正，否则皆为零。选择6/的一个正分量Q；,并以此计算八儿-工儿a：(兀),2=1J：是构造分类超平面(a)-x)+b*=0,并由此求得决策函数Ig(x)=e3(x,x)+b：2=1得到分类函数If(x)=Sgn(工心(石x)+b)(4)i=l从而对未知样本进行分类。1.2线性支持向量分类机当训练集丁的两类样本线性可分时，除了普通支持向最分布在两个分类边界(a)-xt)+b=l上外，其余的所有样本点都分布在分类边界以外。此时构造的超平而是硕间隔超平面。当训练集丁的两类样本近似线性可分时，即允许存在不满足约束条件兀(oxj+b)ni的样本点后，仍然能继续使用超平而进行划分。只是这时要对间隔进行“软化”，构造软间隔超平面。简言之就是在两个分类边界（6；-x.）+d=l之间允许出现样本点，这类样本点被称为边界支持向屋。显然两类样本点集的凸包是相交的，只是相交的部分较小。线性支持向量分类机如图3所示。软化的方法是通过引入松弛变量0,1=1,1来得到“软化”的约束条件片（妙兀）+6）1一空21,Z,当舟充分人时，样本点总是满足上述的约束条件，但是也要设法避免席取太大的值，为此要在目标函数中对它进行惩罚，得到如卜的二次规划问题ZX=1stxj+b）1-,（5）0,z=l,其中C0是一个惩罚参数。其Lagrange函数如F1ziiLgbK）=计妬+c空-工毎5（兀）+b）-1+空）-工久鼻L2=1X=12=1其中/,.0,孟0。原问题的对偶问题如下1/询X-厅工工儿儿4勺（兀）+工e8/1=1J=11=1Is.t.工儿0=0（6）t=i0:儿兀，1=1选择的一个正分量0vaJ=1冃1s.t.Vy.a=0J1I1=10j=lr若K是正定核，则刈偶问题是一个凸二次规划问题，必定有解。求解上述最优化问题，得到最优解刃=(；,0；)丁，选择力的一个正分量Q；,并以此计算I/=儿-工兀匕:&(兀巧)1=1构造分类函数If(x)=sgn(22儿a：K(xXj)+b!=1从而对未知样本进行分类。1.4C支持向量分类机当映射到高维H空间的训练集不能被硕性分划时，需要対约束条件进行软化。结合1.2和1.3中所述,得到如下的模型1?1牙工工儿儿4匕jK(兀可)+工久8L1=1J=11=1Is.t.工儿匕=0(7)!=10儿(兀)10儿8区)=1心C=xg(xJvl其中OvgvC,所对应的兀就是普通支持向量(NSV),位于分类间隔的边界g(x)=l,有|g(x.)|=l；a；=C所对应的兀就是边界支持向量(ESV丿，代表了所有的错分样本点，位J：分类间隔内部，有|g(x.)|0,线性超平面y=f(x)=(co-x)+b沿y方向依次上下平移w所扫过的区域构成碾-带超平面，并且超平而满足-+b-儿21,Z当足够人时，硬-带超平而总是存在的，而最小能使硬-带超平面存在的为&阴，是下列优化问题的最优值nun必(8)St一(69X.)+Z?-儿0,若=f(x)=(C6-x)+b是硬-带超平面，据其定义可知一c(co兀)+5兀0(10)0?一e)-Aco-be0,i=1,-由(10)的第一式可知i=itY-(a)ty)-b=(jj+sefii-69t-(Au)-b0.(11)类似的，ZT的凸包的任意一点都可以表示为s=(s：,sj=工叫(x：,儿)t2=1/其中卩=(叫，川JT，且满足工叫=1，叫no,，儿由(io)的第二式可知2=1片一(69sJ-b=&-比)1比一分-(Atw)-0(12)由(11)和(12)可知Q+和矿的凸包分别位J：该超平面的两侧。充分性：任取满足eJu=1,u0的凸组合系数向量u,则可以得到b中的一点(Atu)t，Cv+)Tw)T与此对应，选择满足eTv=1,Au=Atv的凸组合系数向量V,则可以得到矿中的一点(-4tv)t,(y-)Tv)T=(Tw)T,(y-v)t将该点与上述d+中的点比较，他们的前n个分量和同，同时超平而分离两个集合D+和D的凸包，则可知他们的第n+1个分鼠满足(y+se)Tu-(y-se)Tv0由此可见，关于变量的不等式组ATk=AveTu=eTv=1(y+se)Tu-(y一0,v0无解，不难证明=AveTu=eTv=10,v0无解，由择一定理知不等式组(y+se)-Aa)-be0(y一se)-Aco-be0有解，即超平面丿=f(X)=(C6X)+b是换-带超平面。定理4说明寻找训练集T的最优碾-带超平面等价J：集合Q+和矿的最优分类超平面。是可以得到如卜的最优化问题B1111(13)s.t.yt-(twxj+d),1=1,-,I其中69G,bwR。(13)的解存在的前提是$，而仏就为最优解。定理5给出了两者之间的联系。定理5若且是优化问题(8)的最优值，则(13)的解存在，并且对于e的解唯一,即若(瓦屁),(国,b；)都是解,则ct=ci.证明：若仏，则问题(13)的可行域非空，又因为该问题是凸的，所以一定有解，解的存在性即证。卜证解的唯一性。设(可&)，(阈上;)是问题(13)的两个最优解,显然-773-Lly其中r是一个常数，则有=亦，园=1。令69=3+,b=G+I,贝ij（co.b）22是问题（13）的可行解，从而有上式说明|倒=r,当2=-1时，a）=0,即厂=|倒=0,则有国=马=0；若2=19则有血；=国，故解的唯一性得证。引入Lagrange函数厶於上）=+加一工匕（Z2=1i兀一（oxx）b）-工力（一儿+（妙兀）+b）i=i其+a=（a1,a；,-,a/,a；）T0为Lagrange乘子，根据WoLfe对偶的定义，分别对dLdcotzjx.=0带入Lagrange函数,得到（13）的对偶问题如下Izz*11曙佻厅工S（&一）（；一）（%卩）+W工（&一e）-工儿（N-0）aeKZ1=1J=11=12=11S.t.工（&-匕）=0（14）X=1a丿=a,Q；,.,q,Q；）To对J：给定的训练样本集T，首先选择适当的精度0,构造并求解优化问题（14）,得到最优解护刁=（乞,石,，筠,乞丁，其中只有支持向蹟对应的0或斫非零，计算I1=1选择反的正分量暫0,计算b=yJ-（x.）+：或选择臣的正分量可0,计算b=儿_（页巧）_构造决策函数y=（6x）+F=（0以及合适的(15)核函数K（x,x）o构造并求解优化问题nun1I1/-工（a：-0）6；-）口兀）+$工（一at）一工儿（a：-务）Z!,/=11=1!=1s.t.工（a：-务）=0i=i*C,0。,2=1,丿得到最优解更b=（召,召坷,筠丁，选择臣的正分量再0,计算/F=儿_S（；_0）&（X“Xj）+i=i或选择K）的正分量0,计算/F=儿-工：-ajg込）y1=1构造决策函数y=工（a；-务）K（x“x）+b,即可对未知样本进行预测。1=1如卜定理给出了样本点与Lagrange乘子之间的关系。定理6若样本（兀，儿）在-带内部，则=0o若样本（x.,y.）在-带的边界上，则a；g0,a:=0；或a：=0,%w0,若样本（x.,y.）在一带的外部，则g=,务=0；或a=09务=oZZ可见，在-带内部的样本点都不是支持向鼠，它们对决策函数没有贡献，并且它们在样本集中的比例较人。3乳腺癌的诊断3.1问题的提出乳腺肿瘤通过穿刺采样进行分析可以确定其为良性的或为恶性的。医学研究发现乳腺肿瘤病灶组织的细胞核显微图像的10个最化特征：细胞核直径、质地.周长.而积、光滑度.紧密度、凹陷度、凹陷点数.对称度、断裂度与该肿瘤的性质有密切的关系。现试图根据已获得的实验数据建立起一种诊断乳腺肿瘤是良性述是恶性的方法。数据來自已确诊的500个病例，每个病例的一组数据包括采样组织中各细胞核的这10个特征晟的平均值、标准差和最坏值共30个数据，并将这种方法用J：另外69名己做穿刺采样分析的患者。这个问题实际上属丁模式识别问题。什么是模式呢？广义地说，在自然界中可以观察的事物，如果我们能够区别它们是否相同或是否相似，都可以称Z为模式。人们为了掌握客观事物，按事物相似的程度组成类别。模式识别的作用和目的就在J：而炖某一具体事物时将其正确地归入某一类别。模式识别的方法很多，如数理统计方法、聚类分析方法等。3.2支持向彊机的分类模型-#-支持向就机（SportVectorMachine,以卜简称SVM）是一种基于统计学习理论的模式识别方法。在模式识别等领域获得了广泛的应用。其主耍思想是这样：找到一个超平面，使得它能够尽可能多的将两类数据点正确地分开，同时使分开的两类数据点距离分类面最远，如图5（b）o图5最佳超平而示意图记n（这里n=500）个已知观测样本为（自）卫2牆）。其中张护，g,=1为良性肿瘤，/=-1为恶性肿瘤。（1）样本线性或非线性可分我们要找一个最优分类面w7+b=0,其中w,xgA30,bwR,w上待定，满足如下条件:心+bni,&=1时w+Z?1,i=1,2,;?求得最优值对应的可得分类函数：g（x）=sgn（w叮x+Z/）模型1是一个二次规划模型。卜面把模型1化为其对偶问题。定义广义拉格朗口函数厶(w)=-|w|2+工y1-&(w乜+byZ=1其中=（&“心）T,.0o由Karush-Kuhn-Tuck已r互补条件，通过对W和b求偏导可得QTn訂p針。得闪=工询i,工yg,=o,代入原始拉格朗日函数得1=12=1厶=-片丈f恥辭】(切tji=l上i=lJ=1其中(兀Xj)表示向量的内积于是模型1可以化为模型2n|nnmax工刁工工4匕&乞)1=1z1=1J=1S,.|g=00n/1=1st0(心+恥1-玄SV,0,z=1,2,/?求得最优值对应的w可得分类函数：g(x)=sgn(wTx+Z/)对应地，模型3改造得到模型5n|nnmax工匕一3工工aggg)KgtJi=l/i=lJ=1+Ie=St.I=10a.c,i=1,2,/注意到其只是在模型3的基础上约束0%提出待分类数据H=eye(3UH(31,31尸0,%v,b总共31个待定参数，b对应最后一个参数ga=gd,ones(n1,1),%良性律本点对应的系数矩阵ba=bd,ones(n2,l),%恶性样本点对应的系数矩阵a=.ga,ba,%线性不等号约束的系数矩阵b=-ones(500J),%线性不等号约束的右端项wbvral/lag=quadprog(kH,b)%调用二次规划命令xdf=xd,ones(694),g=xdf*、vb,w*x+b的值gl=find(g0)%良性样本序号g2=find(gv0),%恶性样本序号模型2的Matlab计算程序如卜：functionsvmlclc,clearglobalNLoadcancerdata.txt,caicancerdata,can(:,l尸山删除第一列病例号gdb=find(can(：4尸=1力读出良性肿瘤的序号nlHengthgdb),%计算良性肿瘤样本点的个数bdb=find(can(*1尸=1力读出恶性肿瘤的序号n2=length(bdb),%计算恶性肿瘤样本点的个数gd=can(gdb,2:end方提出良性肿瘤的数据-775-bd=can(bdb,2:end%提出恶性肿瘤的数据xd=can(50L5692:end);%提出待分类数据X=gd,bd,%重新排序后的训练样本N=size(X,l)gb=ones(nl,l)1O*eps)%计算v*x+b=O中的bsavedwbwbfunctiony=qfuiKaXgb人定义非线性规划的目标函数globalNV=-ones(1,N)*a+0.5*a*diag(gb)*X*X*diag(gb)*a,模型3的Ma血b计算程序如下：%原始数据中的B替换成1,M替换成-1,X替换成2,删除了分割符*clc,clearloadcancerdata.txt,caicancerdata,canc,l尸,%删除第一列病例号gdb=find(can(:,1)=1%读出良性肿瘤的序号nlHengthgdb),%计算良性肿瘤样本点的个数bdb=find(can(:,1尸=J方读出恶性肿瘤的序号n2=lengthbdb),%计算恶性肿瘤样本点的个数gd=can(gdb,2:end方提出良性肿瘤的数据bd=can(bdb,2:end%提出恶性肿瘤的数据xd=can(50L5692:end);%提出待分类数据hd=gd,bd,%重新排序后的训练样本N=size(hci4)basefun=x,y丿(x*y*+1).A2,%定义多项式核函数的匿名函数gb=ones(nl,l),-ones(n2,l),%g_i的取值向量H=gb*gb*basefun(hdJid丿,定义二次规划目标函数的一次项系数矩阵f=-ones(N4A%定义二次规划目标函数的一次项系数列向量aeq=gb；%定义二次规划的线性等号约束矩阵alphaXTal/lag=quadprog(H/,aeq,0zeros(N,loneN.l)模型2和模型3的Matlab程序计算时间很长，必须寻找一些更好的算法。习题三一1.嫌虫分类问题：生物学家试图对两种螳虫(Af与Apf)进行鉴别，依据的资料是触角和翅膀的长度，己经测得了9支Af和6支Apf的数据如I、Af：(1.24,1.27),(1.36,1.74),(1.38,1.64),(1.38,1.82),(1.38,1.90),(1.40,1.70),(1.48,1.82),(1.54,1.82),(1.56,2.08)Apf：(1.14,1.82),(1.18,1.96),(1.20,1.86),(1.26,2.00),(1.28,2.00),(1.30,1.96)现在的问题是：(1)根据如上资料，如何制定一种方法，正确地区分两类媒虫。(il)对触角和翼长分别为(1.24J.80),(1.28丄84)与(1.40204丿的3个标本，用所得到的方法加以识别。2.考虑卜面的优化问题mm护+0龙空+。2丈益1=11=1s.t.gx.(w-xj+d)1-.,i=12/0,z=1,2,/?讨论参数q和5变化产生的影响。导出对偶表示形式。-#-