常见面试算法：支持向量机

What's the SVM?

^_^ 首先，支持向量机不是一种机器，而是一种机器学习算法。

1、SVM - Support Vector Machine ，俗称支持向量机，是一种 supervised learning （监督学习）算法，属于 classification （分类）的范畴。

2、在数据挖掘的应用中，与 unsupervised learning （无监督学习）的 Clustering（聚类）相对应和区别。

3、广泛应用于 Machine Learning （机器学习），Computer Vision （计算机视觉，装逼一点说，就是 cv）和 Data Mining （数据挖掘）当中。

“ Machine （机）” 是什么？

Classification Machine，是分类器，这个没什么好说的。也可以理解为算法，机器学习领域里面常常用 “机” 也就是 machine 这个字表示算法。

“支持向量” 又是什么？

通俗理解： support vector （支持向量）的意思就是 数据集中的某些点，位置比较特殊。比如 x+y-2=0 这条直线，直线上面区域 x+y-2>0 的全是 A 类，下面的 x+y-2<0 的全是 B 类，我们找这条直线的时候，一般就看聚集在一起的两类数据，他们各自的 最边缘 位置的点，也就是最靠近划分直线的那几个点，而其他点对这条直线的最终位置的确定起不了作用，所以我姑且叫这些点叫 “支持点”（意思就是有用的点），但是在数学上，没这种说法，数学里的点，又可以叫向量，比如 二维点 (x,y) 就是二维向量，三维度的就是三维向量 (x,y,z)。所以 “支持点” 改叫 “支持向量” ，听起来比较专业，而且又装逼，何乐而不为呢？是吧...

不通俗的理解： 在 maximum margin （最大间隔）上的这些点就叫 “支持向量”，我想补充的是为啥这些点就叫 “支持向量” ，因为最后的 classification machine （分类器）的表达式里只含有这些 “支持向量” 的信息，而与其他数据点无关：

linearly separable （线性可分）: 如上图中的两组数据，它们之间已经分的足够开了，因此很容易就可以在图中画出一条直线将两组数据点分开。在这种情况下，这组数据就被称为线性可分数据。

separating hyperplane（分隔超平面）: 上述将数据集分隔开来的直线称为分隔超平面。

hyperplane（超平面）: 在上面给出的例子中，由于数据点都在二维平面上，所以此时分隔超平面就只是一条直线。但是，如果所给的数据集是三维的，那么此时用来分隔数据的就是一个平面。显而易见，更高纬度的情况可以依此类推。如果数据是 1024 维的，那么就需要一个 1023 维的某某对象（不是你们的男（女）票）来对数据进行分隔。这个 1023 维的某某对象到底应该叫什么呢？ N-1 维呢？该对象被称为超平面，也就是分类的决策边界。分布在超平面一侧的所有数据都属于某个类别，而分布在另一侧的所有数据则属于另一个类别。

margin（间隔）: 我们希望能通过上述的方式来构建分类器，即如果数据点离决策边界越远，那么其最后的预测结果也就越可信。既然这样，我们希望找到离分隔超平面最近的点，确保它们离分隔面的距离尽可能远。这里所说的点到分隔面的距离就是 间隔。我们希望间隔尽可能地大，这是因为如果我们犯错或者在有限数据上训练分类器的话，我们希望分类器尽可能健壮。

支持向量（support vector） : 就是上面所说的离分隔超平面最近的那些点。

分类器 : 分类器就是给定一个样本的数据，判定这个样本属于哪个类别的算法。例如在股票涨跌预测中，我们认为前一天的交易量和收盘价对于第二天的涨跌是有影响的，那么分类器就是通过样本的交易量和收盘价预测第二天的涨跌情况的算法。

特征 : 在分类问题中，输入到分类器中的数据叫做特征。以上面的股票涨跌预测问题为例，特征就是前一天的交易量和收盘价。

线性分类器 : 线性分类器是分类器中的一种，就是判定分类结果的根据是通过特征的线性组合得到的，不能通过特征的非线性运算结果作为判定根据。还以上面的股票涨跌预测问题为例，判断的依据只能是前一天的交易量和收盘价的线性组合，不能将交易量和收盘价进行开方，平方等运算。

How does it work? （SVM 原理）

