支持向量分类机原理

1、Support Vector Classification数据挖掘中的新方法支持向量分类机原理数据挖掘中的新方法支持向量分类机原理位礼奎2016年6月提纲提纲nSVM有关概念介绍nSVM分类问题的数学表示和推导简单的最优分类面广义最优分类面非线性最优分类面HistorynSVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon, Vapnik在COLT-92上首次提出，从此迅速发展起来，目前已经在许多智能信息获取与处理领域都取得了成功的应用。 n传统的统计模式识别方法只有在样本趋向无穷大时，其性能才有理论的保证。统计学习理论（STL）研究有限样本情况下的机器学习问题。SVM的理

2、论基础就是统计学习理论。n传统的统计模式识别方法在进行机器学习时，强调经验风险最小化。而单纯的经验风险最小化会产生“过学习问题”，其推广能力较差。n推广能力推广能力是指: 将学习机器(即预测函数,或称学习函数、学习模型)对未来输出进行正确预测的能力。n“过学习问题过学习问题”：某些情况下，当训练误差过小反而会导致推广能力的下降。n例如：对一组训练样本(x,y),x分布在实数范围内，y取值在0，1之间。无论这些样本是由什么模型产生的，我们总可以用y=sin(w*x)去拟合，使得训练误差为0.n根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方

3、法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，因此其推广能力较差。nVapnik 提出的支持向量机（Support Vector Machine, SVM）以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即SVM是一种基于结构风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。n由于SVM 的求解最后转化成二次规划问题的求解，因此SVM 的解是全局唯一的最优解nSVM在解决小样本、非线性及高维模式识别问题在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中

4、数拟合等其他机器学习问题中关于SVMn思想： 通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。 n途径： 构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题(constrained quadratic programing),求解该问题，构造分类超平面，从而得到决策函数。提纲提纲nSVM有关概念介绍nSVM分类问题的数学表示和推导n简单的最优分类面n广义最优分类面n非线性最优分类面分类问题的数学表示分类问题的数学表示已知：已知：训练

5、集包含 个样本点：说明：说明： 是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标； 是输出指标，或输出. 问题问题：对一个新的模式 ，推断它所对应的输出 是1还是-1.实质：实质：找到一个把 上的点分成两部分的规则.l11(,),(,)()lllTxyxyyxnixRx1, 1iyyxynR2维空间上的分类问题) n维空间上的分类问题.根据给定的训练集其中， ，寻找 上的一个实值函数 ，用决策函数判断任一模式 对应的 值. 可见，分类学习机构造决策函数的方法(算法)， 两类分类问题 多类分类问题 线性分类学习机 非线性分类学习机 ,1, 1,1,niixR yilyx n

6、Rx( )sgn( ( )f xg x11(,),(,)()lllTxyxyyx( )g xxy分类学习方法分类学习方法SVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。 最大间隔原则最大间隔原则考虑图1.2.1(a) 上的线性可分的分类问题.这里有许多直线 能将两类点正确分开.如何选取如何选取 和和 ？简单问题：简单问题：设法方向 已选定，如何选取 ？解答：解答： 选定 平行直线 极端直线 和 取 和 的中间线为分划直线如何选取如何选取 ？对应一个 ，有极端直线 ，称 和 之间的距离为“间隔”，显然应选使“间隔”最 大的。 2l3lw2R()0w xb bwwbw2l

7、3lw2233( ) ( )ll wll w2l3lw最大间隔法的直观导出最大间隔法的直观导出数学语言描述：数学语言描述：给定适当的法方向 后，这两条极端直线 可表示为12()()w xbkw xbk，w 调整 ，使得b), ()-w xbkw xbk （ ,wbwbkk令 ，则两式可以等价写为)1, ()-1w xbw xb（ 与此相应的分划直线表达式: )0w xb（23,l l如何计算分划间隔？如何计算分划间隔？考虑2维空间中极端直线之间的间隔情况2222121-1bbDwwwDw 221222Dwww求出两条极端直线的距离： ()0w xb 2|wbw2,1min| , (1.2.1)

8、2s.t.()1,1, (1.2.2)w biiwyw xbil 原始问题原始问题求解原始问题？求解原始问题？为求解原始问题，根据最优化理论，我们转化为对偶问题来求解11111min2. .0,0,1llli jijijjijjliiiiyyx xstyil 对偶问题对偶问题 为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解i*1. 线性可分问题线性可分问题计算 ，选择 的一个正分量 , 并据此计算*1(,)Tlaa*1liiiiwyx*a*j*1ljiijiibyyxx事实上， 的每一个分量 都与一个训练点相对应。而分划超平面仅仅依

