再见！支持向量机

支持向量机 (SVM) 是一种用于分类和回归任务的监督式机器学习算法，它们广泛应用于各种领域，包括模式识别、图像分析和自然语言处理。

SVM 分类的核心是通过构建最优超平面将数据分成不同类别。本文没有复杂的公式推导，逐步的讲清楚支持向量机算法，最后阐述为什么要跟支持向量机说再见的原因，来吧！开始我们的学习之旅。

算法的一些关键术语

超平面

超平面是一个决策边界，可以在高维空间中将数据点分隔成不同类别。

在二维空间中，超平面只是将数据点分为两类的直线，如下图的红色直线：

image-20240418221011348

在三维空间中，超平面是将数据点分为两类的平面，如下图的红色平面：

image-20240418214728858

同样，在 N 维空间中，超平面是具有 (N-1) 维的空间。

SVM的分类思想是通过评估新数据点落在超平面的哪一侧进行分类，如下图，若新数据点（黑色）位于超平面的上面，则该点属于蓝色类；若位于超平面的下面，则属于绿色类。

间隔

间隔（Margin）是超平面与来自每个类的最近数据点之间的距离，SVM 的目标是最大化这一间隔，同时尽量减少分类错误。

如下图，是超平面与蓝色类的最近数据点的距离，是超平面与绿色类的最佳数据点距离，间隔Margin：

较大的间隔表明分类的置信度较高，因为这意味着决策边界与来自每个类别的最近数据点之间的距离较大。SVM 的设计旨在找到最大化间隔的超平面，这也是为什么它们有时被称为最大间隔分类器的原因。

支持向量

支持向量（support vector）是最靠近决策边界（超平面）的数据点。这些数据点非常重要，因为它们决定了超平面的位置和方向，从而对 SVM 的分类准确性产生重大影响。实际上，SVM 之所以命名为支持向量机，是因为这些支持向量“支持”或定义了决策边界。支持向量用于计算间隔（Margin），也就是超平面与来自每个类别的最近数据点之间的距离之和。SVM 的目标是最大化这一间隔，同时尽量减少分类错误。

支持向量的定义，可参考下图：

image-20240418223343551

用示例数据集理解SVM

在著名的数据集“鸢尾花”（Iris）中，有四个特征（列或自变量），如下图。

image-20240418223454042

为了更好的理解SVM，我们只关注两个特征，即“花瓣长度（petal length）”和“花瓣宽度（petal width）”，这些点被绘制在一个二维平面上，如下图：

image-20240423124751074

其中，浅色点代表'Iris Setosa’品种，深色点代表'Iris versicolor’。我们可以简单地通过绘制线条，使用线性分类器来对其进行分类。

上图的深色和浅色线条可以准确地对测试数据集进行分类，但由于与各自类别的边界接近，可能在新数据上失败。相反，虚线分类器完全无用，误分类了许多点。

我们可以将SVM看作在类别之间拟合最宽的可能路径（由平行虚线表示），这种方法称为“最大间隔分类”。如下图：

image-20240423125258337

实际的场景问题类比SVM：

你可以把SVM想象成一家建筑公司，二维平面是一张地图，两个类别分别是两座城市，数据点类比为建筑物。如果你是政府且目标是创建一条最佳的高速公路，以最小化通过两个城市的交通，但你受到可用区域的限制。

我们暂时将道路视为“直线”。

你将合同交给了SVM建筑公司。SVM为了最小化交通，希望最大化道路的宽度。它看着两座城市之间最宽的土地，道路末端的建筑物被称为“支持向量”，因为它们限制或“支持”模型。

分隔高速公路的中央线代表决策边界（超平面），边缘代表各自类别的超平面，这条高速公路的宽度就是间隔。

线性不可分情况

当线性超平面不可分时，输入数据将被转换为更高维度的特征空间，这样可能更容易找到一个线性的决策边界来分离类别。

这是什么意思呢？让我们看一个例子：

image-20240423133206141

如上图，在二维平面上绘制一组点，分为两个类别（红色和黄色），排列在同心圆形区域内。黄色点从原点开始，一直延伸到同心圆周上的点的距离。然后在一定距离后，开始绘制红色点，这些点的绘制方式与黄色点类似。它们之间有一个圆，作为分隔类别的超平面。

