支持向量机

一、基本思想

支持向量机（Support Vector Machine）可以看作是感知机的扩展。如果存在一个超平面可以将数据点分为两类，感知机将会找到这个超平面，而支持向量机则是找到一个具有最大边距的超平面。

其形式化定义与感知机相同：

$\begin{aligned} &数据集：D=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\},y_i\in\{-1,+1\}\\ &模型：h(x)=\text{sign}(w^Tx+b) \end{aligned}$

如果数据是二元可分的，感知机可以找到很多不同的超平面，但是哪个超平面是最好的呢？这就需要我们用SVM去寻找

SVM找到的是一个具有最大边距的超平面如下图所示，γ是超平面到两类点之间的最小距离，而我们要找到一个超平面使得γ最大，这也意味着该超平面在这两类数据点的中间，即SVM找到的超平面到两类点的最小距离是相等的。

二、线性支持向量机

2.1 计算边距$\gamma$

假设当前的超平面为：

$\mathcal{H}=\{x|w^Tx+b=0\}$

任取超平面中的一个点$x$，则它到超平面的距离为：设$x$到超平面的距离为$d$，它在超平面上的投影为$x^P$

$\begin{aligned} &根据向量关系，则有：x^P+d=x，x^P\in \mathcal{H}\\ &\because w为\mathcal{H}的法向量~~~~\therefore w//d，d=\alpha w\\ &\therefore x^P=x-d=x-\alpha w\\ &\therefore w^Tx^P+b=w^T(x-\alpha w)+b=0\\ &\therefore \alpha =\frac{w^Tx+b}{w^Tw}，d=\alpha w=\sqrt{d^Td}=|\alpha|\sqrt{w^Tw}=\frac{|w^Tx+b|}{\sqrt{w^Tw}} \end{aligned}$

由此我们得到：

$\gamma(w,b)=\min_{x\in D}\frac{|w^Tx+b|}{\sqrt{w^Tw}}$

根据比例关系，我们可以进一步得简化计算过程：

$\begin{aligned} &\gamma(w,b)=\min_{x\in D}\frac{|w^Tx+b|}{\sqrt{w^Tw}}=\min_{x\in D}\frac{\beta|w^Tx+b|}{\beta\sqrt{w^Tw}}=r(\beta w,\beta b),\beta\not=0 \end{aligned}$

我们可以找到一个合适的$\beta$，对于使得$\gamma(w,b)$取得最小值的$x$有：

$\beta|w^Tx+b|=1$

我们对空间进行比例变换：$w=\beta w，b=\beta b$，则$\gamma(w,b)$可表示为：

$\gamma(w,b)=\frac{1}{||w||_2}$

2.2 最大化边距$\gamma$

我们可以将求解γ最大值的过程等效为一个约束化问题：

$\begin{aligned} &求解问题：(w,b)=\underset{w,b}{argmax}~\gamma(w,b)\\ &约束条件：y_i(w^Tx_i+b)\ge 0 \end{aligned}$

结合我们上述的比例变换，则约束化问题等效为：

$\begin{aligned} &求解问题：(w,b)=\underset{w,b}{argmax}~\gamma(w,b)=\underset{w,b}{argmax}~\frac{1}{||w||_2}=\underset{w,b}{argmin}~w^Tw\\ &约束条件：\min_{x\in D}|w^Tx+b|=1,y_i(w^Tx+b)\ge 0 \end{aligned}$

我们可以对约束条件继续进行整合：

$\begin{aligned} &\min_{x\in D}|w^Tx+b|=1\rightarrow |w^Tx+b|\ge 1\\ &y_i\in\{-1,+1\}\rightarrow y_i(w^Tx_i+b)\ge 1 \end{aligned}$

最终，我们得到的约束化问题为：

$\begin{aligned} &求解问题：(w,b)=\underset{w,b}{argmin}~w^Tw\\ &约束条件：y_i(w^Tx_i+b)\ge 1\\ \end{aligned}$

在我们求得最终的$w,b$时，有$y_i(w^Tx_i+b)=1$

这是一个二次最优化问题，目标是二次的，约束是线性的，我们可以用任何QCQP（二次约束二次规划解算器）唯一且有效地求解它。

如上图所示，我们将离决策边界最近的几个点称为支持向量，支持向量机的最终模型仅仅与支持向量有关

三、软约束

3.1 噪声影响

如果存在噪声，可能使得数据线性不可分，如下图所示，这就导致我们无法找到一个最终的超平面，而感知机模型是通过限制最大训练轮数避免死循环的，支持向量机则是通过引入软约束处理噪声。

在能找到超平面的情况下也可能存在一些噪声点使得超平面的选取并不好，如下图所示，我们仍要尽量规避掉这类噪声。

3.2 软约束实现

对于上述的例子，我们可以将那些噪音点忽略掉，并将它们看作损失，统计进行忽略后不匹配的点的个数加到目标公式中，则有：

$\begin{aligned} &求解问题：(w,b)=\underset{w,b}{argmin}~w^Tw+C\sum_{i=1}^nI(y_i\not=\text{sign}(w^Tx_i+b))\\ &约束条件：正确分类的y_i:y_i(w^Tx_i+b)\ge 1，不正确分类的y_i(w^Tx_i+b)\ge\infty \end{aligned}$

即：我们对分类错误的点不加以任何约束，$C$是对大边距和噪声点耐受性的权衡

但是上述计算公式是非线性且不连续的，为此我们引入一个线性松弛变量$\xi_i$：

$\begin{aligned} &求解问题：(w,b)=\underset{w,b}{argmin}~w^Tw+C\sum_{i=1}^n\xi_i\\ &约束条件：y_i(w^Tx_i+b)\ge 1-\xi_i \end{aligned}$

