支持向量机实现与应用

8486 字 · 466 阅读 · 2023 年 05 月 10 日

本文已更新，你可以访问 AI By Doing 以获得更好的阅读体验。

本篇文章需特别授权许可，内容版权归作者所有，未经授权，禁止转载。

介绍

在前面的文章中，我们对线性分布和非线性分布的数据处理方法进行了简单的介绍和实验操作。当前还有一种机器学习方法，它在解决小样本、非线性及高维模式识别中都表现出了许多独特的优势。同时，其不仅可以应用于线性分布数据，还可以用于非线性分布数据。相比于其他基本机器学习分类算法如逻辑回归、KNN、朴素贝叶斯等，其最终效果的表现一般都会优于这些方法。

知识点

线性分类支持向量机
拉格朗日对偶性
线性支持向量机分类实现
非线性分类支持向量机
核技巧与核函数

线性分类支持向量机

逻辑回归的文章中，我们尝试通过一条直线针对线性可分数据完成分类。同时，实验通过最小化对数损失函数来找到最优分割边界，也就是下图中的紫色直线。

逻辑回归是一种简单高效的线性分类方法。而在这篇文章中，我们将接触到另一种针对线性可分数据进行分类的思路，并把这种方法称之为支持向量机（英语：Support Vector Machine，简称：SVM）。

如果你第一次接触支持向量机这个名字，可能会感觉读起来比较拗口。至少我当年初次接触支持向量机时，完全不知道为什么会有这样一个怪异的名字。假如你和当年的我一样，那么当你看完下面这段介绍内容后，就应该会对支持向量机这个名词有更深刻的认识了。

支持向量机分类特点

假设给定一个训练数据集 $T=\lbrace(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)\rbrace$ 。同时，假定已经找到样本空间中的分割平面，其划分公式可以通过以下线性方程来描述：

$$ wx+b=0$$

使用一条直线对线性可分数据集进行分类的过程中，我们已经知道这样的直线可能有很多条：

问题来了，哪一条直线是最优的划分方法呢？

在逻辑回归中，我们引入了 S 形曲线和对数损失函数进行优化求解。如今，支持向量机给了一种从几何学上更加直观的方法进行求解，如下图所示：

上图展示了支持向量机分类的过程。图中 $wx+b=0$ 为分割直线，我们通过这条直线将数据点分开。与此同时，分割时会在直线的两边再设立两个互相平行的虚线，这两条虚线与分割直线的距离一致。这里的距离往往也被我们称之为「间隔」，而支持向量机的分割特点在于，要使得分割直线和虚线之间的间隔最大化。同时也就是两虚线之间的间隔最大化。

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

支持向量机分类演示

下面，我们使用 Python 代码来演示支持向量机的分类过程。

首先，我们介绍一种新的示例数据生成方法。即通过 scikit-learn 提供的 samples_generator() 类完成。通过 samples_generator() 类下面提供的不同方法，可以产生不同分布状态的示例数据。这篇文章，首先要用到 make_blobs 方法，该方法可以生成团状数据。

from sklearn.datasets import samples_generator
import matplotlib.pyplot as plt
%matplotlib inline

x, y = samples_generator.make_blobs(
    n_samples=60, centers=2, random_state=30, cluster_std=0.8)  # 生成示例数据

plt.figure(figsize=(10, 8))  # 绘图
plt.scatter(x[:, 0], x[:, 1], c=y, s=40, cmap='bwr')

接下来，我们在示例数据中绘制任意 3 条分割线把示例数据分开。

import numpy as np

plt.figure(figsize=(10, 8))
plt.scatter(x[:, 0], x[:, 1], c=y, s=40, cmap='bwr')

# 绘制 3 条不同的分割线
x_temp = np.linspace(0, 6)
for m, b in [(1, -8), (0.5, -6.5), (-0.2, -4.25)]:
    y_temp = m * x_temp + b
    plt.plot(x_temp, y_temp, '-k')

然后，可以使用 fill_between 方法手动绘制出分类间隔。

plt.figure(figsize=(10, 8))
plt.scatter(x[:, 0], x[:, 1], c=y, s=40, cmap='bwr')

