数据挖掘-支持向量机

支持向量机（support vector machine，SVM）是一种出色的分类技术，也可以用于回归分析（SVR）。这种技术可以很好的应用于高维数据，避免维度灾难等问题。

SVM有一个特点就是使用训练集中的一个子集来表示决策边界，该子集称作 支持向量 。

SVM的核心目标是找到分类中的最大边缘超平面，让其作为决策边界，那么什么是最大边缘超平面呢？

但是可以发现，这种超平面有无数多个（图中就能看到有好多个），如果有一些未知的点需要预测分类，那么他们可能未必会被这些超平面完美的分隔：

以最下侧的超平面为例，如果我们有未知的点按照蓝色排布，那么可以看到，最下侧的这个超平面完全不能分类所有蓝色点的“-”号，那么如果它作为决策边界，泛化能力就不是很好。

我们肯定要从这些超平面中选一个最合理的作为决策边界，使得未知的点尽量的能被正确预测分类，那么肯定是上图中间的这个超平面最好了，我们目测就可以得到结果，因为 它离两边这些点的距离围成的面积应该是最大的，而且两边的面积基本是差不多的 。（个人理解）所以应该能装得下更多的未知点，也就能得到最好的泛化效果。

为了不用肉眼观测，能量化的得到这个结果，我们可以定义 最大边缘超平面 。

下图中有两个决策边界， 和 ，其中每个决策边界都对应着两个超平面(记作 )。其中 是由 进行两侧平移，直到接触到最近的一个训练集的点停止，生成的，同理 也是。

我们把两个超平面（同一个决策边界生成的）之间的距离叫做分类器的边缘，那么下图中，显然 生成的两个超平面距离应该是最大的， 就叫做 最大边缘超平面 （ 虽然是决策边界，但是决策边界都是超平面）。

通常来说，较大边缘的超平面具有更好的泛化误差，如果边缘比较小，那么决策边界的轻微扰动都可能对分类产生显著影响。

SVM算法的核心就是设计最大化决策边界边缘的分类器，以保证最坏情况下泛化误差最小 。

假设有一个包含 个训练样本的二元分类问题，每个样本表示为一个二元组 , 其中 ，对应于第i个样本的属性集（一个样本有多个属性/特征）,设y有-1和1两个类别，则一个 线性分类器的决策边界 可以写成如下形式：

其中的 为参数， 是法向量（垂直于决策边界）的向量，代表着超平面的方向，而 代表超平面与原点之间的距离（可以用一次函数的公式来理解）。

为什么 一定会垂直于决策边界呢？我们设有两个点 是决策边界上的两点，那么有：

二者相减有：

因为 肯定是平行于决策边界的，那么为了保证内积为0， 肯定要垂直于决策边界。

根据以上的决策边界，则肯定有：

如果上方的点是1类，下方是-1类，则有：

如果我们能得到 ，那么就可以用这个公式对未知点进行预测分类。代入公式，如果 就是1类，反之则为-1类。

接下来我们的任务就是如何求这两个参数，首先，既然是求最大边缘超平面，我们要把决策边界的边缘算出来。

根据上图，考虑那些离决策边界最近的方形和圆形，我们可以得到两个平行的超平面表示如下：

决策边界的边缘就是这两个超平面的距离。

参考上图的 ，不难得出边缘 为：

其中 是w的2范数。

很显然，我们想要让这个 最大，那么就要让 最小。

于是，接下来我们的求参数目标就明确了。

由于 肯定是非负的，我们可以改写一下

这个式子，让它变成求 的最小值。

既然要求最小值，就需要有另外一个约束条件，否则是没办法求的，我们来看之前总结的线性SVM分类器的公式：

由于 和 是决策边界的两个超平面，我们从上图中可以看出，所有的点（除了这两个超平面经过的点以外，经过的点是离决策边界最近的点），都肯定有 和 。

我们把y引入进来，那么这两个式子就能合到一起写为：

注意不要和之前总结的公式中的 弄混，那个条件是最终预测分类的公式，也就是表明只要在决策边界的上方就可以进行分类，而现在的>=1是在已知训练集的情况下求模型的参数。

综合以上的式子，我们可以得到求参数的基本式：

目标函数是二次的，而约束在参数 和 上是线性的，因此这是一个凸优化问题， 不存在局部优化的问题 。

求这一套公式的最小值，需要用到 拉格朗日乘数法 ，这个我也不是很明白，就按照百度百科的定义往里套：

