大数据十大经典算法SVM-讲解课件

1、数据挖掘十大算法之SVM2013年10月分类概念：通过构造一个分类函数或分类器的方法，该方法能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知数据。数据：线性可分线性不可分什么是SVM全名：Support Vector Machine（支持向量机）支持向量：支持或支撑平面上把两类类别划分开来的超平面的向量点。机：一个算法基于统计学习理论的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。SVM的特点 SVM是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性之间寻求最佳折衷，以期获得最好的推广能力（或

2、泛化能力）。 核函数 松弛变量线性分类1线性分类1线性分类问题1. 如何求得最优的g(x)？2. 最优的标准是什么？3. g(x)=wx+b中的w和b如何确定？最优标准：分类间隔数据表示Di=(xi,yi)分类间隔即两分类之间的距离越远越不易混淆定义i = (1/|w|)|g(xi)|，称为几何间隔|w|叫做向量w的范数,WX的p范数为 |w|p=(X1p+X2p+.+Xnp）(1/p)最优标准：分类间隔H2与H之间的间隔便是几何间隔。其中H1：+b = 1；H2：+b = -1；几何间隔与样本的误分次数间的关系：误分次数 = (2R/)2，其中是样本集合到分类面的间隔，R=max | xi

3、|,i=1,.,n;所以问题转化成为求最大值。因为w是超平面的法向量，所以w实际上只由在H1平面上的样本点确定；在H1上的向量则叫做Supported Vectors ，因为它们“撑”起了分界线。求最大的于是问题便转化成了求很容易看出当|w|=0的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带解决方法：加一个约束条件求最大的我们把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间隔都不会小于1，于是不难得到有不等式：yi+b1 (i=1,2,l)总成立。于是上面的问题便转化成了求条件最优化问题：约束条件这是

4、一个凸二次规划问题，所以一定会存在全局的最优解，但实际求解较为麻烦。实际的做法：将不等式约束转化为等式约束，从而将问题转化为拉格朗日求极值的问题。最优问题的求解引入拉格朗日对偶变量a，w可表示为：w=a1y1x1+a2y2x2+anynxn；利用Lagrange乘子法：凸二次规划问题求解代入 L(w,b,a):问题转换为：由凸二次规划的性质能保证这样最优的向量a是存在的凸二次规划问题求解线性分类目标函数： 约束条件：目标函数： 约束条件：拉格朗日乘数法可将问题转化为对偶问题：目标函数： 约束条件：线性分类巧妙之处：原问题 = 二次凸优化问题 = 对偶问题对偶问题求解：更巧妙的地方： 未知数据x

5、的预测，只需要计算它与训练数据点的内积即可非线性分类对于以上所述的SVM，处理能力还是很弱，仅仅能处理线性可分的数据。如果数据线性不可分的时候，我们就将低维的数据映射向更高的维次，以此使数据重新线性可分。这转化的关键便是核函数。非线性分类找不到一个超平面（二维空间：直线）将其分割开来，而很自然的想到可以用一个椭圆将数据分为两类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 =

6、a6 使得数据很好的分类。映射过后的空间:非线性分类令：Z1=X1, Z2=X12, Z3=X2, Z4=X22, Z5=X1X2(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) = 21 , 12, 22 , 22, 212 , 1T则：那么区别在于什么地方呢？1. 一个是将低维空间数据映射到高维空间中，然后再根据内积的公式进行计算； 另一个则直接在原来的低维空间中进行计算，

7、而不需要显式地写出映射后的结果。当样本空间处于高维度时，第一种方法将引发维度灾难，第二种方法仍然能够从容处理核函数核函数：概念：x,zX, X属于Rn空间,非线性函数实现输入空间X到特征空间F的映射,其中F属于Rm，nm。核函数技术接收2个低维空间的向量，能够计算出经某变换后高维空间里的向量内积值。根据核函数技术有：K(x,z) = 其中：为内积,K(x,z)为核函数。例如：加入核函数以后的分类函数为：核函数核函数应用广泛的原因：核函数的引入避免了“维数灾难”,大大减小了计算量。而输入空间的维数n对核函数矩阵无影响，因此，核函数方法可以有效处理高维输入。无需知道非线性变换函数的形式和参数核函数

8、的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法。常用的核函数多项式核：线性核：高斯核：总结线性可分：求解使得超平面具有最大内间间隔的wT，b参数。将问题转化为对偶问题进行快速求解。改进：加入松弛变量 和惩罚因子C的SVM 松弛变量允许实际分类中一定的不准确性的存在，引入松弛变量后原先的约束条件变为：惩罚因子C则是为了避免系统轻易放弃一些重要的数据，减小系统损失。引入C后目标函数变为：总

9、结线性不可分：将数据空间映射到高维空间，使原本线性不可分变为线性可分。引入核函数，简化映射空间中的内积运算。它避开了直接在高维空间中进行计算，而表现形式却等价于高维空间。不同的样本结构与不同的核函数结合，达到很好的分割效果参考资料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：/zhenandaci/category/31868.html； 10. 数据挖掘掘中所需的概率论与数理统计知识、上； 11.数理统计学简史，陈希孺院士著； 12.最优化理论与算法(第2 版)，陈宝林编著； 13. A G