支持向量机-算法概述
我的微信公众号: s406205391; 欢迎大家一起学习,一起进步!!!
有些人认为,支持向量机(SVM)是最好的现成的分类器,这里说的“现成”指的是分类器不加修改即可直接使用。同时,这就意味着在数据上应用基本形式的SVM分类器就可以得到低错误率的结果。SVM能够对训练集之外的数据点做出很好的分类决策。
距离的定义:基于最大间隔分隔数据
假设在一个平面上有如下两组数据,我们可以用如下一条直线将两组数据分隔开(我们将上述可以把数据集分隔开的直线称为分隔超平面)。图左和图右两条直线均可有效的将数据分隔开。那么,哪一条直线的分隔效果更好呢?很明显图右的直线分隔效果更好,因为它距离两组数据的距离相对于图左直线更远。支持向量就是离分隔超平面最近的那些点。
image 那么,我们在设计分类器之前,就先得学会如何计算支持向量到分隔超平面之间的距离。假设由图点x是分隔超平面的支持向量,w是超平面上的法向量,w'和w''是超平面上的两个点。我们定义超平面方程为wTx+b=0。那么我们可以得到两个等式:
-
w'和w''在超平面上:wTx' = -b; WTx'' = -b
-
法向量与w'和w''的向量垂直:
我们要求点到直线的距离,其实也就是求向量(x - x’)与法向量w的单位向量的投影(內积)。那么公式即为: 因为w'是随机找的一个点,因此必然可以约分,将w'约分完之后,即可得到最终的表达式。
优化目标: 找到一条线(w和b),是的离该线最近的点能够最远
有了距离公式,那么也有了我们机器学习的优化方向:让支持向量与超平面的距离最远。在做SVM机器学习的时候,我们首先需要定义标签,即将我们的训练数据进行分类。在这里,为了后期计算方便,我们将数据分类两类,分别用1和-1表示。那么就有了如下的决策方程:
这里的φ(x)我们可以先暂时理解为x
将距离公式带入到决策方程,可得: (由于, 所有将绝对值展开,公式依旧成立。)
对于该决策方程,我们设计优化目标,找到一条离支持向量的点最远的直线,优化目标如下:
目标函数:
求解目标函数
上述的目标函数看起来很复杂,通俗的将,大括号内的意思即为,找到在整个样本中,距离决策边界距离最小的样本。大括号外面即,找到与这些这些样本距离最大的线。
放缩变换
对于决策方程,不太好求解,我们这里可以做一下变换。我们通过放缩变换使得:对于决策方程(w,b),其结果 (之前我们认为恒大于0,现在更严格了一些)
由于 , 那么,其最小值就为1,那么,我们只需要考虑。
当前目标:,约束条件:
函数变换
对于上述目标函数,我们适当转换一下,方便求解。我们可以将上述函数的求最大值问题,改为求极小值问题:
转换函数
转换思路为:先将转换成其倒数,再取其平方,再添加一个常规项1/2。虽然做了如下操作之后,最后得到的点的值会发生变换,但是,取到的点是不变的。
对于这个函数,我们可以用拉格朗日乘子法求解。
求解拉格朗日乘子法
拉格朗日乘子法是专门用来求解带约束条件的问题的。他的基本公式为:
把我们的方程代入,即得:
约束条件:
上式有三个未知量,w, α,b。如果我们能求得这三个变量之间的关系,即可得到方程的解。我们分别对w和b求偏导,得:
对w求偏导:
对b求偏导:
我们带入原式即得:
其中:;
完成了第一步求解minL(w,b,α)
求解该式的极值
继续求解
我们需要求解上式的极大值,添加一个符号,我们转换为求解该式的极小值。
即: ; 条件:
实例求解
我们现在以一个实例,求解上述方程。
image 我们将上面数据代入即可得:
image
对α1和α2求偏导即可得: ;
这里,α2小于0,不满足约束条件,所以应该在边界上。此时α1=0或者α2=0.
image将α结果代入求解:; 平面方程为:
软间隔问题
在这里插入图片描述核函数
核函数即为了解决低维不可分问题,通过核函数将我们的数据转换到高维的层面,这里就不多介绍了。我们最常用的一个核函数即为高斯核函数。