虽然我们这里的附加条件是大于等于1的，不过不妨改写一下试试，则有：

其中的 就是 拉格朗日乘子 ，理论上来说，拉格朗日乘子可以为任何值。

如果约束条件是=0的话，我们就可以直接对 和 求偏导数，让他们等于0，就能求得参数。

但是目前条件并不是等于0的，而是大于等于0的。

处理不等式约束一种方法就是变换成一组等式约束，根据KKT条件，可以限制拉格朗日乘子飞赴，把之前的约束变换为：

该约束表明，除非训练样本满足方程 ，否则拉格朗日乘子必须为0。

结合上面展示决策边界和超平面的图，我们可以想到，满足这个方程的样本，肯定都在决策边界生成的两个超平面上。这些样本处的拉格朗日乘子肯定够大于0，而其他样本的拉格朗日乘子，肯定等于0，因此问题得到简化。 因为参数的确定仅依赖于这些在超平面上的样本。

这些在超平面上的样本，被称作 支持向量 ，这也就是支持向量机的命名缘由。

有了以上的修改后的约束，我们可以在 对 和 求偏导，并让他们等于0.

我们已知，这个时候的 和 是有满足条件的最优解的，把这两个式子代入原公式，就能得到 的最小值（当然此时因为不知道拉格朗日乘子，我们是求不出来的），代入公式可得：

该函数叫做对偶拉格朗日函数。

用这个函数，就是把之前求w和b的公式变换成了求拉格朗日乘子的公式，同时需要注意，这个式子中是求拉格朗日对偶函数的最大化问题。

我们可以用二次规划法或者SMO方法来求拉格朗日乘子。

二次规划算法比较通用，但是计算量比较大，SMO算法的核心就是把复杂的式子变换成比较简易的之后，用二次规划来计算。

SMO的基本思路是：先固定 之外的所有参数，然后求 上的极值，由于存在约束 ，如果固定了 之外的其他变量，则能求出 。

那么对偶函数里有两个λ，我们就可以固定这两个λ之外的参数，之后求解 。

其中有一个λ不满足KKT条件，则目标函数就会在迭代后减小，违背程度越大，变量更新后导致的目标函数值就越大。 所以SMO先选取违背KKT条件最大的变量，第二个变量选择使目标函数值见效最快的变量，使选取的两个变量对应样本之间的间隔最大。

然后可以变换为简单的二次规划问题：

找到一组λ后，就可以用原公式求得 的解，决策边界可以表示为：

之后b可以通过 求解。

因为λ通过数值计算得到，因此可能存在误差，则b可能不唯一。通常我们可以用b的 平均值 作为决策边界的参数。

如图所示，这组数据集有两个特征 和一个 标签，我们要对其进行建模分类，可以得到有两个拉格朗日乘子（支持向量上的），其他的均为0.

我们可以得到 有：

第一个 是针对 的参数，以此类推。

有了 ，可以求得 有：

可以根据两个b求平均值，得到b=7.93，因此就能得到分类的模型。

如果需要做预测，把对应点的x向量代入到模型中，求得结果为1的话，就是方形类，其他为圆形类。

上面讨论的模型最终都会生成一条直线，也就是线性的模型，那么往往需要判断非线性的如何处理呢，这里需要引入核函数的技术。

要把SVM应用到非线性决策边界的数据集上，就要把数据集从原来的坐标空间x变换到新的坐标空间中。

我们假定存在一个合适的函数 来变化给定的数据集，那么变换之后，我们就可以根据 来构建线性决策边界（类似于换元法，回忆一下）。变换之后，线性决策边界具有以下的形式：

根据线性SVM的参数计算公式，我们把公式里面的 换成 ，即可求解。

不过这种方式往往会涉及到向量对的点积，计算比较麻烦，当特征数较多时，可能会造成维度灾难的问题，因此我们要引入核函数。

核函数是一种使用原属性集计算变换后的空间中的相似度的方法，简而言之就是，我们如果按照上一段说的算法，则我们需要先计算 ，然后再计算参数，而我们运用核函数，可以直接计算\boldsymbol{x}就可以达到变换属性集的目的。

我们令 ，这样就可以把映射的函数变成了原属性集的计算。 就是核函数。

但是这个 一般我们是不知道的，因此我们要找寻几种通用的函数，让他们可以实现 的功能，以便模拟非线性的决策边界。

这里我们引入一个 Mercer定理 ， 所有的核函数都必须满足Mercer定理。

通常有如下几种核函数：

