【转】干货 | 从超平面到SVM（一）

62 阅读 0 评论 41 点赞

我是靠谱客的博主矮小音响，最近开发中收集的这篇文章主要介绍【转】干货 | 从超平面到SVM（一），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

转自：http://www.sohu.com/a/206572358_160850（如有疑问，联系删除）

源| 小象文| 数据挖掘机

SVM（support vector machines，支持向量机）是机器学习算法里面非常重要的一个二分类模型，不过该模型也可以算是机器学习算法里面最基础、最难理解的一个算法，因为该算法涉及到大量的数学知识，包括线性代数、高等数学，所以本文将从最基本的知识讲起，逐步深入讲清楚SVM的原理。一、深入理解超平面

很多讲解支持向量机的文章从一开头就开始讲超平面及其方程，这样对多数没有基础的人来说较难理解，下面将从一维直线讲起，带你逐步过渡理解超平面。

例如，下面是一个只有x轴的一维坐标轴，该轴同样存在原点，x轴正方向和x轴反方向，且该轴上分布了很多点：

其中，红色的圆圈和绿色的菱形表示该坐标轴上的样本点，绿色的菱形坐标从左至右依次为：-5，-3，-1；红色的圈圈坐标从左到右依次为：2，3，5，6，7；此时，假如要求在坐标轴上找一个分割点，来分割红色的圆圈和绿色的菱形，如何去找呢？

显然的，仅仅靠眼睛就可以找到很多分割点，比如：-0.5，0，1，1.5等多个坐标点都可以把这些样本点分成两部分，一部分在左侧，一部分在右侧，不过，如果此时我只允许找一个点来分割这两部分样本，并且要求此点分割效果最好，如何去找呢？

那么此时，问题就变成了：“在坐标轴上找一个分割点，能划分两部分样本，并且要求此点分割效果最好”。对于这个问题，寻找分割点是很容易的，因为很多点都可以分割，但是如何去衡量该点就是最好的呢？从坐标轴上的点的分布可以看出，要分的绿色菱形和红色圆圈在菱形坐标=-1和圆圈坐标=2处就开始分开了，所以在闭区间(-1,2)直接任取一点都可以将这两部分样本分开，且只能取这里面的点，关于如何效果最好，可以类比修公路，即菱形代表村庄A，圆圈代表村庄B，我要在两个村庄之间修一条公路且不能干涉两村庄的生活（鸣笛噪音、路灯），我只需要在两个村庄之间最靠近的那两户人家的中间修公路就可以了（同样适用于下面讲的二维直角坐标系的情况），也就是坐标点为：(-1+2)/2=0.5处。

上面是一维坐标下的情况，此时，开始考虑二维直角坐标系下的如下情况：

已知有5个红色的正例样本点x，坐标分别为（0，1）、（0，2）、（1，1）、（1，2）、（2，2）；3个绿色的负例样本点o，坐标分别为（2，1）、（3，1）、（3，2）

其中，正例样本点可以记作其分类y=+1，负例样本点可以记作其分类y=-1，这样，在坐标系x2-x1中就可以认为有两类样本，一类是正例，用x表示，一类是负例，用o表示，每个样本点的坐标都可以用(x1,x2)来表示，这里的(x1,x2)可以类比平面直角坐标系中的(x,y)，只是将y换成了x2，这样通过x1、x2后面的数字就可以判断该样本是几维的，并且这样，每个样本点都可以用一个唯一的坐标来表示，也可以认为这是一个向量，另外，需要注意的是，样本点的坐标可以认为是机器学习里面的各个特征，即样本点(x1,x2)表示的是特征x1，x2，它对应的分类就是这个坐标的正反例，红色的x表示正例，绿色的o表示反例，如样本点(1,1)，如果要整理成训练数据里面的一条样本的话，就是：

x1， x2， y = 1，1，+1

明白了上面约定的一些符号后，就可以引出主要的话题了，现在要在两类样本点之间找一条直线来将两类样本点分开，并且和前面那个问题一样，要求划分效果最好，如何做呢？

