">

一步步教你轻松学支持向量机SVM算法之理论篇1

摘要:支持向量机即SVM(Support Vector Machine) ,是一种监督学习算法,属于分类的范畴。首先,支持向量机不是一种机器,而是一种机器学习算法。在数据挖掘的应用中,与无监督学习的聚类相对应和区别。广泛应用于机器学习,计算机视觉和数据挖掘当中。(本文原创,转载必须注明出处.)

相关概念

  • 支持向量就是数据集中的某些点,位置比较特殊。比如 x+y-2=0 这条直线,直线上面区域 x+y-2>0 的全是 A 类,下面的 x+y-2<0 的全是 B 类,我们找这条直线的时候,一般就看聚集在一起的两类数据,他们各自的最边缘 位置的点,也就是最靠近划分直线的那几个点,而其他点对这条直线的最终位置的确定起不了作用,所以我姑且叫这些点叫 “支持点”(意思就是有用的点).
  • 在最大间隔上的这些点就叫 “支持向量”,因为最后的 classification machine (分类器)的表达式里只含有这些 “支持向量” 的信息,而与其他数据点无关,借助图形理解(支持向量就是图中用紫色框框圈出来的点)如下:

  • 线性可分(linearly separable): 如上图中的两组数据,它们之间已经分的足够开了,因此很容易就可以在图中画出一条直线将两组数据点分开。在这种情况下,这组数据就被称为线性可分数据
  • 分隔超平面(separating hyperplane): 上述将数据集分隔开来的直线称为分隔超平面
  • 超平面(hyperplane): 在上面给出的例子中,由于数据点都在二维平面上,所以此时分隔超平面就只是一条直线。但是,如果所给的数据集是三维的,那么此时用来分隔数据的就是一个平面。显而易见,更高纬度的情况可以依此类推。如果数据是 1024 维的,那么就需要一个 1023 维的某某对象来对数据进行分隔。这个 1023 维的某某对象到底应该叫什么呢? N-1 维呢?该对象被称为超平面,也就是分类的决策边界。分布在超平面一侧的所有数据都属于某个类别,而分布在另一侧的所有数据则属于另一个类别。
  • 间隔(margin): 我们希望能通过上述的方式来构建分类器,即如果数据点离决策边界越远,那么其最后的预测结果也就越可信。既然这样,我们希望找到离分隔超平面最近的点,确保它们离分隔面的距离尽可能远。这里所说的点到分隔面的距离就是间隔。我们希望间隔尽可能地大,这是因为如果我们犯错或者在有限数据上训练分类器的话,我们希望分类器尽可能健壮。
  • 支持向量(support vector) : 就是上面所说的离分隔超平面最近的那些点。
  • 分类器 : 分类器就是给定一个样本的数据,判定这个样本属于哪个类别的算法。例如在股票涨跌预测中,我们认为前一天的交易量和收盘价对于第二天的涨跌是有影响的,那么分类器就是通过样本的交易量和收盘价预测第二天的涨跌情况的算法。
  • 特征 : 在分类问题中,输入到分类器中的数据叫做特征。以上面的股票涨跌预测问题为例,特征就是前一天的交易量和收盘价。
  • 线性分类器 : 线性分类器是分类器中的一种,就是判定分类结果的根据是通过特征的线性组合得到的,不能通过特征的非线性运算结果作为判定根据。还以上面的股票涨跌预测问题为例,判断的依据只能是前一天的交易量和收盘价的线性组合,不能将交易量和收盘价进行开方,平方等运算。

SVM 原理

直观理解

我们在桌子上放置一些不同颜色的球,让小明用一根棍分开它们?要求:尽量在放更多球之后,仍然适用。

于是小明这样放,看起来还不错?

然后我们又在桌上放了更多的球,似乎有一个球站错了阵营。

SVM 就是试图把棍放在最佳位置,好让在棍的两边有尽可能大的间隙。

现在即使我们放了更多的球,棍仍然是一个好的分界线。

然后,在 SVM 工具箱中有另一个更加重要的 trick。 我们看到小明已经学会了一个 trick ,于是我们给了小明一个新的挑战。

现在,小明没有棍可以很好帮他分开两种球了,现在怎么办呢?当然像所有武侠片中一样大侠桌子一拍,球飞到空中。然后,凭借大侠的轻功,大侠抓起一张纸,插到了两种球的中间。

现在,从我们的角度看这些球,这些球看起来像是被一条曲线分开了。

我们把这些球叫做 「data」,把棍子叫做「classifier」, 最大间隙 trick 叫做「optimization」, 拍桌子叫做「kernelling」, 那张纸叫做「hyperplane」 。到这里,大家对支持向量机有个更加直观的感受了吧,以上引用网络案例。

支持向量机分类

先考虑最简单的情况,豌豆和米粒,用晒子很快可以分开,小颗粒漏下去,大颗粒保留。用一个函数来表示就是当直径 d 大于某个值 D ,就判定为豌豆,小于某个值就是米粒。

  • d>D, 豌豆
  • d<D,米粒

