支持向量机算法理解_大数据中支持向量机算法的理解

        支持向量机（Support Vector Machines，SVM），在很多地方见过，如强化学习、入侵检测中，作为机器学习的一种据说很好算法，今天开始了解一下，还不够深入，等待更新。

一、分隔超平面

假设有两类线性可分的样本，分隔超平面就是将两类样本进行分隔。在二维平面上，分隔超平面是一条一维（一元）直线f(x)=ax+b；在三维空间里，分隔超平面是一个二维（二元）平面f(x,y)=ax+by+c；更高维的空间依次类推，N维空间的分隔超平面是N-1维。几维空间主要看有几个自变量。例如一维空间，只有一个坐标轴，其分隔超平面是x=b，没有自变量，可以认为是0维。

二、间隔

样本（二维平面上的点）到分隔超平面的距离称为间隔。有时候，间隔更多的指数据集中所有点到分隔超平面最小间隔的2倍，成为分类器或数据集的间隔。

三、支持向量

离分隔超平面最近的那些点称为支持向量。

四、支持向量机目的

“机”的意思是算法。算法的目的是最大化支持向量到分隔超平面的距离，即最大化最近点的间隔。理想情况下，分隔超平面将两类完全分开，这样所有样本点都离分隔超平面很远，分类更准确。

五、法线和距离长度

分隔超平面可通过如下线性方程来表示：

       

分隔超平面的法向量为w，证明：

 

点A到分隔超平面的距离为：

    

证明：

    

关于超平面的证明参考其他博客学习：

S是超平面，w是法向量，任何+号类的样本在法向量的投影到原点距离ot1都大于任何-号样本在法向量的投影到原点的距离ot2，即：

ot1>ot2，以此作为分类的依据。

首先看距离ot2怎么求。(以下加粗字体为向量)

cosθ=ox2.w/|ox2||w|

|ot2|=|ox2|cosθ=|ox2| ox2.w/|ox2||w|= ox2.w   (w为单位法向量时模为1)

同理|ot1|= ox1.w，即超平面的w.x。再用一个常数b将两类数据分开，即

w.x+b>0是正分类，w.x+b<0是负分类，w.x+b=0即分隔超平面。

六、分类器 

可以使用类似单位阶跃函数直接分类，即：

>0时，f()=1，<0时，f()=-1,这样根据1或-1进行分类。

所以目标就是找出分类器定义中的w和b。

七、函数间隔和几何间隔

y表示类别时，取1或-1。

函数间隔则为：y*()，始终大于0。当>0时，y=1，函数间隔>0；当<0时，y=-1，函数间隔>0。

函数间隔代表了样本是正例还是反例的确信度，因为当>0越大时，y=1的可信度越高，反之一样。

但是，当w和b同时扩大倍数时，例如w和b都乘以系数2，函数间隔会增加2倍，但是超平面=0不会变化。

为了计算方便，也使间隔尽可能大，即分隔超平面明显，当类别y=1时，使得>=1，当类别y=-1时，使得<=-1，当点为支持向量时，函数间隔为1。

几何间隔则为：（几何间隔实际上就是点到超平面距离）

        

证明：

这里求的r是带符号的，加上类别y即可得绝对值，因此几何间隔为：y*r，即

         

八、最优求解

距离超平面最近的样本点（即支持向量）使得函数间隔为1，所以两类支持向量到超平面的距离之和为：

支持向量机算法欲找到具有“最大间隔”的划分超平面，也即满足下面约束：

等价为：

对于上述带不等式约束的最优求解问题，需要用到著名的拉格朗日乘子法。通过引入拉格朗日乘子，可以基于约束条件来表达原来的问题。优化目标函数最终可写成：

上述假设数据必须100%线性可分，但是几乎所有数据都不那么“干净”，通过引入所谓松弛变量（slack variable），来允许有些数据点可以处于分隔面的错误一侧。这样优化目标就能保持仍然不变，新的约束条件则变为：

常数C用于控制“最大化间隔”和“保证大部分点的函数间隔小于1.0”这两个目标的权重。在优化算法的实现代码中，常数C是一个参数，因此可以通过调节该参数得到不同的结果。一旦求出了所有的alpha，那么分隔超平面就可以通过这些alpha来表达。SVM中的主要工作就是求解这些alpha。