资源描述
,数据挖掘十大算法之,SVM,程广兵,201,分类,概念：,通过构造一个,分类函数,或,分类器,的方法，该方法能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知数据。,数据：,线性可分,线性不可分,什么是,SVM,全名：,Support Vector Machine,（支持向量机）,支持向量,：,支持或支撑平面,上把两类类别划分开来的超平面的,向量点,。,机,：一个算法,基于统计学习理论的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。,SVM,的特点,SVM是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性之间寻求最佳折衷，以期获得最好的推广能力（或泛化能力）。,核函数,松弛变量,线性分类,1,线性分类,1,线性分类,最优标准：分类间隔,对于给定的训练数据集,T,和超平面（,w,b,），定义超平面（,w,b,）关于样本点（,x,i,y,i,）的函数间隔为,对于给定的训练数据集,T,和超平面（,w,b,），定义超平面（,w,b,）关于样本点（,x,i,y,i,）的几何间隔为,|w|叫做向量w的范数,WX的p范数为|w|p=(X1p+X2p+.+Xnp）(1/p),函数间隔和几何间隔的关系,=/|w|,（,1,）,最优标准：分类间隔,H2与H之间的间隔便是几何间隔。其中H1：wx+b=1；H2：wx+b=-1；,定义超平面（,w,b,）关于训练数据集,T,的函数间隔为超平面（,w,b,）关于,T,中所有样本点（,x,i,y,i,）的函数间隔之最小值，即,同理,最终问题转化成为求最大,值。（,ps:,我的理,解 在找到几何间隔,后，就要使,H1,和,H2,尽可能,的离,H,远，这样分类就更有说服力）,在H1和,H2,上的点就叫做支持向量,H1,和,H2,之间的距离称为间隔，间隔依赖于法向量,w,等于,2/|w|,H1,和,H2,称为间隔边界,由等式（,1,），可将问题写为,求最大的,由于函数间隔,不影响最优化问题的解，这样可以取,=1,，由于最大化,1/|w|,和最小化,1/2*|w|*|w|,问题是等价的,于是问题便转化成了求,很容易看出当|w|=0的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带,解决方法：加一个约束条件,求最大的,我们把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间隔都不会小于1，于是不难得到有不等式：yi+b1(i=1,2,l)总成立。,于是上面的问题便转化成了求条件最优化问题：,约束条件,这是一个凸二次规划问题，所以一定会存在全局的最优解，但实际求解较为麻烦。,实际的做法：将不等式约束转化为等式约束，从而将问题转化为拉格朗日求极值的问题。,（,2,）,（,3,）,最优问题的求解,为了求解线性可分支持向量机的最优化问题（,2,）,（,3,），将它作为原始最优化问题，应用拉格朗日对偶性（参考李航的统计学习方法附录,C,），通过求解对偶问题得到原始问题的最优解，这是线性可分支持向量机的对偶算法。,最优问题的求解,引入拉格朗日乘子 （,ps:,之所以，,=0,是因为如果不做限定，因为 要求极大值，而 ，那么 可以取负无穷，这样目标值就会无穷大，其实当点是支持向量时,0,其他的点,=0,）,利用Lagrange乘子法：,当点是支持向量时,y(wx+b)=1,当点不是支持向量时,y(wx+b)1,这样Lagrange函数的第二项,始终为零,凸二次规划问题求解,代入,L(w,b,a):,问题转换为,凸二次规划问题求解,凸二次规划问题求解,更多细节请参照李航的统计学习方法,SVM,这一章,凸二次规划问题求解,为了,例题,例题,线性分类,目标函数：约束条件：,目标函数：约束条件：,拉格朗日乘数法可将问题转化为对偶问题：,目标函数：约束条件：,线性分类,巧妙之处：原问题,=,二次凸优化问题,=,对偶问题,对偶问题求解：,更巧妙的地方：,未知数据,x,的预测，只需要计算它与训练数据点的内积即可,非线性分类,对于以上所述的,SVM,，处理能力还是很弱，仅仅能处理线性可分的数据。如果数据线性不可分的时候，我们就将低维的数据映射向更高的维次，以此使数据重新线性可分。这转化的关键便是核函数。,非线性分类,找不到一个超平面（二维空间：直线）将其分割开来，而很自然的想到可以用一个椭圆将数据分为两类,Z,1,=X,1,Z,2,=X,1,2,Z,3,=X,2,Z,4,=X,2,2,Z,5,=X,1,X,2,(X,1,X,2,),(Z,1,Z,2,Z,3,Z,4,Z,5,),即将：,R,2,空间映射到,R,5,空间。,此时，总能找到一个超平面,w,T,Z+b=0,w,T,=a,1,，,a,2,，,a,3,，,a,4,，,a,5,T,，,b=a,6,使得数据很好的分类。,映射过后的空间,:,非线性分类,令：,Z,1,=X,1,Z,2,=X,1,2,Z,3,=X,2,Z,4,=X,2,2,Z,5,=X,1,X,2,(X,1,X,2,),(Z,1,Z,2,Z,3,Z,4,Z,5,),则：对于样本,x,1,=(,1,2,),x,2,=(,1,2,),(x,1,)=,1,1,2,2,2,2,1,2,T,(x,2,)=,1,1,2,2,2,2,1,2,T,内积,:,我们注意到：,非线性分类,我们注意到：,若令,(x,1,)=,2,1,1,2,2,2,2,2,2,1,2,1,T,则：,那么区别在于什么地方呢？,1.,一个是将低维空间数据映射到高维空间中，然后再根据内积的公式进行计算；,另一个则直接在原来的,低维空间中进行计算,，而,不需要显式,地写出映射后的结果。,当样本空间处于高维度时，第一种方法将引发,维度灾难,，第二种方法仍然能够从容处理,核函数,核函数：,概念：,x,zX,X,属于,R,n,空间,非线性函数,实现输入空间,X,到特征空间,F,的映射,其中,F,属于,R,m,，,nm,。核函数技术接收,2,个低维空间的向量，能够计算出经某变换后高维空间里的向量内积值。,根据核函数技术有：,K(x,z)=,其中：,为内积,K(x,z),为核函数。,例如：,加入核函数以后的分类函数为：,核函数,核函数应用广泛的原因：,核函数的引入避免了“,维数灾难,”,大大,减小了计算量,。而输入空间的维数,n,对核函数矩阵无影响，因此，核函数方法可以有效处理高维输入。,无需知道非线性变换函数,的形式和参数,核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。,核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这,两部分的设计可以单独进行,，并可以为,不同的应用选择不同的核函数,和算法。,常用的核函数,多项式核：,线性核：,高斯核：,总结,线性可分：,求解使得超平面具有最大内间间隔的,w,T,，,b,参数。,将问题转化为对偶问题进行快速求解。,改进：加入松弛变量 和惩罚因子,C,的,SVM,松弛变量允许实际分类中一定的不准确性的存在，引入松弛变量后原先的约束条件变为：,惩罚因子C则是为了避免系统轻易放弃一些重要的数据，减小系统损失。引入C后目标函数变为：,总结,线性不可分：,将数据空间映射到高维空间，使原本线性不可分变为线性可分。,引入核函数，简化映射空间中的内积运算。它,避开了直接在高维空间中进行计算,，而表现形式却,等价于高维空间,。,不同的样本结构与不同的核函数结合，达到很好的分割效果,因时间有限，先介绍这么多，如果有兴趣进一步学习的同学，很开心找我们可以课下讨论,参考资料,1.,支持向量机导论,，,美,Nello Cristianini/John Shawe-Taylor,著；,2.,支持向量机导论一书的支持网站：；,3.,数据挖掘导论,，,美,Pang-Ning Tan/Michael Steinbach/Vipin Kumar,著；,4.,数据挖掘：概念与技术,，,(,加,)Jiawei Han;Micheline Kamber,著；,5.,数据挖掘中的新方法：支持向量机,，邓乃扬 田英杰 著；,6.,支持向量机,-,理论、算法和扩展,，邓乃扬 田英杰 著；,7.,模式识别支持向量机指南,，,C.J.C Burges,著；,8.,统计自然语言处理,，宗成庆编著，第十二章、文本分类；,9.SVM,入门系列，,Jasper,：；,10.,数据挖掘掘中所需的概率论与数理统计知识、上；,11.,数理统计学简史,，陈希孺院士著；,12.,最优化理论与算法,(,第,2,版,),，陈宝林编著；,13.A Gentle Introduction to Support Vector Machines in Biomedicine,：,14.,卡梅隆大学的讲解,SVM,的,PPT,：；,15.,统计学习方法,，李航 著，第七章 支持向量机；,16.,斯坦福大学公开课 机器学习第,7,8,集,
展开阅读全文