这是一个不能线性分离的数据集，在上图中，二维超平面是不可能的，因此需要进行转换（高速公路不是笔直的情况）。

特征变换或增加新特征

我们有两个特征 X 和 Y，并且数据不能线性分类。我们需要做的是添加另一个维度，使数据在该维度上变得线性可分。

数据点在维度上的值就是数据点的列值。要添加另一个维度，我们必须创建另一列（或特征）。

在这里，我们有两个特征 X 和 Y，需要一个第三个特征，它将是原始特征 X 和 Y 的函数，足以在三维空间中线性分类数据。

我们取第三个特征 Z = f(X, Y)；其中 f 表示对 X 和 Y 的函数。在这里，径向基函数（RBF）等于原点到点的欧几里得距离，函数公式：

通过增加Z维度，平面图像转换为下图：

image-20240423134313602

上图是线性可分的情况，超平面与XY平面平行。

这种方法的缺点

这里的主要问题是需要执行的计算量很大，径向基函数是以同心方式取原点为中心的点。假设点不是同心的，但可以通过径向基函数分隔。那么我们需要每次将数据集中的每个点都作为参考点，并找到其他所有点相对于该点的距离。因此，我们需要计算 n*(n-1)/2 个距离。（相当于取其中任意1个点，计算该点与其他n-1个点的距离，但一旦计算了点1和点2 的距离，就不需要计算点2和点1 的距离）

时间复杂度计算

这里平方根的时间复杂度是 O(log(n))，而幂运算和加法的时间复杂度是 O(1)。因此，要执行 n*(n-1)/2 总计算，我们需要 O(n²log(n)) 的时间复杂度。但是，我们的目标是分隔类别，而不是计算距离，因此我们可以不使用平方根，即Z = X² + Y²，在这种情况下，我们将获得 O(n²) 的时间复杂度。

但是，这还不是问题的关键，更麻烦的问题现在出现了。

我们先假设知道要使用哪个函数，但是只限于二次方的函数可能有很多种维度（X、Y、XY、X² 和 Y²）。

我们可以将这些 5 个作为 3 维空间的组合方式10种（）。更不用说，它们的线性组合有无限的可能性（比如 Z = 4X² + 7XY + 13Y²，Z= 8XY +17X²，等等）。

而且这还只是对于二次多项式的情况。如果我们开始使用三次多项式，那么 X³、Y³、X²Y 和 XY² 也会成为考虑的因素，这些额外的特征可能对于分类没什么用处。

例如，我们选择（X，Y，XY）作为特征，将二维平面映射为三维空间，如下图：

image-20240423211653546

图形看起来像是两只鸟的喙接触在一起，其中鸟是红色类别，它们的喙是黄色的。这种分布的数据是线性不可分类的，所有的计算是徒劳的。

我们再仔细观察上面不可线性分类的图，两个黄色喙在中心相遇，其中一个是朝着负 X 和负 Y 方向移动的，所以我决定对 X 和 Y 进行平方，这样新的数值从 0 开始，只形成一个区域，将喙和鸟的脸分开，而不是两个区域。

因此我们选择作为特征，将二维平面映射为三维空间，如下图：

image-20240423212019031

图形看起来像一只带着喙的鸟，这种分布的数据是线性可分类的。

但是，即使是这种方法也有局限性，比如只使用一个或两个特征数据集，这样我们就可以得到一个 3 维的图，而不是更多的维度；另外，我们的大脑容量有限，无法找到下一个特征集合的模式，而且如果第一个图没有任何可延伸的方法，我们就必须再次猜测一个特征并从头开始。

但是如果有种方法，我们只用两个步骤就得到了所需的特征集，这种方法称为核方法（Kernel Trick）

核函数方法（Kernel Trick）

核函数方法不是添加另一个维度/特征，而是找到点之间的相似性。

