支持向量分类机原理

SupportVectorClassification数据挖掘中的新方法－支持向量分类机原理位礼奎2016年6月提纲SVM有关概念介绍SVM分类问题的数学表示和推导简单的最优分类面广义最优分类面非线性最优分类面HistorySVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon,Vapnik在COLT-92上首次提出，从此迅速发展起来，目前已经在许多智能信息获取与处理领域都取得了成功的应用。

传统的统计模式识别方法只有在样本趋向无穷大时，其性能才有理论的保证。统计学习理论（STL）研究有限样本情况下的机器学习问题。SVM的理论基础就是统计学习理论。传统的统计模式识别方法在进行机器学习时，强调经验风险最小化。而单纯的经验风险最小化会产生“过学习问题”，其推广能力较差。推广能力是指:将学习机器(即预测函数,或称学习函数、学习模型)对未来输出进行正确预测的能力。“过学习问题”：某些情况下，当训练误差过小反而会导致推广能力的下降。例如：对一组训练样本(x,y),x分布在实数范围内，y取值在[0，1]之间。无论这些样本是由什么模型产生的，我们总可以用y=sin(w*x)去拟合，使得训练误差为0.根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化置信范围值，因此其推广能力较差。Vapnik提出的支持向量机（SupportVectorMachine,SVM）以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即SVM是一种基于结构风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。由于SVM的求解最后转化成二次规划问题的求解，因此SVM的解是全局唯一的最优解SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中关于SVM思想：

通过某种事先选择的非线性映射（核函数）将输入向量映射到一个高维特征空间，在这个空间中寻找最优分类超平面。使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类数据点距离分类面最远。

途径：

构造一个约束条件下的优化问题，具体说是一个带线性不等式约束条件的二次规划问题(constrainedquadraticprograming),求解该问题，构造分类超平面，从而得到决策函数。提纲SVM有关概念介绍SVM分类问题的数学表示和推导简单的最优分类面广义最优分类面非线性最优分类面分类问题的数学表示已知：训练集包含个样本点：

说明：是输入指标向量，或称输入，或称模式，其分量称为特征，或属性，或输入指标；是输出指标，或输出.问题：对一个新的模式，推断它所对应的输出是1还是-1.实质：找到一个把上的点分成两部分的规则.

2维空间上的分类问题)n维空间上的分类问题.根据给定的训练集其中，，寻找上的一个实值函数，用决策函数

判断任一模式对应的值.

可见，分类学习机——构造决策函数的方法(算法)，两类分类问题多类分类问题线性分类学习机非线性分类学习机

分类学习方法SVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题。

最大间隔原则考虑图1.2.1(a)——上的线性可分的分类问题.这里有许多直线能将两类点正确分开.如何选取和？简单问题：设法方向已选定，如何选取？解答：选定平行直线极端直线和取和的中间线为分划直线如何选取？对应一个，有极端直线，称和之间的距离为“间隔”，显然应选使“间隔”最大的。

最大间隔法的直观导出数学语言描述：给定适当的法方向后，这两条极端直线可表示为调整，使得令，则两式可以等价写为与此相应的分划直线表达式:如何计算分划间隔？考虑2维空间中极端直线之间的间隔情况求出两条极端直线的距离：

原始问题求解原始问题？为求解原始问题，根据最优化理论，我们转化为对偶问题来求解对偶问题

为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解1.线性可分问题计算，选择的一个正分量,并据此计算事实上，的每一个分量都与一个训练点相对应。而分划超平面仅仅依赖于不为零的训练点，而与对应于为零的那些训练点无关。称不为零的这些训练点的输入为支持向量(SV)构造分划超平面,决策函数根据最优解2.近似线性可分问题不要求所有训练点都满足约束条件，为此对第个训练点引入松弛变量(SlackVariable),把约束条件放松到。

体现了训练集被错分的情况，可采用作为一种度量来描述错划程度。两个目标：1.间隔尽可能大2.错划程度尽可能小显然，当充分大时，样本点总可以满足以上约束条件。然而事实上应避免太大，所以需在目标函数对进行惩罚（即“软化”约束条件）2.近似线性可分问题因此，引入一个惩罚参数，新的目标函数变为:

体现了经验风险，而则体现了表达能力。所以惩罚参数实质上是对经验风险和表达能力匹配一个裁决。当时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。算法：(广义)线性支持向量分类机设已知训练集，其中2.选择适当的惩罚参数，构造并求解最优化问题3.计算，选择的一个分量，并据此计算出4.构造分划超平面,决策函数求得3.非线性分划例子:3.非线性分划设训练集，其中假定可以用平面上的二次曲线来分划：现考虑把2维空间映射到6维空间的变换上式可将2维空间上二次曲线映射为6维空间上的一个超平面：3.非线性分划可见，只要利用变换(2.3.4)，把所在的2维空间的两类输入点映射到所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：最后得出原空间中的二次曲线：怎样求6维空间中的分划超平面？(线性支持向量分类机)3.非线性分划需要求解的最优化问题其中3.非线性分划在求得最优化问题的解后，得到分划超平面其中最后得到决策函数或

线性分划－>非线性分划

代价：2维空间内积－>6维空间内积3.非线性分划为此，引进函数有比较(2.3.6)和(2.3.7)，可以发现这是一个重要的等式，提示6维空间中的内积可以通过计算中2维空间中的内积得到。实现非线性分划的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数，一旦选定了函数，就可以求解最优化问题得，而决策函数实现非线性分划的思想决策函数其中核函数(核或正定核)定义设是中的一个子集。称定义在