机器学习_13_SVM支持向量机、感知器模型

1 感知器模型

1.1 感知器的思想

• 感知器算法是最古老的分类算法之一，原理比较简单，不过模型的分类泛化能力比较弱，不过感知器模型是SVM、神经网络、深度学习等算法的基础。
• 感知器的思想很简单：比如有很多的学员，分为男学员和女学员，感知器模型就是试图找到一条直线，能够把所有的男学员和女学员分隔开，如果是高维空间中，感知器模型寻找的就是一个超平面，能够把所有的二元类别分割开。感知器模型的前提是：数据是线性可分的。
  

1.2 感知器模型构建

1.3 损失函数构建、求解

2 SVM

支持向量机(Support Vecor Machine, SVM)本身是一个二元分类算法，是对感知器算法模型的一种扩展，现在的SVM算法支持线性分类和非线性分类的分类应用，并且也能够直接将SVM应用于回归应用中，同时通过OvR或者OvO的方式我们也可以将SVM应用在多元分类领域中。在不考虑集成学习算法，不考虑特定的数据集的时候，在分类算法中SVM可以说是特别优秀的。

3 线性可分SVM

• 在感知器模型中，算法是在数据中找出一个划分超平面，让尽可能多的数据分布在这个平面的两侧，从而达到分类的效果，但是在实际数据中这个符合我们要求的超平面是可能存在多个的。
  

• 在感知器模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都离超平面尽可能的远，但是实际上离超平面足够远的点基本上都是被正确分类的，所以这个是没有意义的；反而比较关心那些离超平面很近的点，这些点比较容易分错。所以说我们只要让离超平面比较近的点尽可能的远离这个超平面，那么我们的模型分类效果应该就会比较不错喽。SVM其实就是这个思想。

3.1 线性可分SVM—概念

• 线性可分(Linearly Separable)：在数据集中，如果可以找出一个超平面，将两组数据分开，那么这个数据集叫做线性可分数据。
• 线性不可分(Linear Inseparable)：在数据集中，没法找出一个超平面，能够将两组数据分开，那么这个数据集就叫做线性不可分数据。
• 分割超平面(Separating Hyperplane)：将数据集分割开来的直线/平面叫做分割超平面。
• 间隔(Margin)：数据点到分割超平面的距离称为间隔。
• 支持向量(Support Vector)：离分割超平面最近的那些点叫做支持向量。
  

3.2 线性可分SVM —SVM 模型公式表示

• SVM模型是让所有的分类点在各自类别的支持向量的两边，同时要求支持向量尽可能的远离这个超平面，用数学公式表示如下：

3.3 线性可分SVM —SVM 损失函数

3.4 优化函数求解

3.5 线性可分SVM—算法流程

3.6 线性可分SVM—案例

3.7 线性可分SVM—总结

• 要求数据必须是线性可分的；
• 纯线性可分的SVM模型对于异常数据的预测可能会不太准；
• 对于线性可分的数据，SVM分类器的效果非常不错。

4 SVM的软间隔模型

线性可分SVM中要求数据必须是线性可分的，才可以找到分类的超平面，但是有的时候线性数据集中存在少量的异常点，由于这些异常点导致了数据集不能够线性划分；直白来讲就是：正常数据本身是线性可分的，但是由于存在异常点数据，导致数据集不能够线性可分；

4.1 SVM的软间隔模型—概念

• 如果线性数据中存在异常点导致没法直接使用SVM线性分割模型的时候，我们可以通过引入软间隔的概念来解决这个问题；

• 硬间隔：可以认为线性划分SVM中的距离度量就是硬间隔，在线性划分SVM中，要求函数距离一定是大于1的，最大化硬间隔条件为：

• 软间隔：SVM对于训练集中的每个样本都引入一个松弛因子(ξ)，使得函数距离加上松弛因子后的值是大于等于1；这表示相对于硬间隔，对样本到超平面距离的要求放松了。
  

4.2 SVM的软间隔模型—目标函数

• 松弛因子(ξ)越大，表示样本点离超平面越近，如果松弛因子大于1，那么表示允许该样本点分错，所以说加入松弛因子是有成本的，过大的松弛因子可能会导致模型分类错误，所以最终的目标函数就转换成为：

