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 这种直线问题了。
这就是支持向量机的思想。
### 3、引用 [@胡KF](https://www.zhihu.com/people/hu-kf/answers) 大佬的回答(这个需要一些数学知识):
如图的例子,(训练集)红色点是我们已知的分类1,(训练集)蓝色点是已知的分类2,我们想寻找一个分隔超平面(图中绿线)(因为示例是二维数据点,所以只是一条线,如果数据是三维的就是平面,如果是三维以上就是超平面)把这两类完全分开,这样的话再来一个样本点需要我们预测的话,我们就可以根据这个分界超平面预测出分类结果。
![hu_1](img/hu_1.jpg "hu_1")
那我们如何选择这个分类超平面呢?从数学上说,超平面的公式是,也就是说如何选取这个 ![w](img/w.png "w")(是个向量)。
传统方法是根据最小二乘错误法(least squared error),首先随便定选取一个随机平面,也就是随机选取 ![w](img/w.png "w") 和 ![b](img/b.png "b"),然后想必会在训练集中产生大量的错误分类,也就是说,![wtx+b](img/hu_5.png "wtx+b") 结果应该大于 0 的时候小于 0 ,应该小于 0 的时候大于 0 。这时候有一个错误损失,也就是说对于所有错误的分类,他们的平方和(least squared error) 为: ![平方和](img/hu_8.png "平方和") , 最小二乘法的目标就是让这个值趋于最小,对 ![w](img/w.png "w") 求导取 0 ,采用梯度下降算法,可以求出错误平方和的极值,求出最优的 ![w](img/w.png "w") ,也就是求出最优的超平面。(可以证明,如果基函数是指数族函数,求出的超平面是全局最优的)。
那我们 SVM 算法的思路是怎样的呢?
不同于传统的最小二乘策略的思想,我们采用一种新的思路,这个分界面有什么样的特征呢?
第一,它 “夹” 在两类样本点之间;第二,它离两类样本点中所有 “离它最近的点” ,都离它尽可能的远。如图所示:
![hu_2](img/hu_2.jpg "hu_2")
在虚线上的点,就是我们所找到的离分解超平面最近的样本点,X 类中找到了一个,O 类找到了两个。我们需要分类超平面离这三个样本点都尽可能的远,也就是说,它处在两条虚线的中间。这就是我们找到的分界超平面。
另外,这里我们就可以解释什么是 “支持向量” 了,支持向量就是虚线上的离分类超平面最近的样本点,因为每一个样本点都是一个多维的向量,向量的每一个维度都是这个样本点的一个特征。比如在根据身高,体重,特征进行男女分类的时候,每一个人是一个向量,向量有两个维度,第一维是身高,第二维是体重。
介绍完 SVM 的基本思想,我们来探讨一下如何用数学的方法进行 SVM 分类。
首先我们需要把刚刚说的最大间隔分类器的思想用数学公式表达出来。先定义几何间隔的概念,几何间隔就是在多维空间中一个多维点到一个超平面的距离,根据向量的知识可以算出来:
![hu_3](img/hu_3.png "hu_3")
然后对于所有的支持向量,使他们到超平面 ![hu_5](img/hu_5.png "hu_5") 的距离最大,也就是
![hu_4](img/hu_4.png "hu_4")
因为对于所有支持向量,他们 ![hu_5](img/hu_5.png "hu_5") 的值都是一定的,我们假设恒等于 1 ,那么上式变成了 ![hu_6](img/hu_6.png "hu_6") ,并且对于所有的样本点,满足 ![hu_10](img/hu_10.png "hu_10") 的约束,因此,可以利用拉格朗日乘数法计算出它的极值。也就是求出这个超平面。
推导过程略为复杂,详细了解可以参考凸二次规划知识,结合 SMO 算法理解 SVM 计算超平面的详细过程。
总之,在计算的过程中,我们不需要了解支持向量以外的其他样本点,只需要利用相对于所有样本点来说为数不多的支持向量,就可以求出分类超平面,计算复杂度大为降低。
### 4、引用知乎 [@靠靠靠谱](https://www.zhihu.com/people/kao-kao-kao-pu/answers) 大佬的理解(这个需要的数学知识更加厉害一点):
先看思维导图:
* 左边是求解基本的SVM问题
* 右边是相关扩展
![k_1](img/k_1.jpg "k_1")
什么是 SVM ?
Support Vector Machine, 一个普通的 SVM 就是一条直线罢了,用来完美划分 linearly separable 的两类。但这又不是一条普通的直线,这是无数条可以分类的直线当中最完美的,因为它恰好在两个类的中间,距离两个类的点都一样远。而所谓的 Support vector 就是这些离分界线最近的『点』。如果去掉这些点,直线多半是要改变位置的。可以说是这些 vectors (主,点点) support (谓,定义)了 machine (宾,分类器)...
![k_2](img/k_2.jpg "k_2")
所以谜底就在谜面上啊朋友们,只要找到了这些最靠近的点不就找到了 SVM 了嘛。
如果是高维的点,SVM 的分界线就是平面或者超平面。其实没有差,都是一刀切两块,我就统统叫直线了。
怎么求解 SVM ?
关于这条直线,我们知道
(1)它离两边一样远,(2)最近距离就是到support vector的距离,其他距离只能更远。
于是自然而然可以得到重要表达 I. direct representation
![k_7](img/k_7.png "k_7")
(可以把 margin 看作是 boundary 的函数,并且想要找到使得是使得 margin 最大化的boundary,而 margin(*) 这个函数是: 输入一个 boundary ,计算(正确分类的)所有苹果和香蕉中,到 boundary 的最小距离。)
又有最大又有最小看起来好矛盾。实际上『最大』是对这个整体使用不同 boundary 层面的最大,『最小』是在比较『点』的层面上的最小。外层在比较 boundary 找最大的 margin ,内层在比较点点找最小的距离。
其中距离,说白了就是点到直线的距离;只要定义带正负号的距离,是 {苹果+1} 面为正 {香蕉-1} 面为负的距离,互相乘上各自的 label ![k_8](img/k_8.png "k_8") ,就和谐统一民主富强了。
![k_9](img/k_9.png "k_9")
到这里为止已经说完了所有关于SVM的直观了解,如果不想看求解,可以跳过下面一大段直接到 objective function 。
直接表达虽然清楚但是求解无从下手。做一些简单地等价变换(分母倒上来)可以得到 II. canonical representation (敲黑板)
![k_10](img/k_10.png "k_10")
要得到 III. dual representation 之前需要大概知道一下拉格朗日乘子法 (method of lagrange multiplier),它是用在有各种约束条件(各种 "subject to" )下的目标函数,也就是直接可以求导可以引出 dual representation(怎么还没完摔)
![k_11](img/k_11.png "k_11")
稍微借用刚刚数学表达里面的内容看个有趣的东西:
还记得我们怎么预测一个新的水果是苹果还是香蕉吗?我们代入到分界的直线里,然后通过符号来判断。
刚刚w已经被表达出来了也就是说这个直线现在变成了: ![k_12](img/k_12.png "k_12")
看似仿佛用到了所有的训练水果,但是其中 ![k_13](img/k_13.png "k_13") 的水果都没有起到作用,剩下的就是小部分靠边边的 Support vectors 呀。
III. dual representation
![k_14](img/k_14.png "k_14")
如果香蕉和苹果不能用直线分割呢?
![k_3](img/k_3.jpg "k_3")
Kernel trick.
其实用直线分割的时候我们已经使用了 kernel ,那就是线性 kernel , ![k_15](img/k_15.png "k_15")
如果要替换 kernel 那么把目标函数里面的内积全部替换成新的 kernel function 就好了,就是这么简单。
第一个武侠大师的比喻已经说得很直观了,低维非线性的分界线其实在高维是可以线性分割的,可以理解为——『你们是虫子!』分得开个p...(大雾)
如果香蕉和苹果有交集呢?
![k_4](img/k_4.jpg "k_4")
![k_16](img/k_16.png "k_16")
如果还有梨呢?
![k_5](img/k_5.jpg "k_5")
可以每个类别做一次 SVM: 是苹果还是不是苹果?是香蕉还是不是香蕉?是梨子还是不是梨子?从中选出可能性最大的。这是 one-versus-the-rest approach。
也可以两两做一次 SVM: 是苹果还是香蕉?是香蕉还是梨子?是梨子还是苹果?最后三个分类器投票决定。这是 one-versus-one approace。
但这其实都多多少少有问题,比如苹果特别多,香蕉特别少,我就无脑判断为苹果也不会错太多;多个分类器要放到一个台面上,万一他们的 scale 没有在一个台面上也未可知。
课后题:
1、vector 不愿意 support 怎么办?
2、苹果好吃还是香蕉好吃?
最后送一张图我好爱哈哈哈 (Credit: Burr Settles)
![k_6](img/k_6.png "k_6")
[1] Bishop C M. Pattern recognition[J]. Machine Learning, 2006, 128.
[2] Friedman J, Hastie T, Tibshirani R. The elements of statistical learning[M]. Springer, Berlin: Springer series in statistics, 2001.
[3] James G, Witten D, Hastie T, et al. An introduction to statistical learning[M]. New York: springer, 2013.
## 理解和应用
### 1、DataMining (数据挖掘)
做数据挖掘应用的一种重要算法,也是效果最好的分类算法之一。
举个例子,就是尽量把样本中的从更高纬度看起来在一起的样本合在一起,比如在一维(直线)空间里的样本从二维平面上可以分成不同类别,而在二维平面上分散的样本如果从第三维空间上来看就可以对他们做分类。
支持向量机算法目的是找出最优超平面,使分类间隔最大,要求不但正确分开,而且使分类间隔最大,在两类样本中离分类平面最近且位于平行于最优超平面的超平面上的点就是支持向量,为找到最优超平面只要找到所有支持向量即可。
对于非线性支持向量机,通常做法是把线性不可分转化成线性可分,通过一个非线性映射将输入到低维空间中的数据特性映射到高维线性特征空间中,在高维空间中求线性最优分类超平面。
### 2、scikit-learn (sklearn)
SVM 的基本原理基本上已经说的差不多了,下面咱们就来看看 SVM 在实际应用该如何使用了。幸运的是,在 python 下面,sklearn 提供了一个非常好用的机器学习算法,我们调用相关的包就好啦。
![sklearn_map](img/ml_map.png "sklearn")
## 小结
学习 SVM 需要有耐心,当初研究这个部分的时候,炼哥(github [jiangzhonglian](https://github.com/jiangzhonglian)),法超大佬(github [geekidentity](https://github.com/geekidentity)),羊三大佬(github [sheepmen](https://github.com/sheepmen)),庭哥(github [wangyangting](https://github.com/wangyangting))都花费了好长时间,我只能躲在角落发抖....