机器学习Python实战-第三章-分类问题-4.支持向量机算法

3.4.1 原理简介

3.4.2 算法步骤

3.4.3 实战

3.4.4 实验

前半部分是理论介绍，后半部分是代码实践，可以选择性阅读。

GitHub源码地址： HeShen-1/python-MachineLearning: 机器学习python实战（西唯兵版本）。代码仅供参考。

3.4.1 原理简介

支持向量机(support vector machine，SVM)是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的学习算法就是求解凸二次规划的最优化算法。

1.线性SVM算法原理

SVM的基本思想是求解能够正确划分训练数据集并且使几何间隔最大的分离超平面。如图所示，其中，实心圆和空心圆代表两类样本；虚线为分类线，它们之间的距离叫做分类间隔(margin)；虚线上的点 $(x_i,y_i)$ 称为支持向量； $\omega \cdot x+b=0$ 即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个(即感知机)，但是几何间隔最大的分离超平面却是唯一的。

假设给定一个在特征空间上线性可分的训练数据集为

$T=\{(x_1,y_1),(x_2,y_2), \dots ,(x_N,y_N)\}$

其中， $x_i\in R^n,y_i\in \{+1,-1\},i=1,2,\dots ,N;$ $x_i$ 为第 $i$ 个特征向量； $y_i$ 为类标记， $y_i=+1$ 表示正例， $y_i=-1$ 表示负例。

对于给定的数据集 $T$ 和超平面 $\omega \cdot x+b=0$ ，则超平面关于样本点 $(x_i,y_i)$ 的几何间隔为 $\gamma _i=y_i(\frac{\omega}{\left \| \omega \right \| }\cdot x_i+\frac{b}{\left \| \omega \right \| })$

超平面关于所有样本点的几何间隔的最小值为 $\gamma=\underset{i=1,2,\dots ,N}{min} \gamma _i$

实际上，这个最小的几何间隔就是支持向量到超平面的距离。

根据以上定义，SVM模型求解最大分割超平面的问题就可以表示为以下约束最优化问题：

$s.t.\ y_i(\frac{\omega}{\left \| \omega \right \| }\cdot x_i+\frac{b}{\left \| \omega \right \| })\ge \gamma,\ i=1,2,\dots ,N$

将约束条件两边同时除以 $\gamma$ ，得到

$y_i(\frac{\omega}{\left \| \omega \right \| \gamma}\cdot x_i+\frac{b}{\left \| \omega \right \| \gamma})\ge 1$

因为 $\left \| \omega \right \|$ 、 $\gamma$ 都是标量，上式可以简化为：

$\omega=\frac{\omega}{\left \| \omega \right \| \gamma}$

$b=\frac{b}{\left \| \omega \right \| \gamma}$

得到

$y_i(\omega\cdot x_i+b)\ge1, \ i=1,2,\dots ,N$

因为最大化 $\gamma$ 等价于最大化 $\frac{1}{\left \| \omega \right \| }$ ，也等价于最小化 $\frac{1}{2} \frac{1}{\left \| \omega \right \| }^2$ （ $\frac{1}{2}$ 是为了使后面的求导形式简单，不影响结果，二阶导与 $\frac{1}{2}$ 抵消)，故SVM模型求解最大分割超平面的问题又可以表示为分割超平面的问题，所以可以进一步表示为以下约束最优化问题：

$\underset{\omega,b}{min}\ \frac{1}{2} \left \| \omega \right \| ^2$

约束条件为

$s.t.\ y_i(\omega\cdot x_i+b)\ge 1,\ i=1,2,\dots ,N$

这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到对偶问题(dual problem)，此处不做推导。

至此都是基于训练集数据线性可分的假设下进行的，但是实际情况下几乎不存在完全线性可分的数据，为了解决这个问题，引入了“软间隔”的概念，即允许某些点不满足约束条件：

$y_i(\omega\cdot x_j+b)\ge 1$

采用 $hinge$ 损失函数，将原优化问题改写为

$\underset{\omega,b}{min}\ \frac{1}{2} \left \| \omega \right \| ^2+C\sum_{i=1}^{m}\varepsilon _i$

约束条件为

$s.t.\ y_i(\omega\cdot x_i+b)\ge 1-\varepsilon _i,\varepsilon _i\ge 0 , \ i=1,2,\dots ,N$

其中， $\varepsilon _i$ 为松弛变量， $\varepsilon _i=max(0,1-y_i(\omega \cdot x_i+b))$ ，即一个 $hinge$ 损失函数。每个样本都一个对应的松弛变量，表示该样本不满足约束的程度。 $C>0$ 称为惩罚参数，C值越大，对分类的惩罚越大。与线性完全可分求解思路一样，这里需要先用拉格朗日乘子法得到拉格朗日函数，再求其对偶问题。

2.非线性SVM算法原理

在非线性的情况下，对于参数 $\varepsilon$ 无法精准的估计，会对结果造成较大的影响及误差，在这里可以引入松弛因子 $\xi _i$ 、 $\xi _i^*$ ，则二次凸优化问题可以变形为：

$min\ \frac{1}{2} \left \| \omega \right \| ^2+C\sum_{i=1}^{N}(\xi _i+\xi _i^*)$

而相应的约束条件也发生变化：