在数轴上就是在d左边就是米粒,右边就是绿豆,这是一维的情况。但是实际问题没这么简单,考虑的问题不单单是尺寸,一个花的两个品种,怎么分类?
假设决定他们分类的有两个属性,花瓣尺寸和颜色。单独用一个属性来分类,像刚才分米粒那样,就不行了。这个时候我们设置两个值 尺寸 x 和颜色 y.我们把所有的数据都丢到 x-y 平面上作为点,按道理如果只有这两个属性决定了两个品种,数据肯定会按两类聚集在这个二维平面上。我们只要找到一条直线,把这两类划分开来,分类就很容易了,以后遇到一个数据,就丢进这个平面,看在直线的哪一边,就是哪一类。比如 x+y-2=0 这条直线,我们把数据 (x,y) 代入,只要认为 x+y-2>0 的就是 A 类, x+y-2<0 的就是 B 类。以此类推,还有三维的,四维的,N维的 属性的分类,这样构造的也许就不是直线,而是平面,超平面。
一个三维的函数分类 :x+y+z-2=0,这就是个分类的平面了。有时候,分类的那条线不一定是直线,还有可能是曲线,我们通过某些函数来转换,就可以转化成刚才的哪种多维的分类问题,这个就是核函数的思想。例如:分类的函数是个圆形 x^2+y^2-4=0 。这个时候令 x^2=a ; y^2=b ,还不就变成了a+b-4=0 这种直线问题了。这就是支持向量机的思想。

SVM 工作原理

原理

对于上述的苹果和香蕉,我们想象为2种水果类型的炸弹。(保证距离最近的炸弹,距离它们最远)

  1. 寻找最大分类间距
  2. 转而通过拉格朗日函数求优化的问题
  • 数据可以通过画一条直线就可以将它们完全分开,这组数据叫线性可分(linearly separable)数据,而这条分隔直线称为分隔超平面(separating hyperplane)
  • 如果数据集上升到1024维呢?那么需要1023维来分隔数据集,也就说需要N-1维的对象来分隔,这个对象叫做超平面(hyperlane),也就是分类的决策边界。

SVM学习方法的选择

  • 当训练数据线性可分时,通过硬间隔最大化学习一个线性分类器,即线性可分支持向量机又称为硬间隔支持向量机
  • 当训练数据近似线性可分时,通过软间隔最大化学习一个线性分类器,即线性可分支持向量机又称为软间隔支持向量机
  • 当训练数据线性不可分时,通过核函数及软间隔最大化学习一个非线性支持向量机

更多内容参考如下资料:

https://www.zhihu.com/question/21094489
http://docs.opencv.org/2.4/doc/tutorials/ml/introduction_to_svm/introduction_to_svm.html
https://zhuanlan.zhihu.com/p/26891427?utm_medium=social&utm_source=qq
https://zhuanlan.zhihu.com/p/21308801?utm_medium=social&utm_source=qq
http://blog.csdn.net/v_july_v/article/details/7624837

理解和应用

数据挖掘(DataMining)

做数据挖掘应用的一种重要算法,也是效果最好的分类算法之一。举个例子,就是尽量把样本中的从更高纬度看起来在一起的样本合在一起,比如在一维(直线)空间里的样本从二维平面上可以分成不同类别,而在二维平面上分散的样本如果从第三维空间上来看就可以对他们做分类。支持向量机算法目的是找出最优超平面,使分类间隔最大,要求不但正确分开,而且使分类间隔最大,在两类样本中离分类平面最近且位于平行于最优超平面的超平面上的点就是支持向量,为找到最优超平面只要找到所有支持向量即可。对于非线性支持向量机,通常做法是把线性不可分转化成线性可分,通过一个非线性映射将输入到低维空间中的数据特性映射到高维线性特征空间中,在高维空间中求线性最优分类超平面。

scikit(scikit-learn)

SVM 的基本原理基本上已经说的差不多了,下面咱们就来看看 SVM 在实际应用该如何使用了。幸运的是,sklearn 提供了一个非常好用的机器学习算法,我们调用相关的包就好啦。

参考文献

  1. scikit中文社区:http://sklearn.apachecn.org/cn/0.19.0/
  2. ApacheCN
  3. GitHub:https://github.com/BaiNingchao/MachineLearning-1
  4. 图书:《机器学习实战》
  5. 图书:《自然语言处理理论与实战》

完整代码下载

源码请进【机器学习和自然语言QQ群:436303759】文件下载:自然语言处理和机器学习技术QQ交流

作者声明

本文版权归作者所有,旨在技术交流使用。未经作者同意禁止转载,转载后需在文章页面明显位置给出原文连接,否则相关责任自行承担。

白宁超 wechat
扫一扫关注微信公众号,机器学习和自然语言处理,订阅号datathinks!