《支持向量分类机原理讲述课件.ppt》由会员分享，可在线阅读，更多相关《支持向量分类机原理讲述课件.ppt（35页珍藏版）》请在三一办公上搜索。
1、Support Vector Classification,数据挖掘中的新方法支持向量分类机原理,位礼奎2016年6月,提纲,SVM有关概念介绍SVM分类问题的数学表示和推导简单的最优分类面广义最优分类面非线性最优分类面,History,SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速发展起来，目前已经在许多智能信息获取与处理领域都取得了成功的应用。,传统的统计模式识别方法只有在样本趋向无穷大时，其性能才有理论的保证。统计学习理论（STL）研究有限样本情况下的机器学习问题。SVM的理论基础就是统计学习理论。传统的统计模式
2、识别方法在进行机器学习时，强调经验风险最小化。而单纯的经验风险最小化会产生“过学习问题”，其推广能力较差。推广能力是指:将学习机器(即预测函数,或称学习函数、学习模型)对未来输出进行正确预测的能力。,“过学习问题”：某些情况下，当训练误差过小反而会导致推广能力的下降。例如：对一组训练样本(x,y),x分布在实数范围内，y取值在0，1之间。无论这些样本是由什么模型产生的，我们总可以用y=sin(w*x)去拟合，使得训练误差为0.,根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，因此
3、其推广能力较差。Vapnik 提出的支持向量机（Support Vector Machine,SVM）以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即SVM是一种基于结构风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。,由于SVM 的求解最后转化成二次规划问题的求解，因此SVM 的解是全局唯一的最优解SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中,关于SVM,思想：通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类
4、数据点正确的分开，同时使分开的两类数据点距离分类面最远。途径：构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题(constrained quadratic programing),求解该问题，构造分类超平面，从而得到决策函数。,提纲,SVM有关概念介绍SVM分类问题的数学表示和推导简单的最优分类面广义最优分类面非线性最优分类面,分类问题的数学表示,已知：训练集包含 个样本点：说明：是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标；是输出指标，或输出.问题：对一个新的模式，推断它所对应的输出 是1还是-1.实质：找到一个把 上的点分成两部分的规则
5、.,2维空间上的分类问题)n维空间上的分类问题.,根据给定的训练集其中，寻找 上的一个实值函数，用决策函数判断任一模式 对应的 值.可见，分类学习机构造决策函数的方法(算法)，两类分类问题 多类分类问题 线性分类学习机 非线性分类学习机,分类学习方法,SVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。,最大间隔原则,考虑图1.2.1(a)上的线性可分的分类问题.这里有许多直线 能将两类点正确分开.如何选取 和？简单问题：设法方向 已选定，如何选取？解答：选定 平行直线 极端直线 和 取 和 的中间线为分划直线如何选取？对应一个，有极端直线，称 和 之间的距离为“间隔”，
6、显然应选使“间隔”最 大的。,最大间隔法的直观导出,数学语言描述：给定适当的法方向 后，这两条极端直线 可表示为,调整，使得,令，则两式可以等价写为,与此相应的分划直线表达式:,如何计算分划间隔？考虑2维空间中极端直线之间的间隔情况,求出两条极端直线的距离：,原始问题,求解原始问题？,为求解原始问题，根据最优化理论，我们转化为对偶问题来求解,对偶问题,为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解,1.线性可分问题,计算，选择 的一个正分量,并据此计算,事实上，的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练
7、点，而与对应于 为零的那些训练点无关。,称 不为零的这些训练点的输入 为支持向量(SV),构造分划超平面,决策函数,根据最优解,2.近似线性可分问题,不要求所有训练点都满足约束条件，为此对第 个训练点 引入松弛变量(Slack Variable),把约束条件放松到。,体现了训练集被错分的情况，可采用 作为一种度量来描述错划程度。,两个目标：1.间隔 尽可能大 2.错划程度 尽可能小,显然，当 充分大时，样本点 总可以满足以上约束条件。然而事实上应避免 太大，所以需在目标函数对 进行惩罚,（即“软化”约束条件）,2.近似线性可分问题,因此，引入一个惩罚参数，新的目标函数变为:,体现了经验风险，而
8、 则体现了表达能力。所以惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。当 时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。,算法：(广义)线性支持向量分类机,设已知训练集，其中,2.选择适当的惩罚参数，构造并求解最优化问题,3.计算，选择 的一个分量，并据此 计算出,4.构造分划超平面,决策函数,求得,3.非线性分划,例子:,3.非线性分划,设训练集，其中假定可以用 平面上的二次曲线来分划：,现考虑把2维空间 映射到6维空间的变换,上式可将2维空间上二次曲线映射为6维空间上的一个超平面：,3.非线性分划,可见，只要利用变换(2.3.4)，把 所在的2维空间的两类输入点映射
9、到 所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：,最后得出原空间中的二次曲线：,怎样求6维空间中的分划超平面？(线性支持向量分类机),3.非线性分划,需要求解的最优化问题,其中,3.非线性分划,在求得最优化问题的解 后，得到分划超平面,其中,最后得到决策函数,或,线性分划非线性分划代价：2维空间内积6维空间内积,3.非线性分划,为此，引进函数,有,比较(2.3.6)和(2.3.7)，可以发现,这是一个重要的等式，提示6维空间中的内积可以通过计算 中2维空间中的内积 得到。,实现非线性分划的思想,给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分
10、划办法，则可以考虑选择其它形式的函数，一旦选定了函数，就可以求解最优化问题,得，而决策函数,实现非线性分划的思想,决策函数,其中,核函数(核或正定核)定义,设 是 中的一个子集。称定义在 上的函数,是核函数(正定核或核)，如果存在着从 到某一个空间 的映射,使得,其中 表示 中的内积,核函数的选择,多项式内核径向基函数内核RBFSigmoind内核,目前研究最多的核函数主要有三类：,得到q 阶多项式分类器,每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定,包含一个隐层的多层感知器，隐层节点数是由算法自动确定,Thank you!,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,
