SVM支持向量机

SVM支持向量机
目录

概述

拉格朗日函数

硬间隔SVM

目标函数

函数求解

软间隔SVM

目标函数

函数求解

判别函数另一种表现形式

结论

非线性SVM

核函数升维

常用核函数

SVM的合页损失函数

SVM实现鸢尾花数据集的分类

概述

        SVM是通过寻找超平面，用于解决二分类问题的分类算法，核心思想是样本点到超平面的距离越远越好，是对感知机的优化。SVM又分为线性可分支持向量机、线性支持向量机和非线性支持向量机，分别对应着硬间隔、软间隔和应用核函数的支持向量机。本文将详述支持向量机的原理和公式推导

拉格朗日函数

        假设函数为，要求函数取的最小值时x的值，我们可以很轻易对函数进行求导，令导数为0，求得 $x=-\frac{3}{4}$ 。假设有约束条件x>=0，在此我们知道x=0处可以取到最优解，但是如何统一的将有约束条件优化为题转化为无约束条件优化问题进行求解，就需要用到拉格朗日函数。

设有约束的优化问题：

$\begin{aligned} \min_{x\in{R^n}} {\quad} &f(x) \\ s.t. {\quad}& c_i(x) \leq 0, i=1,2,...,k \\ &h_j(x) = 0,j=1,2,...l \end{aligned}$

拉格朗日函数可以将以上的有约束问题转化成如下的无约束问题，其中 $\alpha$ 和 $\beta$ 是拉格朗日乘子：

$L(x,\alpha,\beta) =f(x) + \sum_{i=1}^{k}\alpha_i c_i(x) + \sum_{j=1}^{l}\beta_j h_j(x)$

则问题转化为：

$\min_{x}\max_{\alpha\geq 0,\beta} [f(x) + \sum_{i=1}^{k}\alpha_i c_i(x) + \sum_{j=1}^{l}\beta_j h_j(x)]{\quad}{\quad}{\quad}(1)$

拉格朗日对偶问题：

$\max_{\alpha\geq 0,\beta}\min_{x} [f(x) + \sum_{i=1}^{k}\alpha_i c_i(x) + \sum_{j=1}^{l}\beta_j h_j(x)]{\quad}{\quad}(2)$

当和是凸函数，是仿射函数时，(1)式和(2)式具有相同的解

KKT条件：

$\begin{equation} &\nabla_{x}L(x^*,\alpha^*,\beta^*)=0 \\ &\nabla_{\alpha}L(x^*,\alpha^*,\beta^*)=0 \\ &\nabla_{\beta}L(x^*,\alpha^*,\beta^*)=0 \\ &\alpha^*\geq0,i=1,2,...,k \\ &c_i(x^*)\leq 0,i=1,2,...,k \\ &\alpha^*_ic_i(x^*)=0,i=1,2,...,k \\ &h_i(x^*)=0,i=1,2,...,l \end{equation}$

硬间隔SVM

目标函数

        硬间隔SVM的思想是：能正确分类的点，距离超平面越远越好。点到超平面的距离公式为 $\frac{|\omega^Tx+b|}{||\omega||_2}$ ，假设点都能被正确分类，故而和 $\omega^Tx_i+b$ 是同号，进而可写成 $\gamma_i = \frac{y_i(\omega^Tx_i+b)}{||\omega||_2}$ 。距离超平面越远越好可表达为：

$\begin{equation}&\gamma = \frac{y_{min}(\omega^Tx_{min}+b)}{||\omega||_2}\\ \\&\max_{\omega,b}\gamma \end{equation}$

且所有的样本点到超平面的距离都要大于最小距离，函数距离可表达为 ${y_{i}(\omega^Tx_{i}+b)}\geq \gamma^`$ ，由于一组 $\omega$ 和b可以确定一个超平面，一个超平面可以对应无数组 $\omega$ 和b（就好比和确定的是同一条直线），求出一组 $\omega$ 和b即可，故而令 $\gamma^`$ =1，最终可得目标函数为：

$\begin{aligned} \max_{\omega,b} {\quad} &\frac{1}{||\omega||_2} \\ s.t. {\quad}& y_i(\omega^Tx_i + b)\geq 1, i=1,2,...,m \end{aligned}$

又由于求 $\frac{1}{||\omega||_2}$ 的极大，相当于求 $\frac{1}{2}||\omega||_2^2$ 的极小，所以目标函数表示为：

$\begin{aligned} \min_{\omega,b} {\quad} &\frac{1}{2} ||\omega||_2^2\\ s.t. {\quad}& y_i(\omega^Tx_i + b)\geq 1, i=1,2,...,m \end{aligned}$

函数求解

构建拉格朗日函数：

