数据挖掘笔记 - 支持向量机基础-白红宇

数据挖掘笔记 - 支持向量机基础

阅读量：4088 次

发布时间：2019-05-25

本文共 4589 字，大约阅读时间需要 15 分钟。

1 概念

支持向量机是一种分类方法，通过寻求结构化、风险最小，来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较小的情况下，亦能获得良好统计规律的目的。通俗来讲，他是一种二类分类模型，基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

SVM可以很好的应用于高维数据，避免维灾难问题。这种方法具有一个独特的特点，它使用训练实例的一个子集来表示决策边界，该子集作为支持向量。

尽管SVM的训练非常慢，但是由于其对复杂的非线性边界的建模能力，他们是非常准确的，与其他模型相比，它们不至于出现过分拟合的现象。

2 最大边缘超平面

具有较大边缘的决策边界比具有较小边缘的决策边界具有更好的泛化误差。直觉上，如果边缘比较小，决策边界任何轻微的扰动都可能对分类产生显著的影响。因此，那些决策边界边缘较小的分类器对模型的过分拟合更加敏感，从而在未知的样本上的泛化能力很差。

统计学理论给出了线性分类器边缘与其泛化误差之间关系的形式化解释，称之为SWM（structural risk minimization）结构风险最小化理论。该理论根据分类器的训练误差。训练样本数N和模型的复杂度h，给出了分类器的泛化误差的一个上界R。在概率下，分类器的泛化误差在最坏情况下满足

其中是能力的单调增函数。所以随着，能力的增加，泛化误差的上界也随之提高，因此需要设计一个最大化决策边界的边缘的线性分类器，以确保最坏情况下的泛化误差最小。线性SVM就是这样的分类器。

3 线性支持向量机：可分情况

线性SVM寻找具有最大边缘的超平面，因此它也经常被称为最大边缘分类器。为了理解SVM如何学习这样的边界，我们需要对线性分类器的决策边界和边缘进行讨论。

线性决策边界

一个包含N个训练样本的二类分类问题，每个样本表示为一个二元组，其中表示第i个样本的属性集，表示它的类标号。一个线性分类器的决策边界可以写成：

其中W和b是模型的参数。

对于任意位于决策边界上方的方块，我们可以证明，k>0。

对于任意位于决策边界下方的方块，我们可以证明，k<0。

于是可以用夏磊的方式预测任何测试样本Z的类标号。

边缘

两个超平面上任意两个数据点的距离可以表示为

表示范数，

SVM模型

最大边缘化等价于最小化下面的目标函数：

所以SVM的模型可以定义为：

由于目标函数是二次的，而约束在参数W和b上是线性的，因此这个问题是一个凸函数优化问题。可以通过标准的拉个朗日乘子方法求解。

对应的拉格朗日函数为：

对于函数的优化问题设计到大量参数，为了简化问题，将问题换成对偶问题，对应的对偶拉格朗日函数为：

通过对偶函数找到对应的一组（可以通过二次规划），再通过，即可求得W和b。

决策边界可以表示成：

实践中，使用b的平均值作为决策边界的参数，它的大小取决于使用的支持向量。

4 线性支持向量机：不可分情况

数据线性可分是一种理想的状态，实际上，训练的数据是有噪声的，因此必须放松不等式的约束，以适应非线性可分数据。可以通过在优化问题的约束中引入正值的松弛变量来实现。

修改后的最大边缘目标函数为：

相应的拉格朗日函数为：

对偶的拉格朗日函数为：

尽管线性可分与线性不可分的对偶的拉个朗日函数一样，但是拉格朗日乘子上的约束不同。

非线性的被限制在。

5 非线性支持向量机

很多真实生活中的数据集，决策面都是非线性的。为了解决分线性分割问题。假设存在一个合适的函数来变换给定的数据集，让数据集的分割问题映射到高维空间下，于是线性决策的边界具有以下形式：

非线性支持向量的模型如下

最大边缘目标函数为：

对偶的拉格朗日函数为：

通过二次规划技术找到对应的一组，再通过，即可求得W和b。

最后可以通过下式对检验的实例Z进行分类。

其中即相似度被称为核技术方法。

核技术

核技术使用中使用原属性集计算变换后的空间中的相似度的方法。该技术有利于处理如何实现非线性的问题。相似度函数K称为核函数，核函数必须满足Mercer定理。

任何半正定的函数都可以作为。当z*Mz > 0弱化为z*Mz≥0时，称M是

