大数据十大经典算法SVM_讲解PPT.ppt

《大数据十大经典算法SVM_讲解PPT.ppt》由会员分享，可在线阅读，更多相关《大数据十大经典算法SVM_讲解PPT.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘十大算法之数据挖掘十大算法之SVM程广兵程广兵 2012014.12.224.12.22分类分类概念：概念：通过构造一个通过构造一个分类函数分类函数或或分类器分类器的方法，该方法能把数据库中的数据项的方法，该方法能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知数据。映射到给定类别中的某一个，从而可以用于预测未知数据。数据：数据：线性可分线性可分线性不可分线性不可分什么是什么是SVM全名：全名：Support Vector Machine（支持向量机）（支持向量机）支持向量支持向量：支持或支撑平面支持或支撑平面上把两类类别划分开来的超平上把两类类别划分开来的超平面的面的

2、向量点向量点。机机：一个算法：一个算法基于统计学习理论的一种机器学习方法。简单的说，基于统计学习理论的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。做划分的算法。SVM的特点的特点 SVM是建立在统计学习理论的是建立在统计学习理论的VC维理论和结构风险最维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性小原理基础上的，根据有限的样本信息在模型的复杂性之间寻求最佳折衷，以期获得最好的推广能力（或泛化之间寻求最佳折衷，以期获得最好的推广能力（或泛化能力）。能力）。核函数核函数 松弛变量松弛变量线