$L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2-\sum_{i=1}^{m}\alpha_i(y_i(\omega x_i+b)-1)$

原有的有约束问题转化为无约束问题：

$\min_{\omega,b}\max_{\alpha\geq 0}L(\omega,b,\alpha)=\min_{\omega,b}\max_{\alpha\geq 0}\frac{1}{2}||\omega||^2-\sum_{i=1}^{m}\alpha_i(y_i(\omega x_i+b)-1)$

对偶问题：

$\max_{\alpha\geq 0}\min_{\omega,b}\frac{1}{2}||\omega||^2-\sum_{i=1}^{m}\alpha_i(y_i(\omega^T x_i+b)-1){\quad}{\quad}(3)$

对拉格朗日函数分别对 $\omega$ 和b求偏导，同时令偏导等于o，求极小：

$\frac{\partial L}{\partial \omega}=\omega-\sum_{i=1}^{m}\alpha_ix_iy_i=0{\quad}\Rightarrow{\quad} \omega=\sum_{i=1}^{m}\alpha_iy_ix_i{\quad}{\quad}(4)$

$\frac{\partial L}{\partial b}=\sum_{i=1}^{m}\alpha_iy_i=0{\quad}{\quad}(5)$

将(4)和(5)代入(3)：

$\frac{1}{2}\omega^T\omega-\sum_{i=1}^{m}\alpha_iy_i\omega^Tx_i-\sum_{i=1}^{m}\alpha_iy_ib+\sum_{i=1}^{m}\alpha_i\\ =\frac{1}{2}\omega^T\omega-\omega^T\sum_{i=1}^{m}\alpha_iy_ix_i-b\sum_{i=1}^{m}\alpha_iy_i+\sum_{i=1}^{m}\alpha_i\\ =\frac{1}{2}\omega^T\sum_{i=1}^{m}\alpha_iy_ix_i-\omega^T\sum_{i=1}^{m}\alpha_iy_ix_i-b\sum_{i=1}^{m}\alpha_iy_i+\sum_{i=1}^{m}\alpha_i\\ =-\frac{1}{2}\omega^T\sum_{i=1}^{m}\alpha_iy_ix_i+\sum_{i=1}^{m}\alpha_i\\ =-\frac{1}{2}\sum_{i=1}^{m}\alpha_iy_ix_i^T\sum_{i=1}^{m}\alpha_iy_ix_i+\sum_{i=1}^{m}\alpha_i\\ =-\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j + \sum_{i=1}^{m}\alpha_i$

去掉负号，极大变极小整理得：

$\begin{aligned} \min_{\alpha}{\quad}&\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j -\sum_{i=1}^{m}\alpha_i \\ s.t. {\quad}& \alpha_i\geq 0, i=1,2,...,m \\ &\sum_{i=1}^{m}\alpha_iy_i=0 \end{aligned}$

可通过SMO算法求得一组 $\alpha^{*}$ 使得函数最优化，再通过 $\omega^*=\sum_{i=1}^{m}\alpha_i^*y_ix_i{\quad}{\quad}$ 可得 $\omega^*$

依据KKT条件： $\alpha_i(y_i(\omega^Tx_i+b)-1)=0$ ， $\alpha_i> 0$ 则 $y_i(\omega^Tx_i+b)-1=0$ ，找出一个 $\alpha_i> 0$ 对应的代入即可得到。（ $\alpha_i> 0$ 对应的点就是支持向量）

软间隔SVM

目标函数

        软间隔SVM是在硬间隔SVM的基础上添加松弛变量 $\xi_i\geq 0$ ，每个样本对应一个松弛变量， $\xi_i$ 代表样本点嵌入间隔面的深度，之前的硬间隔不可分体现在不能满足约束条件，将约束条件放松修改为 $y_i(\omega^Tx_i+b)\geq 1-\xi_i$ ，但是 $\xi_i$ 不能是无穷大，如果是无穷大，任意的 $\omega$ 和b都满足，故而在目标函数上增加惩罚项，目标函数整理如下：

$\begin{aligned} \min_{\omega,b,\xi}{\quad}&\frac{1}{2}||\omega||^2+C\sum_{i=1}^{m}\xi_i\\ s.t. {\quad} & y_i(\omega^Tx_i+b)\geq 1-\xi_i, i=1,2,...,m \\ & \xi_i\geq 0,i=1,2,...,m \end{aligned}$

函数求解

构造拉格朗日函数：

$L(\omega,b,\xi,\alpha,\beta)=\frac{1}{2}||\omega||^2+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^{m}\alpha_i[y_i(\omega^Tx_i+b)+\xi_i-1]-\sum_{i=1}^{m}\beta_i\xi_i$

原有的有约束问题转化为无约束问题：