与其直接找到 f(x,y)，不如计算这些图像点的相似性。换句话说，我们不是直接找到 f(x1,y1) 和 f(x2,y2)，而是取点 (x1,y1) 和 (x2,y2)，并计算图像点在f(x,y) 的相似性；其中 f 可以是任何关于 x,y 的函数。

因此我们不需要在这里找到一组合适的特征集，而是找到一种对所有特征集都有效的方式找到相似性。

为了计算相似性，我们使用高斯函数。

a：表示高斯曲线峰值

b：表示高斯曲线峰值的位置

c：高斯标准差

核函数计算样本间的相似性，因此高斯函数可延伸为RBF 核函数：

其中表示两个样本的特征向量

是超参数，度量模型的线性程度

高斯核函数的本质是升维度，比如训练样本数据集200例，每个样本的特征个数是4，矩阵表示为，计算每个样本与其他样本的相似性，因此可得到（200,200）的数据集，特征个数从4升到200。

为了让大家有个理论依据，直接写出核函数分类的公式（本文不做推导，因为太复杂会偏离本文的主题）。

训练数据集是已知项，分别是拉格朗日乘子和截距，是核函数。模型训练完成后，即可得到这些参数。新数据点x的预测可根据上式判断，若f(x)>0，属于正类；反之，属于负类。

我们回到RBF核函数的讨论，RBF核函数只有一个参数，一个小的（趋向于0）意味着一个更线性的模型，而一个大的意味着一个更加非线性的模型。

如下图两个模型（左侧是，右侧是），可知右侧的分类边界更加线性。

image-20240423215959182

使用非常高的 gamma 值可能会导致过拟合，因此我们需要找到适当的 gamma 值。

下图显示了 3 个模型，从左到右分别为 。（左边的模型拟合准确，中间的模型过度拟合，右边的模型极度过度拟合）

image-20240423224247969

时间复杂度

核函数需要计算每个点与所有其他点的相似性，所以我们总共需要进行 n*(n-1)/2 次计算。核函数的指数运算的时间复杂度是 O(1)，因此我们得到总的时间复杂度是 O(n²)。

我们不需要绘制点、检查特征集、特征集组合等等，这使得核方法更加高效。

常用的核函数包括：

线性核

多项式核

RBF核

Sigmoid核

为了进一步优化我们的计算，我们使用“Gram 矩阵”。Gram 矩阵是一个可以轻松存储和操作的矩阵，非常高效，Gram矩阵是所有样本两两相似性所组成的矩阵。

正则化和软间隔SVM

如果我们严格要求所有点必须在正确的一侧远离间隔线，那么这就被称为硬间隔分类。

这种方法有两个问题。首先，它只适用于线性可分的数据，而对于非线性可分的数据，虽然大部分情况下可以通过核函数进行分类，但是若数据本身是包含噪声的非线性结构，导致这类数据偏离正常位置很远，通过硬间隔分类还是很难处理。

其次，它对异常值非常敏感。在下图中，红点被引入为左侧类别的异常值（与浅色点的距离远远大于浅色点之间的距离），并且它显著改变了决策边界，这可能导致在测试模型时出现错误的浅色点数据分类。

image-20240423230203761

尽管这个模型没有误分类任何点，但它并不是一个非常好的模型，在测试期间可能会产生更高的错误。

为了避免这种情况，我们使用软间隔分类。

软间隔是一种允许在训练数据中出现一些分类错误的边界，如下图的分类边界：

image-20240423230615491

软间隔通过允许一些数据点（红色点）位于决策边界的错误一侧，从而允许一些分类错误。

即使在训练数据集中存在分类错误，并且相对于之前的模型，性能较差。但由于软间隔使得决策边界更加灵活，因此在测试期间，整体性能会更好，因为它与两个类别都更远。

但是我们可以通过数据预处理和数据清理来解决异常值的问题，对吗？那为什么要使用软间隔？

主要原因是数据本身可能是包含噪声的非线性结构，不一定能找到没有分类错误的决策边界，而且通过硬间隔构建的决策边界往往测试精度较差。

相关概念介绍

类超平面

支持向量机除了决策边界（超平面）外，还有各自类的超平面，如下图用虚线表示的浅色类超平面和深色类的超平面，统称为类超平面。