$\left\{\begin{matrix} y_i-\omega\cdot x_i-b \leq \varepsilon +\xi _i \\ \omega \cdot x_i +b-y_i \leq \varepsilon +\xi _i^* \end{matrix}\right.$

根据实际情况可知， $\xi _i$ 、 $\xi _i^*$ 为正数， $\varepsilon$ 则需满足不敏感损失函数，其表达式为：

$e(f(x)-y)=max(0,|f(x)-y|-e)$

运用拉格朗日函数及对偶变量，则有：

$L=min\ \frac{1}{2} \left \| \omega \right \| ^2+C\sum_{i=1}^{N}(\xi _i+\xi _i^*)-\sum _{i=1}^{N}\alpha _i(\xi _i+\varepsilon -y_i+\omega \cdot x_i+b)-\sum _{i=1}^{N}\alpha _i(\xi _i^*+\varepsilon -y_i+\omega \cdot x_i+b)-\sum _{i=1}^{N}(\eta _i\xi _i+\eta _i^*\xi _i^*)$

其中， $\eta _i$ 、 $\eta _i^*$ 、 $\alpha _i$ 、 $\alpha _i^*$ 、 $C$ 均大于0.

再通过KKT(Karush-Kuhn-Tucker)条件的运算得出：

$W(\alpha _i, \alpha _i^*) = -\frac{1}{2}\sum_{i,j=1}^{N}(\alpha _i - \alpha _i^*)(\alpha _j - \alpha _j^*)k(x_i,x_j)+\sum_{i=1}^{N}(\alpha _i - \alpha _i^*)y_i-\sum_{i=1}^{N}(\alpha _i + \alpha _i^*)\varepsilon$

并且有

$\omega =\sum_{i=1}^{N}(\alpha _i - \alpha _i^*)\phi (x_i)$

对于输入空间中的非线性分类问题，可以通过非线性变换将其转换为不同维特征空间中的线性分类问题，在高维特征空间中去学习一个线性支持向量机。由于在线性SVM学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，不需要显式的指定非线性变换，所以在非线性SVM学习的对偶问题里，可用核函数替换当中的内积，其中，核函数表示通过一个非线性转换后的两个实例间的内积。具体的， $K(x_i, x_j)$ 是一个函数，意味着存在一个从输入空间到特征空间的映射 $\phi (x)$ ，对任意输入空间中的 $x_i$ 、 $x_j$ ，有

$K(x_i,x_j)=\phi (x_i)\phi (x_j)$

在实际应用中，有以下常用的核函数：

线性函数： $K(x_i,x_j)=x_i\cdot x_j$
多项式核函数： $K(x_i,x_j)=(x_i\cdot x_j+1)^d$
径向基核函数： $K(x_i,x_j)=exp(-||x_i-x_j||^2/(2\sigma ^2))$
拉普拉斯核函数： $K(x_i,x_j)=exp(-||x_i-x_j||/\sigma ^2)$
Sigmoid核函数： $(\beta >0,\theta > 0)K(x_i,x_j)=tanh(\beta x_i^T\cdot x_j+\theta)$

综上所述，用核函数替代线性SVM学习的对偶问题中的内积，求解得到非线性SVM：

3.4.2 算法步骤

1.SVM的选用

当训练数据集线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机。 $\underset{a}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_ia_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}a_i$
当训练数据集近似线性可分时，通过软间隔最大化，学习一个线性分类器，即线性支持向量机。
当训练数据集线性不可分时，通过使用核函数，将低维度的非线性问题转换为高维度下的线性问题，学习得到非线性支持向量机。

2.线性SVM算法

输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}$ ,其中, $x_i\in R^n,y_i\in \{+1,-1\},i=1,2,\dots ,N$
输出：分离超平面和分类决策函数。
算法步骤。

3.非线性SVM算法

4.自编SMO(序列最小优化)算法的步骤

启发式方法选择 $a_1$ 和 $a_2$ 。
计算上界 $H$ 和下界 $L$ 。
计算误差项 $E_i$ 。
更新 $a_2$ 。
更新 $a_1$ 。
更新 $b$ 。

3.4.3 实战（源码请见Github）

GitHub： HeShen-1/python-MachineLearning: 机器学习python实战（西唯兵版本）。代码仅供参考。

1.数据集

鸢尾花数据集。

2.sklearn实现

1.线性SVM 结果

2.非线性SVM 结果

3.自编代码实现

3.4.4 实验（源码请见Github）

GitHub： HeShen-1/python-MachineLearning: 机器学习python实战（西唯兵版本）。代码仅供参考。

1.实验目的

掌握SVM引入核函数的动机和核函数思想，会选用合适的核函数，对数据集进行分类。
理解软间隔和硬间隔，尤其是 KKT 条件的不同，并针对正则化系数 C 会进行参数调整和模型选择。
熟练使用 Python 以及 NumPy、Sklearn、Matplotlib 等第三方库。

2.实验数据

定义五个函数，分别为 linear()、nolinear()、gauss_linear()、gauss_nolinear()、circle()，并按要求生成不同分布的数据：

生成两组线性均匀分布的数据（完全线性可分）。
生成两组线性均匀分布的数据（线性不可分）。
生成两组高斯分布的数据（完全线性可分）。
生成两组高斯分布的数据（线性不可分）。
生成环状数据。

3.实验要求

使用线性 SVM 对实验数据(1)中生成的数据进行分类，并画出分类界面。

使用线性 SVM 对实验数据(2)中生成的数据进行分类，并画出分类界面。

分别使用 Linear 核、rbf 核、degree=2 的 poly 核和 degree=3 的poly核的 SVM对实验数据(3)中生成的数据进行分类，并画出分类界面。

分别使用 Linear 核、rbf 核、degree=2 的 poly 核和 degree=3 的poly核的 SVM 对实验数据(4)中生成的数据进行分类，并画出分类界面。

分别使用 rbf 核、degree=2,3,4 的 poly 核的 SVM 对实验数据(5)中生成的数据进行分类，并画出分类界面。

代码结果(部分)：

实验1：