支持向量机

支持向量机，其英文名为Support Vector Machine,简称SVM，是基于统计学习理论的结构风险最小化原则，选用最优分类超平面作为判别函数，并引入核函数，将线性不可分问题投射到高维空间后转化为线性可分问题，进而解决分类或回归问题[3,4]。它是20世纪90年代在计算机界发展起来的一种分类方法，自推出以后变得越来越受欢迎。支持向量机在许多问题中都被证实有较好的效果，被认为是适应性最广的分类器之一。

通俗来讲，支持向量机可以看作一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略是间隔最大化，最终可转化为一个凸二次规划问题的求解。

通常把最大间隔分类器、支持向量分类器和支持向量机都简单地叫作“支持向量机”。

最大间隔分类器

在介绍最大间隔分类器之前，首先要介绍一下超平面的定义。

什么是超平面？

在p维空间中，超平面是p-1维的平面仿射子空间。例如，在二维空间中，超平面是一个平直的以为子空间，也就是一条直线。在三维空间中，超平面是一个平坦的二维子空间，也就是一个平面。在p>3维的空间中，很难可视化超平面，但是超平面仍然是一个p-1维的平面子空间。

超平面的数学定义非常简单。在二维空间中，超平面定义为：

为参数。任何满足（1）式的点都在超平面上。因为是二维空间中的超平面，所以是一条直线的方程（图2-31）。

图2-31　二维空间中的超平面

我们将其扩展到多维的情况（图2-32），公式如下：

图2-32　多维空间超平面

该式定义了一个p维的超平面。在P维空间中，任何满足该式的点都落在超平面上。

如果X不满足该式，则有下面公式：说明X位于超平面的一侧。如果满足下面公式的情况：

说明X位于超平面的另一侧。因此，可以认为超平面可以将P维空间分成两个部分。根据此特性我们可以设计二类分类器如下：

这些观测分为两个类别，即,其中-1代表一种类别，1代表另一种类别。

我们定义超平面:

则对所有观测点存在:

即可以根据

的符号对观测点进行分类。的值越大则距离超平面越远。通常来说，如果数据可以被超平面分割，事实上存在无数个这样的超平面（图2-33）。

图2-33　多个超平面

为了构建一个基于超平面的分类器，我们需要从无数个超平面中选出一个合理的，即找出最大间隔超平面，也叫最优超平面（图2-34）。首先我们定义超平面的间隔D：

为第个观测点到超平面的垂直距离。

这里，我们构建最大间隔分类器：

则解该优化问题即可。

图2-34　实线是超平面，虚线表示间隔。

如图2-34所示，有3个训练观测到最大间隔超平面的距离是一样的（都落在虚线上，虚线表示间隔的宽度）。这3个训练观测就叫做支持向量，它们是p维空间中的向量。某种意义上，只要这3个点的位置稍微改变，最大超平面也会随之改变。最大间隔超平面跟其他观测点无关，只要其他观测点移动的时候不越过间隔的边界，最大间隔超平面就不会改变。

支持向量分类器

如果分割超平面确实存在，那么最大间隔分类器是一种非常自然的分类方法。但在许多情况下，并不存在分割超平面，因此也就没有最大间隔分类器。在这种情况下，优化问题在M>0时无解。因此我们将扩展分割超平面的概念，只要求超平面几乎能够把类别区分开，即适用所谓的软间隔。最大间隔分类器在线性不可分情况下的推广叫做支持向量分类器。

图2-35　

图2-35左：实线表示超平面，虚线代表间隔。观测值3～6落在了间隔的正确一侧，第2个观测落在了间隔上，但是第1个观测落在了间隔错误的一侧。第7个和第10个观测落在了正确的一侧，第9个观测落在了间隔上，第8个观测落在了间隔错误的一侧。没有任何一个观测落在超平面错误的一侧。右：与左图相同，只是额外增加了两个点，11和12这两个点不仅落在超平面错误的一侧，还落在间隔错误的一侧。

如图2-35所示支持向量分类器允许一些观测落在间隔错误的一侧，甚至超平面错误的一侧。所选超平面时，如下优化问题的解：

其中，C时非负的调节参数。M是间隔的宽度，目标是最大化M。是松弛变量，松弛变量的作用是允许训练观测中又小部分观测可以落在间隔的错误的一侧或超平面的错误的一侧。

支持向量机

在相应变量只有两个类别的情况下，如果两个类别边界是线性的，适用支持向量分类器进行分类是非常自然的方法。但实际中，经常会碰到非线性分类边界。如图2-36所示，采用支持向量分类器进行分类，得到的结果并不理想。

图2-36　使用支持向量分类器寻求线性的分类边界，分类效果非常不理想

为了解决该问题，我们将支持向量分类器进行扩展，扩展为支持向量机。支持向量机采用了一种特殊的方式，即核函数来扩大特征空间。例如适用二次多项式和三次多项式：

其中，可称为核函数，核函数能够通过扩大特征空间来适应类别之间的非线性边界。

核函数的种类有多种多样，常用的核函数有：

其中d是正整数。跟线性核函数比起来，在支持向量分类器的算法中使用d>1的多项式核函数，能够生成光滑度更高的决策边界。从本质上来说，它是在与多项式的自由度d有关的高位空间中拟合支持向量分类器，而不是在原始的特征空间中拟合支持向量分类器。支持向量分类器与这样的非线性核函数的结合，就是支持向量机。

其中是一个正常数。

LSVM

支持向量机（SVM）是数据分类的强大工具，传统的标准SVM需要解一个二次规划问题，往往速度很慢，计算复杂度又高，而Manga Sarian等人对标准SVM进行修改，提出了一些很好的SVM分类算法。

LSVM算法通过对SVM标准模型原始问题的目标函数作较小改动, 使得其对偶问题转化为一个无上界约束的二次函数的最小值问题, 并最终利用拉格朗日方法迭代进行求解, 避免了分解算法多次求解子问题, 从而大大提高了算法的训练速度。