# 绘制 3 条不同的分割线
x_temp = np.linspace(0, 6)
for m, b, d in [(1, -8, 0.2), (0.5, -6.5, 0.55), (-0.2, -4.25, 0.75)]:
    y_temp = m * x_temp + b
    plt.plot(x_temp, y_temp, '-k')
    plt.fill_between(x_temp, y_temp - d, y_temp +
                     d, color='#f3e17d', alpha=0.5)

上图为了呈现出分类间隔的效果，手动指定了参数。

从上面的绘图中可以看出，不同的分割线所对应的间隔大小是不一致的，而支持向量机的目标是找到最大的分类间隔所对应的分割线。在这里这个间隔指的是分类点与超平面之间的几何间隔，与此同时如果需要了解支持向量机的求解原理就要引入另一个与之关联的概念：函数间隔。

小贴士

以下支持向量机推导过程比较复杂，可根据自身数学基础尽量掌握，不做强制要求。

函数间隔

一个样本点在支持向量机中是如何进行分类判断的呢？当超平面 $w^{T}x+b=0$ 确定时，样本点到超平面的距离可以用 $|w^{T}x+b|$ 来表示，而通过观察 $w^{T}x+b$ 的符号与样本点的类别 $y$ 符号是否一致来判断分类正确性。

这个过程，可以用公式 $(y-\frac{(m+n)}{2})(w^{T}x +b)$ 的正负性来表示。其中，$m$ 、$n$ 分别为两个样本点类别值，$y$ 为 $m$，$n$ 中任意一个，对于任意点都能用此公式进行分类判断。于是，这里我们便引入了函数间隔的概念。

首先我们定义函数间隔公式，为简化公式这里定义类别 $m=1$，$n=-1$：

$$ h_{1} = y(w^{T}x +b) = yf(x) \tag{1}$$

集合 $T$ 中每个样本点 $(x_i, y_i)$ 关于超平面 $(w, b)$ 都有一个函数间隔，其中最小值便是超平面 $(w, b)$ 关于集合 $T$ 的函数间隔，定义如下：

$$ h_{1} = min\: h_{1i}\: (i=1,2,...,n) \tag{2}$$

所有点到超平面的函数间隔都 $\geq h_{1}$ ，有了最小函数间隔 $h_{1}$ ，那么现在是否可以直接用来确定超平面？当然不行，这里就要提到函数间隔的局限性。

其实到这里你也应该可以看出我们这样定义函数间隔公式的一个问题，当按比例的改变 $w$ 与 $b$ 的值， $f(x)$ 也会成比例的改变大小，但是超平面 $(w, b)$ 却不会改变。支持向量机的机制就是找到最大分类间隔，如果间隔可以任意改变，但超平面却不随之改变，那么这个度量就是没有意义的。

因此仅有函数间隔是不够的，要是能有一个方法对法向量 $w$ 进行约束就好了，恰好前面提到过的几何间隔能帮我们解决这个问题。

几何间隔

我们定义一个点 $x$ ，其到超平面上的垂直映射点为 $x_0$ ，两点之间的距离为 $h$，$w$ 表示超平面的法向量。如下图所示：

根据平面几何知识，有：

$$ x = x_{0}+h\frac{w}{\left \| w \right \|} \tag{3}$$

其中，$\frac{w}{\left | w \right |}$ 不难理解，一个向量除以它的模表示的就是单位向量。此时，对公式两边同时乘以一个 $w$ 得到：

$$ w ^ { T } x = w ^ { T } x _ { 0 } + h \frac { \| w \| ^ { 2 } } { \| w \| } \tag{4}$$

此外，从图中可以看到 $x_0$ 为超平面上的点，满足 $f(x_0)=0$ ，所以带入超平面有 $w^{T}x_0 + b = 0$。最后，带入上面的公式求解距离 $h$ 得到如下结果：

$$ h = \frac{w^{T}x+b}{\left \| w \right \|}=\frac{f(x)}{\left \| w \right \|} \tag{5}$$

上面的公式很好理解，我们都知道在平面中点到直线的距离公式为 $D = \frac{Ax_{0}+By_{0}+C}{\sqrt{A^{2}+B^{2}}}$，当升到更高维度时就与上面一致了。此处为了取得距离 $h$ 的绝对值，需要乘上类别 $y$ ，得到如下结果：

$$ \left | h \right | = yh= \frac{h_{1}}{\left \| w \right \|} \tag{6}$$