松弛变量$~\xi_i~$允许输入$x_i$更接近超平面（甚至位于错误的一侧），但这种“松弛”在目标函数中会受到惩罚。

$C$非常大时，$SVM$将变得非常严格，尝试将所有的点都分到正确的一侧去
$C$非常小时，$SVM$将变得非常松散，可能会牺牲一些简单的点来获得超平面

松弛变量$~\xi_i~$的定义方式如下：我们可以将$~\xi_i~$看成损失函数，$SVM$的建立要尽可能得最小化$~\xi_i~$

$\begin{aligned} &\xi_i=\left\{ \begin{aligned} &1-y_i(w^Tx_i+b)~,~y_i(w^Tx_i+b)<1\\ &~~~~~~~~~~~~0~~~~~~~~~~~~~~~~,~y_i(w^Tx_i+b)\ge 1 \end{aligned} \right. \end{aligned}$

即：$\xi_i=\max(1-y_i(w^Tx_i+b),0)$

最终我们的软约束模型为：

$(w,b)=\underset{w,b}{argmin}~w^Tw+C\sum_{i=1}^n\max(1-y_i(w^Tx_i+b),0)$

参数$C$对支持向量机最后拟合结果的影响如图所示：

四、算法实现

支持向量机的手动实现结合核函数最优，因此我们此处仅通过调库实现模型。

4.1 数据集

我们此处选择自己生成数据集，依靠的是sklearn的make_blobs函数，这是一个用于生成聚类数据的函数

'''屏蔽warning'''
import warnings
warnings.filterwarnings("ignore")
'''导入重要库'''
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

'''生成数据'''
data,target=make_blobs(n_samples=1000,n_features=2,centers=2)
ax=plt.figure(figsize=(10,4),dpi=100).add_subplot()#初始化画板
plt.scatter(data[:,0],data[:,1],c=target)
plt.show()

我们生成的数据集分布的例子如下：

4.2 模型实现

我们实现的是线性支持向量机，不可以用核函数进行优化，主要用到的是sklearn的LinearSVC函数，它的函数原型如下：

LinearSVC(penalty='l2', loss='squared_hinge', *, dual=True, tol=0.0001, C=1.0, multi_class='ovr', fit_intercept=True, intercept_scaling=1, class_weight=None, verbose=0, random_state=None, max_iter=1000)

①penalty：正则化项，可选择："l1","l2"
②loss：损失函数，可选择："hinge"（合页损失函数），"squared_hinge"（合页损失函数的平方）
③dual：求解对偶问题，当样本数量>特征数量时倾向于解决原始问题
④tol：中止迭代的阈值
⑤C：软约束的惩罚系数
⑥multi_class：多分类问题的策略，"ovr"（one-vs-rest分类策略），"crammer_singer"（多类联合分类）
⑦fit_intercept：是否考虑截距b
⑧max_iter：最大训练轮数

'''屏蔽warning'''
import warnings
warnings.filterwarnings("ignore")
'''导入重要库'''
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.svm import LinearSVC
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

'''生成数据'''
data,target=make_blobs(n_samples=1000,n_features=2,centers=2)
'''划分数据集'''
X_train,X_test,y_train,y_test=train_test_split(data,target,test_size=0.2)#选取20%的数据作为测试集
'''确定参数'''
params={
    "penalty":"l2",
    "loss":"squared_hinge",
    "dual":False,
    "tol":0.0001,
    "C":100,
    "fit_intercept":True,
    "max_iter":1000
}
'''初始化模型'''
SVM=LinearSVC(**params)
SVM.fit(X_train,y_train)
y_pred=SVM.predict(X_test)
print(accuracy_score(y_test,y_pred))
'''可视化'''
w=SVM.coef_[0]  #获得超平面法向量b
b=SVM.intercept_[0] #获得截距b
plt.figure(figsize=(8,4),dpi=100).add_subplot()#初始化画板
plt.scatter(data[:,0],data[:,1],c=target)
'''获得数据集中各个点到超平面的距离'''
ax = plt.gca()  # 移动坐标轴
'''获得坐标范围'''
xlim = ax.get_xlim()  # 获得Axes的 x坐标范围
ylim = ax.get_ylim()  # 获得Axes的 y坐标范围
'''创建等差数列'''
xx = np.linspace(xlim[0], xlim[1], 30)
yy = np.linspace(ylim[0], ylim[1], 30)
'''生成网格点坐标矩阵'''
YY, XX = np.meshgrid(yy, xx)
xy = np.vstack([XX.ravel(), YY.ravel()]).T  #xy中存储了整个坐标系中的网格点坐标
Z = SVM.decision_function(xy).reshape(XX.shape)
ax.contour(XX, YY, Z, colors='k', levels=[-1, 0, 1], alpha=0.5,
           linestyles=['--', '-', '--'])  # 绘制决策边界和分隔
plt.show()

五、总结

①支持向量机（SVM）是一种线性分类器，可以看作是感知器的扩展，支持向量机寻找最大边距分离超平面。
②边距是从超平面到两个类中最近点的距离。
③最大边距分类器是在所有数据点必须位于超平面的正确一侧的约束下，使边距最大化。
④对于最优的w，b对，一些训练点会有严格的约束，我们将这些训练点称为支持向量，严格的约束为：

$y_i(w^Tx_i+b)=1$

⑤支持向量机是凸二次函数，可以用QCQP求解器求解。
⑥通过在目标中加入松弛变量，我们可以得到无约束SVM公式：软约束SVM。