https://www.youtube.com/watch?v=3liCbRZPrZA

2、我认为是超级通俗的一个版本：

支持向量机是用来解决分类问题的。

先考虑最简单的情况，豌豆和米粒，用晒子很快可以分开，小颗粒漏下去，大颗粒保留。

用一个函数来表示就是当直径 d 大于某个值 D ，就判定为豌豆，小于某个值就是米粒。

d>D, 豌豆

d<D,米粒

在数轴上就是在d左边就是米粒，右边就是绿豆，这是一维的情况。

但是实际问题没这么简单，考虑的问题不单单是尺寸，一个花的两个品种，怎么分类？

假设决定他们分类的有两个属性，花瓣尺寸和颜色。单独用一个属性来分类，像刚才分米粒那样，就不行了。这个时候我们设置两个值 尺寸 x 和颜色 y.

我们把所有的数据都丢到 x-y 平面上作为点，按道理如果只有这两个属性决定了两个品种，数据肯定会按两类聚集在这个二维平面上。

我们只要找到一条直线，把这两类划分开来，分类就很容易了，以后遇到一个数据，就丢进这个平面，看在直线的哪一边，就是哪一类。

比如 x+y-2=0 这条直线，我们把数据 (x,y) 代入，只要认为 x+y-2>0 的就是 A 类， x+y-2<0 的就是 B 类。

以此类推，还有三维的，四维的，N维的 属性的分类，这样构造的也许就不是直线，而是平面，超平面。

一个三维的函数分类 ：x+y+z-2=0，这就是个分类的平面了。

有时候，分类的那条线不一定是直线，还有可能是曲线，我们通过某些函数来转换，就可以转化成刚才的哪种多维的分类问题，这个就是核函数的思想。

例如：分类的函数是个圆形 x^2+y^2-4=0 。这个时候令 x^2=a ; y^2=b ,还不就变成了a+b-4=0 这种直线问题了。

这就是支持向量机的思想。

3、（这个需要一些数学知识）：

如图的例子，（训练集）红色点是我们已知的分类1，（训练集）蓝色点是已知的分类2，我们想寻找一个分隔超平面（图中绿线）（因为示例是二维数据点，所以只是一条线，如果数据是三维的就是平面，如果是三维以上就是超平面）把这两类完全分开，这样的话再来一个样本点需要我们预测的话，我们就可以根据这个分界超平面预测出分类结果。

4、（这个需要的数学知识更加厉害一点）：

先看思维导图：

• 左边是求解基本的SVM问题
• 右边是相关扩展

什么是 SVM ？

Support Vector Machine, 一个普通的 SVM 就是一条直线罢了，用来完美划分 linearly separable 的两类。但这又不是一条普通的直线，这是无数条可以分类的直线当中最完美的，因为它恰好在两个类的中间，距离两个类的点都一样远。而所谓的 Support vector 就是这些离分界线最近的『点』。如果去掉这些点，直线多半是要改变位置的。可以说是这些 vectors （主，点点） support （谓，定义）了 machine （宾，分类器）...

所以谜底就在谜面上啊朋友们，只要找到了这些最靠近的点不就找到了 SVM 了嘛。

如果是高维的点，SVM 的分界线就是平面或者超平面。其实没有差，都是一刀切两块，我就统统叫直线了。

怎么求解 SVM ？

关于这条直线，我们知道

(1)它离两边一样远，(2)最近距离就是到support vector的距离，其他距离只能更远。

于是自然而然可以得到重要表达 I. direct representation

SMO 高效优化算法

• SVM有很多种实现，最流行的一种实现是： 序列最小优化(Sequential Minimal Optimization, SMO)算法。
• 下面还会介绍一种称为 核函数(kernel) 的方式将SVM扩展到更多数据集上。
• 注意：SVM几何含义比较直观，但其算法实现较复杂，牵扯大量数学公式的推导。

序列最小优化(Sequential Minimal Optimization, SMO)

