Python3机器学习实践：支持向量机理论与实例
1.png
支持向量机属于监督式学习的方法，可实现分类以及回归。它是Corinna Cortes和Vapnik等于1995年首先提出的。算法优点在于具有完整的理论支持，可以得到全局最优解，并且可以解决非线性问题。缺点在于不适用于样本数较大的情况，另外针对非线性问题时核函数的选择，没有特别的依据。
image
分类--引入
如上图，平面内展示了二维数据样本，其中“+”号表示正例，“-”号表示负例。存在无数条分割线可以分开上述两类样本(见下图，图中仅列出了4条分割线)。
image
所有分割线中，只存在一条最优的：分割线到负例的距离中最小的那个距离，要等于到正例的距离中最小的距离，并且这两个距离的和是所有满足前一个条件的分割线中最大的(见下图左)。
下面定义一个向量W，现在只定义它的方向，就是与分割线垂直。假设这个样本空间中存在一个样本向量U，PP=U·W可看作向量U在W上的投影(因为W未定义长度)。现在规定：如果U是一个负例，则PP的值越小越好；如果是一个正例，则PP的值越大越好(见上图右)。
因此在判断样本属于正例还是负例时，就是判断PP的值是否大于一个数，也就是判断U·W+b>=0。为了求得W和b，需要添加一些约束条件。不失一般性，对于一个正例Xz，可以令Xz·W+b>=1， 对于一个负例Xf，可以令Xf·W+b<=-1。数学便利性：对于正例，令Y= 1，对于负例，令Y=-1。因此结合以上式子可得：对于任意的样本h，有Yh(Xh·W+b) >=1，也就是Yh(Xh·W+b)-1>=0。
现在着重研究下Yh(Xh·W+b)-1=0的情况，当样本h在上边缘或者在下边缘时，式子成立。假设正例Xz，负例Xf分别在上边缘、下边缘上。则上边缘与下边缘的距离，也就是分割线的最大间隔为：
image
因为Yz=1，Xz·W = 1-b， Yf=-1，Xf·W = -1-b， 所以g=2/||W||。
OK，整理下思路。要获得g的最大值，
image
分类--推导
- 线性可分情况：硬间隔
问题的表达式如下：
image
因为上面的约束条件包含不等式约束，因此需要利用KKT(Karush-Kuhn-Tucker)条件求解(只有等式约束，才可利用拉格朗日乘子法求解)。将原始问题转为下面形式的对偶问题(在满足KKT条件时，求取对偶问题最大值的最优解就是原始问题取得最小值的最优解，理论参见《凸优化》)：
image
KKT条件是保证取得的解是最优解的必要条件，而对于像本问题这样的凸优化问题，则是充要条件，下面给出KKT条件：
image
- 线性可分情况：软间隔
上面描述的是线性可分的情形，也就是存在线或者面可以将样本按类别很好的分开。现在看下面存在离群点的2种情况：
情况A：如果依然按着硬间隔进行划分，泛化能力会减弱；
情况B：不存在硬间隔。因此在这种情形下，要适当的对约束条件进行如下的放宽。
image
对于硬间隔而言，Yh(Xh·W+b) >=0对任何的样本均成立，也就是保证所有的样本均分类正确。而在软间隔中，Yh(Xh·W+b) >=0不是对所有的样本均成立，也就是允许对一些离散的点分类错误。
因为不能无限放宽，因此需要在目标函数里面增加一个惩罚项，问题变为：
上式中C的值越大，离群点的存在会使得目标函数的值变大，为了降低目标函数的值，这时候，得到的结果便趋向于硬间隔。经过和硬间隔同样的变化，得到软间隔的对偶问题：
image
模型多了αi<=C的限制条件，并且表达式中并没有参数ξi，此时b的求值公式也会发生相应的改变。下面给出KKT条件：
- 线性不可分情况：核函数
以上描述的都是线性可分的情形，现在考虑下面的情形(下图左)：
image
首先上述不存在硬间隔，如果使用软间隔，则和数据分布不符，因此需要对原始的数据进行非线性转换(上图右)。前面线性可分的2种情况的最终对偶问题表达式中，都只是和内积有关。因此只要找到一个函数Ｆ，使得
其中P是非线性转换函数。也就是说F的值恰好是非线性转换后的向量的内积，此时的F称为核函数。
下面介绍几种常用的核函数：
image
经过核函数的对偶问题为：
image
分类--结果展示
- AnFany
- TensorFlow
image
- Sklearn
image
回归
image
image
SVM求解
- 基于SMO算法求解
1996年，Platt发布了SMO算法。SMO算法是将大优化问题分解为多个小优化问题来求解。这点和坐标上升/下降法类似。SMO算法的工作原理：每次循环选择2个变量进行优化处理，一旦找到一对符合条件的变量，那么就增大其中一个通式减小另一个。符合的条件一是这2个变量必须在间隔边界之外，二是这2个变量还没有进行过区间化处理或者不在边界上。SMO算法的原理类似于坐标上升/下降算法。点击阅读原文，可获得分类、回归的SMO伪码以及坐标上升/下降算法的详细代码。
- 基于梯度下降的求解
image
实例代码：回归，分类，扫描下方二维码或者微信公众号直接搜索”Python范儿“，关注微信公众号pythonfan， 获取更多实例和代码。
pythonfan.jpg