3、性分类线性分类1线性分类线性分类1线性分类线性分类最优标准：分类间隔最优标准：分类间隔对于给定的训练数据集对于给定的训练数据集T和超平面（和超平面（w,b），定义超平面（），定义超平面（w,b）关于样本点（）关于样本点（xi,yi）的函数间隔为的函数间隔为 对于给定的训练数据集对于给定的训练数据集T和超平面（和超平面（w,b），定义超平面（），定义超平面（w,b）关于样本点（）关于样本点（xi,yi）的几何间隔为的几何间隔为|w|叫做向量叫做向量w的范数的范数,WX的的p范数为范数为|w|p=(X1p+X2p+.+Xnp）(1/p)函数间隔和几何间隔的关系函数间隔和几何间隔的关系=/|w|（1

4、）最优标准：分类间隔最优标准：分类间隔H2与与H之间的间隔便是几何间隔。其中之间的间隔便是几何间隔。其中H1：wx+b=1；H2：wx+b=-1；定义超平面（定义超平面（w,b）关于训练数据集）关于训练数据集T的函数间隔为超平面（的函数间隔为超平面（w,b）关于）关于T中所有样本点中所有样本点（xi,yi）的函数间隔之最小值，即）的函数间隔之最小值，即同理同理最终问题转化成为求最大最终问题转化成为求最大值。（值。（ps:我的理我的理解解 在找到几何间隔在找到几何间隔后，就要使后，就要使H1和和H2尽可能尽可能的离的离H远，这样分类就更有说服力）远，这样分类就更有说服力）在在H1和和H2上的点就

5、叫做支持向量上的点就叫做支持向量H1和和H2之间的距离称为间隔，间隔依赖于之间的距离称为间隔，间隔依赖于法向量法向量w,等于等于2/|w|,H1和和H2称为间隔边界称为间隔边界由等式（由等式（1），可将问题写为），可将问题写为求最大的求最大的由于函数间隔由于函数间隔不影响最优化问题的解，这样可以取不影响最优化问题的解，这样可以取=1，由于最大化，由于最大化1/|w|和最小化和最小化1/2*|w|*|w|问题是等价的问题是等价的于是问题便转化成了求于是问题便转化成了求很容易看出当很容易看出当|w|=0的时候就得到了目标函数的最小值。反映在图中，就是的时候就得到了目标函数的最小值。反映在图中，就是

6、H1与与H2两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带解决方法：加一个约束条件解决方法：加一个约束条件求最大的求最大的我们把所有样本点中间隔最小的那一点的间隔定为我们把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间，也就意味着集合中的其他点间隔都不会小于隔都不会小于1，于是不难得到有不等式：，于是不难得到有不等式：yi+b1(i=1,2,l)总成立。总成立。于是上面的问题便转化成了求条件最优化问题：于是上面的问题便转化成了求条件最优化问题：约束条件约束条件这是一个凸二次规划问题，所以一定会存在全

7、局的最优解，但实际求解较为麻烦。这是一个凸二次规划问题，所以一定会存在全局的最优解，但实际求解较为麻烦。实际的做法：将不等式约束转化为等式约束，从而将问题转化为拉格朗日求极值的实际的做法：将不等式约束转化为等式约束，从而将问题转化为拉格朗日求极值的问题。问题。（2）（3）最优问题的求解最优问题的求解为了求解线性可分支持向量机的最优化问题（为了求解线性可分支持向量机的最优化问题（2）（3），将它作为原始最优化问），将它作为原始最优化问题，应用拉格朗日对偶性（参考李航的统计学习方法附录题，应用拉格朗日对偶性（参考李航的统计学习方法附录C），通过求解对偶问题得），通过求解对偶问题得到原始问题的最优解

8、，这是线性可分支持向量机的对偶算法。到原始问题的最优解，这是线性可分支持向量机的对偶算法。最优问题的求解最优问题的求解引入拉格朗日乘子引入拉格朗日乘子 （ps:之所以，之所以，=0 是因为如果不是因为如果不做限定，因为做限定，因为 要求极大值，而要求极大值，而 ，那么那么 可以取负无可以取负无穷，这样目标值就会无穷大穷，这样目标值就会无穷大，其实当点是支持向量时，其实当点是支持向量时 0,其他的点其他的点 =0）利用利用Lagrange乘子法：乘子法：当点是支持向量时当点是支持向量时y(wx+b)=1当点不是支持向量时当点不是支持向量时y(wx+b)1这样这样Lagrange函数的第二项函数的

9、第二项始终为零始终为零凸二次规划问题求解凸二次规划问题求解代入代入 L(w,b,a):问题转换为问题转换为凸二次规划问题求解凸二次规划问题求解凸二次规划问题求解凸二次规划问题求解更多细节请参照李航的统计学习方法更多细节请参照李航的统计学习方法SVM这一章这一章凸二次规划问题求解凸二次规划问题求解为了为了 例题例题 例题例题线性分类线性分类目标函数：目标函数：约束条件：约束条件：目标函数：目标函数：约束条件：约束条件：拉格朗日乘数法可将问题转化为对偶问题：拉格朗日乘数法可将问题转化为对偶问题：目标函数：目标函数：约约束条件：束条件：线性分类线性分类巧妙之处：原问题巧妙之处：原问题=二次凸优化问题

10、二次凸优化问题=对偶问题对偶问题对偶问题求解：对偶问题求解：更巧妙的地方：更巧妙的地方：未知数据未知数据x的预测，只需要计算它与训练数据点的内积即可的预测，只需要计算它与训练数据点的内积即可非线性分类非线性分类对于以上所述的对于以上所述的SVMSVM，处理能力还是很弱，仅仅能处理线性可分的数据。如，处理能力还是很弱，仅仅能处理线性可分的数据。如果数据线性不可分的时候，我们就将低维的数据映射向更高的维次，以此果数据线性不可分的时候，我们就将低维的数据映射向更高的维次，以此使数据重新线性可分。这转化的关键便是核函数。使数据重新线性可分。这转化的关键便是核函数。非线性分类非线性分类找不到一个超平面（

11、二维空间：直线）将其分割开来，而很自找不到一个超平面（二维空间：直线）将其分割开来，而很自然的想到可以用一个椭圆将数据分为两类然的想到可以用一个椭圆将数据分为两类Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X1X2(X1,X2)(Z1,Z2,Z3,Z4,Z5,)即将：即将：R2空间映射到空间映射到R5空间。空间。此时，总能找到一个超平面此时，总能找到一个超平面wT Z+b=0 wT=a1，a2，a3，a4，a5T，b=a6 使得数据很好的分类。使得数据很好的分类。映射过后的空间映射过后的空间:非线性分类非线性分类令：令：Z1=X1,Z2=X12,Z3=X2,Z4=X22,Z5=X

12、1X2(X1,X2)(Z1,Z2,Z3,Z4,Z5,)则：对于样本则：对于样本 x1=(1,2),x2=(1,2)(x1)=1,12,2,22,12T(x2)=1,12,2,22,12 T内积内积:我们注意到：我们注意到：非线性分类非线性分类我们注意到：我们注意到：若令若令(x1)=2 21,12,2 22,22,2 212,1T则：则：那么区别在于什么地方呢？那么区别在于什么地方呢？1.一个是将低维空间数据映射到高维空间中，然后再根据内积的公式进行计算；一个是将低维空间数据映射到高维空间中，然后再根据内积的公式进行计算；2.另一个则直接在原来的另一个则直接在原来的低维空间中进行计算低维空间中

13、进行计算，而，而不需要显式不需要显式地写出映射后的结果。地写出映射后的结果。3.当样本空间处于高维度时，第一种方法将引发当样本空间处于高维度时，第一种方法将引发维度灾难维度灾难，第二种方法仍然能够从容处理，第二种方法仍然能够从容处理核函数核函数核函数：核函数：概念：概念：x,z X,X属于属于Rn空间空间,非线性函数非线性函数实现输入空间实现输入空间X到特征空间到特征空间F的映射的映射,其中其中F属于属于Rm，nm。核函数技术接收。核函数技术接收2个低维空间的向量，个低维空间的向量，能够计算出经某变换后高维空间里的向量内积值。能够计算出经某变换后高维空间里的向量内积值。根据核函数技术有：根据核

14、函数技术有：K(x,z)=其中：其中：为内积为内积,K(x,z)为核函数。为核函数。例如：例如：加入核函数以后的分类函数为：加入核函数以后的分类函数为：核函数核函数核函数应用广泛的原因：核函数应用广泛的原因：核函数的引入避免了核函数的引入避免了“维数灾难维数灾难”,大大大大减小了计算量减小了计算量。而输入空间的维。而输入空间的维数数n对核函数矩阵无影响，因此，核函数方法可以有效处理高维输入。对核函数矩阵无影响，因此，核函数方法可以有效处理高维输入。无需知道非线性变换函数无需知道非线性变换函数的形式和参数的形式和参数核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，核函数的形式和参

15、数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这的方法，且这两部分的设计可以单独进行两部分的设计可以单独进行，并可以为，并可以为不同的应用选择不不同的应用选择不同的核函数同的核函数和算法。和算法。常用的核函数常用的核函数多项式核：多项式核：线性核：线性核：高斯核：高斯核：总结总结线性可分：线性可分：求解使得超平面具有最大内间间隔的求解使得超平

16、面具有最大内间间隔的wT，b参数。参数。将问题转化为对偶问题进行快速求解。将问题转化为对偶问题进行快速求解。改进：加入松弛变量改进：加入松弛变量 和惩罚因子和惩罚因子C的的SVM l松弛变量允许实际分类中一定的不准确性的存在，引入松弛变量后原先的约束条件变为：松弛变量允许实际分类中一定的不准确性的存在，引入松弛变量后原先的约束条件变为：l惩罚因子惩罚因子C则是为了避免系统轻易放弃一些重要的数据，减小系统损失。引入则是为了避免系统轻易放弃一些重要的数据，减小系统损失。引入C后目标函数后目标函数变为：变为：总结总结线性不可分：线性不可分：将数据空间映射到高维空间，使原本线性不可分变为线性可分。将数

17、据空间映射到高维空间，使原本线性不可分变为线性可分。引入核函数，简化映射空间中的内积运算。它引入核函数，简化映射空间中的内积运算。它避开了直接在高维空间中避开了直接在高维空间中进行计算进行计算，而表现形式却，而表现形式却等价于高维空间等价于高维空间。不同的样本结构与不同的核函数结合，达到很好的分割效果不同的样本结构与不同的核函数结合，达到很好的分割效果因时间有限，先介绍这么多，如果有兴趣进一步学习的同学，很开心找因时间有限，先介绍这么多，如果有兴趣进一步学习的同学，很开心找我们可以课下讨论我们可以课下讨论参考资料参考资料1.支持向量机导论支持向量机导论，美美 Nello Cristianini

18、/John Shawe-Taylor 著；著；2.支持向量机导论一书的支持网站：支持向量机导论一书的支持网站：http:/www.support- Pang-Ning Tan/Michael Steinbach/Vipin Kumar 著；著；4.数据挖掘：概念与技术数据挖掘：概念与技术，(加加)Jiawei Han;Micheline Kamber 著；著；5.数据挖掘中的新方法：支持向量机数据挖掘中的新方法：支持向量机，邓乃扬，邓乃扬 田英杰田英杰 著；著；6.支持向量机支持向量机-理论、算法和扩展理论、算法和扩展，邓乃扬，邓乃扬 田英杰田英杰 著；著；7.模式识别支持向量机指南模式识别支

19、持向量机指南，C.J.C Burges 著；著；8.统计自然语言处理统计自然语言处理，宗成庆编著，第十二章、文本分类；，宗成庆编著，第十二章、文本分类；9.SVM 入门系列，入门系列，Jasper：http:/ 版版)，陈宝林编著；，陈宝林编著；13.A Gentle Introduction to Support Vector Machines in Biomedicine：http:/www.nyuinformatics.org/downloads/supplements/SVM_Tutorial_2010/Final_WB.pdf14.卡梅隆大学的讲解卡梅隆大学的讲解SVM的的PPT：http:/www.autonlab.org/tutorials/svm15.pdf；15.统计学习方法统计学习方法，李航，李航 著，第七章著，第七章 支持向量机；支持向量机；16.斯坦福大学公开课斯坦福大学公开课 机器学习第机器学习第7,8集集