【十大经典数据挖掘算法】SVM

浏览: 1064

作者简介:

Treant  人工智能爱好者社区专栏作者

博客专栏:https://www.cnblogs.com/en-heng


SVM(Support Vector Machines)是分类算法中应用广泛、效果不错的一类。《统计学习方法》对SVM的数学原理做了详细推导与论述,本文仅做整理。由简至繁SVM可分类为三类:线性可分(linear SVM in linearly separable case)的线性SVM、线性不可分的线性SVM、非线性(nonlinear)SVM。

1.线性可分

对于二类分类问题,训练集,其类别,线性SVM通过学习得到分离超平面(hyperplane):

以及相应的分类决策函数:

有如下图所示的分离超平面,哪一个超平面的分类效果更好呢?

直观上,超平面的分类效果更好一些。将距离分离超平面最近的两个不同类别的样本点称为支持向量(support vector)的,构成了两条平行于分离超平面的长带,二者之间的距离称之为margin。显然,margin更大,则分类正确的确信度更高(与超平面的距离表示分类的确信度,距离越远则分类正确的确信度越高)。通过计算容易得到:

从上图中可观察到:margin以外的样本点对于确定分离超平面没有贡献,换句话说,SVM是有很重要的训练样本(支持向量)所确定的。至此,SVM分类问题可描述为在全部分类正确的情况下,最大化(等价于最小化);线性分类的约束最优化问题

对每一个不等式约束引进拉格朗日乘子(Lagrange multiplier)构造拉格朗日函数(Lagrange function):

根据拉格朗日对偶性,原始的约束最优化问题可等价于极大极小的对偶问题:

求偏导并令其等于0,则

将上述式子代入拉格朗日函数(3)中,对偶问题转为

等价于最优化问

线性可分是理想情形,大多数情况下,由于噪声或特异点等各种原因,训练样本是线性不可分的。因此,需要更一般化的学习算法。

2.线性不可分

线性不可分意味着有样本点不满足约束条件(2),为了解决这个问题,对每个样本引入一个松弛变量这样约束条件变为:


目标函数则变为

其中,为惩罚函数,目标函数有两层含义:

  • margin尽量大,

  • 误分类的样本点计量少

为调节二者的参数。通过构造拉格朗日函数并求解偏导(具体推导略去),可得到等价的对偶问题:

与上一节中线性可分的对偶问题相比,只是约束条件发生变化,问题求解思路与之类似。

3.非线性

对于非线性问题,线性SVM不再适用了,需要非线性SVM来解决了。解决非线性分类问题的思路,通过空间变换ϕ(一般是低维空间映射到高维空间后实现线性可分,在下图所示的例子中,通过空间变换,将左图中的椭圆分离面变换成了右图中直线。

在SVM的等价对偶问题中的目标函数中有样本点的内积在空间变换后则是由于维数增加导致内积计算成本增加,这时核函数(kernel function)便派上用场了,将映射后的高维空间内积转换成低维空间的函数:

将其代入一般化的SVM学习算法的目标函数(7)中,可得非线性SVM的最优化问题:

4.参考资料

[1] 李航,《统计学习方法》.

[2] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining.


往期回顾:

【十大经典数据挖掘算法】C4.5

【十大经典数据挖掘算法】k-means

公众号后台回复关键词学习

回复 免费                获取免费课程

回复 直播                获取系列直播课

回复 Python           1小时破冰入门Python

回复 人工智能         从零入门人工智能

回复 深度学习         手把手教你用Python深度学习

回复 机器学习         小白学数据挖掘与机器学习

回复 贝叶斯算法      贝叶斯与新闻分类实战

回复 数据分析师      数据分析师八大能力培养

回复 自然语言处理  自然语言处理之AI深度学习

推荐 0
本文由 人工智能爱好者社区 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册