我们也可以通过核函数的组合来形成新的核函数：

我们直到一般算法都要防止过拟合，防止噪声带来的模型泛化能力下降，那么SVM的防止过拟合方法就是软边缘。

此外，根据KKT条件，可以变换约束如下：

注意，上述三个式子中的 是非零的，当且仅当训练样本位于直线 上或者 。另外对于误分类的训练样本， 都为0.

我们按照正常优化的算法，对 , , 求偏导数，可以得到参数：

代入原公式，可以得到只包括拉格朗日乘子的对偶拉格朗日函数。

这个式子看上去跟不加软边缘的对偶函数是一样的，但是约束是不同的。

软边缘的对偶函数约束为

之后就可以用二次规划或者SOM求参数值了，从而得到模型。

这就是带软边缘的SVM。

以上提到的都是二元分类的办法，那么多分类可以参考常用的多分类处理，用一对一方法，如果有多分类问题，我们可以分解为K（K-1）/2个二类分类器，每一个分类器用来区分一对类 。（注意这里的y都是单独的类，不是一堆类别的集合）

当为 构建分类器时，其他不属于这两类的点都被忽略掉。

之后针对需要预测分类的样本，我们用不同的分类器进行分类，最后进行投票，得到结果。

以上就是SVM（用于分类的支持向量机）的内容，最后看看该算法的特点：

简单的说，支持向量机就是通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。（引自刘知行）

假设给定一个训练数据集。同时，假定已经找到样本空间中的分割平面，其划分公式可以通过以下线性方程来描述： 使用一条直线对线性可分数据集进行分类的过程中，我们已经知道这样的直线可能有很多条：

对于线性可分的正负样本点而言，位于虚线外的点就是正样本点，而位于虚线外的点就是负样本点。另外，正好位于两条虚线上方的样本点就被我们称为支持向量，这也就是支持向量机的名字来源。

对于线性可分数据而言，几何间隔最大的分离超平面是唯一的，这里的间隔也被我们称之为「硬间隔」，而间隔最大化也就称为硬间隔最大化。上图实际上就是硬间隔的典型例子。

最大间隔分离超平面，我们希望最大化超平面关于训练数据集的几何间隔 ，满足以下约束条件：每个训练样本点到超平面的几何间隔至少都是，因此可以转化为以下的约束最优化问题：

实际上， 的取值并不会影响最优化问题的解，同时，我们根据数学对偶性原则，可以得到面向硬间隔的线性可分数据的支持向量机的最优化问题：

我们通常使用拉格朗日乘子法来求解最优化问题，将原始问题转化为对偶问题，通过解对偶问题得到原始问题的解。对公式（3）使用拉格朗日乘子法可得到其「对偶问题」。具体来说，对每条约束添加拉格朗日乘子 ，则该问题的拉格朗日函数可写为：

我们通过将公式（4）分别对和求偏导为 0 并代入原式中，可以将和消去，得到公式（3）的对偶问题：

解出最优解后，基于此我们可以求得最优解 , ，由此得到分离超平面：

使用符号函数求得正负类之间的分类决策函数为：

当数据集变成严格意义上的线性不可分，如下图所示，在实心点和空心点中各混入了零星的不同类别的「噪声」数据点，造成线性不可分的原因往往是因为包含「噪声」数据，它同样可以被看作是不严格条件下的线性可分。

当我们使用支持向量机求解这类问题时，就会把最大间隔称之为最大「软间隔」，而软间隔就意味着可以容许零星噪声数据被误分类。

当出现上图所示的样本点不是严格线性可分的情况时，某些样本点就不能满足函数间隔的约束条件，即公式（3b）中的约束条件。为了解决这个问题，可以对每个样本点引入一个松弛变量 ，使得函数间隔加上松弛变量 ，即约束条件转化为：

同时，对每个松弛变量支付一个代价 ，目标函数由原来的变成：

这里， 称为惩罚参数，一般根据实际情况确定。 值越大对误分类的惩罚增大，最优化问题即为：

这就是软间隔支持向量机的表示过程。同理，我们可以使用拉格朗日乘子法将其转换为对偶问题求解：

解出最优解后，基于此我们可以求得最优解 , ，由此得到分离超平面：

使用符号函数求得正负类之间的分类决策函数为：

对于线性不可分的数据集，我们也可以通过支持向量机去完成分类。但是需要通过一些方法把线性不可分数据转换为线性可分数据之后，再完成分类。

我们把这种数据转换的方法称作「核技巧」，实现数据转换的函数称之为「核函数」 。

