《大数据十大经典算法svm 讲解》课件.ppt

数据挖掘十大算法之 SVM 小组成员： 杨凌云、徐小江、刘洁 刘家旺、吕佳艳、伍俊 2013年10月 分类 概念： 通过构造一个分类函数或分类器的方法，该方法能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知数据。 数据： 线性可分 线性不可分 什么是SVM 全名：Support Vector Machine（支持向量机） 支持向量：支持或支撑平面上把两类类别划分开来的超平面的向量点。 机：一个算法 基于统计学习理论的一种机器学习方法。简单的说，就是将数据单元表示在多维空间中，然后对这个空间做划分的算法。 SVM的特点 SVM是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性之间寻求最佳折衷，以期获得最好的推广能力（或泛化能力）。 核函数 松弛变量 线性分类 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=(X1^p+X2^p+...+Xn^p）^(1/p) 最优标准：分类间隔 H2与H之间的间隔便是几何间隔。其中H1：w,x+b = 1；H2：w,x+b = -1； 几何间隔与样本的误分次数间的关系：误分次数 = (2R/δ)^2，其中δ是样本集合到分类面的间隔，R=max || xi ||,i=1,...,n; 所以问题转化成为求最大δ值。 因为w是超平面的法向量，所以w实际上只由在H1平面上的样本点确定； 在H1上的向量则叫做Supported Vectors ，因为它们“撑”起了分界线。 求最大的δ 于是问题便转化成了求 很容易看出当||w||=0的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，所有样本点都进入了无法分类的灰色地带 解决方法：加一个约束条件 求最大的δ 我们把所有样本点中间隔最小的那一点的间隔定为1，也就意味着集合中的其他点间隔都不会小于1，于是不难得到有不等式：yi[w,xi+b]≥1 (i=1,2,…,l)总成立。 于是上面的问题便转化成了求条件最优化问题： 约束条件 这是一个凸二次规划问题，所以一定会存在全局的最优解，但实际求解较为麻烦。 实际的做法：将不等式约束转化为等式约束，从而将问题转化为拉格朗日求极值的问题。 最优问题的求解 引入拉格朗日对偶变量a，w可表示为：w=a1y1x1+a2y2x2+…+anynxn； 利用Lagrange乘子法： 凸二次规划问题求解 代入 L(w,b,a): 问题转换为： 由凸二次规划的性质能保证这样最优的向量a是存在的 凸二次规划问题求解 线性分类 目标函数： 约束条件： 目标函数： 约束条件： 拉格朗日乘数法可将问题转化为对偶问题： 目标函数： 约束条件： 线性分类 巧妙之处：原问题 = 二次凸优化问题 = 对偶问题 对偶问题求解： 更巧妙的地方： 未知数据x的预测，只需要计算它与训练数据点的内积即可 非线性分类 对于以上所述的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， a5}T ，b = 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, η1η2]T Φ(x2) = [ξ1, ξ12, ξ2, ξ22, ξ1ξ2] T 内积: 我们注意到： 非线性分类 我们注意到： 若令 Φ(x1) = [√2η1 , η1