从式中可以看到几何间隔中对法向量 $w$ 做了约束，$h_{1}$ 也就是上面我们得出的函数间隔，只是人为定义的一个距离，而几何间隔 $\left | h \right |$ 才是直观上点到超平面的距离，它的取值不会因 $w$ 和 $b$ 缩放而改变，只会随超平面的改变而改变。

通过上面介绍，可以看出函数间隔除以 $\left | w \right |$ 得到的就是几何间隔，而函数间隔的本质其实可以理解为 $\left | f(x) \right |$。

拉格朗日对偶性

在对函数间隔与几何间隔有了一定的了解后，现在我们面临另一个问题，如何求解这个分类间隔最优化问题。

前面提到因为函数间隔 $h_{1}$ 的缩放问题，不适合作为最大化间隔值，从而引入了几何间隔 $h$ 来解决这个问题。所以这里我们可以定义最大化分类间隔的目标函数如下：

$$ max\: \left | h \right |= max\: \frac{h_{1}}{\left \| w \right \|} \tag{7}$$

由于每个点的函数间隔都是大于或等于最小函数间隔，所以同时需要满足以下约束条件：

$$ y_{i}(w^{T}x_{i}+b)\geq h_{1}\: \: (i=1,2,...,n) \tag{8}$$

我们令函数间隔 $h_{1}$ 为 1，得出下面的二次规划问题：

$$ max\: \frac{1}{\left \| w \right \|} \: \: \: \: s.t.\: \: y_{i}(w^{T}x_{i}+b)-1\geq 0\: \: (i=1,2,...,n) \tag{9}$$

二次规划问题中前面为目标函数，$s.t.$ 后面为约束条件。

同时便于后面运算，等价转换目标函数为 $min \frac{1}{2}\left | w \right |^{2}$ ，得到下面的凸二次规划问题：

$$ min\: \frac{1}{2}\left \| w \right \|^{2} \: \: \: \: s.t.\: \: y_{i}(w^{T}x_{i}+b)-1\geq 0\: \: (i=1,2,...,n) \tag{10}$$

故上式表达为：在约束条件 $y_{i}(w^{T}x_{i}+b)-1\geq 0: : (i=1,2,...,n)$ 的情况下，最大化几何间隔 $\frac{1}{\left | w \right |}$ 。

为了公式推导方便，我们直接「令函数间隔 $h_{1}$ 为 1」，来得到二次规划问题的表达式。那么，这样做会不会影响了后续运算的结果呢？

首先，简单点可以通过函数间隔的性质来理解，前面提到过函数间隔是可以任意伸缩的；其次，也可以通过换元方法来理解，将 $w$ 换为 $\frac{w}{h_{1}}$ ， $b$ 换为 $\frac{b}{h_{1}}$ ， $h_{1}$ 自然就是 1。同样，需要将目标函数替换。

目前我们已经得到了支持向量机凸二次规划问题的表达式，接下来就可以求解了。对于这样特殊形式的结构，通常的做法是使用拉格朗日对偶性将原始问题转变为其对偶问题，即通过求解与原始问题等价的对偶问题得到原始问题的最优解。通过这种方法会使得原始问题更容易求解，以及后续更自然的引入核函数求解非线性问题。

在满足条件的情况下，拉格朗日对偶性通过给每一个约束条件加上一个拉格朗日乘子 $\lambda $，将约束条件融合到目标函数中，仅通过一个函数表达出问题。所以上面的凸二次规划问题转换如下：

$$ L(\lambda ,w,b)=\frac{1}{2}\left \| w \right \|^{2}-\sum_{i=1}^{n}\lambda_{i}(y_{i}(w^{T}x_{i}+b)-1) \tag{11}$$

现在问题就得到了简化，我们只需要最大化 $L$ 即可：

$$ \theta (w)=max\: L(\lambda ,w,b)\: \: \: \: \lambda_{i}\geq 0 \tag{12}$$

上面的融合目标函数是如何等价解决我们问题的呢？