重要误分类（major misclassifications）和次要误分类（minor misclassifications）

若以类超平面作为分类边界，产生的错误分类为minor misclassifications；若以决策边界作为分类边界，产生的错误分类为major misclassifications。根据定义，上图有5个major misclassifications（3个浅色点和2个深色点）和7个minor misclassifications（以深色类超平面作为分类边界，有3个误分类；以浅色类超平面作为分类边界，有4个误分类）。

我们主要根据major misclassifications评估模型的性能，若major misclassications相同，我们可以通过minor misclassifications比较模型，若minor misclassifications增加，模型的性能可能变差了。

软间隔原理

软间隔通过为每个数据点引入一个松弛变量来实现，这使得支持向量机能够容忍一定程度的分类误差。容忍度的程度由一个称为正则化超参数 C 的参数控制，它决定了应该给出多少权重来最小化分类错误与最大化间隔之间的平衡。

最小化SVM目标函数：

通过上述公式，我们应该可以定性得到几个结论：

• 松弛变量足够大时，训练点就很轻易的满足约束条件，得到的分类间隔也越大，但是模型的性能会降低
• 超参数C是一个惩罚参数，避免取太大的值，目标函数既要最小化（最大化分类间隔），又要最小化（松弛变量对的破坏程度），参数C体现了两者总体的一个权衡。
• 惩罚参数C越大，表示模型对准确率的容忍度低，体现在分类间隔越硬；C越小，表示模型对准确率的容忍度高，体现在分类间隔越软。

如C=1000的决策边界和类超平面：

image-20240424192326703

C=1的决策边界和类超平面：

image-20240424192453414

比较两图，C=1000的误分类小于C=1的误分类，但是C=1的分类间隔比C=1000的大，模型的泛化性能可能更好。

C越小，模型趋于欠拟合；C越大，模型趋于过拟合。

SVM回归

尽管支持向量机（SVM）通常用于分类，但它们可以同时用于回归和分类。支持向量回归（support vector regression，SVR）是一种用于回归分析的机器学习算法。它与传统的线性回归方法不同，因为它在连续空间中找到最适合数据点的超平面，而不是将数据点拟合成一条直线。

与SVM原理相比，SVR试图最大化间隔中的数据点数量，这个间隔的宽度由一个超参数 ε（epsilon）来控制。

image-20240424194156090

右图的表示对x进行高维映射。

这可以用一个类比来理解：就像在建筑物或房屋上搭建一座天桥或桥梁，我们希望以最薄的桥梁为尽可能多的房屋提供遮阳。

SVR希望将整个数据都包含在其范围内，同时试图最小化间隔，原则上是试图包围这些点。而线性回归则希望通过一条直线，使得点到线的距离之和最小。

SVR相对于普通回归的优势包括：

• 非线性关系：SVR能够捕捉输入特征和目标变量之间的非线性关系。它通过使用核技巧来实现这一点，相比之下，线性回归假设输入特征和目标变量之间存在线性关系，而非线性回归则需要大量的计算。
• 对异常值的鲁棒性：与线性回归相比，SVR对异常值更具鲁棒性。SVR旨在最小化围绕预测值的一定间隔内的误差，这个间隔称为epsilon-insensitive区域。这种特性使得SVR对超出间隔之外的异常值影响较小，从而导致更稳定的预测结果。
• 对模型复杂度的控制：SVR通过正则化参数C和核参数等超参数提供对模型复杂度的控制。通过调整这些参数，可以权衡模型复杂度和泛化能力，而线性回归则不提供这种灵活性。
• 支持向量的稀疏性：SVR通常依赖于一个称为支持向量的训练实例子集来构建回归模型。这些支持向量对模型具有最重要的影响，并代表了用于确定决策边界的关键数据点。这种稀疏性特性使得SVR在内存使用和计算速度方面比线性回归更有效率，特别是对于大型数据集而言。此外，一个优点是在添加新的训练点后，如果它们位于间隔内，模型不会发生变化。

代码实战

分类一个线性不可分的数据。

加载训练数据集：

import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.datasets import make_circles
X, y = make_circles(100, factor=.1, noise=.1)
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')