参考文献

《数据挖掘导论》 5.5支持向量机

一、支持向量机简介

本文中支持向量机的理论推导止于凸优化，至于是如何求解凸优化问题的请参阅其他文章。

1.支持向量机的基础概念

支持向量机（SVM）是利用最大边缘超平面对样本进行分类的方法，这里的边缘指的是和决策边界平行，到决策边界距离相等，且相交于最近的两类样本点的超平面之间的距离。边缘最大化的目的是为了最小化泛化误差。

在概率 $1-\eta$ 下，SVM分类器的泛化误差的上界 $R$ 满足：

$R \leq R_e + \varphi \left ( \frac{h}{N}, \frac{\log(\eta)}{N} \right )$ ，其中 $\frac{\partial \varphi}{\partial h}>0$

其中 $R_e$ 是训练误差， $N$ 是样本容量， $h$ 是模型复杂度（复杂度越高，训练误差越小，与边缘负相关），根据上式可以得出：1）训练误差越大，泛化误差上确界越大；2）边缘越大，训练误差可能会更大，但是泛化误差的上界越小；3）概率 $\eta$ 越大，泛化误差上界越大（判断越肯定，内容信息量越少）；4）样本容量 $N$ 越大，可以降低模型复杂度 $h$ 和判断的肯定程度 $\eta$ 对泛化误差上界的正向影响（样本越多越好）。

SVM一般需要设定几个参数，包括：核函数 $K$ ，边缘软硬度（ $C$ ， $k$ ）。

2.支持向量机的特点

1）SVM本质是一个凸优化问题，因此可以得到一个全局最优解。

2）SVM基础模型针对的是二元分类问题，但是可以通过嵌套实现解决多元分类问题。

二、线性支持向量机（完美可分）

设有一个样本容量为 $N$ 的样本集,其属性数据矩阵为 $\textbf{\emph X}= \begin{bmatrix} \textbf{\emph{x}}_1 \\ \textbf{\emph{x}}_2 \\ \vdots \\ \textbf{\emph{x}}_N \\ \end{bmatrix} = \begin{bmatrix} x_{11} , & x_{12}, & \dots & x_{1d} \\ x_{21} , & x_{22}, & \dots & x_{2d} \\ \vdots & \vdots &\ddots & \vdots \\ x_{N1} , & x_{N2}, & \dots & x_{Nd} \\ \end{bmatrix}$ ，其标签向量为 $Y=\begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_N\\ \end{bmatrix}$ ，其中 $\textbf{\emph x}_i = \left [ x_1, x_2, \dots, x_d \right ]$ ，表示第 $i$ 个样本的属性向量，那么一个线性分类器的决策边界可以写成如下形式： $\textbf{\emph w} \cdot \textbf{\emph x} + b =0$ ，即是一个线性流形（超平面）。下面以一个2维空间中的随机样本为例进行说明。

假设有两个样本点 $\textbf{\emph x}_1$ 及 $\textbf{\emph x}_2$ 处于决策边界上，那么可以得到如下等式：

$\\ \textbf{\emph w} \cdot \textbf{\emph x}_1 +b =0\\ \textbf{\emph w} \cdot \textbf{\emph x}_2 +b =0$

于是可以得到 $\textbf{\emph w} \cdot \left (\textbf{\emph x}_1 - \textbf{\emph x}_2 \right ) =0$ 。由于向量 $\textbf{\emph x}_1 - \textbf{\emph x}_2$ 便是一个平行于决策边界的向量（起始点都在决策边界上），因此可以得出，向量 $\textbf{\emph w}$ 和决策边界正交，如下图所示：

因此通过简单证明可以得到红色点满足 $\textbf{\emph w} \cdot \textbf{\emph x} + b =k, \quad k>0$ ，蓝色叉满足 $\textbf{\emph w} \cdot \textbf{\emph x} + b =k', \quad k'<0$ 。如果红色点的类标号为1，而蓝色叉的类标号为-1，那么对于任何一个测试样本 $\textbf{\emph z}$ ，可以进一步得到：