• 备注：函数中的C>0是惩罚参数，是一个超参数，类似L1/L2 norm的参数；C越大表示对误分类的惩罚越大，C越小表示对误分类的惩罚越小；C值的给定需要调参。
  

4.3 优化函数求解

4.4 SVM的软间隔模型 —支持向量

• 在硬间隔最大化的时候，支持向量比较简单，就是离超平面的函数距离为1的样本点就是支持向量。
• 在软间隔中，根据KKT条件中的对偶互补条件: β(y(wx+b)-1+ξ)=0，从而有：
  • 当0<βi≤C的时候，并且ξi=0的样本点均是支持向量(即所有的0<β_i<C)。即满足|wx+b|=1的所有样本均是支持向量。
  • 备注：软间隔和硬间隔中的支持向量的规则是一样的；

4.5 SVM的软间隔模型—算法流程

4.6 SVM的软间隔—模型总结

• 可以解决线性数据中携带异常点的分类模型构建的问题；
• 通过引入惩罚项系数(松弛因子)，可以增加模型的泛化能力，即鲁棒性；
• 如果给定的惩罚项系数越小，表示在模型构建的时候，就允许存在越多的分类错误的样本， 也就表示此时模型的准确率会比较低；如果惩罚项系数越大，表示在模型构建的时候，就越不允许存在分类错误的样本，也就表示此时模型的准确率会比较高。

5 多项式回归回顾

在线性回归中，我们可以通过多项式扩展将低维度的数据扩展成为高维度的数据，从而可以使用线性回归模型来解决问题。也就是说对于二维空间中不是线性可分的数据，将其映射到高维空间中后，变成了线性可分的数据。

6 非线性可分SVM

• 不管是线性可分SVM还是加入惩罚系数后的软间隔线性可分SVM其实都要求数据本身是线性可分的，对于完全不可以线性可分的数据，这两种算法模型就没法解决这个问题了
• 结合多项式回归在处理非线性可分数据时候的作用，在SVM的线性不可分的数据上，如果将数据映射到高维空间中，那么数据就会变成线性可分的，从而就可以使用线性可分SVM模型或者软间隔线性可分SVM模型。
• 也就是说，对于线性不可分SVM模型来讲，重点在于低维特征数据到高维特征数据之间的映射。

6.1 非线性可分SVM —概念

• 定义一个从低维特征空间到高维特征空间的映射函数Ф，非线性可分SVM的优化目标函数：

• 可以看到的是，只需要将原来的低维空间中的两个向量的点积转换为高维空间中两个向量的点积即可。

• 这样一来问题就解决了吗？似乎是的：拿到非线性数据，就找一个映射，然后一股脑把原来的数据映射到新空间中，再做线性 SVM 即可。不过事实上没有这么简单！其实刚才的方法稍想一下就会发现有问题：在最初的例子里做了一个二阶多项式的转换，对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了5个维度；如果原始空间是三维，那么我们会得到9维的新空间；如果原始空间是n维，那么我们会得到一个n(n+3)/2维的新空间；这个数目是呈爆炸性增长的，这给计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算。

6.2 核函数

• 假设函数Ф是一个从低维特征空间到高维特征空间的一个映射，那么如果存在函数K(x,z), 对于任意的低维特征向量x和z，都有：

• 称函数K(x,z)为核函数(kernal function)；

• 核函数在解决线性不可分问题的时候，采取的方式是：使用低维特征空间上的计算来避免在高维特征空间中向量内积的恐怖计算量；也就是说此时SVM模型可以应用在高维特征空间中数据可线性分割的优点，同时又避免了引入这个高维特征空间恐怖的内积计算量。

6.2.1 核函数例子

6.2.2 核函数分类

6.2.3 核函数总结

1. 核函数可以自定义；核函数必须是正定核函数，即Gram矩阵是半正定矩阵；
2. 核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算；
3. 通过核函数，可以将非线性可分的数据转换为线性可分数据；

7 SMO

• 序列最小优化算法(Sequential minimal optimization, SMO)是一种用于解决SVM训练过程中所产生的优化问题的算法。 于1998年由John Platt发明，论文详见：Sequencial Minimal Optimization-a Fast Alg for Training SVM.pdf