当某个约束条件不满足，也就是函数间隔小于 1 时只要 $\lambda_{i}$ 定义足够大， $L$ 就趋近无穷。而当所有约束条件都满足时，则最优值表示为 $\frac{1}{2}\left | w \right |^{2}$ ，也就是最初我们需要最小化的量。因为当 $x_{i}$ 为支持向量时 $(y_{i}(w^{T}x_{i}+b)-1)=0$，此时最优值为 $\frac{1}{2}\left | w \right |^{2}$ ；当 $x_{i}$ 为非支持向量时，函数间隔必定大于 1，且 $\lambda_{i}$ 取值非负，为了满足最大化， $\lambda_{i}$ 必须等于 0，此时的最优值依旧是 $\frac{1}{2}\left | w \right |^{2}$ 。

其实，通过上面的解释还能发现一些很有趣的结论，就是在满足约束条件时非支持向量的 $\lambda$ 都等于 0，后面整体为 0；而支持向量的 $\lambda$ 虽然有无数个取值，但是由于函数间隔等于 1，因此后面整体取值依旧为 0 。

通过一系列的等价转换后，现在我们可以归纳目标函数，如下：

$$ min_{(w,b)}\, max_{(\lambda \geq 0)}\, L(\lambda ,w,b) = p^{*} \tag{13}$$

若此时直接对目标函数求解并不是那么容易的，因为此时 $\lambda$ 为不等式的约束，我们还的面对 $w$，$b$ 两个参数，所以通常的做法是转换为对偶问题，将最大最小优化的位置进行交换：

$$ max_{(\lambda \geq 0)}\, min_{(w,b)}\, L(\lambda ,w,b) = d^{*} \tag{14}$$

当然公式并不能随意交换位置，需要满足一定条件。当原始问题与对偶问题都有最优解时，可以得到：

$$ d^{*}=max_{(\lambda \geq 0)}\, min_{(w,b)}\, L(\lambda ,w,b)\leq min_{(w,b)}\, max_{(\lambda \geq 0)}\, L(\lambda ,w,b) = p^{*} \tag{15}$$

对于所有的优化问题如上公式都成立，即使原始问题非凸，这个性质叫做弱对偶性，当然与之对应的就有强对偶性，强对偶需满足：

$$ d^{*}=p^{*} \tag{16}$$

在支持向量机中满足 Slater 条件与 KKT 条件后，我们直接假定强对偶性成立，通过求解对偶问题来得到原始问题的解。在验证满足条件之后我们就可以对第二个公式的最优值 $d^{*}$ 进行求解了。

对偶问题求解

关于 $d^{*}$ 的求解我们可以分为两个部分展开，但是由于需要有较强的逻辑性以及对数学知识有较强的功底，因此这部分不做要求。其实了解了上面介绍的三个内容后你应该对支持向量机数学原理有了不错的掌握。

在固定 $\lambda $ 的前提下，对 $w$ 和 $b$ 进行求偏导处理，使得 $L$ 关于 $w$，$b$ 最小化，并将导数设为 0，可以得到：

$$ \bigtriangledown _{w}L(\lambda ,w,b)=w-\sum_{i=1}^{n}\lambda_{i}y_{i}x_{i}=0 \tag{17}$$

$$ \bigtriangledown _{b}L(\lambda ,w,b) = \sum_{i=1}^{n}\lambda_{i}y_{i}=0 \tag{18}$$

现在将两个式子代入到上面的 $L$ 中就可以得到最终的公式：

$$ L(\lambda ,w,b)=\sum_{i=1}^{n}\lambda_{i}-\frac{1}{2}\sum_{i,j=1}^{n}\lambda_{i}\lambda_{j}y_{i}y_{j}x_{i}^{T}x_{j} \tag{19}$$

所以现在我们的问题就变成了该对偶形式：

$$ max_{(\lambda )}\: \sum_{i=1}^{n}\lambda_{i}-\frac{1}{2}\sum_{i,j=1}^{n}\lambda_{i}\lambda_{j}y_{i}y_{j}x_{i}^{T}x_{j} \tag{20}$$

$$ s.t.\: \:\sum_{i=1}^{n}\lambda_{i}y_{i}\: \: \: \: \lambda_{i}\geq 0,\: \: i=1,2,...,n$$

目前，问题中只有 $\lambda$ 一个变量，接下来就可以使用序列最小优化算法针对这个拉格朗日乘子进行求解了。

序列最小优化算法（Sequential minimal optimization，SMO）由微软研究院的约翰·普莱特于 1998 年发明，目前被广泛使用于 SVM 的训练过程中。先前可用的 SVM 训练方法必须使用复杂的方法计算量大，并需要昂贵的第三方二次规划工具。而 SMO 算法则较好地避免了这一问题。