核技巧的关键在于空间映射，即将低维数据映射到高维空间中，使得数据集在高维空间能被线性可分。

如上图所示，假设我们在二维空间中有蓝色和红色代表的两类数据点，很明显无法使用一条直线把这两类数据分开。此时，如果我们使用核技巧将其映射到三维空间中，就变成了可以被平面线性可分的状态。

对于「映射」过程，我们还可以这样理解：分布在二维桌面上的红蓝小球无法被线性分开，此时将手掌拍向桌面（好疼），小球在力的作用下跳跃到三维空间中，这也就是一个直观的映射过程。

同时，「映射」的过程也就是通过核函数转换的过程。这里需要补充说明一点，那就是将数据点从低维度空间转换到高维度空间的方法有很多，但往往涉及到庞大的计算量，而数学家们从中发现了几种特殊的函数，这类函数能大大降低计算的复杂度，于是被命名为「核函数」。也就是说，核技巧是一种特殊的「映射」技巧，而核函数是核技巧的实现方法。

此外，核函数还可以通过函数组合得到，例如：

若和是核函数，那么对于任意正数 ，其线性组合：

我们通过直接引入核函数 ，而不需要显式的定义高维特征空间和映射函数，就可以利用解线性分类问题的方法来求解非线性分类问题的支持向量机。引入核函数以后，对偶问题就变为：

同样，解出最优解后，基于此我们可以求得最优解 , ，由此得到分离超平面：

使用符号函数求得正负类之间的分类决策函数为：

主要参数说明：

1.支持向量机（SVM）概述

（1）支持向量机(Support Vector Machines，SVM)是一种二元分类模型，它是一类模型的统称，其中包括：

①线性可分支持向量机；

②线性支持向量机；

③非线性支持向量机。

（2）核心思想：

    训练阶段在特征空间中寻找一个超平面，它能（或尽量能）将训练样本中的正例和负例分离在它的两侧，预测时以该超平面作为决策边界判断输入实例的类别。寻找超平面的原则是，在可分离的情况下使超平面与数据集间隔最大化。

（3）支持向量机的分类示意图为：

简单来说，SVM的原理就是在平面内找到一条直线，使得这两类不同的样本点分开，并且保证能够尽可能远的远离这条直线。用向量表示两类样本点之间的分类间隔(Margin)为：

支持向量机的目的是使r最大，等价于使||w||/2最小。而几何向量使分类间隔最大问题可以转化为运筹学上的约束优化问题。因为涉及太多复杂公式，此处省略。

只要理解了SVM的原理，并且学会利用sklearn库调用SVM模块，就达到了数据分析的目的。

2.SVM算法实现

（1）重要参数说明：

①kernel ：核函数，默认是rbf，可以是‘linear’, ‘poly’, ‘rbf’, ‘sigmoid’, ‘precomputed’ 。

·kernel='linear'时为线性核，C越大分类效果越好，但有可能会过拟合（defaul C=1）；

·kernel='poly'时为多项式核函数；

·kernel='rbf'时（default）为高斯核，gamma值越小，分类界面越连续；gamma值越大，分类界面越“散”，分类效果越好，但有可能会过拟合。

②decision_function_shape：

·decision_function_shape='ovr'时，为one v rest，即一个类别与其他类别进行划分；

·decision_function_shape='ovo'时，为one v one，即将类别两两之间进行划分，用二分类的方法模拟多分类的结果。

（2）程序实现过程：

【注】

在分类型模型评判的指标中，常见的方法有如下三种：

①混淆矩阵（也称误差矩阵，Confusion Matrix）

    混淆矩阵是评判模型结果的指标，属于模型评估的一部分。此外，混淆矩阵多用于判断分类器（Classifier）的优劣，适用于分类型的数据模型，如分类树（Classification Tree）、逻辑回归（Logistic Regression）、线性判别分析（Linear Discriminant Analysis）等方法。

混淆矩阵的一级指标：

通过混淆矩阵可以计算出评估模型的几个指标（二级指标）：

三级指标：F1-score

其中，P代表Precision，R代表Recall。

F1-Score指标综合了Precision与Recall的产出的结果。F1-Score的取值范围从0到1的，1代表模型的输出最好，0代表模型的输出结果最差。

Ps：当分类结果多于两种时，需要将结果转化为上面的类型。

详细内容参考博文https://blog.csdn.net/Orange_Spotty_Cat/article/details/80520839

②ROC曲线

③AUC面积

---