[科普中国]-支持向量机分类

支持向量机是针对二值分类问题提出的，并且成功地应用子解函数回归及一类分类问题·虽然支持向量机在解决二值分类问题时获得了巨大的成功，但实际应用中的大量多值分类问题也进一步要求如何将支持向量机推广到多分类问题上，目前有以下几种常用的方法1：

一对多法。其思想是把某一种类别的样本当作一个类别，剩余其他类别的样本当作另一个类别，这样就变成了一个两分类问题。然后，在剩余的样本中重复上面的步骤`这种方法箱要构造k个svM模型，其中，k是待分类的个数。这种方案的缺点是训练样本数目大，训练困难。

一对一方法。其做法是在多值分类中，每次只考虑两类样本，即对每两类样本设计一个SVM模型，因此，总共需要设计k(k一l)2/个SVM模型.这种做法需要构造多个二值分类器，并且测试时需要对每两类都进行比较，导致算法计算复杂度很高。

SVM决策树法。它通常和二叉决策树结合起来，构成多类别的识别器。这种方法的缺点是如果在某个节点上发生了分类错误，将会把错误延续下去，该节点后续下一级节点上的分类就失去了意义。weston虽然提出了用一个优化式解多值分类问题’〕，但由于其变量t数目过多，所以只能在小型问题的求解中使用。一类分类方法的出现为异常值检测提供了一条新的思路，该方法通过核映射思想确定一个包含正类样本的紧致区域，以便使异常值更容易暴露出来，从而达到检测的目的。

在统计学习理论中，我们经常使用的就是支持向量机分类，因为它的效果非常好，其中心思想是把结构风险最小化原则应用于分类领域中2。

如何从训练样本中找到一个支持向量，能够建构出最好的分类超平面，这是支持向量机的核心内容，它是从线性可分情况下的最优分类超平面发展而来的。用数学语言描述就是求解一个二次规划问题，这一问题的约束条件可以用不等式的形式表述出来。

我们将训练样本集

分成两个类别，标记为正 的属于第一类 ；标记为负 的属于第二类 。如果我们建构的决策函数能够将被测试数据分开，那么学习目标就达成了。现将训练样本集分为两种情况进行讨论，一种为线性的，另一种为非线性情况。

设训练样本集为

，

其中

，

不妨假设存在一个超平面能够线性划分这个样本集。设这个超平面为

。

如果存在一个超平面能够将训练样本集中的所有向量都正确划分，而且能达到最大边缘化，那这个超平面叫做最优超平面。支持向量就是距离超平面最近的训练样本集中的向量，支持向量和超平面之间是一一对应的关系。

首先考虑线性可分的情况，假定支持向量满足条件：

因为超平面和支持向量之间的距离是 ，可知两个支持向量间的距离是 。所以只要求出 的最小值，就能构造出最优超平面。当样本点在超球体内部时，

的VC维h：

如果超球体的半径是R，那么上式就细化为

支持向量空间的维数用N表示，R是超球体半径，这个超球体能够覆盖所有的支持向量，

.由此可知，VC维随w的减小而减小，所以支持向量机方法的目的是找到最小的w，从而解决风险最小化问题。

如果存在分类超平面

使得：

那么这个训练集就是线性可分的，其中 表示向量 与 的内积。

假设在三维空间中，存在线性可分的两个类别的训练样本集 其中样本维数n=3，样本类别+1或-1用iy来表示.我们致力于找到一个能够准确的把两类样本区分开的分类平面H，并且他们之间的分类间隔是最大的，那么这个分类平面H就被叫做最优分类超平面。

分类平面H、分类平面1H和分类平面2H将几何空间分成三个分类平面，它们之间是平行的位置关系，分类平面H处于分类平面1H和分类平面2H的中间，并且他们之间的距离都是相等的，我们用D来表示。如果样本点得类别为+1，那么它就落在分类平面1H上，如果样本点得类别为-1，那么它就落在分类平面1H上。从数学上看，分类平面H的方程为

其中w，x表示的是向量之间的内积，权值用w表示，常数为b。

最初研究的支持向量机问题都是线性可分的，但在实际应用中多数为线性不可分的情况，为了解决这一难题，我们将输入的数据通过非线性变换(x)将其映射到高维特征空间中去。在高维特征空间中，原空间输入的非线性分类就转化为线性问题。在无限大的高维特征空间中，我们通过构建最优分类超平面：

得到决策函数为

通过式子可以发现，不同于其他最优分类超平面需要以多种形式来描述特征空间，我们所构建的超平面只需要计算向量的内积。假定，把输入向量映射到无限高维特征空间，即由Hilbert-Schmidt理论可知，高维特征空间中的内积可以表示为,我们称K(x1,x2)为核函数，它是满足Mercer定理的对称函数。。核函数相对映射函数简单，而且映射函数的维数很高，因此，引入核函数才能解决维数太大的难题。