简单理解它的思路就是通过一次迭代只优化两个变量而固定剩余的变量。从而将一个大的优化问题分解为若干个小的优化问题，而这些小的优化问题往往更容易求解。

虽然序列最小化算法在支持向量机求解中发挥了强大的作用，但同时带来的就是相对于第一步更为复杂的数学推导。于此，文章中将不再对其进行大篇幅的描述，有一定数学功底和想深入的同学可以自行查阅相关资料或参考这篇文章给出的链接学习。

线性支持向量机分类实现

上面，我们对支持向量机中函数间隔、几何间隔和运用拉格朗日对偶性求解的过程进行了推演，推导过程由简单到复杂因此不需要全部掌握，但至少要知道函数间隔与几何间隔在支持向量机中的意义。

接下来，我们就使用 Python 对支持向量机找寻最大间隔的过程进行实战。由于支持向量机纯 Python 实现太过复杂，所以这篇文章直接使用 scikit-learn 完成。

scikit-learn 中的支持向量机分类器对应的类及参数为：

sklearn.svm.SVC(C=1.0, kernel='rbf', degree=3, gamma='auto', coef0=0.0, shrinking=True, probability=False, tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, decision_function_shape='ovr', random_state=None)

主要的参数如下：

C: 支持向量机中对应的惩罚参数。
kernel: 核函数，linear, poly, rbf, sigmoid, precomputed 可选，下文详细介绍。
degree: poly 多项式核函数的指数。
tol: 收敛停止的容许值。

如下图所示，支持向量机中当训练数据集并非完全线性可分时，这样在保证每个点都被正确分开后会造成过拟合，为了解决过拟合问题，引入惩罚因子 $\xi$，可以看作上面的参数 C ，允许少部分的点出错。在训练集不完全线性可分情况下，我们就要使几何间隔尽可能的大，同时使误分类点的个数尽量小，C 则是调合二者的系数。

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

这里，我们还是使用上面生成的示例数据训练支持向量机模型。由于是线性可分数据，kernel 参数指定为 linear 即可。

首先，训练支持向量机线性分类模型：

from sklearn.svm import SVC

linear_svc = SVC(kernel='linear')
linear_svc.fit(x, y)

对于训练完成的模型，我们可以通过 support_vectors_ 属性输出它对应的支持向量：

linear_svc.support_vectors_

可以看到，一共有 3 个支持向量。如果你输出 $x, y$ 的坐标值，就能看到这 3 个支持向量所对应的数据。

接下来，我们可以使用 Matplotlib 绘制出训练完成的支持向量机对于的分割线和间隔。为了方便后文重复使用，这里将绘图操作写入到 svc_plot() 函数中：

def svc_plot(model):

    # 获取到当前 Axes 子图数据，并为绘制分割线做准备
    ax = plt.gca()
    x = np.linspace(ax.get_xlim()[0], ax.get_xlim()[1], 50)
    y = np.linspace(ax.get_ylim()[0], ax.get_ylim()[1], 50)
    Y, X = np.meshgrid(y, x)
    xy = np.vstack([X.ravel(), Y.ravel()]).T
    P = model.decision_function(xy).reshape(X.shape)

    # 使用轮廓线方法绘制分割线
    ax.contour(X, Y, P, colors='green', levels=[-1, 0, 1], linestyles=['--', '-', '--'])

    # 标记出支持向量的位置
    ax.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], c='green', s=100)

# 绘制最大间隔支持向量图
plt.figure(figsize=(10, 8))
plt.scatter(x[:, 0], x[:, 1], c=y, s=40, cmap='bwr')
svc_plot(linear_svc)

如上图所示，绿色实线代表最终找到的分割线，绿色虚线之间的间隔也就是最大间隔。同时，绿色实心点即代表 3 个支持向量的位置。

上面的数据点可以被线性可分。那么，如果我们加入噪声使得数据集变成不完美线性可分，结果会怎么样呢？

接下来，我们就来处理有噪声点时支持向量机的分类过程：

# 向原数据集中加入噪声点
x = np.concatenate((x, np.array([[3, -4], [4, -3.8], [2.5, -6.3], [3.3, -5.8]])))
y = np.concatenate((y, np.array([1, 1, 0, 0])))

