SVM是数据挖掘算法中比较复杂难懂的，反复观看斯坦福机器学习的视频， 以及网上零散学习各种数学和SVM相关资料， 对SVM还只能算有个粗浅的理解，写篇文章梳理下SVM的基本脉络，和大家分享下，有不正确之处请指正。

SVM介绍

SVM支持向量机（英文全称：support vector machine）是一个分类算法， 通过找到一个分类平面， 将数据分隔在平面两侧， 从而达到分类的目的。
如下图所示， 直线表示的是训练出的一个分类平面， 将数据有效的分隔开。

SVM分类示意图

SVM实现原理

SVM的分类基本思路是找到一个分类平面， 下面重点探讨下如何找到这个平面。 先梳理下SVM求解的基本思路;

Paste_Image.png

如图SVM的推导分为5个步骤：

1. 用数学来定义要求解的问题
   SVM是求解一个平面S：y = wx + b， 其实就是求解参数w, b。如何来求解w, b呢？ 怎么判断训练的w, b构成的平面已经足够好呢？ 这就需要把问题建模成一个数学问题（称为原始问题），从而明确求解的目标以及约束条件。

2. 求解原始问题转换为二次凸函数+约束条件的优化问题
   原始问题很难求解出参数， 转换为二次凸函数+约束条件的优化问题， 这种转换保证两个函数取最优解时，参数是相同的。做这种转换的主要原因是二次凸函数和约束条件有成熟的计算方法和理论支撑(拉格朗日优化理论)。

3. 拉格朗日优化+对偶特性构建方程
   将w, b参数优化转换为对参数alpha的优化（alpah为拉格朗日约束函数的参数）

4. SMO求解alpha最优值
   通过上步构建的方程， w, b可以通过alpha来表示。 SMO可以求解出alpha， 再通过alpha求出w,b。 到此平面的方程就可推导出来。

SVM的数学定义

SVM是要找到最合适的分类平面， 那么怎么才算最合适的? 最直接的评估标准：被分隔的两边数据距离平面间隔最大， 换句话，SVM就是获取最大间隔的超平面。下面介绍两个衡量样本到超平面间隔的定义。

1. 函数间隔
   在超平面w * x + b = 0确定的情况下，|wx+b|表示点距离超平面的距离，而超平面作为二分类器，如果wx+b>0， 判断类别y为1, 否则判定为-1。从而引出函数间隔的定义：

单样本函数间隔

其中y是训练数据的类标记值， 如果y(w^T * x + b) >0说明，预测的值和标记的值相同， 分类正确，而且值越大，说明点离平面越远，分类的可靠程度更高。这是对单个样本的函数定义， 对整个样本集来说，要找到所有样本中间隔值最小的作为整个集合的函数间隔：

整个数据集的函数间隔

即w和b同时缩小或放大M倍后，超平面并没有变化，但是函数间隔跟着w和b变化。所以，需要加入约束条件使得函数间隔固定, 也就是下面介绍的几何间隔。

2.几何间隔
根据点到平面的距离公式和w*x+b=0平面公式， 推导得到几何间隔定义：

Paste_Image.png

和函数间隔类似， 为得到r的绝对值， 我们定义几何间隔:在上述公式中乘以y值， 同时也得到与函数间隔的关系：几何间隔就是函数间隔除以w的范式。

Paste_Image.png

为方便推导和优化， 令函数间隔等于1得到最大间隔分类器的原始定义：

Paste_Image.png

最大间隔分类器就是我们求取的分类超平面， 等于max(几何间隔)， 而函数间隔假设为1，就可得到最大间隔超平面: max(1/||w||), 而约束条件是因为函数间隔是所有样本点的间隔函数中最小值。

SVM的二次凸函数和约束条件

最大间隔分类器的求解， 可以转换为上面的一个最优化问题， 即在满足约束条件：

Paste_Image.png

求出就最大的1/||w||。
为更好的利用现有的理论和计算方法， 可以将求解1/||w||最大值， 转换为一个二次凸函数优化问题：求解 Min(1/2 * (||w||)^2 )， 两者问题是等价的。原来的问题转换为二次凸函数优化问题：

Paste_Image.png

拉格朗日构建方程

在对二次凸函数进行优化前，先讨论下对偶性问题。 如下图所示, 假设一个函数F(x,y) = f(x, y) + a * (g(x, y) - c)， 椭圆线是f(x, y)在平面上的等高线， 绿色是g(x, y)=c的轨迹。

拉格朗日

从图上可以看出， F(x, y)的极值点肯定是f(x,y)和g(x,y)-c相切的点， 这点上两个曲线的法向量平行。从而可以得到如下结论：

Paste_Image.png

类似的，可以将1/2 * ||w|| ^2优化函数和约束条件结合起来， 构建一个函数：

Paste_Image.png

其中ai是拉格朗日乘子。

利用对偶性的结论， 对L(w，b，a)关于w和b求偏导数：

Paste_Image.png

将上面两个等式，代入L(w, b, a)函数，最终最大间隔分类器优化文件， 就转换成如下定义（过程太过复杂，直接看下结论就可以）， 注意这个公式中只涉及求解ai的极大值， 不涉及w, b参数的求解， 因为w, b都可以用ai来表示， 求出ai后， 自然就求出了w,b的值。

Paste_Image.png

SMO算法求解alpha

上面推导的公式， 是通过SMO算法来求解的。最常见的是Platt SMO算法 ， 这个算法是在1996年John Platt 发布的。SMO算法（Sequential Minimal Optimization）全称是最小序列优化。SMO的基本思路类似动态规划， 也是一种启发式算法，它将原优化问题分解为多个小优化问题来求解，并且对这些小优化问题进行顺序求解得到的结果作为作为整体的结果。本文不详细介绍， 后续文章更新。

后记：

1. 本文大体梳理下SVM的推导求解过程， 但这个推导只针对线性的分类超平面，非线性分类超平面需要用到核函数， 将低维线性不可分通过空间映射到高维， 从而变得线性可分。
2. SMO的具体用法和实现代码先记下， 有时间再更新。

介绍一篇比较总结比较好的文章：
http://mp.weixin.qq.com/s/Uha_MJQtJiWRhBuVW32y9g