SVM的本质上是一个线性分类器，并且引入了Margin区间的概念，保证Margin最大进而提高模型的准确性。Soft Margin对于SVM改善了模型泛化能力不足的问题，允许噪音、异常点的存在，但本质上仍是处理线性分割的问题。

1.0 使用多项式处理非线性数据

处理非线性数据最典型的思路就是使用多项式的方式：扩充原本数据，制造新的多项式特征。

使用sklearn.datasets中的make_moon数据集，创建经典的月牙形数据：

import numpy as np

import matplotlib.pyplot as plt

from sklearn import datasets

X, y = datasets.make_moons(noise=0.20,random_state=123)

plt.scatter(X[y==0,0], X[y==0,1])

plt.scatter(X[y==1,0], X[y==1,1])

plt.show()

使用多项式特征，建立SVM模型：

from sklearn.preprocessing import PolynomialFeatures, StandardScaler

from sklearn.svm import LinearSVC

from sklearn.pipeline import Pipeline

def PolynomialSVC(degree, C=1.0):

return Pipeline([

("poly", PolynomialFeatures(degree=degree)),

("std_scaler", StandardScaler()),

("linearSVC", LinearSVC(C=C))

])

poly_svc = PolynomialSVC(degree=3)

poly_svc.fit(X, y)

poly_svc的决策边界如下图所示。可以看出，通过多项式的方式使得决策边界不再是一条直线了，而是一条曲线。

对于SVM算法来说，可以不使用多项式PolynomialFeatures的方式，而是使用另一种巧妙的方法实现非线性划分。

2.0 SVM解决非线性问题

2.1 示例1

上图中有两种情况：第一种情况是线性可分的一维数据，可以在红蓝之间找到一个阈值将二者分开，黑色竖线（非0点刻度）就是决策边界，左右距离决策竖线最近的点是支持向量（外面套着圆圈的点）。

第二种情况中，存在红-蓝-红三组数据分布，不存在单一的阈值将三组数据分开。

对于第二种情况，SVM使用了一种非常巧妙的思路：一维空间不能解决，投影到二维空间，是数据的空间分布变成了如下的样子：

$x$ 横坐标是，纵坐标是 $x^2$ ，相当于引入了一个新的维度。此时，就可以用一条线将其分开。

SVM将在原始空间中无法使用线性分类的数据映射到另一空间（Feature Space）当中，使其变得容易划分。

2.2 示例2

在下面的样本数据集中，红色点在中心，蓝色点在四周，所以一条直线是肯定无法分划开的。如果一定要在当前空间将其分开的话，可以找到一个圆圈作为决策边界，将其分离。

同样，通过坐标变化将其映射到新的空间中，也能够得到线性可分的形式。将横坐标变为 $x_1^2$ ，纵坐标变为 $x_2^2$ ，这样数据在空间分布中如下图所示：

可以想象，有一个内功深厚的武林高手，面对桌子上的一堆混在一起的绿豆和红豆（数据点），一掌拍在桌子上，用内力将其逼到空中（从低维空间映射到高维空间），再它们在空中分散的时候（在高维空间上线性可分），然后再一刀将其分开（决策平面）。如下图：

3.0 核函数

核函数指得是一类将数据从原始空间映射到Feature Space中的方法，就可以解决原本的线性不可分问题。一般求解最优化问题中也常用到核函数。

3.1 多项式核函数

一种核函数映射方法:

$\Phi (x)$ 映射方法实际上是将数据维度升上去，映射到一个非常高的维度（大约有 $\frac{m^2}{2}$ 维）。

一般情况下，高维数据的运算是十分复杂的，但SVM算法的精妙之处在于：两个向量做内积运算。这样在原始空间中，两个向量做内积映射到高维空间中则变成 $x_i·x_j=\Phi (x_i)·\Phi (x_j)$ 。展开后相乘得到：

$\Phi (a)·\Phi (b)=1+2\sum_{i=1}^l a_ib_i+\sum_{i=1}^l a_i^2b_i^2+\sum_{i=1}^{l-1}\sum_{j=i+1}^l 2a_i a_jb_ib_j$

数学家们神奇地发现（具体怎么发现的不用知道...），存在这样一个表达式：

这就是SVM中最重要的一个特性，是SVM算法的精妙之处：数学家设计出一种巧妙的数学变换，使高维空间的操作等价于低维空间的操作，解决了高维空间中的计算量问题，大大减少了运算量，这被称为Kernel Trick。

上面的 $K(a,b)$ 就是所谓的多项式核函数。可以拓展为一般形式：

$K(x,y)=(x·y+c)^d$

其中 $d$ 为多项式的阶数，在sklearn中，阶数degree的默认值为3。

3.2 高斯核函数

高斯核函数是SVM算法中使用最多的核函数，也被称作是RBF核（Radial Basis Function Kernel），形式为：

$K(x,y)=e^{-\lambda \vert \vert x-y \vert \vert ^2}$

高斯核函数的 $\gamma$ 与高斯函数（统计学中的正态分布函数）的 $\sigma$ （标准差）成反比，即 $\gamma$ 越大，高斯分布越窄； $\gamma$ 越小，高斯分布越宽。 $\vert \vert x-y \vert \vert ^2$ 表示向量的范数，可以理解为向量的模。

通过一个例子看高斯核函数的作用：