$y= \left\{ \begin{array}{lr} 1 \quad & if: \quad \textbf{\emph w} \cdot \textbf{\emph z} + b>0\\ -1 \quad & if: \quad \textbf{\emph w} \cdot \textbf{\emph z} + b<0 \end{array} \right. \qquad \qquad (1)$

如上图所示，直线 $bl_1$ 和 $bl_2$ 分是线性分类器的边缘的边界线，离决策边界最近的两个样本点 $\textbf{\emph z}_1$ 及 $\textbf{\emph z}_2$ 分别在这两条直线上，在边界线上的点称为支持向量。假设：

$\begin{array}{lr} bl_1: \quad \textbf{\emph w} \cdot \textbf{\emph z}_1 + b=k \\bl_2: \quad \textbf{\emph w} \cdot \textbf{\emph z}_2 + b=-k \end{array} \qquad \qquad (2)$

注：这里 $k$ 是一个常数。直线 $bl_1$ 和 $bl_2$ 的斜率及截距是由向量 $\textbf{\emph w}$ 和标量 $b-k$ 共同决定的，因此 $\\ \textbf{\emph w} \cdot \textbf{\emph z}_1 + b=k$ 依然可以代表所有过点 $\textbf{\emph z}_1$ 的直线，为了方便计算，可以设 $k=1$ 。

等式组（2）结合等式组（1）（其中 $k=1$ ），可以合并简化为：

$y (\textbf{\emph w} \cdot \textbf{\emph x} +b) \geq 1 \qquad \qquad \qquad \qquad (3)$

等式组（2）中两式相减可得：

$\\ \textbf{\emph w} \cdot \left (\textbf{\emph z}_1 - \textbf{\emph z}_2 \right ) =2$

假设边界线 $bl_2$ 沿着向量 $\textbf{\emph d}$ 平行移动可以达到边界线 $bl_1$ ，如果我们要计算分类器的边缘（宽度），那其实就是计算向量 $\textbf{\emph d}$ 的模 $d=\left |\textbf{\emph d} \right |$ 。由于向量 $\textbf{\emph d}$ 和向量 $\textbf{\emph w}$ 平行，因此向量 $\textbf{\emph d}$ 就是向量 $\textbf{\emph z}_1 - \textbf{\emph z}_2$ 在向量 $\textbf{\emph w}$ 上的投影，于是根据向量内积（ $\textbf{\emph w} \cdot \left (\textbf{\emph z}_1 - \textbf{\emph z}_2 \right )$ ）的几何意义，可以得出：

$d=\left |\textbf{\emph d} \right | = \frac{ \textbf{\emph w} \cdot \left (\textbf{\emph z}_1 - \textbf{\emph z}_2 \right ) }{\left |\textbf{\emph w} \right |} = \frac{2}{\left |\textbf{\emph w} \right |} \qquad \qquad (4)$

结合等式（3）和等式（4），SVM问题可以归纳为一个凸优化问题，目标函数为

$f\left ( \textbf{\emph w} \right )= \frac{\left | \textbf{\emph w} \right |}{2} \qquad \qquad \qquad \qquad (5)$

再加上约束，完整的优化问题如下：

$\\argmin \quad f\left ( \textbf{\emph w} \right )= \frac{\left | \textbf{\emph w} \right |}{2} \\ s \cdot t \cdot \qquad y (\textbf{\emph w} \cdot \textbf{\emph x}_i +b) \geq 1\qquad 1 \leq i \leq N$

这种模型下的SVM是没有训练误差的，既存在一个线性流形完美分割样本点，然而事实上这往往不太现实。

三、线性支持向量机（非完美可分）

现实中很少会出现完美可分的情况，因此一个标准的SVM应当考虑两个目标，第一是尽可能拓宽边缘，第二是尽可能减少噪音进入甚至穿过边缘。因此需要引入一种称为软边缘的方法，即允许一定的训练误差。（事实上这种改良还能使线性SVM部分实现非线性可分）

在不等式（3）的基础上加入松弛变量 $\boldsymbol{\xi}$ ，不等式（3）变为：

$y (\textbf{\emph w} \cdot \textbf{\emph x} +b) \geq 1 - \boldsymbol{\xi} \qquad \forall \xi_i \in \boldsymbol{\xi}, \xi_i \ge 0 \qquad (3')$

其中松弛变量 $\boldsymbol{\xi}$ 是一个长度为 $N$ 的向量，当样本点 $x_i$ 所对应的不等式等号成立时，那么松弛变量 $\xi_i$ 是“紧的”，否则就是“松的”（类似凸优化中的互补松弛定理）。如图所示：

通过类似等式（4）的推导方法，可以得出直线（橙色） $\textbf{\emph w} \cdot \textbf{\emph x} +b =1 - \xi$ 和直线（ $bl_2$ ） $\textbf{\emph w} \cdot \textbf{\emph x} +b = 1$ 的距离为 $\frac{\xi}{\left | \textbf{\emph w} \right |}$ 。如上图所示，样本点 $\textbf{\emph x}_j$ 所处的边界线 $bl_j$ 是 $bl_2$ 延向量 $\textbf{\emph w}$ 方向平移 $\frac{\xi}{\left | \textbf{\emph w} \right |}$ 得到的。此时不等式（3'）等号成立，即：

$\textbf{\emph w} \cdot \textbf{\emph x}_j +b = 1 - \xi_j \qquad \xi_j > 0 \qquad$

样本点 $\textbf{\emph x}_j$ 突破了原来的边界线 $bl_2$ （甚至突破了原来的决策边界）。相比之下，样本点 $\textbf{\emph x}_i$ 所处的边界线 $bl_i$ 对应的不等式等号不成立且松弛变量 $\xi_i=0$ （样本点 $x_i$ 和之前完美可分的情况一样），即：

$\textbf{\emph w} \cdot \textbf{\emph x}_i +b > 1$

因此可以看出，在加入软边缘的方法之后，可以通过松弛变量向量 $\boldsymbol{\xi}$ 来度量SVM分类器的第二个目标：尽可能少的噪音进入甚至穿过边缘（尽可能少的训练误差），而向量 $\boldsymbol{\xi}$ 中大于0的元素所对应的正是穿过边缘边界线的样本点，而且值越大，穿越程度越大，因此可以通过构造如下成本函数来度量训练误差：

$g(C, k)=C\left ( \sum ^{N}_{i=1}\xi_i \right )^k$

其中 $\sum ^{N}_{i=1}\xi_i$ 简单线性地度量了噪音穿越边界造成的代价， $C$ 和 $k$ 对代价分别进行了线性和几何的缩放，也就是说，参数 $C$ 和 $k$ 决定了软边缘的软硬度，当 $C$ 和 $k$ 中存在0时，边缘最软（可以不计成本的肆意穿越）。

因此目标函数由等式（5）改写为：

$f\left ( \textbf{\emph w} \right )= \frac{\left | \textbf{\emph w} \right |}{2} + C\left ( \sum ^{N}_{i=1}\xi_i \right )^k\qquad \qquad \qquad (5')$

优化问题可以转换为：

$\\argmin \quad f\left ( \textbf{\emph w} \right )= \frac{\left | \textbf{\emph w} \right |}{2} + C\left ( \sum ^{N}_{i=1}\xi_i \right ) \\ s \cdot t \cdot \qquad y (\textbf{\emph w} \cdot \textbf{\emph x}_i +b) \geq 1-\xi_i \qquad 1 \leq i \leq N$

四、非线性支持向量机（非线性变换）

当遇到完全不可分的非线性情况时，如下图所示：

蓝色样本点就是在圆 $\sqrt{(x_1-5)^2(x_2-5)^2}=15$ 周围正态分布，而红色样本点则是在 $\sqrt{(x_1-5)^2(x_2-5)^2}=5$ 周围正态分布，因此最佳的决策边界是圆 $\sqrt{(x_1-5)^2(x_2-5)^2}=10$ ，也就是虚线的圆，这是一个非线性的决策边界。

对决策边界进行简单计算，可以到如下等式：

$\begin{align*} \\& (x_1-5)^2(x_2-5)^2 =x_1^2-10x_1+x_2^2-10x_2+50 =100 \\ \\ & (x_1^2-10x_1)+(x_2^2-10x_2)=50 \end{align*}$

从上面等式可以看到，决策边界是由 $x_1^2-10x_1$ 和 $x_2^2-10x_2$ 构成的一根直线。因此如果能把属性 $x_1$ 和 $x_2$ 进行非线性变换，变成由 $x_1^2-10x_1$ 和 $x_2^2-10x_2$ 表示的属性，那么就可以线性可分了，如下图所示：

其实为了方便展示，上面的例子已经对变换后的空间进行了降维（选取了新空间中两个维度的线性组合）。事实上如果要对数据矩阵进行非线性变换，会产生一个更高维的空间。以这个例子来讲，二维属性 $\textbf{\emph x}_i=(x_1,x_2)$ 通过一个非线性变换 $\Phi$ （二次变换）转换到一个新的线性空间中（注：变换后还是个线性空间，而且决策边界也线性），即：

$\Phi(x_1,x_2) \rightarrow( \beta_1x_1^2, \beta_2x_2^2, \beta_3x_1, \beta_4x_2, \beta_5x_1 x_2, \beta_0 )$

变换后取得了一个5维的高维数据，然后对这个高维数据使用高纬度的线性SVM分类器便可解决问题。非线性SVM的优化问题和线性SVM类似，只是需要对属性做一次非线性变换，进入高维空间中求解凸优化问题，即：

$\\argmin \quad f\left ( \textbf{\emph w} \right )= \frac{\left | \textbf{\emph w} \right |}{2} \\ s \cdot t \cdot \qquad y (\textbf{\emph w} \cdot \Phi(\textbf{\emph x}_i) +b) \geq 1\qquad 1 \leq i \leq N$

上个例子中（ $\beta_i=1$ ）决策边界的 $\textbf{\emph w}= \begin{bmatrix} 1,1,-10,-10,0 \end{bmatrix}$ ， $b=-51$ 。

事实上，这样会极大的浪费计算资源（2维数据变为5维数据），如果样本的属性本身维度较高，那么可能导致维灾难，比如一个1000维的属性数据矩阵，进行二次变换后会得到一个维度为 $2 \times _{1000}^{1}\textrm{C} + _{1000}^{2}\textrm{C}+1=501501$ 的属性数据矩阵，从而需要使用一个50万维的线性SVM来进行分类，计算量大幅上升。

不过核函数技术可以解决上述问题，核函数在本质思想上依然是对原有数据进行升维，但是实际计算的时候是在原空间中进行的。

五、非线性支持向量机（核函数 Kernel Function）

依然考虑上面例子中的非线性变换 $\Phi(x_1,x_2) \rightarrow( x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2, 1 )$ ，其中 $\beta_i$ 取什么值影响不大，这里是为了方便计算。假设有两样本 $\textbf{\emph u}$ 和 $\textbf{\emph v}$ ，那么进行非线性变换 $\Phi$ 后，会得到两个处于新空间中的向量 $\Phi(\textbf{\emph u})$ ， $\Phi(\textbf{\emph v})$ ，这两个向量的点积 $\Phi(\textbf{\emph u}) \cdot \Phi(\textbf{\emph v})$ 可以看做它们在变换后的空间中的相似程度：

$\\ \begin{align*} \Phi(\textbf{\emph u}) \cdot \Phi(\textbf{\emph v}) &=(u_1^2 , u_2^2 , \sqrt{2} u_1 , \sqrt{2} u_2 , \sqrt{2} u_1u_2 , 1) \cdot (v_1^2 , v_2^2 , \sqrt{2} v_1 , \sqrt{2} v_2 , \sqrt{2} v_1v_2 , 1) \\ &=u_1^2 v_1^2 + u_2^2 v_2^2 + 2 u_1v_1 + 2 u_2v_2 + 2 u_1v_1u_2v_2 \\ &=(u_1v_1 + u_2v_2)^2 + 2(u_1v_1 + u_2v_2) + 1 \\ &=(\textbf{\emph u}\textbf{\emph v} + 1)^2 \end{align*}$

通过上面等式的推导可以看出，原本需要在升维的新空间中进行的点积计算可以在更低维度的原空间中完成。上述等式可以记为函数 $K$ ：

$K(\textbf{\emph u}, \textbf{\emph v}) = \Phi(\textbf{\emph u}) \cdot \Phi(\textbf{\emph v}) =(\textbf{\emph u}\textbf{\emph v} + 1)^2$

这个在原空间（低维）中计算变换后空间（高维）的相似度的函数 $K$ 被称为核函数。当且仅当函数 $K$ 为正定核函数（满足Mercer定理）时，才能在在非线性SVM中使用（不确定对不对）。在实践中不需要了解变换 $\Phi$ 的具体形式，可以直接使用函数 $K$ 。

Mercer定理（半懂不懂）：

核函数 $K$ 可以表示为： $K(u,v)=\Phi(u) \cdot \Phi(v)$ ，当且仅当对于任意满足 $\int g(x)^2dx$ 为有限值的函数 $g(x)$ ，则 $\int K(\textbf{\emph x},\textbf{\emph y})g(\textbf{\emph x})g(\textbf{\emph y})d\textbf{\emph x} d\textbf{\emph y} \geq 0$ ，满足Mercer定理的核函数称为正定核函数（positive definite kernel function）（有的文章说是半正定函数）。