plt.figure(figsize=(10, 8))
plt.scatter(x[:, 0], x[:, 1], c=y, s=40, cmap='bwr')

可以看到，此时的红蓝数据团中各混入了两个噪声点。

训练此时支持向量机模型并绘制成分割线和最大间隔：

linear_svc.fit(x, y) # 训练

plt.figure(figsize=(10, 8))
plt.scatter(x[:, 0], x[:, 1], c=y, s=40, cmap='bwr')
svc_plot(linear_svc)

由于噪声点的混入，此时支持向量的数量由原来的 3 个变成了 11 个。

前面的文章中，我们提到了惩罚系数 $C$，下面可以通过更改 $C$ 的取值来观察支持向量的变化过程。与此同时，我们要引入一个可以在 Notebook 中实现交互操作的模块。你可以通过选择不同的 $C$ 查看最终绘图的效果。

from ipywidgets import interact
import ipywidgets as widgets

def change_c(c):
    linear_svc.C = c
    linear_svc.fit(x, y)
    plt.figure(figsize=(10, 8))
    plt.scatter(x[:, 0], x[:, 1], c=y, s=40, cmap='bwr')
    svc_plot(linear_svc)

interact(change_c, c=[1, 10000, 1000000])

非线性分类支持向量机

上面的内容中，我们假设样本是线性可分或不严格线性可分，然后通过建立两种情况下的支持向量机实现样本分类。然而，线性可分的样本往往只是理想情况，现实中的原始样本大多数情况下是线性不可分。此时，还能用支持向量机吗？

还记得之前对处理偶问题提到的核函数吗？其实，对于线性不可分的数据集，我们也可以通过支持向量机去完成分类。但是，这里需要增加一个技巧把线性不可分数据转换为线性可分数据之后，再完成分类。

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

小贴士

核技巧是一种数学方法，这篇文章仅针对于其在支持向量机中的应用场景进行讲解。

核技巧与核函数

根据上面的介绍，我们提到一个思路就是核技巧，即先把线性不可分数据转换为线性可分数据，然后再使用支持向量机去完成分类。那么，具体是怎样操作呢？

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

上面这句话不太好理解，我们通过一个比喻来介绍：

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

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

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

下面，我们就认识几种常见的核函数：

线性核函数：

$$ k\left ( x_i, x_j \right )=x_i*x_j \tag{21}$$

多项式核函数：

$$ k\left ( x_i, x_j \right )=\left ( x_i*x_j \right )^d, d \geq 1\tag{22}$$

高斯径向基核函数：

$$ k\left(x_{i}, x_{j}\right)=\exp \left(-\frac{\left\|\mathbf{x}_{\mathrm{i}}-\mathbf{x}_{\mathrm{j}}\right\|_{2}^{2}}{2 \sigma^{2}}\right)=\exp \left(-\gamma *\left\|x_{i}-x_{j}\right\|_{2}^{2}\right), \gamma>0 \tag{23}$$

Sigmoid 核函数：

$$ k\left(x_{i}, x_{j}\right)=\tanh \left(\beta * x_{i} x_{j}+\theta\right), \beta>0, \theta<0 \tag{24}$$

这 4 个核函数也就分别对应着上文介绍 scikit-learn 中 SVC 方法中 kernel 参数的 linear, poly, rbf, sigmoid 等 4 种不同取值。

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

若 $k_1$ 和 $k_2$ 是核函数，那么对于任意正数 $\lambda_1,\lambda_2$，其线性组合：

$$ \lambda_1 k_1+\lambda_2 k_2 \tag{25}$$

引入核函数的间隔表示及求解

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

$$ \max\limits_{\lambda } \sum\limits_{i=1}^{N}\lambda _i - \frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\lambda_i\lambda_jy_iy_jk(x_i*x_j) \tag{26}$$

$$ s.t. \sum\limits_{i=1}^{N}\lambda_iy_i=0$$

$$ 0 \leq \lambda_i \leq C ,i=1,2,...,N$$

上面公式中可以看到引入惩罚系数后与原目标函数形式相同，唯一不同就在于 $\lambda_{i}$ 的范围。

同样，通过前面的对偶问题求解得出最优解 $\lambda^{}=\left(\lambda_{1}^{}, \lambda_{2}^{}, \ldots, \lambda_{N}^{}\right)$ 后，基于此我们可以求得最优解 $w^{}$, $b^{}$，由此得到分离超平面：