7.1 最优的分割超平面

7.2 SMO解题思路

从而可以得到解决问题的思路如下：

• 首先，初始化后一个β值，让它满足对偶问题的两个初始限制条件；
• 然后不断优化这个β值，使得由它确定的分割超平面满足g(x)目标条件；而且在优化过程中，始终保证β值满足初始限制条件。
• 备注：这个求解过程中，和传统的思路不太一样，不是对目标函数求最小值，而是让g(x)目标条件尽可能的满足。

7.3 β值的优化原则

• 在这样一个过程中，到底如何优化这个β值呢？？？整理可以发现β值的优化必须遵循以下两个基本原则：
  • 每次优化的时候，必须同时优化β的两个分量；因为如果只优化一个分量的话，新的β值就没法满足初始限制条件中的等式约束条件了。
  • 每次优化的两个分量应该是违反g(x)目标条件比较多的。也就是说，本来应当是大于等于1的，越是小于1违反g(x)目标条件就越多。
• 或者换一种思路来理解，因为目标函数中存在m个变量，直接优化比较难，利用启发式的方法/EM算法的思想，每次优化的时候，只优化两个变量，将其它的变量看成常数项，这样SMO算法就将一个复杂的优化算法转换为一个比较简单的两变量优化问题了。

7.3.1 不考虑β值限制条件

7.3.2 考虑β值限制条件

7.4 两个β值的变量选择

• 可以发现SMO算法中，是选择两个合适的β变量做迭代，其它变量作为常量来进行优化的一个过程，那么这两个变量到底怎么选择呢???
  • 每次优化的时候，必须同时优化β的两个分量；因为如果只优化一个分量的话，新的β值就没法满足初始限制条件中的等式约束条件了。
  • 每次优化的两个分量应该是违反g(x)目标条件比较多的。也就是说，本来应当是大于等于1的，越是小于1违反g(x)目标条件就越多。

7.4.1 第一个β变量的选择

SMO算法在选择第一个β变量的时候，需要选择在训练集上违反KKT条件最严重的样本点。一般情况下，先选择0<β<C的样本点(即支持向量)，只有当所有的支持向量都满足KKT条件的时候，才会选择其它样本点。因为此时违反KKT条件越严重，在经过一次优化后，会让变量β尽可能的发生变化，从而可以以更少的迭代次数让模型达到g(x)目标条件。

7.4.2 第二个β变量的选择

• 在选择第一个变量β₁后，在选择第二个变量β₂的时候，希望能够按照优化后的β₁和β₂有尽可能多的改变来选择，也就是说让|E₁-E₂|足够的大，当E₁为正的时候，选择最小的E_i作为E₂；当E₁为负的时候，选择最大的E_i作为E₂。
• 备注：如果选择的第二个变量不能够让目标函数有足够的下降，那么可以通过遍历所有样本点来作为β₂，直到目标函数有足够的下降，如果都没有足够的下降的话，那么直接跳出循环，重新选择β₁；

7.5 计算阈值b和差值E_i

7.6 SMO算法流程总结

8 SVR

• SVM和决策树一样，可以将模型直接应用到回归问题中；在SVM的分类模型(SVC)中，目标函数和限制条件如下：

• 在SVR中，目的是为了尽量拟合一个线性模型y=wx+b；从而我们可以定义常量eps>0，对于任意一点(x,y)，如果|y-wx-b|≤eps，那么认为没有损失，从而我们可以得到目标函数和限制条件如下：

8.1 构造拉格朗日函数

8.2 求解优化函数

对步骤2构造的拉格朗日函数求解：

9 scitit-learn SVM算法库概述

• scikit-learn中SVM的算法库主要分为两类，
  • 一类是分类算法，包括：SVC、NuSVC和LinearSVC这三个类，
  • 另外一类是回归算法，包括：SVR、NuSVR和LinearSVR这三个类；
  • 除此之外，用的比较多的SVM模型还有OneClassSVM类 (主要功能是：异常点检测)。
• 详见：http://scikit-learn.org/dev/modules/svm.html

9.1 分类算法

9.2 回归算法

9.3 异常点检测