将 $\vert \vert x-y \vert \vert ^2$ 原本的中的 $y$ 替换成两个固定点 $l_1$ 和 $l_2$ ，这两个特殊的点为地标landmark。高斯核函数升维的过程就是对于原本的每个x值，如果有两个landmark的话，就将其升维为二维样本点，每个样本升维后的值是高斯核函数的值： $x\Rightarrow (e^{-\lambda \vert \vert x-l_1 \vert \vert ^2},e^{-\lambda \vert \vert x-l_2 \vert \vert ^2})$ 。通过这样的映射，就可以将线性不可分数据变得线性可分。

对于地标点的选择，若认为 $y$ 地标点，那么对于每一个数据点都是landmark，有多少样本，就有多少地标点，这样就将m*n的数据映射成m*m的数据。

4.0 SVM最终优化函数

SVM本身的优化函数：

$minL_p= \frac{1}{2} w^Tw+C\sum_{1}^l \zeta _i$ $s.t.$ $y_i(w^Tx_i+b)\geq 1-\zeta _i$ ， $\zeta _i\geq 0$

为求解有条件的最优化问题，使用拉格朗日乘数法构造对偶函数：

$maxL_D = \sum_{i}^l a_i-\frac{1}{2} \sum_{i,j}^la_ia_jy_iy_jx_i·x_j$ $s.t.$ $0\leq a_i\leq C$ ， $\sum_{i=1}^la_iy_i=0$

引入核函数变换后的函数形式：

$maxL_K = \sum_{i}^l a_i-\frac{1}{2} \sum_{i,j}^la_ia_jy_iy_jK(x_i,x_j)$ $s.t.$ $0\leq a_i\leq C$ ， $\sum_{i=1}^la_iy_i=0$

其中 $K(x_i,x_j)$ 可以使用不同的核函数代入： $K(x_i,x_j)=(x_i·x_j+1)^d$ 或者 $K(x_i,x_j)=$ $e^{-\lambda \vert \vert x_i-x_j \vert \vert ^2}$

5.0 sklearn中的核函数实现

使用本篇开头时的示例数据（make_moons），建立核函数的SVM模型。

5.1 多项式核函数建立SVM

from sklearn.svm import SVC

def PolynomialKernelSVC(degree, C=1.0):

return Pipeline([

("std_scaler", StandardScaler()),

("kernelSVC", SVC(kernel='poly', degree=degree, C=C))

])

poly_kernel_svc = PolynomialKernelSVC(degree=3)

poly_kernel_svc.fit(X, y)

poly_kernel_svc的决策边界为：

5.1.1 调整参数C

poly_kernel_svc2 = PolynomialKernelSVC(degree=3,C=200)

poly_kernel_svc2.fit(X, y)

poly_kernel_svc2的决策边界如下图。可见参数C越大，中间的“凸起”越尖锐。而参数C是正则化项的系数，C越大，越接近于Hard Margin；C越小，容错性越大。

5.1.2 调整参数degree

poly_kernel_svc3 = PolynomialKernelSVC(degree=4)

poly_kernel_svc3.fit(X, y)

poly_kernel_svc3的决策边界如下图。通过一些尝试发现，degree参数为偶数时，决策边界类似于双曲线的形式，而为奇数时则是以直线为基础。需要注意多项式阶数degree参数越大，则越容易出现过拟合。

5.2 RBF核函数建立SVM

def RBFKernelSVC(gamma=1.0):

return Pipeline([

('std_scaler', StandardScaler()),

('svc', SVC(kernel='rbf', gamma=gamma))

])

rbf_svc = RBFKernelSVC(gamma=1.0)

rbf_svc.fit(X,y)

rbf_svc的决策边界如下，此时KBF中的参数 $\gamma$ 默认为1.0。

5.2.1 调整参数 $\gamma$

rbf_svc2 = RBFKernelSVC(gamma=100)

rbf_svc2.fit(X,y)

rbf_svc2的决策边界如下，可见分类效果非常不好，严重的过拟合。但可以直观看出 $\gamma$ 的作用：已知参数 $\gamma$ 取值越大，意味着高斯函数的“山峰”越窄。对于每个样本点来说，相当于在其周围都形成了一个“山峰”（想象成一个俯视图，蓝色点是“山顶”），以“山峰”比较窄，所以看起来就在每个蓝色点的周围圆环区域就比较小。

由此可见，RBF核函数以该类中的每个点为“山尖”，用gamma参数表示“山峰的粗细”，所有的数据点连成“山脉”，这一区域是一类范围，其他范围都属于另一类。

适当缩小 $\gamma$ 的取值，查看分类效果：

rbf_svc3 = RBFKernelSVC(gamma=10)

rbf_svc3.fit(X,y)

rbf_svc3的决策边界如下，可以看出缩小 $\gamma$ 后，分类效果要平滑很多。

机器学习入门（二十二）——SVM（3）

机器学习入门（二十二）——SVM（3）

1.0 使用多项式处理非线性数据

2.0 SVM解决非线性问题

2.1 示例1

2.2 示例2

3.0 核函数

3.1 多项式核函数

3.2 高斯核函数

4.0 SVM最终优化函数

5.0 sklearn中的核函数实现

5.1 多项式核函数建立SVM

5.1.1 调整参数C

5.1.2 调整参数degree

5.2 RBF核函数建立SVM

5.2.1 调整参数 $\gamma$