如上图，这两类样本之间存在多条直线可以划分，对于此问题，可以借鉴前面讲到的村庄修公路，只需要找到两个村庄里面离得最近的两户人家，修的公路离这两户人家同时最远即在中间修即可，不过，此处变成了二维空间，要想找到最近的那两户人家不再那么简单了，此时可以转化成数学问题，即把寻找这两户人家的过程转化为求两点之间的距离即可，所以根据两点距离公式：

|AF|2=9、|BF|2=4、|CF|2=1、|DF|2=10、|EF|2=5、|AG|2=5、|BG|2=2、|CG|2=1、|DG|2=4、|EG|2=1、|AH|2=10、|BH|2=5、|CH|2=2、|DH|2=9、|EH|2=4

从上面的距离计算可以看出，已经用距离的平方代替了距离，经过计算得到了三对距离CF、CG、EG，那么此问题就转化为了在四个点C、E、F、G中找一条直线将两类样本效果最好的分开。这个问题和前面的修公路一样，只需在三对距离之间找到一个中点就好了，所以可以连线CF、CG、EG，找到它们的中点，然后连线，正好三点共线得到直线y=x-0.5，此问题解决。

不过，这是眼睛看到后利用几何知识得到的结果，如果是三维、四维甚至更高维度如何去找这条直线（高维称之为超平面）呢？那么此时要把该问题转化为纯数学计算问题，根据上面讲的，该问题可以分两步进行解决：

（1）找到两类样本之间最近的那一部分样本点（这部分上面已经解决，用距离公式即可，高维空间同样适用）

（2）找到一条直线（高维空间称之为超平面）使得（1）中最近的那些样本点到此直线（或超平面）的距离相等且尽量最大，此处可以用“点到直线的距离”来解决，并且由于要把两类样本分开，所以必然一部分样本点在直线上方，一部分在直线下方，根据直线的规律可知（斜率大于0），若(x0,y0)在直线上方，则满足Ax0+By0+C>0，若（x0,y0）在直线下方，则满足Ax0+By0+C<0。

好了，此时上面的问题，已经转化为一个纯数学问题了，那么就按照上面两个步骤来求这条直线的具体方程：

（1）点已经求得了，分别是C(2,2)，E(1,1)，F(3,2)，G(2,1)

（2）假设该方程为Ax+By+C=0，则根据公式联立方程：

由于A、B均不为0，所以可以赋值A=1，则得到B=-1、C=-0.5，最终求得直线x-y-0.5=0，即上面得到的直线y=x-0.5。

好了，通过上面的过渡，从一维到二维已经理解了如何划分样本点了，但是在实际问题中，导致一个事件发的的因素不会是单一因素或简单的两个因素（一个因素对应一个维度或一个特征），对于多个特征的情况，其在数学上的表示就不再是二维直角坐标系可以表达的了，有可能是三维坐标系、四维坐标系甚至更高维度坐标系，此时划分样本的不再是一维里面的一个点，二维里面的一条直线，有可能是三维里面的一个平面，四维里面的一个超平面（四维空间里面的平面很难想象，可以认为是一个超平面），那么此时可以把之前讲的二维方程过渡到更高维度：

因为二维空间里面，一条直线的方程可以表示为：

Ax+By+C=0

三维空间里面，平面的方程可以表示为：

Ax+By+Cz+D=0

依次推广，n维空间的超平面方程可以表示为：

Ax1+Bx2+Cx3+Dx4+Ex5+Fx6+....+K=0

因为n维空间对应的是n维坐标系，仅仅用x、y、z几个字母较难表示，所以此处用x1、x2、x3、...、xn来表示n维坐标系，各个维度的系数此处也可以用w1、w2、w3、...、wn来表示，所以n维空间里面的超平面方程可以写成如下形式：

w1x1+w2x2+w3x3+w4x4+...+wnxn+b=0

x相乘可以看作是内积的相乘：

可以将x看作w，y看作x则上面超平面方程就变成了：