• 创建作者：John Platt
• 创建时间：1996年
• SMO用途：用于训练 SVM
• SMO目标：求出一系列 alpha 和 b,一旦求出 alpha，就很容易计算出权重向量 w 并得到分隔超平面。
• SMO思想：是将大优化问题分解为多个小优化问题来求解的。
• SMO原理：每次循环选择两个 alpha 进行优化处理，一旦找出一对合适的 alpha，那么就增大一个同时减少一个。
  • 这里指的合适必须要符合一定的条件
  • 之所以要同时改变2个 alpha；原因是我们有一个约束条件： \(\sum_{i=1}^{m} a_i·label_i=0\)；如果只是修改一个 alpha，很可能导致约束条件失效。
  1. 这两个 alpha 必须要在间隔边界之外
  2. 这两个 alpha 还没有进行过区间化处理或者不在边界上。

SMO 伪代码大致如下：

创建一个 alpha 向量并将其初始化为0向量
当迭代次数小于最大迭代次数时(外循环)
   对数据集中的每个数据向量(内循环)：
       如果该数据向量可以被优化
           随机选择另外一个数据向量
           同时优化这两个向量
           如果两个向量都不能被优化，退出内循环
   如果所有向量都没被优化，增加迭代数目，继续下一次循环

SVM 开发流程

收集数据：可以使用任意方法。
准备数据：需要数值型数据。
分析数据：有助于可视化分隔超平面。
训练算法：SVM的大部分时间都源自训练，该过程主要实现两个参数的调优。
测试算法：十分简单的计算过程就可以实现。
使用算法：几乎所有分类问题都可以使用SVM，值得一提的是，SVM本身是一个二类分类器，
对多类问题应用SVM需要对代码做一些修改。

SVM 算法特点

优点：泛化（由具体的、个别的扩大为一般的，就是说：模型训练完后的新样本）错误率低，
计算开销不大，结果易理解。
缺点：对参数调节和核函数的选择敏感，原始分类器不加修改仅适合于处理二分类问题。
使用数据类型：数值型和标称型数据。

课本案例（无核函数）

对小规模数据点进行分类

开发流程

完整代码地址：SVM简化版，应用简化版SMO算法处理小规模数据集: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/6.SVM/svm-simple.py

完整代码地址：SVM完整版，使用完整 Platt SMO算法加速优化，优化点：选择alpha的方式不同:

https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/6.SVM/svm-complete_Non-Kernel.py

收集数据

文本文件格式：

核函数(kernel) 使用

• 对于线性可分的情况，效果明显
• 对于非线性的情况也一样，此时需要用到一种叫核函数(kernel)的工具将数据转化为分类器易于理解的形式。

利用核函数将数据映射到高维空间

• 使用核函数：可以将数据从某个特征空间到另一个特征空间的映射。（通常情况下：这种映射会将低维特征空间映射到高维空间。）
• 如果觉得特征空间很装逼、很难理解。
• 可以把核函数想象成一个包装器(wrapper)或者是接口(interface)，它能将数据从某个很难处理的形式转换成为另一个较容易处理的形式。
• 经过空间转换后：低维需要解决的非线性问题，就变成了高维需要解决的线性问题。
• SVM 优化特别好的地方，在于所有的运算都可以写成内积(inner product: 是指2个向量相乘，得到单个标量 或者 数值)；内积替换成核函数的方式被称为核技巧(kernel trick)或者核"变电"(kernel substation)
• 核函数并不仅仅应用于支持向量机，很多其他的机器学习算法也都用到核函数。最流行的核函数：径向基函数(radial basis function)
• 径向基函数的高斯版本，其具体的公式为：

项目案例: 手写数字识别的优化（有核函数）

项目概述

你的老板要求：你写的那个手写识别程序非常好，但是它占用内存太大。顾客无法通过无线的
方式下载我们的应用。
所以：我们可以考虑使用支持向量机，保留支持向量就行（knn需要保留所有的向量），
就可以获得非常好的效果。

使用算法：一个图像识别的完整应用还需要一些图像处理的知识

完整代码地址: https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/6.SVM/svm-complete.py

开发流程

收集数据：提供的文本文件

https://github.com/apachecn/AiLearning/blob/dev/blog/ml/6.1.%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA%E7%9A%84%E5%87%A0%E4%B8%AA%E9%80%9A%E4%BF%97%E7%90%86%E8%A7%A3.md

https://github.com/apachecn/AiLearning/blob/dev/blog/ml/6.%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA.md