image-20240424202038194

正如您所看到的，数据无法通过一条直线进行分隔。我们用线性核函数分类，完整代码：

import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.datasets import make_circles
from sklearn.svm import SVC
import numpy as np
X, y = make_circles(100, factor=.1, noise=.1)
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')

model=SVC(kernel='linear').fit(X, y)
ax = plt.gca()
xlim = ax.get_xlim()
ylim = ax.get_ylim()
print(xlim)
# 构建评估模型的坐标数组
xx = np.linspace(xlim[0], xlim[1], 30)
yy = np.linspace(ylim[0], ylim[1], 30)
print(xx)
YY, XX = np.meshgrid(yy, xx)
xy = np.vstack([XX.ravel(), YY.ravel()]).T
print(XX.shape)
Z = model.decision_function(xy).reshape(XX.shape)
# 绘制决策边界与类超平面，实线为决策边界
ax.contour(XX, YY, Z, colors='r', levels=[-1, 0, 1], alpha=0.5,
           linestyles=['--', '-', '--'])
# 绘制支持向量,黑色边缘
ax.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=100,
           linewidth=1, facecolors='none', edgecolors='k')
plt.show()

我们得到了以下结果：

image-20240424203518998

分类效果很差，映射到高维后的数据分布可视化：

from mpl_toolkits import mplot3d
# 构建新特征
r = np.exp(-(X ** 2).sum(1))
ax = plt.subplot(projection='3d')
ax.scatter3D(X[:, 0], X[:, 1], r, c=y, s=50, cmap='autumn')
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('r')


image-20240424203913960

通过高维映射，我们可以用一个平面将这两个类别分开。然而，在大型数据集上使用三维空间在计算速度上是非常昂贵的。此外，我们还应该确保我们计算的高维映射函数（我们的 r）是最能将我们的两个类别远离的函数（对于多维特征来说，这种方法难度太大）。

幸运的是，我们不需要担心这些问题，甚至不需要计算第三维度。我们的SVM算法通过核方法（样本数据间的相似性）隐式地完成了这一任务，并且以一种方式完成，使得上述两个问题都得到了解决。

因此，我们使用核函数为rbf的svm，完整代码：

import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.datasets import make_circles
from sklearn.svm import SVC
import numpy as np
X, y = make_circles(100, factor=.1, noise=.1)
plt.scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='autumn')

model=SVC(kernel='rbf').fit(X, y)
ax = plt.gca()
xlim = ax.get_xlim()
ylim = ax.get_ylim()
print(xlim)
# 构建评估模型的坐标数组
xx = np.linspace(xlim[0], xlim[1], 30)
yy = np.linspace(ylim[0], ylim[1], 30)
print(xx)
YY, XX = np.meshgrid(yy, xx)
xy = np.vstack([XX.ravel(), YY.ravel()]).T
print(XX.shape)
Z = model.decision_function(xy).reshape(XX.shape)
# 绘制决策边界与类超平面，实线为决策边界，虚线为类超平面
ax.contour(XX, YY, Z, colors='r', levels=[-1, 0, 1], alpha=0.5,
           linestyles=['--', '-', '--'])
# 绘制支持向量,黑色边缘
ax.scatter(model.support_vectors_[:, 0], model.support_vectors_[:, 1], s=100,
           linewidth=1, facecolors='none', edgecolors='k')
plt.show()

分类效果图：

SVM缺点

还记得之前介绍的核函数吗？SVM的理论这么完美，设计的这么巧妙，为什么我们大部分使用神经网络进行分类而非SVM？因为核函数是我们手动设计的固定算法进行特征提取，就如同图像处理早期的手动设计的卷积核一样，无法训练，这样的方法能力上限有限，浪费了大数据资源，所以就被神经网络淘汰了，这也是传统机器学习的通病。

结论

SVM在小样本数据集有较大的应用，算法设计非常巧妙，如最大间隔、核方法、凸优化、KKT条件和拉格朗日优化等颇有难度的知识点，很多人说算法是需要一定的数学基础，SVM可以满足；也有很多人说算法是需要一定的编程基础，SVM一样可以满足。