189 8069 5689
09 SVM - 线性不可分模型
创新互联建站是一家从事企业网站建设、网站制作、成都网站设计、行业门户网站建设、网页设计制作的专业的建站公司，拥有经验丰富的网站建设工程师和网页设计人员，具备各种规模与类型网站建设的实力，在网站建设领域树立了自己独特的设计风格。自公司成立以来曾独立设计制作的站点近1000家。
假设： 函数Ф是一个从低维特征空间到高维特征空间的一个映射，那么如果存在函数K(x,z), 对于任意的低维特征向量x和z，都有：
称函数K(x,z)为核函数(kernal function)；
核函数在解决线性不可分问题的时候，采取的方式是：使用低维特征空间上的计算来避免在高维特征空间中向量内积的恐怖计算量；也就是说此时SVM模型可以应用在高维特征空间中数据可线性分割的优点，同时又避免了引入这个高维特征空间恐怖的内积计算量。
本质： 核函数是一个低纬的计算结果，并没有采用低纬到高维的映射。只不过核函数低纬运算的结果 等价于 映射到高维时向量点积的值。
不妨还是从最开始的简单例子出发，设两个向量x 1 = (μ 1 + μ 2 ) T 和x 2 = (η 1 + η 2 ) T ，两个向量的点积是五维空间的映射，因此映射过后的内积为：
而同时我们可以发现有以下公式：
可以发现两者之间非常相似，所以我们只要乘上一个相关的系数，就可以让这两个式子的值相等，这样不就将五维空间的一个内积转换为两维空间的内积的运算。
现有有两个两维的向量，进行二阶多项式扩展，然后进行内积计算，这个时候映射高高维后计算的计算量为：11次乘法+4次加法；采用近似计算的计算量为：3次乘法+2次加法；采用加系数后的近似计算的计算量为：4次乘法+2次加法；
线性核函数(Linear Kernel): 即原函数，不做映射。
多项式核函数(Polynomial Kernel)：其中γ、r、d属于超参，需要调参定义；
类似上面的函数，上面的0.8476是调参出来的结果。
重点：
高斯核函数(Gaussian Kernel)： 其中γ属于超参，要求大于0，需要调参定义；
高斯核在实际运用中特别多 ，不仅仅是因为需要调的参数比较少。
最重要的原因是：
在sklearn中，核函数是rbf，即Radial basis functionfuntion 径向基 ；其中真正用到的核函数算法是高斯核。
PS：之前在讲加权线性回归中提过相似度的度量，其中用到的就是类似高斯核的函数。
Sigmoid核函数(Sigmoid Kernel)：其中γ、r属于超参，需要调参定义；
了解即可，这个核函数别去用它，垃圾得一塌糊涂。
该算法大致上就是把Sigmoid函数变成了tan函数。
将原始数据映射到高维，然后找一个超曲面来分割它们。差不多就是我上一章一开始画的那个图。
1、 核函数可以自定义；核函数必须是正定核函数，即Gram矩阵是半正定矩阵；
2、核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算；
3、 通过核函数，可以将非线性可分的数据转换为线性可分数据；
令z=x；那么进行多维变换后，应该是同一个向量，从而可以得到以下公式：
了解核函数的构造方式，尤其是高斯核。
11 SVM - 序列最小优化算法 SMO
我先直观地阐述我对SVM的理解，这其中不会涉及数学公式，然后给出Python代码。
SVM是一种二分类模型，处理的数据可以分为三类：
线性可分，通过硬间隔最大化，学习线性分类器
近似线性可分，通过软间隔最大化，学习线性分类器
线性不可分，通过核函数以及软间隔最大化，学习非线性分类器
线性分类器，在平面上对应直线；非线性分类器，在平面上对应曲线。
硬间隔对应于线性可分数据集，可以将所有样本正确分类，也正因为如此，受噪声样本影响很大，不推荐。
软间隔对应于通常情况下的数据集（近似线性可分或线性不可分），允许一些超平面附近的样本被错误分类，从而提升了泛化性能。
如下图：
实线是由硬间隔最大化得到的，预测能力显然不及由软间隔最大化得到的虚线。
对于线性不可分的数据集，如下图：
我们直观上觉得这时线性分类器，也就是直线，不能很好的分开红点和蓝点。
但是可以用一个介于红点与蓝点之间的类似圆的曲线将二者分开，如下图：
我们假设这个黄色的曲线就是圆，不妨设其方程为x^2+y^2=1，那么核函数是干什么的呢？
我们将x^2映射为X，y^2映射为Y，那么超平面变成了X+Y=1。
那么原空间的线性不可分问题，就变成了新空间的（近似）线性可分问题。
此时就可以运用处理（近似）线性可分问题的方法去解决线性不可分数据集的分类问题。
---------------------------------------------------------------------------------------------------------------------------
以上我用最简单的语言粗略地解释了SVM，没有用到任何数学知识。但是没有数学，就体会不到SVM的精髓。因此接下来我会用尽量简洁的语言叙述SVM的数学思想，如果没有看过SVM推导过程的朋友完全可以跳过下面这段。
对于求解（近似）线性可分问题：
由最大间隔法，得到凸二次规划问题，这类问题是有最优解的（理论上可以直接调用二次规划计算包，得出最优解）
我们得到以上凸优化问题的对偶问题，一是因为对偶问题更容易求解，二是引入核函数，推广到非线性问题。
求解对偶问题得到原始问题的解，进而确定分离超平面和分类决策函数。由于对偶问题里目标函数和分类决策函数只涉及实例与实例之间的内积，即xi,xj。我们引入核函数的概念。
拓展到求解线性不可分问题：
如之前的例子，对于线性不可分的数据集的任意两个实例：xi,xj。当我们取某个特定映射f之后，f(xi)与f(xj)在高维空间中线性可分，运用上述的求解（近似）线性可分问题的方法，我们看到目标函数和分类决策函数只涉及内积f(xi),f(xj)。由于高维空间中的内积计算非常复杂，我们可以引入核函数K(xi,xj)=f(xi),f(xj)，因此内积问题变成了求函数值问题。最有趣的是，我们根本不需要知道映射f。精彩！
我不准备在这里放推导过程，因为已经有很多非常好的学习资料，如果有兴趣，可以看：CS229 Lecture notes
最后就是SMO算法求解SVM问题，有兴趣的话直接看作者论文：Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines
我直接给出代码：SMO+SVM
在线性可分数据集上运行结果：
图中标出了支持向量这个非常完美，支持向量都在超平面附近。
在线性不可分数据集上运行结果（200个样本）：
核函数用了高斯核，取了不同的sigma
sigma=1，有189个支持向量，相当于用整个数据集进行分类。
sigma=10，有20个支持向量，边界曲线能较好的拟合数据集特点。
我们可以看到，当支持向量太少，可能会得到很差的决策边界。如果支持向量太多，就相当于每次都利用整个数据集进行分类，类似KNN。
SVM 是 Support Vector Machine 的简称，它的中文名为支持向量机，属于一种有监督的机器学习算法，可用于离散因变量的分类和连续因变量的预测。通常情况下，该算法相对于其他单一的分类算法（如 Logistic 回归、决策树、朴素贝叶斯、 KNN 等）会有更好的预测准确率，主要是因为它可以将低维线性不可分的空间转换为高维的线性可分空间。
“分割带”代表了模型划分样本点的能力或可信度，“分割带”越宽，说明模型能够将样本点划分得越清晰，进而保证模型泛化能力越强，分类的可信度越高；反之，“分割带”越窄，说明模型的准确率越容易受到异常点的影响，进而理解为模型的预测能力越弱，分类的可信度越低。
线性可分的 所对应的函数间隔满足 的条件，故 就等于 。所以，可以将目标函数 等价为如下的表达式：
假设存在一个需要最小化的目标函数 ，并且该目标函数同时受到 的约束。如需得到最优化的解，则需要利用拉格朗日对偶性将原始的最优化问题转换为对偶问题，即：
分割面的求解
分割面的表达式
对于非线性SVM模型而言，需要经过两个步骤，一个是将原始空间中的样本点映射到高维的新空间中，另一个是在新空间中寻找一个用于识别各类别样本点线性“超平面”。
假设原始空间中的样本点为 ，将样本通过某种转换 映射到高维空间中，则非线性SVM模型的目标函数可以表示为：
其中，内积 可以利用核函数替换，即 。对于上式而言，同样需要计算最优的拉格朗日乘积 ，进而可以得到线性“超平面” 与 的值：
假设原始空间中的两个样本点为 ，在其扩展到高维空间后，它们的内积 如果等于样本点 在原始空间中某个函数的输出，那么该函数就称为核函数。
线性核函数的表达式为 ，故对应的分割“超平面”为：
多项式核函数的表达式为 ，故对应的分割“超平面”为：
高斯核函数的表达式为 ，故对应的分割“超平面”为：
Sigmoid 核函数的表达式为 ，故对应的分割“超平面”为：
在实际应用中， SVM 模型对核函数的选择是非常敏感的，所以需要通过先验的领域知识或者交叉验证的方法选出合理的核函数。大多数情况下，选择高斯核函数是一种相对偷懒而有效的方法，因为高斯核是一种指数函数，它的泰勒展开式可以是无穷维的，即相当于把原始样本点映射到高维空间中。
output_13_0.png