[w,x]+b = 0 ，即wTx+b=0

所以，样本空间中，任何一个超平面都可以用方程如下方程表示：

WTX+b=0

其中，W=(w1,w2,w3,...,wn)为法向量，b为位移项可以认为是截距，该超平面可以唯一的由此方程决定。

可能，此处有人会不理解，为何该方程的法向量正好是该平面方程的变量系数呢？此处可以参考高数平面方程那一节，解释如下：

二、函数间隔最大化

接着，理解了超平面的方程后，类似于前面所讲的分类方法，还需要找到两类样本点之间离得最近的那一部分点（称之为支持向量），并将问题同样转化为找到中间一个超平面将这部分样本点划分开，此时又涉及到这些样本点到超平面的距离（即支持向量到超平面的距离），关于样本点到超平面的距离，可以如下去通俗的理解：

假设给定一个训练数据集T，x表示特征组成的向量，y表示分类结果，T={(x1,y1),(x2,y2),(x3,y3),...,(xN,yN)}，其中，xi∈X=Rn，yi∈Y={+1，-1}，i=1，2，3，...，N，xi表示第i个特征向量，yi数为该特征向量的类别标记，yi=-1表示负例，yi=+1表示正例，Rn中的n可以认为是n维空间，类似于直角坐标系里面的n=2，R表示该空间里面的向量取值是全体实数，并且假设该数据集线性可分。

可以如下定义：

定义：（线性可分支持向量机）给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题得到的分离超平面为

wTx+b=0

最大，相应的分类决策函数为：f(x)=sign(wTx+b)，称为线性可分支持向量机。

正如前面二维坐标系里面讲的，在直线上方的样本点带入超平面方程后使得wTx+b>0，在超平面下方的样本点带入后使得wTx+b<0，并且假设超平面已经得到了，则w值就是定值，即||w||也是定的，假设某个样本点为(x0,y0)根据点到平面距离公式可知|wTx0+b|/||w||在||w||定的情况下，|wTx0+b|越大，则点到超平面的距离就越大，所以|wTx0+b|可以近似代替样本点到超平面的距离，并且由于默认分类正确的话wTx0+b正好与y0同号，所以又可以用y0(wTx0+b)来表示分类正确，结合二者，y0(wTx0+b)可以同时表示分类正确和样本点到超平面的距离。

为了计算所有样本点到该超平面的距离并且找到最近的样本点，可以定义如下函数间隔：

函数间隔：对于给定的训练数据集T和超平面(w,b)，可以定义超平面(w,b)与样本点(xi,yi)的函数间隔为：

ri=yi(wTxi+b)

为了找到最小的那几个样本点（即支持向量），于是可以求出所有样本点距离里面最小的那个：

rmin=min(ri)

不过上面函数间隔存在一个问题就是，假如w和b同时成比例变化，超平面方程没有变化，但是函数间隔会变成原来的同比例倍数，为了解决这个问题，又引入了几何间隔，即

ri=yi((wT/||w||)xi+b/||w||)

这样就保证了，如果w和b成比例变化超平面也会变化。

讲到这里，后面的步骤就和前面说的寻找最好分割直线一样了，如果可以找到一个超平面，使得最近的支持向量离此超平面的距离尽量大，类似于公路离最近的那几个住户尽量远就可以了，所以问题可以由下面的数学公式来代替，此处将wT换成了w，后面不再严格区分二者，默认是行向量即可：

上面的公式已经把该问题完全转化为了一个数学问题，公式第一部分很容易看懂，第二部分和第三部分可以这样理解：

因为函数间隔和几何间隔的关系为几何间隔r：r=r·/||w||，即将该距离带入第一部分就可以得到第二部分，而第三部分可以如下理解：

假设w=w0r，b=b0r，则推导以后r可以被消掉，即在优化过程中r的大小对优化并不产生影响，此时可以认为w0和b0就是需要求的，并且认为就是w和b，所以最终该问题就转化成了上面的数学最优化问题。