理学支持向量机算法课件.pptx

1、 支持向量机是数据挖掘中的一项新技术，是借助于最优化方法解决机器学习的问题的新工具，它由Vapnik等根据提出的一种新的机器学习方法，它以结构风险最小为原则，它本质上是求解凸二次规划问题，在解决小样本、非线性和高维模式识别问题中有较大优势。 基本原理问题转化为寻找映射f(x,w)： 它是评价预测准确度的一种度量，不同的学习问题有不同形式的损失函数。例),(wfiixx 给定样本1122(,),(,),(,),nniiyyyyxxxx( )( ( ,(,)( ,( ,)( , )R wE L Y f X wL y f x w dF x y( ,( ,)L y f x w其中损失函数。0( ,)(

2、1)( ,( ,)1( ,)yf xL y f xyf x2(2)( ,( ,)( ,)L y f xyf x(3)( ( ,)log( ,)L p xp x 基本原理11( )( , ( , )minnempiiiRwL y f x wn定义经验风险Remp(w): lim sup|( )( )|0,0empPR wRw 理论上证明：如果采用损失函数(1)，则min(Remp(w)表示错判率达最小；如果采用损失函数(2)，则min(Remp(w)即是最小二乘法；如果采用损失函数(3)，则min(Remp(w)即是极大似然法； 经验风险最小化存在的问题： （1）Remp(w)R(w)，推广能力

3、或泛化能力受影响； （2）所需样本容量大； （3）某些情况下，当经验风险过小时，推广能力反而下降；经验风险和期望风险的最小点不一致。 需要一种在有限的样本条件下建立有效的学习和推广方法的理论，统计学习理论的发展和完善对解决上面的问题，提供了坚实的理论基础与有效的学习方法。统计学习理论 统计学习理论主要包括VC理论、泛化性的界、结构风险最小化等。 1. VC维的直观定义：对于一个指示函数集，如果存在k个样本能被函数集中的函数按所有可能的2k种形式分开，则称函数集能把k个样本打散； VC维反映了函数集的一种学习能力。VC维越大则学习机越复杂。统计学习理论*VC维：23=8平面上任何一条直线都不能正

4、确划分*统计学习理论2. 推广性的界 统计学习理论研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。对于两分类的问题，推广性的界是指对指示函数集中的所有函数f，经验风险和实际风险之间至少以1-p的概率满足如下关系：(ln(2 / ) 1)ln(4/)( )( )()emphn hpR fRfn其中h是函数集的VC维，n是样本数。 实际风险由两部分组成：一部分是经验风险，另一部分称作置信范围，它和学习机的VC维和样本数有关。 统计学习理论3. 结构风险最小化原则 基本思想：要使实际风险最小，就需要使得不等式中两项相互平衡，共同趋于极小。统计学习理论中提出了一种新的策略，即把

5、函数集合构造为一个函数子集序列：各个子集按照VC维的大小排序：12kfff12khhh12()()()empempempkRfRfRf而统计学习理论4.支持向量机的基本思想 通过最大化分类边界及最小化VC维，在保证经验风险最小的基础上最小化置信范围，从而达到最小化结构风险的目的。分类间隔（1）线性可分情形|2w:0Hxb2,1min|2. .()1,1, 1,1w biiiwstyw xbily 支持向量机引入Lagrange函数：对偶问题：2,1min|2. .()1,1, 1,1w biiiwstyw xbily 211( , , )( () 1)2liiiiLbyxb11( , ,)(

6、, ,)0,00,lliiiiiiiLbLbKKTbwyy x由条件11111min()2. .0,0,1, .lllijijijiijiliiiiy yx xstyil（1.1）注意：求解过程涉及到了样本的内积运算。注意：求解过程涉及到了样本的内积运算。 算法步骤：（1）设训练集（2）求解最优化问题(1.1)，得最优解：*12(,)Tl （3）计算1122( ,),(,),( ,)(, )lllTx yxyx yX Y, 1,1,1, ;PiixXRyYil 其中*1liiiiwyx并选择 的正分量，计算 *1()ljiiijibyyx x（4）构造线性最优分类超平面，得出决策函数：1( )

7、sgn()liiiif xa y x xb支持向量机 情形1：当训练样本线性不可分时，允许有不满足约束条件 的样本点存在。()1,1,0,1,iiiiyw xbilil 支持向量机()1iiyw xb通过引入松弛变量，“软化”约束条件得到如下优化问题：2,11min|2. .()1,1,0,1, C0liw biiiiiwCstyw xbilil 其中为惩罚参数。转化为对偶问题：11111min()2. .0,1.20,1, .lllijijijiijiliiiiy yx xstyC il（）支持向量机 情形2：当训练集线性不可分时，可以通过非线性映射将原始空间的样本映射到高维特征空间中，即寻

8、找非线性变换： 支持向量机:( ),()pmxRxRmp11111min( ( )()2. .0,(1.3)0,1, .lllijijijiijiliiiiy yxxstyil 由于内积运算是在相对的高维空间中进行，容易引起维数灾难。为此引入核函数K(.)，满足 ( ,)( ( )()ijijK x xxx支持向量机即11111min( ,)2. .0,(1.4)0,1, .lllijijijiijiliiiiy yK x xstyil注意：还可以引入松弛变量到优化问题中。支持向量机常见的核函数： （1）多项式核 （2）高斯径向基核 （3）Sigmoid核 （4）Fourier核函数( , )

9、()0dK x xx xcc2( ,)exp()xxK x x ( ,)tanh( ()0,0K x xx xaa2121( , )2(1 2 cos()qK x xqxxq2cosh()( , )2sin()xxrKx xrr支持向量机核函数的性质： 1. 封闭性2. 对称性3. 复合性12112,limnnKKKKKKK是核函数。( , )( ), ( )( ), ( )( , )K x zxzzxK z x:( ) ( )( )( , ) ( )K XXRfXRf x f zf x K x z f z若是核函数，是任意函数，则和也是核函数。针对问题，如何选择核函数？针对问题，如何选择核函

10、数？ 支持向量机算法的改进支持向量机算法的改进问题：问题： 1. 1. 对于核函数及其参数的选择没有形成一个统一的对于核函数及其参数的选择没有形成一个统一的模式，只能凭经验、实验对比、大范围的搜索或交叉验模式，只能凭经验、实验对比、大范围的搜索或交叉验证等方法进行寻优。证等方法进行寻优。 2. 2. 当样本数很大时，一般的二次规划求解方法不再当样本数很大时，一般的二次规划求解方法不再适用，需要用到适用，需要用到“分块分块”或或“分解分解”的近似算法，但所的近似算法，但所耗内存空间大，迭代次数多，训练时间长等。耗内存空间大，迭代次数多，训练时间长等。支持向量机算法的改进支持向量机算法的改进1 1

11、）v-SVMv-SVM 特点：克服了特点：克服了SVMSVM中中C C参数难以确定问题。同时还可以减参数难以确定问题。同时还可以减少两类样本不平衡问题。适用于样本不均衡问题。少两类样本不平衡问题。适用于样本不均衡问题。2 2）LS-SVMLS-SVM 特点：通过映射将原空间的不等式约束转化为特征空间特点：通过映射将原空间的不等式约束转化为特征空间中的等式约束，转化后的对偶问题为求解一组线性方程中的等式约束，转化后的对偶问题为求解一组线性方程组。优点：计算代价小，泛化性能好，不易陷入局部极组。优点：计算代价小，泛化性能好，不易陷入局部极小。小。支持向量机算法的改进支持向量机算法的改进3 3）GS

12、VMGSVM 当数据线性不可分时，当数据线性不可分时，SVMSVM要求满足要求满足MercerMercer条件，即正条件，即正定核条件。定核条件。GSVMGSVM突破了这一限制。突破了这一限制。4 4）Smooth SVMSmooth SVM 特点：通过一定的变形技巧，使其转化为光滑的无约束特点：通过一定的变形技巧，使其转化为光滑的无约束问题，再利用经典的最优化方法求解。问题，再利用经典的最优化方法求解。支持向量机算法的改进支持向量机算法的改进5 5）Possibilistic SVMPossibilistic SVM 结合输入数据的几何分布，每个数据有一个可能性隶属结合输入数据的几何分布，每

13、个数据有一个可能性隶属值，反映对本类的隶属度，有效克服值，反映对本类的隶属度，有效克服SVMSVM中对每个数据平中对每个数据平等对待的缺点。当样本点个数小于维数时，能有效解决过等对待的缺点。当样本点个数小于维数时，能有效解决过拟合问题。拟合问题。6 6）Semi Supervised SVMSemi Supervised SVM 适用于训练集规模比工作集大得多的情况。加进约束条适用于训练集规模比工作集大得多的情况。加进约束条件：两类中的误分误差情形，有效地增强了它的泛化能力。件：两类中的误分误差情形，有效地增强了它的泛化能力。基本思想：构造映射的svm对原样本进行特征提取，引入距离映射或条件概

14、率映射，将高维空间的样本x转化为二维空间的样本 引入核函数： 212( )( ,),Txz zR( ( ), ( )( ( )( )Kxxxx1.距离映射 211111( )()()Tdxxx马氏距离212212( )()()Tdxxx2212:( ),( )Txdxdx定义映射由此定义核函数：22221122( ,)( ( )( )( )( )( )( ), pK x xxxdx dxdx dxx xR构造映射的svm2. 条件概率映射 1122:( () ( |),() ( |)TxP G P x GP G P x G22111222( ,)( ( )( )()( |) ( |)()( |

15、) ( |)K x xxxP GP x G P xGP GP x G P xG在二维空间中求解原始最优化问题： , 1,1)(. .|21min2,libxwytswiibw决策变量只有三个：w1,w2, b 1122( )sgn( ( )sgn()0, 2f xxwbw xw xb其中 为修正参数，一般取构造映射的svm051015202530051015202530正类负类构造映射的svm构造映射的svm构造映射的svm构造映射的svm构造映射的svm支持向量机多分类问题支持向量机多分类问题1. 一对多分类方法 基本思路： 对k个类别的分类问题，构造k个两分类的支持向量分类机。在构建第j个

16、分类器中时，将训练集中属于第j类的样本标为+1，属于其它类的样本标为-1。这样第i个分类器的最优化问题：211min2()1.1,2,.,01,iiiliijbjiiijjjijCyxbstikjl 111( )( )kkkf xxbfxxb 求出k个决策函数argmax( )iixclassf x支持向量机多分类问题支持向量机多分类问题2.一对一分类方法 基本思路： 分解为多个二分类问题的算法。总共需要构建k(k-1)/2个子SVM分类器。得到 决策函数 2kC2kC1,21,21,2,1,1,1,( )( )()( )i ji ji jkkkkkkfxxbfxxbijfxxb ,1,( ) 1( )(1, )2ki jijj ifxD xikargmax( )iixclassD x支持向量机多分类问题支持向量机多分类问题1.二叉树分类方法 Class1Class2Class3Class4Svm2Svm3Svm1对有k个类别的多分类问题，需要构造k-1个二分类SVM分类器，