1、9.3 支持向量机支持向量机支持向量机，一种线性和非线性数据有前途的新划分类方法。巧妙利用向量内积的回旋，通过将非线性核函数将问题变为高维特征空间与低维输入空间的相互转换，解决了数据挖掘中的维数灾难。由于计算问题最终转化为凸二次规划问题，因此挖掘算法是无解或有全局最优解。支持向量机定义n所谓支持向量机，顾名思义，分为两个部分了解：n一，什么是支持向量（简单来说，就是支持或支撑平面上把两类类别划分开来的超平面的向量点）n二，这里的“机（machine，机器）”便是一个算法。在机器学习领域，常把一些算法看做是一个机器，如分类机（当然，也叫做分类器），而支持向量机本身便是一种监督式学习的方法，它广泛
2、的应用于统计分类以及回归分析中。SVM的描述n目标：找到一个超平面，使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。n解决方法：构造一个在约束条件下的优化问题，具体的说是一个约束二次规划问题(constrained quadratic programing),求解该问题，得到分类器。最大边缘超平面最大边缘超平面(MMH)边缘：从超平面到其边缘的侧面的最短距离等于到边缘：从超平面到其边缘的侧面的最短距离等于到其边缘的另一个侧面的最短距离，边缘侧面平行于其边缘的另一个侧面的最短距离，边缘侧面平行于超平面超平面1122( ,),(,),(,)nnx yxyxy, 1
3、,1diixy 1211 iiiiyxyx 表表示示；表表示示分类面与边界距离分类面与边界距离(margin)的数学表示的数学表示:分类超平面表示为：分类超平面表示为：0 x wTb2wm Class 1Class 2m1x wTb 1x wTb一、线性可分的支持向量(分类)机),( ,),(),(2211nnyxyxyxD，niyRXximi, 1,1, 1,0)(bxw首先考虑线性可分情况。设有如下两类样本的训练集：首先考虑线性可分情况。设有如下两类样本的训练集： 线性可分情况意味着存在线性可分情况意味着存在超平面超平面使训练点中的正类和使训练点中的正类和负类样本分别位于该超平面的两侧。负
4、类样本分别位于该超平面的两侧。如果能确定这样的参数对（如果能确定这样的参数对（w,bw,b）的话的话, ,就可以构造就可以构造决策函数决策函数来进行来进行识别新样本。识别新样本。)sgn()(bxwxf线性可分的支持向量(分类)机nibxwytswiibw, 1, 1)(. .21min2,问题是问题是：这样的参数对（：这样的参数对（w,bw,b）有许多。）有许多。 解决的方法是采用最大间隔原则。解决的方法是采用最大间隔原则。最大间隔原则最大间隔原则：选择使得训练集：选择使得训练集D D对于线性函数对于线性函数(wx)+b的几何间隔取最大值的的几何间隔取最大值的参数对参数对(w,b)(w,b)
5、，并，并由此构造决策函数。由此构造决策函数。在规范化下，超平面的几何间隔为在规范化下，超平面的几何间隔为于是，找最大于是，找最大几何间隔的超平面几何间隔的超平面表述成如下的最优化问题：表述成如下的最优化问题：w1(1)(1)线性可分的支持向量(分类)机niiiibxwywbwL12) 1)(21),(nTnR),(210),(, 0),(bwLbwLwb 为求解问题为求解问题(1),(1),使用使用Lagrange乘子法乘子法将其转化为对将其转化为对偶问题。于是引入偶问题。于是引入Lagrange函数函数：其中，其中， 称为称为Lagrange乘子。乘子。首先求首先求Lagrange函数关于函
6、数关于w,bw,b的极小值。由的极小值。由极值条件有：极值条件有：niiiy10niiiixyw1得到：得到：(2)(2)(3)(3)(4)(4)线性可分的支持向量(分类)机niytsxxyyiniiininjjnjjijiji, 1, 0, 0. .)(21min1111niiiixyw1niiiixyw1*将将(3)(3)式代入式代入Lagrange函数，并利用函数，并利用(4)(4)式，则原始式，则原始的优化问题转化为如下的的优化问题转化为如下的对偶问题对偶问题( (使用极小形式使用极小形式) )：这是一个凸二这是一个凸二次规划问题次规划问题有唯一的最优有唯一的最优解解(5)(5)求解问
7、题求解问题(5)(5)，得，得 。则参数对。则参数对(w,b)(w,b)可由下式计算：可由下式计算：nyiniiiixwb1*1*2线性可分的支持向量(分类)机0) 1)(*bxwyiii 支持向量：支持向量：称训练集称训练集D中的样本中的样本xi为支持向量，如为支持向量，如 果它对应的果它对应的 i*0。 根据原始最优化问题的根据原始最优化问题的KKTKKT条件，有条件，有 于是，支持向量正好在间隔边界上于是，支持向量正好在间隔边界上 于是，得到如下的决策函数：于是，得到如下的决策函数：niiiibxxyxf1*)(sgn)(几何意义：超平面法向量是支持向量的线性组合。几何意义：超平面法向量
8、是支持向量的线性组合。 6=1.4Class 1Class 2 1=0.8 2=0 3=0 4=0 5=0 7=0 8=0.6 9=0 10=0n 对于线性不可分的样本怎么办？对于线性不可分的样本怎么办？n 如何找到正确的分类曲线和正确的超平面对此类情况分类如何找到正确的分类曲线和正确的超平面对此类情况分类?n关键点关键点: 把把 xi 变换到高维的特征空间变换到高维的特征空间n为什么要变换？为什么要变换？ 通过加入一个新的特征通过加入一个新的特征xi，使得样本变成线性可分的，使得样本变成线性可分的，此时特征空间维数变高此时特征空间维数变高nTransform x (x) na x12+b x
9、22=1 w1 z1+ w2z2 + w3 z3+ b =0设训练集设训练集 ，其中，其中假定可以用假定可以用 平面上的二次曲线来划分：平面上的二次曲线来划分： ( ,),1,iiTx yil 12( , ) ,1, 1Tiiiixxxy12( , )xx22212132412516 2 2 2 0wwxwxwxxwxwxb现考虑把现考虑把2维空间维空间 映射到映射到6维空间的变换维空间的变换12( )Txxx,22121212( )(1,2 ,2 ,2 , , )Txxxxxxx上式可将上式可将2维空间上二次曲线映射为维空间上二次曲线映射为6维空间上的一个超平面：维空间上的一个超平面：112
10、233445566 2 2 2 0wXwXwXwXwXwXb可见，只要利用变换，把可见，只要利用变换，把 x 所在的所在的2维空间的两类输入点映射维空间的两类输入点映射x 所在的所在的6维空间，然后在这个维空间，然后在这个6维空间中，使用维空间中，使用线性学习机求出线性学习机求出分划超平面：分划超平面：2*2*2121324125162 2 2 0wwxwxwxxwxwxb*16()0 ( , )Twxbwww ，其中最后得出原空间中的二次曲线：最后得出原空间中的二次曲线：n如何选择到较高维空间的非线性映射？给定的检验元组，必须计算与每个支持向量的点积，出现形如 可以引入核函数（内积的回旋）来
11、替代()()ijXX (,)()()ijijK XXXX111l1i1min ()()2. . 0 0,1,lllijijijjijjiiiy yxxs tyC il n需要求解的最优化问题需要求解的最优化问题n最后得到决策函数最后得到决策函数*1( )sgn( )( )sgn( ( )( )liiiif xwxbf xyxxb 或或为此，引进函数为此，引进函数2( ,)( ( )()() 1)ijijijK x xxxx xn 给定训练集后，决策函数仅依赖于给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换而不需要再考虑非线性变换2( ,)() 1)ijijK x xxx( )x111l
12、1i1min ,2. . 0 0,1,lllijijijjijjiiiy yK x xstyC il ( ,)ijK x xn 如果想用其它的非线性分划办法，则可以考虑选择其它形式如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数的函数 ，一旦选定了函数，就可以求解最优化问题，一旦选定了函数，就可以求解最优化问题*1( )sgn( ,)liiijif xyK x xb其中其中*1( ,) |0ljiiijjibyyK x xjjC ( ,) ijK x x 核函数*1(,)Tl解得解得 ，而决策函数，而决策函数目前研究最多的核函数主要有三类：目前研究最多的核函数主要有三类：n多项式内核
13、多项式内核( ,)()qiiK x xx xc得到得到q 阶多项式分类器阶多项式分类器( ,)tanh( ()iiK x xx xc包含一个隐层的多层感知器，隐层节点数是由算法自动确定包含一个隐层的多层感知器，隐层节点数是由算法自动确定nSigmoid内核内核22|( ,)expiixxK x x每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定n高斯径向基函数内核高斯径向基函数内核RBF几个典型的核函数n现有现有5个一维数据个一维数据 x1=1, x2=2, x3=4, x4=5, x5=6, 其中其中 1, 2, 6 为
14、为 class 1，4, 5 为为class 2 y1=1, y2=1, y3=-1, y4=-1, y5=1n选择选择 polynomial kernel of degree 2 K(x,y) = (xy+1)2 C = 100n求解求解 i (i=1, , 5)12456n通过二次规划求解，得到通过二次规划求解，得到 支持向量为支持向量为 x2=2, x4=5, x5=6n判别函数为判别函数为nb 满足满足 f (2)=1, f (5) = - -1, f (6)=1, 得到得到 b=9123450,2.5,0,7.333,4.833判别函数12456class 2class 1class 1n分类、回归、密度估计分类、回归、密度估计手写字符识别手写字符识别文本自动分类文本自动分类人脸识别人脸识别时间序列预测时间序列预测蛋白质识别蛋白质识别DNA 排列分析排列分析