$$ w^{*}x+b^{*}=0 \tag{27}$$

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

$$ f(x)=sign(w^{*}x+b^{*}) \tag{28}$$

非线性支持向量机分类实现

同样，我们使用 scikit-learn 中提供的 SVC 类来构建非线性支持向量机模型，并绘制决策边界。

首先，实验需要生成一组示例数据。上面我们使用了 make_blobs 生成一组线性可分数据，这里使用 make_circles 生成一组线性不可分数据。

x2, y2 = samples_generator.make_circles(150, factor=.5, noise=.1, random_state=30) # 生成示例数据

plt.figure(figsize=(8, 8)) # 绘图
plt.scatter(x2[:, 0], x2[:, 1], c=y2, s=40, cmap='bwr')

上图明显是一组线性不可分数据，当我们训练支持向量机模型时就需要引入核技巧。例如，我们这里使用下式做一个简单的非线性映射：

$$ k\left ( x_i, x_j \right )=x_i^2 + x_j^2 \tag{29}$$

def kernel_function(xi, xj):
    poly = xi**2 + xj**2
    return poly

from mpl_toolkits import mplot3d
from ipywidgets import interact, fixed

r = kernel_function(x2[:,0], x2[:,1])
plt.figure(figsize=(10, 8))
ax = plt.subplot(projection='3d')
ax.scatter3D(x2[:, 0], x2[:, 1], r, c=y2, s=40, cmap='bwr')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('r')

上面展示了二维空间点映射到效果维空间的效果。接下来，我们使用 sklearn 中 SVC 方法提供的 RBF 高斯径向基核函数完成实验。

rbf_svc = SVC(kernel='rbf', gamma='auto')
rbf_svc.fit(x2, y2)

plt.figure(figsize=(8, 8))
plt.scatter(x2[:, 0], x2[:, 1], c=y2, s=40, cmap='bwr')

svc_plot(rbf_svc)

同样，我们可以挑战不同的惩罚系数 $C$，看一看决策边界和支持向量的变化情况：

def change_c(c):
    rbf_svc.C = c
    rbf_svc.fit(x2, y2)
    plt.figure(figsize=(8, 8))
    plt.scatter(x2[:, 0], x2[:, 1], c=y2, s=40, cmap='bwr')
    svc_plot(rbf_svc)

interact(change_c, c=[1, 100, 10000])

多分类支持向量机

支持向量机最初是为二分类问题设计的，当我们面对多分类问题时，其实同样可以使用支持向量机解决。而解决的方法就是通过组合多个二分类器来实现多分类器的构造。根据构造的方式又分为 2 种方法：

一对多法：即训练时依次把某个类别的样本归为一类，剩余的样本归为另一类，这样 $k$ 个类别的样本就构造出了 $k$ 个支持向量机。
一对一法：即在任意两类样本之间构造一个支持向量机，因此 $k$ 个类别的样本就需要设计 $k(k-1) \div 2$ 个支持向量机。

而在 scikit-learn，实现多分类支持向量机通过设定参数 decision_function_shape 来确定，其中：

decision_function_shape='ovo'：代表一对一法。
decision_function_shape='ovr'：代表一对多法。

由于这里只需要修改参数，所以就不再赘述了。

最后，我们总结一下 SVM 的优点和缺点。首先，SVM 是一种表现非常不错的方法，尤其是对于非线性分类问题。而且最大的劣势在于计算效率，随着数据集的增大，计算时间陡增。所以，一般我们会在小数据集下应用 SVM，而大数据集基本不予考虑。

小结

在这篇文章中，我们了解了什么是支持向量机，并探索了函数间隔、几何间隔、拉格朗日对偶性以及核函数特点及使用方法。在机器学习领域众所周知，支持向量机是一个很容易理解，但却很难深入的算法，尽管文章中尽量给出了由简入深的部分数学原理，但这篇文章还是建议只掌握 scikit-learn 中 SVC 类的使用方法即可。当然，对于数学基础比较好的同学，可以尝试自行推导 SVM 的实现过程。

系列文章

本篇文章需特别授权许可，内容版权归作者所有，未经授权，禁止转载。

BY-ND 4.0

△