支持向量机SVM原理及实践（一）
一、什么是支持向量机 SVM
支持向量机（ Support Vector Mavhine ）简称 SVM ，是一种二类分类模型。SVM 的目标是找到一个超平面，然后找到各个分类离这个超平面最近的样本点，使得这个点到超平面的距离最大化，即使直线两端的数据间隔最大。与分割超平面距离最近的样本称为支持向量，下图中虚线是间隔边界，确定最终的分割超平面只有支持向量起作用，其他样本点不起作用，所以称为支持向量机。
这个超平面用 ，f(x)>0 时，y=1，为正类，如图中圆圈表示；f(x)<0 时，y= - 1，为负类，如图中星星表示；
y 为什么用+1，-1表示？
1.对于二类问题，y 只要取两个任意值就行；
2.支持向量机 SVM 去解二类问题，目标是求一个特征空间的超平面，而超平面分开的两类对应于超平面的函数值的符号是刚好相反的。上述两种考虑，为了使问题足够简单，我们取 y 的值为 1 和 -1。
接下来问题是寻找最大间隔的超平面
二、函数间隔和几何间隔
在分割超平面 w*x+b=0 确定的情况下，|w*x+b| 可以表示样本点距离超平面的远近。当 w*x+b 与样本标签 y 同号时，表示分类是正确的，所以使用 y(w*x+b)来表示分类的正确性和确信度，这是函数间隔的定义。
１．函数间隔：
超平面 (w，b) 关于训练数据集 T ( m 个)中所有样本点 (xi，yi) 的函数间隔最小值（其中，x 是特征，y 是结果标签，i 表示第 i 个样本），便为超平面 (w, b) 关于训练数据集 T 的函数间隔：
函数间隔可以表示分类预测的正确性和确定性，但是，当 w 和 ｂ同时放大对于超平面没有任何改变，函数值ｆ却变大。为解决这个问题我们对法向量ｗ加约束条件，从而引入几何函数。
２．几何函数：
假定对于一个点 x ，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直于超平面的一个向量，为样本x到超平面的距离，如下图所示，
由平面几何知识得：
因为x0在超平面上，所以f（x0）,即 ，对式
左右两边同乘
，由
得：
为了得到的绝对值，对上式同乘以y，使
，则几何间隔定义为：
由上式知几何间隔就是函数间隔除以 ||w||，函数间隔 y*(wx+b) = y*f(x) 实际就是 |f(x)|，几何间隔才是直观上的点到超平面的距离。
3. 最大间隔
对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是下图中的 Gap 的一半。
在函数间隔中超平面不变的情况下，等比例地缩放 w 的长度和 b 的值，这样可以使 f 得的值任意大。但几何间隔因为除，使得在缩放 w 和 b 的时候几何间隔的值是不会改变的，它只随着超平面的变动而变动，所以最大间隔分类超平面中的“间隔”指的是几何间隔。
则几何间隔最大化的目标函数为：
同时满足：
可以令 ，则可转化为最小优化问题为： (由于求 1/||w|| 的最大值相当于求
的最小值)
三、分割超平面的求解
在前面我么们所有的数据集其样本都是可分类的，即存在分割超平面。但现实中的数据集，总存在着部分的特异点，只有将其去除才可线性可分。我们为了解决这个问题，对每个样本引入松弛变量 。每个松弛变量都有一个代价 C，优化目标变为：
对前面求出的最小优化问题我们使用拉格朗日乘数法求解，将其转化为无约束条件的问题，即：
其中
则最小化问题为：，根据拉格朗日的对偶性，转化为对偶问题则为：
先对 w,b 求偏导并使其为零，则：
将结果带入 L 中，则有下面的推导过程：
当a* 为最优解时，可得问题的最优解为：
选择a*的一个分量，则b的最优解为：
参考文献 赵志勇《python 机器学习算法》