$\min_{\omega,b,\xi}\max_{\alpha\geq 0,\beta\geq 0}\frac{1}{2}||\omega||^2+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^{m}\alpha_i[y_i(\omega^Tx_i+b)+\xi_i-1]-\sum_{i=1}^{m}\beta_i\xi_i$

对偶问题：

$\max_{\alpha\geq 0,\beta\geq 0}\min_{\omega,b,\xi}\frac{1}{2}||\omega||^2+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^{m}\alpha_i[y_i(\omega^Tx_i+b)+\xi_i-1]-\sum_{i=1}^{m}\beta_i\xi_i{\quad}{\quad}(6)$

对拉格朗日函数分别对 $\omega$ 、b、 $\xi$ 求偏导，同时令偏导等于o，求极小：

$\frac{\partial L}{\partial \omega}=\omega-\sum_{i=1}^{m}\alpha_iy_ix_i=0{\quad}\Rightarrow {\quad}\omega=\sum_{i=1}^{m}\alpha_iy_ix_i{\quad}{\quad}(7)$

$\frac{\partial L}{\partial b}=\sum_{i=1}^{m}\alpha_iyi=0{\quad}{\quad}(8)$

$\frac{\partial L}{\partial \xi}=C-\alpha_i-\beta_i=0{\quad}\Rightarrow {\quad}C=\alpha_i+\beta_i{\quad}{\quad}(9)$

将(7)(8)(9)式代入(6)式：

$\frac{1}{2}\omega^T\omega+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^{m}\alpha_iy_i\omega^Tx_i-\sum_{i=1}^{m}\alpha_iy_ib-\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\beta_i\xi_i\\ =\frac{1}{2}\omega^T\sum_{i=1}^{m}\alpha_iy_ix_i+C\sum_{i=1}^{m}\xi_i-\omega^T\sum_{i=1}^{m}\alpha_iy_ix_i-b\sum_{i=1}^{m}\alpha_iy_i-\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\beta_i\xi_i\\\\ =-\frac{1}{2}\omega^T\sum_{i=1}^{m}\alpha_iy_ix_i+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\beta_i\xi_i\\ =-\frac{1}{2}\sum_{i=1}^{m}\alpha_iy_ix_i^T\sum_{i=1}^{m}\alpha_iy_ix_i+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\beta_i\xi_i\\ =-\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j+C\sum_{i=1}^{m}\xi_i-\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\beta_i\xi_i\\$

$\begin{aligned} &=-\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\sum_{i=1}^{m}(\alpha_i+\beta_i)\xi_i-\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\beta_i\xi_i\\ &=-\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\beta_i\xi_i-\sum_{i=1}^{m}\alpha_i\xi_i+\sum_{i=1}^{m}\alpha_i-\sum_{i=1}^{m}\beta_i\xi_i\\ &=-\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j+\sum_{i=1}^{m}\alpha_i \end{aligned}$

去掉负号，极大变极小整理得：

$\begin{aligned} \min_{\alpha,\beta}{\quad}&\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^{m}\alpha_i \\ s.t. {\quad} &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &\alpha_i\geq 0, i=1,2,...,m {\quad}{\quad}(10) \\ & \beta_i\geq 0,i=1,2,...,m {\quad}{\quad}(11) \\ & C-\alpha_i-\beta_i=0,i=1,2,...,m {\quad}{\quad}(12) \end{aligned}$

(10)(11)(12)式整理：

$\begin{aligned} &\because C-\alpha_i-\beta_i=0 {\quad}and {\quad}\beta_i\geq 0\\ &\therefore\beta_i=C-\alpha_i\geq 0{\quad}\Rightarrow {\quad}\alpha_i\leq C\\ &\because\alpha_i\geq 0\\ &\therefore0\leq \alpha_i\leq C \end{aligned}$

最终对偶问题为：

$\begin{aligned} \min_{\alpha,\beta}{\quad}&\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^{m}\alpha_i \\ s.t. {\quad} &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &0\leq \alpha\leq C \end{aligned}$

仍然可以通过SMO算法求得一组 $\alpha^{*}$ 使得函数最优化， $\omega^*$ 、和硬间隔SVM的 $\omega^*$ 、的求法一致

判别函数另一种表现形式

$\begin{aligned} &\because y=\omega^T+b{\quad} and {\quad} \omega=\sum_{i=1}^{m}\alpha_iy_ix_i\\ &\therefore y=\sum_{i=1}^{m}\alpha_iy_i(x_i\cdot x)+b{\quad} \end{aligned}$

结论
- $\alpha_i=0$ ，点被正确分类
- $0< \alpha_i< C$ ，该点是位于软边界上的点
- :
  - $\xi_i<1$ ，点被正确分类
  - $\xi_i=1$ ，点位于超平面上
  - $\xi_i>1$ ，点未被正确分类
