情景：小样本、非线性及高纬模式识别，不仅可以应用于线性分布数据，还可以用于非线性分布数据

一、支持向量机

---

（1）什么是支持向量机？

支持向量机（Support vector machine，SVM）：一种针对线性可分数据进行分类的思路。
（PS：逻辑回归是一种简单高效的线性分类方法）

在逻辑回归中，我们通常找到一条直线对线性可分数据集进行分类，如下图
$$wx+b=0\text{\hspace{1em}(1)}$$

可这样，问题来了，哪一条才是最优的划分方法？

在逻辑回归中，引入S 形曲线和对数损失函数进行优化求解。

支持向量机则在几何学上以更加直观的方法进行求解，如下图：

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

目标： 找到最大的分类硬间隔所对应的分割线

（2）支持向量机分类演示

使用 scikit-learn 提供的 samples_generator()
samples_generator() 可产生不同分布状态的示例数据

# 导包
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

# 使用 samples_generator 生成分类数据
from sklearn.datasets import samples_generator
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 根线

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,b)$ 关于训练数据集的几何间隔 $\gamma$，满足以下约束条件：每个训练样本点到超平面 $(w,b)$ 的几何间隔至少都是 $\gamma$ ，因此可以转化为以下的约束最优化问题：

$$\underset{w,b}{\max }\gamma =\frac{2}{\Vert w\Vert }\text{\hspace{1em}(2a)}$$

$$\text{s}.t.y_i(\frac{w}{\Vert w\Vert }{x}_i+\frac{b}{\Vert w\Vert })\ge \frac{\gamma }{2}\text{\hspace{1em}(2b)}$$

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

$$\underset{w,b}{\min }\frac{1}{2}{\Vert w\Vert }^2\text{\hspace{1em}(3a)}$$

$$\text{s}.t.y_i(w{x}_i+b)-1\ge 0\text{\hspace{1em}(3b)}$$

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

$$L(w,b,\alpha )=\frac{1}{2}{\Vert w\Vert }^2+\sum _{i=1}^m{\alpha }_i(1-y_i(w{x}_i+b))\text{\hspace{1em}(4)}$$

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

$$\underset{\alpha }{\max }\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i{x}_j\text{\hspace{1em}(5a)}$$

$$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0,\text{\hspace{1em}(5b)}$$

$${\alpha }_i\ge 0,i=1,2,\cdots ,N\text{\hspace{1em}(5c)}$$

解出最优解 ${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_N^{\ast })$ 后，基于此我们可以求得最优解 $w^{\ast }$, $b^{\ast }$，由此得到分离超平面：

$$w^{\ast }x+b^{\ast }=0\text{\hspace{1em}(6)}$$

使用符号函数求得正负类之间的分类决策函数为：
$$f(x)=sign(w^{\ast }x+b^{\ast })\text{\hspace{1em}(7)}$$

三、软间隔表示及求解

---

实际情况，可能会遇到 在实心点和空心点中各混入了零星的不同类别的数据点。

对于这种情况，数据集就变成了严格意义上的线性不可分。

但是，造成这种线性不可分的原因往往是因为包含「噪声」数据，它同样可以被看作是不严格条件下的线性可分。

这时候使用 「软间隔」，即可以容忍零星噪声数据被误分类

当出现上图所示的样本点不是严格线性可分的情况时，某些样本点 $(x_i,y_i)$ 就不能满足函数间隔 $⩾1$ 的约束条件，即公式（3b）中的约束条件。为了解决这个问题，可以对每个样本点 $(x_i,y_i)$ 引入一个松弛变量 ${\xi }_i\ge 0$，使得函数间隔加上松弛变量 $⩾1$，即约束条件转化为：
$$y_i(w{x}_i+b)\ge 1-{\xi }_i\text{\hspace{1em}(8)}$$

同时，对每个松弛变量 ${\xi }_i$ 支付一个代价 ${\xi }_i$，目标函数由原来的 $\frac{1}{2}||w|{|}^2$ 变成：

$$\frac{1}{2}{\Vert w\Vert }^2+C\sum _{j=1}^N{\xi }_i\text{\hspace{1em}(9)}$$

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

$$\underset{w,b,\xi }{\min }\frac{1}{2}{\Vert w\Vert }^2+C\sum _{i=1}^N{\xi }_i\text{\hspace{1em}(10a)}$$

$$s.t.y_i(w{x}_i+b)\ge 1-{\xi }_i,i=1,2,...,N\text{\hspace{1em}(10b)}$$

$${\xi }_i\ge 0,i=1,2,...,N\text{\hspace{1em}(10c)}$$

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

$$\underset{\alpha }{\max }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\ast x_j)-\sum _{i=1}^N{\alpha }_i\text{\hspace{1em}(11a)}$$

$$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0\text{\hspace{1em}(11b)}$$

$$0\le {\alpha }_i\le C,i=1,2,...,N\text{\hspace{1em}(11c)}$$

解出最优解 ${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_N^{\ast })$ 后，基于此我们可以求得最优解 $w^{\ast }$, $b^{\ast }$，由此得到分离超平面：

$$w^{\ast }x+b^{\ast }=0\text{\hspace{1em}(12)}$$

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

$$f(x)=sign(w^{\ast }x+b^{\ast })\text{\hspace{1em}(13)}$$

四、非线性分类支持向量机

---

上面方式应用场景是在 线性可分 或 不严格线性可分 情况下。

然而，线性可分的样本往往只是理想情况下，现实中的原始样本大多数情况下是线性不可分。

这时候，支持向量机还能进行分类吗？

步骤：

1. 将线性不可分数据转换为线性可分数据
2. 再对线性可分数据进行划分

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

（1） 核技巧与核函数

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

如下图所示：

在二维空间，明显无法使用一条直线把两类数据分开。

此时，使用 核技巧 将其映射到三维空间，就变成了可以被平面线性可分的状态。

「映射」的过程也就是通过核函数转换的过程

以下为常见的核函数：

线性核函数

$$k\left(x_i,x_j\right)=x_i\ast x_j\text{\hspace{1em}(1)}$$

多项式核函数

$$k\left(x_i,x_j\right)={\left(x_i\ast x_j\right)}^d,d\ge 1\text{\hspace{1em}(2)}$$

高斯径向基核函数

$$k\left(x_i,x_j\right)=\exp \left(-\frac{{\Vert {\mathbf{x}}_{\mathbf{i}}-{\mathbf{x}}_{\mathbf{j}}\Vert }_2^2}{2{\sigma }^2}\right)=exp\left(-\gamma \ast {\Vert x_i-x_j\Vert }_2^2\right),\gamma >0\text{\hspace{1em}(16)}$$

Sigmoid 核函数

$$k\left(x_i,x_j\right)=tanh\left(\beta \ast x_i{x}_j+\theta \right),\beta >0,\theta <0\text{\hspace{1em}(17)}$$

（2） 多分类支持向量机

支持向量机最初是为二分类问题设计

• 一对多法：即训练时依次把某个类别的样本归为一类，剩余的样本归为另一类，这样 $k$ 个类别的样本就构造出了 $k$ 个支持向量机。

• 一对一法：即在任意两类样本之间构造一个支持向量机，因此 $k$ 个类别的样本就需要设计 $k(k-1)÷2$ 个支持向量机。

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

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