ch7 支持向量机

理学院武汉理工大学2010.5第七章支持向量机PatternRecognition线性可分情形近似线性可分情形概述线性不可分情形第十三章支持向量机CortesandVapnik,1995.最大边界距离分类器概述概述1.线性可分情形线性可分情形下的最大边界距离分类超平面线性可分情形1122(,),(,),(,)nnxyxyxy,(1,1)diixy1211iiiiyxyx表示；表示分类面与边界距离(margin)的数学表示:分类超平面表示为：0xwTb2wmClass1Class2m1xwTb1xwTb数学语言描述()1,xwTiybi求分界面即为条件约束的极值问题212()1Tiybmaxwsubjecttoxw求解原始问题构造拉格朗日函数为法向量是样本的线性组合！求解原始问题将上式带入拉格朗日函数为求解原始问题为求解原始问题，根据最优化理论，我们转化为对偶问题来求解11111min2..0,0,1lllijijijjijjliiiiyyxxstyil为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解i*二次规划问题QP化为对偶问题由Kuhn-Tucker（KT）条件，分类面是最优超平面的充分必要条件是：化为对偶问题决策函数：用内积符号表示化为对偶问题几何意义：超平面法向量是支持向量的线性组合。几何意义6=1.4Class1Class21=0.82=03=04=05=07=08=0.69=010=0近似线性可分Class1Class2iXijjX线性不可分情形下，广义最大边界距离分类超平面：称为松弛变量，它允许在一定程度上违反间隔约束i如果，则没有错分样本。0i212()1,0iiTiiiCybmaxwsubjecttoxw于是，优化问题转化为C称为惩罚因子，起到对错分样本惩罚的程度的作用近似线性可分thelargerCthesmalleri近似线性可分求解仍然转化为对偶问题软间隔线性支持向量机i有上界近似线性可分对于线性不可分的样本怎么办？非线性可分情形如何找到正确的分类曲线和正确的超平面对此类情况分类?非线性可分情形关键点:把xi变换到高维的特征空间为什么要变换？–通过加入一个新的特征xi，使得样本变成线性可分的，此时特征空间维数变高Transformx(x)例子ax12+bx22=1[w]1z1+[w]2z2+[w]3z3+b=0设训练集，其中假定可以用平面上的二次曲线来划分：{(,),1,}iiTxyil12([],[]),{1,1}Tiiiixxxy12([],[])xx22212132412516[]2[][]2[][]2[][][][][][][]0wwxwxwxxwxwxb现考虑把2维空间映射到6维空间的变换12([][])Txxx,22121212()(1,2[],2[],2[][],[],[])Txxxxxxx上式可将2维空间上二次曲线映射为6维空间上的一个超平面：112233445566[][]2[][]2[][]2[][][][][][]0wXwXwXwXwXwXb非线性分类可见，只要利用变换，把x所在的2维空间的两类输入点映射x所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：2*****2*212132412516[]2[][]2[][]2[][][][][][][]0wwxwxwxxwxwxb*****16()0([],[])Twxb，其中最后得出原空间中的二次曲线：非线性分类111l1i1min()()2..00,1,lllijijijjijjiiiyyxxstyCil需要求解的最优化问题非线性分类最后得到决策函数***1()sgn((()))()sgn((()()))liiiifxwxbfxyxxb或为此，引进函数2(,)(()())(()1)ijijijKxxxxxx实现非线性分类的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换2(,)(()1)ijijKxxxx()x111l1i1min,2..00,1,lllijijijjijjiiiyyKxxstyCil(,)ijKxx如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数，一旦选定了函数，就可以求解最优化问题实现非线性分类的思想*1()sgn((,)))liiijifxyKxxb其中**1(,){|0}ljiiijjibyyKxxjjC(,)ijKxx－核函数***1(,)Tl解得，而决策函数目前研究最多的核函数主要有三类：核函数的选择多项式内核(,)[()]qiiKxxxxc得到q阶多项式分类器(,)tanh(())iiKxxxxc包含一个隐层的多层感知器，隐层节点数是由算法自动确定Sigmoid内核22||(,)exp{}iixxKxx每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定径向基函数内核RBF核的比较SVM寻优算法传统的利用二次型优化技术解决对偶问题时：需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过4000时，存储核函数矩阵就需要多达128兆内存；SVM在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。根据子问题的划分和迭代策略的不同，大致分为：1.块算法(ChunkingAlgorithm)2.SMO算法（SequentialMinimalOptimization）3.并行学习算法现有5个一维数据–x1=1,x2=2,x3=4,x4=5,x5=6,其中1,2,6为class1，4,5为class2y1=1,y2=1,y3=-1,y4=-1,y5=1选择polynomialkernelofdegree2–K(x,y)=(xy+1)2–C=100求解i(i=1,…,5)12456例子例子通过二次规划求解，得到–支持向量为{x2=2,x4=5,x5=6}判别函数为b满足f(2)=1,f(5)=-1,f(6)=1,得到b=9123450,2.5,0,7.333,4.833结果判别函数12456class2class1class1SVM实现SVMlightbsvmlibsvmmySVMMATLABsvmtoolboxLS-SVMlab1.5SVM应用分类、回归、密度估计•手写字符识别•文本自动分类•人脸识别•时间序列预测•蛋白质识别•DNA排列分析SVM实验LS-SVMlab1.5软件，是一个有GNU通用公共授权保证的可以分享与修改的自由软件。样本选择一个来自UCI数据库的小样本数据集iris，样本规模为100，是一个两类分类问题。核函数选用高斯核函数，需要选取最优的模型参数(正则参数和核参数)。SVM实验