支持向量机(Support Vector Machines-SV
本文主要是学习支持向量机的算法原理，并且用Python来实现相关算法。内容包括：SVM概述、线性可分支持向量机、线性支持向量机、非线性不可分向量机、核函数、核技巧、SMO、KKT条件等等，但是还是没有讲完，会继续学习讨论~~
再次申明：本文的理论知识来自Peter Harrington的《机器学习实战》和李航的《统计学习方法》，非常感谢这些优秀人物和优秀书籍
1、概述
支持向量机（support vector machines，SVM）是一种二类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机还包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划（convex quadratic programming）的问题，也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机(linear support vector machine in linearly separable case)、线性支持向量机(linear support vector machine)及非线性支持向量机(non-linear support vector machine)。Cortes与Vapnik提出线性支持向量机，Boser、Guyon与Vapnik引入核技巧，提出非线性支持向量机。--摘自《统计学习方法》
别晕，马上图文并茂的说明
针对下面的二分类问题，为了区分两类数据，该如何确定一条线（二维是线，多维以上就是平面、超平面）来使得区分效果最好？
图1 二类分类问题
在图1的分类问题中，显然黑色的线分类效果最好，算法的鲁棒性较高，SVM就是找到这样的平面，来更好的分类。
2、线性可分支持向量机
图2 数据集的相关参数定义说明
图3 线性可分支持向量机-定义
线性可分支持向量机的学习目标就是找到一个分离超平面，能将实例分配到不同的类中，分离超平面对应于方程w*x+b=0，该平面由法向量w和截距b来决定。分离超平面将空间分为两部分，一部分是正类，一部分是负类，法向量指向的一侧为正类。
一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面w·x+b＝0确定的情况下，|w·x+b|能够相对地表示点x距离超平面的远近。而w·x+b的符号与类标记y的符号是否一致能够表示分类是否正确。所以可用量y(w·x+b)来表示分类的正确性及确信度，这就是函数间隔(functional margin)的概念，见图4
图4 函数间隔的定义
定义超平面w·x+b＝0与训练集T的函数间隔为训练集T中全部点与超平面函数间隔的最小值，即
图5 超平面与训练集的函数间隔
但是存在一个问题，比如超平面与T中A点的函数间隔为y(w·x+b)，那么当w和b分别增长为2*w，2*b时，其实超平面还是没有变，可以把2约掉，但是与点A的函数间隔变为y(2w·x+2b)。函数间隔本来是用来表示分类的正确性以及确信度，其实点和面都没变，但是函数间隔却增长了，这样函数间隔就不能很好的表示确信度了，因此，需要对法向量进行规范化处理，所以出来了几何间隔的概念。
图6 超平面与训练集的几何间隔
支持向量机算法的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，这里的间隔最大化又称为硬间隔最大化。那么如何求解一个几何间隔最大的分离超平面，这个问题可以表示为下面的最优化问题：
图7 求解分离超平面的最优化模型
从算法的便捷性考虑，将图7中的优化模型转换为图8的计算模型：
图8 线性可分支持向量机学习算法模型
具体图8中的模型怎么求解呢->构造拉格朗日函数(Lagrange function)：
图9 构造拉格朗日函数来求解最优化模型
那么，结合图9中构造的拉格朗日函数，图8中的模型最终转换为：
图10 线性可分支持向量机学习算法模型转换后的计算模型
基于该模型，得到最终的w和b的计算公式如下：
图11 线性可分支持向量机学习算法模型w和b的计算式
3、线性支持向量机
对于线性不可分数据集，因为不存在一个分离平面，可以让全部点到它的距离都大于某一数值(即不能满足y_i*(wx+b)>1)，因此，线性可分支持向量机算法已经不能应用于线性不可分数据集，辣么，肿么办呢？
好办嘛，放松条件，既然大家不能一致均大于1，那就酌情考虑，给每一个点到分离超平面的距离放点水，达不到1，就根据自己情况，引入一个变量ξ，针对第i个点，让其到平面的距离为1-ξ_i，总结一下，线性支持向量模型如下：
图12 线性支持向量模型的软间隔示意图
图13 线性支持向量算法模型
图12中，C为惩罚因子，ξ为松弛因子，可以得知W是唯一的，b是一个区间数
图14 线性支持向量算法w和b的计算式
4、核函数
图15 非线性可分数据集
如图15所示，*表示正类，·表示负类，要将这两类分开，只能用曲线了；而如果出现高维的数据，那么只能用曲面来区分了，辣么，这些曲线或者曲面怎么确定呢？非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。
比如图15中的分类问题，将特征值进行非线性转换：
图16 将特征值进行非线性转换
然后，基于特征值Z就可以进行线性分类啦，见图17
图17 经过非线性变换后，转为线性分类
图16的转换技巧就是利用核函数来将原来的特征值空间(X)映射为新的特征值空间(Z)，基于这种方法求非线性分类问题的方法叫做核技巧。
核技巧：核技巧应用到支持向量机，其基本想法就是通过一个非线性变换将输入空间（欧氏空间Rn或离散集合）对应于一个特征空间（希尔伯特空间），使得在输入空间中的超曲面模型对应于特征空间中的超平面模型（支持向量机）。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。
那么，是不是出来非线性可分数据集，就直接将低维映射为高维呢？答案是否定的，因为可能出现维度爆炸，也就是维度太高，反而不适合计算。具体见图18
图18
针对此种问题，核函数来帮忙啦
核函数定义
图19 核函数
核函数说白了，就是两向量的內积。核函数的出现，可以将低维数据映射到高维，辣么，有啥用？他与上面图18的映射的区别就是他不管每一个具体的特征值是怎么映射的，而只是进行一个总的计算。详情见图20
图20
这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。接下来简单显示映射前后的输入数据集和特征集合的结构图，图片来自文章支持向量机通俗导论，这篇文章讲的不错。
其中一个高斯核函数(另名径向基函数，radial bias function)可以表示为：
图21 高斯核函数举例
图22 基于图21中高斯核函数将输入数据集映射为高纬的可分的特征集
再补充一句，你观察一下图21的公式，核函数比图18中直接从低维度到高维度的特点，也同时是核函数的优点是：核函数是先在低维计算（不映射，就用X1,X2...），然后将分类结果表现在高维度。
总结一下，什么提到的非线性分类问题，两种方式：
图18：先找到这种映射，然后将输入空间中的样本映射到新的空间中，最后在新空间中去求内积-》缺点：高维爆炸
图20核函数：或者是找到某种方法，它不需要显式的将输入空间中的样本映射到新的空间中而能够在输入空间中直接计算出内积。
具体核函数怎么确定我目前暂不学习了，后期进入机器学习的进阶阶段，我会更深入思考。
先给大家贴两个常用的核函数：
图23 常用核函数
5、非线性支持向量机
图24 非线性支持向量机
6、序列最小最优化(sequential minimal optimization, SMO)算法
SMO算法要解决如下凸二次规划的对偶问题形式见图25
图25 SMO解决问题模型
插曲：KKT条件( Karush-Kuhn-Tucker conditions)
在SMO的求解中，出现了KKT条件这个术语，辣么就让我插曲掰扯一下：
1）首先，这个条件一般是在最优化问题中出现，先通俗介绍下最优化理论：
图26 最优化模型一般表示
2）KKT条件是指在满足约束条件下，一个非线性规划问题能有最优化解法的一个充分必要条件，它是一个广义化的拉格朗日函数的结果。
图27 KKT条件最优化条件
不难发现，SMO算法所要解决的问题满足KKT条件。
为啥要在SVM的实现中，使用SMO算法，因为：SMO算法是一种启发式算法，其基本思路是：如果所有的变量的解都满足KKT条件，那么这个最优化问题的解也就找到了。SMO算法将大优化问题分解为多个小优化问题来求解。这些小优化问题容易求解，并且对它们进行顺序求解的结果与将它们作为整体来求解的结果完全一致。在结果完全相同时，SMO算法的求解时间非常短。
SMO算法的工作原理：在如图25所示的最优化问题中，每次循环中选择两个α进行优化处理。一旦找到一对合适的α，那么就增大其中一个同时减小另一个。这里所谓的‘合适’就是指两个α必须要满足一定的条件，条件之一是这两个α必须要在间隔边界之外，而其第二个条件则是这两个α还没有进行过区间化处理或者不在边界上。比如不是一般性的假设先优化的是变量α1和α2，则其他变量α_i(i=3,4,...N)则是固定的。于是图25中的最优化问题的子问题可以写成：
图28 SMO算法子问题优化(变量α1和α2)
那么每次的变量如何选择呢？
SMO算法中变量选择：SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。
1）第1个变量的选择
SMO称选择第1个变量的过程为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第1个变量，具体：
图29 SMO选择第一个变量-外层循环
2）第2个变量的选择
SMO把选择第2个变量叫做内层循环。假设在外层循环中已经找到第1个变量α1，那么第2个变量的选择标准是希望使变量α2有足够大的变化。
好吧，写了这么一堆太乱，总结一下SMO算法：
图30 总结SMO算法流程
图30是来自李航的统计学习了，他提到的7.101~7.103是图28中的公式哈~
接下来，开始初步实现SMO算法
DEMO1
图31 简单SMO算法的伪代码
贴代码：
图32 数据准备以及一些辅助函数
图33 SMO函数上半部分
图34 SMO函数下半部分
简单的SMO函数代码也不少，只能分为两部分截图，针对SMO函数代码解释，请看我下面自己手写的一些代码解释（字体难看，但愿能看得懂就行）
图35 代码解释
图36 代码解释
最后，代码的结果为(alphas数组长度是100，只显示其大于0的数值)，运行时间是6秒30左右：
b[[-3.72390494]]，alphas[alphas>0]=[0.13005552, 0.1625913,0.05905607,0.02273883,0.3289640]
那么，原来的数集中，可以做支持向量的分别是：[ 4.658191 3.507396](第18个样本)，[ 3.457096 -0.082216](第30个样本)，[ 2.893743 -1.643468](第53个样本)，[ 5.286862 -2.358286](第55个样本)，[ 6.080573 0.418886](第56个样本)
其实，每跑一次SMO算法，他给出的结果是不一样的。
我们用绘图的方式表示一下特征值：
图37 基于SMO算法，红色的点表示支持向量
好哒，这篇真的太长了，关于这部分，我增加一次讨论的汇总吧，包括在仿真中遇到的一些问题。
希望对大家有用~~