9、赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。*i*i,iix y*i称 不为零的这些训练点的输入 为支持向量支持向量(SV)*iix构造分划超平面 ,决策函数*0wxb *sgn()f xwxb根据最优解2. 近似线性可分问题近似线性可分问题1lii1,Tl不要求所有训练点都满足约束条件 ，为此对第 个训练点 引入松弛变量松弛变量(Slack Variable) ,把约束条件放松到 。1iiyw xbi,iix y0i1iiiyw xb 体现了训练集被错分的情况，可采用 作为一种度量来描述错划程度。1lii两个目标两个目标：1. 间隔 尽可能大 2. 错划程度 尽可能小2w显然，

10、当 充分大时，样本点 总可以满足以上约束条件。然而事实上应避免 太大，所以需在目标函数对 进行惩罚（即“软化” 约束条件）i( ,)iix yi2. 近似线性可分问题近似线性可分问题0C 2, ,11min 2. ()1,1, 0,1,liw biiiiiwCstyw xbilil 因此，引入一个惩罚参数惩罚参数 ，新的目标函数变为: 体现了经验风险，而 则体现了表达能力。所以惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。当 时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。 1liiwCC 算法：算法： (广义广义)线性支持向量分类机线性支持向量分类机,1, 1,1,ni

11、ixR yilyx 11(,),(,)()lllTxyxyyx 设已知训练集 ，其中 2. 选择适当的惩罚参数 ，构造并求解最优化问题 0C 111l1i1min 2. . 0 0,1,lllijijijjijjiiiy yx xstyC il 3. 计算 ，选择 的一个分量 ，并据此 计算出 *1liiiiwyx*0jC*1ljiiijibyy ax x4. 构造分划超平面 ,决策函数*()0wxb*( )sgn()f xw xb求得*1(,)Tlaaa3. 非线性分划非线性分划例子:3. 非线性分划非线性分划设训练集 ，其中假定可以用 平面上的二次曲线来分划： ( ,),1,iiTx yi

12、l 12( , ) ,1, 1Tiiiixxxy12( , )xx22212132412516 2 2 2 0wwxwxwxxwxwxb现考虑把2维空间 映射到6维空间的变换12( )Txxx,22121212( )(1,2 ,2 ,2 , , )Txxxxxxx上式可将2维空间上二次曲线映射为6维空间上的一个超平面：(2.3.4)112233445566 2 2 2 0wXwXwXwXwXwXb3. 非线性分划非线性分划可见，只要利用变换(2.3.4)，把 所在的2维空间的两类输入点映射到 所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：2*2*2121324125162

13、 2 2 0wwxwxwxxwxwxbxX*16()0( , )Twxbwww，其中最后得出原空间中的二次曲线：怎样求6维空间中的分划超平面？(线性支持向量分类机)3. 非线性分划非线性分划111l1i1min ()()2. . 0 0,1,lllijijijjijjiiiy yxxstyC il 需要求解的最优化问题22121212( )(1, 2 , 2 , 2 , , )Tiiiiiiixxxxxxx22121212()(1,2 ,2 ,2 , , )Tjjjjjjjxxxxxxx其中1122121222221122( ( ) ()1 2 2 2 ijijijiijjijijxxxxxx

14、xxxxxxxx (2.3.6)(2.3.5)3. 非线性分划非线性分划在求得最优化问题的解 后，得到分划超平面*()0wxb其中*1(,)Tl*1( ), |0liiijiwyxjjC 最后得到决策函数*1( )sgn( )( )sgn( ( )( )liiiif xwxbf xyxxb 或*1( ( )()ljiiijibyyxx 线性分划非线性分划代价：2维空间内积6维空间内积3. 非线性分划非线性分划为此，引进函数有211222222112211221122( ,)( 1) 12 2 2 ijijijijijijijijijK x xxxxxxxxxxxxxxxxx 比较(2.3.6)

15、和(2.3.7)，可以发现2( ,)() 1)ijijK x xx x(2.3.7)2( ( )()( ,)()1)ijijijxxK x xxx这是一个重要的等式，提示6维空间中的内积可以通过计算 中2维空间中的内积 得到。( ( )()ijxx( ,)ijK x x()ijx x实现非线性分划的思想实现非线性分划的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数 ，一旦选定了函数，就可以求解最优化问题2( ,)() 1)ijijK x xx x( ,)ijK x x( )x111l1i1min ,2. . 0 0,1,lllijijijjijjiiiy yK x xstyC il *1(,)Tl得 ，而决策函数实现非线性分划的思想实现非线性分划的思想*1( )sgn( , )liiiif xyK x xb决策函数其中*1( ,) |0ljiiijjibyyK x xjjC ( , ) iK x x 核函数核函数核函数(核或正定核核或正定核)定义定义设 是 中的一个子集。称定义在 上的函数 是核函数(正定核或核)，如果存在着从 到某一个空间 的映射 :( )xx nR (