非线性SVM

当数据线性不可分我们可以通过升维的方式使样本在高维的空间线性可分，如上可知SVM的最优化问题为：

$\begin{aligned} \min_{\alpha,\beta}{\quad}&\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^{m}\alpha_i \\ s.t. {\quad} &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &0\leq \alpha\leq C \end{aligned}$

升维的优化问题为：

$\begin{aligned} \min_{\alpha,\beta}{\quad}&\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_j\Phi(x_i)\cdot \Phi(x_j)-\sum_{i=1}^{m}\alpha_i \\ s.t. {\quad} &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &0\leq \alpha\leq C \end{aligned}$

问题：这样升维带来一些问题，假设用多项式回归进行升维，对于()二维升维的结果是()，共5维，如果是3维数据，升维后就会有19维，以此类推，将会导致维度爆炸。升维后还需要做内积运算，时间（内积运算）和空间（升维之后的数据存储）的消耗将是恐怖的

核函数升维

核函数的思想是不计算 $\Phi (x_i),\Phi (x_j)$ 的中间结果，令 $k(x_i,x_j)=\Phi (x_i)\cdot \Phi (x_j)$ ，直接计算出结果，节省时间和空间，优化问题变为：

$\begin{aligned} \min_{\alpha,\beta}{\quad}&\frac{1}{2}\sum_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jk(x_i,x_j)-\sum_{i=1}^{m}\alpha_i \\ s.t. {\quad} &\sum_{i=1}^{m}\alpha_iy_i=0 \\ &0\leq \alpha\leq C \end{aligned}$

判别函数：

$y=\sum_{i=1}^{m}\alpha_iy_ik(x_i,x)+b{\quad}$

常用核函数
- 线性核函数(没有升维)
$K(x,z)=x\cdot z$
- 多项式核函数
$K(x,z)=(\gamma x \cdot z + r)^d$
- 高斯核函数
$K(x,z)=exp(-\gamma ||x-z||^2)$
- sigmoid核函数
$K(x,z)=tanh(\gamma x \cdot z + r)$

SVM的合页损失函数

合页损失函数图像：

我们知道，函数间隔 $y_i(\omega^Tx_i+b)\geq 1$ 是被正确分类的点，故而当不满足条件时会产生损失，svm的损失函数其实合页损失函数加上L2正则化项：

$\min_{\omega,b}\sum_{i=1}^{m}[1-y_i(\omega^Tx_i+b)]_++\lambda||\omega||^2$

合页损失函数在代码中的可用 $max(0,[1-y_i(\omega^Tx_i+b)])$ 来表达，可以通过梯度下降来求解最优解

SVM实现鸢尾花数据集的分类
```
from sklearn.datasets import load_iris
from sklearn.svm import SVC
import numpy as np
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.metrics import accuracy_score
 
# 加载数据
iris = load_iris()
X = iris['data']
y = iris['target']
 
# 数据集分割
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=666)
'''
kernel  核函数，默认高斯核(rbf)
gamma   对应核函数中的gamma
C       对应软间隔目标函数中的惩罚项系数C
coef0   对应核函数中的r，仅对多项式核函数和sigmoid核函数有效
'''
svc = SVC()
 
param_grid = {
    'C': [1.0, 1.1, 1.2, 2],
    'kernel': ['linear', 'poly', 'rbf', 'sigmoid'],
    'decision_function_shape' : ['ovo', 'ovr']
}
grid_search = GridSearchCV(svc, param_grid=param_grid, cv=3, n_jobs=-1)
grid_search.fit(X_train, y_train)
best_model = grid_search.best_estimator_
 
print('the best params is {}'.format(grid_search.best_params_))
 
# 模型评估
y_predict = best_model.predict(X_test)
acc = accuracy_score(y_test, y_predict)
print('accuracy is {}'.format(acc))
```
相关阅读:
OpenResty编译安装详解
 在uniapp中使用秋云ucharts图表，运行到小程序
 LeetCode128. Longest Consecutive Sequence
elasticSearch（三）报错：org.elasticsearch.ElasticsearchSecurityException:
为Jumpserver 配置企业微信
 数组、字符串、日期笔记【蓝桥杯】
【Try to Hack】HFish蜜罐部署
 序列化和反序列化
 多线程JUC 第2季 ReentranctLock实现加锁和解锁过程
 搜索引擎排名因素有哪些具体的细节？
原文地址：https://blog.csdn.net/IT142546355/article/details/126077216

概述

拉格朗日函数

硬间隔SVM

目标函数

函数求解

软间隔SVM

目标函数

函数求解

判别函数另一种表现形式

结论

非线性SVM

核函数升维

常用核函数

SVM的合页损失函数

SVM实现鸢尾花数据集的分类