支持向量机简介

1. 模型背景

在机器学习中，支持向量机（SVM）是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

除了进行线性分类之外，SVM还可以使用所谓的核技巧有效地进行非线性分类，将其输入隐式映射到高维特征空间中。当数据未被标记时，不能进行监督式学习，需要用非监督式学习，它会尝试找出数据到簇的自然聚类，并将新数据映射到这些已形成的簇。将支持向量机改进的聚类算法被称为支持向量聚类，当数据未被标记或者仅一些数据被标记时，支持向量聚类经常在工业应用中用作分类步骤的预处理。

2. 模型原理

支持向量机（Support Vector Machine, SVM）是一类按监督学习（supervised learning）方式对数据进行二元分类的广义线性分类器（generalized linear classifier），其决策边界是对学习样本求解的最大边距超平面（maximum-margin hyperplane）。

SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用图1来说明。对于一维空间中的点，二维空间中的直线，三维空间中的平面，以及高维空间中的超平面，图中实心点和空心点代表两类样本，H为它们之间的分类超平面，H₁，H₂分别为过各类中离分类面最近的样本且平行于分类面的超平面，它们之间的距离△叫做分类间隔(margin)。

图1 最优分类面示意图

所谓最优分类面要求分类面不但能将两类正确分开，而且使分类间隔最大。将两类正确分开是为了保证训练错误率为0，也就是经验风险最小(为O)。使分类空隙最大实际上就是使推广性的界中的置信范围最小，从而使真实风险最小。推广到高维空间，最优分类线就成为最优分类面。

设线性可分样本集为是类别符号。d维空间中线性判别函数的一般形式为是类别符号。d维空间中线性判别函数的一般形式为，分类线方程为。将判别函数进行归一化，使两类所有样本都满足，也就是使离分类面最近的样本的，此时分类间隔等于，因此使间隔最大等价于使 (或)最小。要求分类线对所有样本正确分类，就是要求它满足

      （1-1）

满足上述条件(1-1)，并且使最小的分类面就叫做最优分类面，过两类样本中离分类面最近的点且平行于最优分类面的超平面H₁，H₂上的训练样本点就称作支持向量(support vector)，因为它们“支持”了最优分类面。

利用Lagrange优化方法可以把上述最优分类面问题转化为如下这种较简单的对偶问题，即：在约束条件，

                                     （1-2a）

                                (1-2b)

下面对求解下列函数的最大值：

                     （1-3）

若为最优解，则

                             （1-4）

即最优分类面的权系数向量是训练样本向量的线性组合。

这是一个不等式约束下的二次函数极值问题，存在唯一解。根据kühn-Tucker条件，解中将只有一部分(通常是很少一部分)不为零，这些不为0解所对应的样本就是支持向量。求解上述问题后得到的最优分类函数是：

                  (1-5)

根据前面的分析，非支持向量对应的均为0，因此上式中的求和实际上只对支持向量进行。是分类阈值，可以由任意一个支持向量通过式(1-1)求得(只有支持向量才满足其中的等号条件)，或通过两类中任意一对支持向量取中值求得。

从前面的分析可以看出，最优分类面是在线性可分的前提下讨论的，在线性不可分的情况下，就是某些训练样本不能满足式(1-1)的条件，因此可以在条件中增加一个松弛项参数，变成：

                        (1-6)

对于足够小的s>0，只要使

                               (1-7)

最小就可以使错分样本数最小。对应线性可分情况下的使分类间隔最大，在线性不可分情况下可引入约束：

                                （1-8）

在约束条件(1-6)幂1(1-8)下对式(1-7)求极小，就得到了线性不可分情况下的最优分类面，称作广义最优分类面。为方便计算，取s=1。为使计算进一步简化，广义最优分类面问题可以迸一步演化成在条件(1-6)的约束条件下求下列函数的极小值：

                          (1-9)

其中C为某个指定的常数，它实际上起控制对锩分样本惩罚的程度的作用，实现在错分样本的比例与算法复杂度之间的折衷。求解这一优化问题的方法与求解最优分类面时的方法相同，都是转化为一个二次函数极值问题，其结果与可分情况下得到的(1-2)到(1-5)几乎完全相同，但是条件(1-2b)变为：

                            (1-10)

对于非线性问题，可以通过非线**换转化为某个高维空间中的线性问题，在变换空间求最优分类超平面。这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是我们可以看到，在上面对偶问题中，不论是寻优目标函数（1-3）还是分类函数(1-5)都只涉及训练样本之间的内积运算。设有非线性映射将输入空间的样本映射到高维(可能是无穷维)的特征空间H中，当在特征空间H中构造最优超平面时，训练算法仅使用空间中的点积，即，而没有单独的出现。因此，如果能够找到一个函数K使得

                           (1-11)

这样在高维空间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数实现的，我们甚至没有必要知道变换中的形式。根据泛函的有关理论，只要一种核函数满足Mercer条件，它就对应某一变换空间中的内积。因此，在最优超平面中采用适当的内积函数就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加。此时目标函数(1-3)变为：

                 (1-12)

而相应的分类函数也变为

                     (1-13)

算法的其他条件不变，这就是SVM。概括地说SVM就是通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间，在这个特征空间中构造最优分类超平面。在形式上SVM分类函数类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应于一个支持向量，如图2所示

图2 SVM示意图

其中，输出(决策规则)：，权值，为基于s个支持向量的非线性变换(内积)，为输入向量。

选择满足Mercer条件的不同内积核丞数，就构造了不同的SVM，这样也就形成了不同的算法。目前研究最多的核函数主要有三类：

• 多顼式核函数

                       （1-14)

其中q是多项式的阶次，所得到的是q阶多项式分类器。

• 径向基函数(RBF)

                      (1-15)

所得的SVM是一种径向基分类器，它与传统径向基函数方法的基本区别是，这里每一个基函数的中心对应于一个支持向量，它们以及输出权值都是由算法自动确定的。径向基形式的内积函数类似人的视觉特性，在实际应用中经常用到，但是需要注意的是，选择不同的S参数值，相应的分类面会有很大差别。

• S形核函数

                 (1-16)

这时的SVM算法中包含了一个隐层的多层感知器网络，不但网络的权值、而且网络的隐层结点数也是由算法自动确定的，而不像传统的感知器网络那样由人凭借经验确定。此外，该算法不存在困扰神经网络的局部极小点的问题。

在上述几种常用的核函数中，最为常用的是多项式核函数和径向基核函数。除了上面提到的三种核函数外，还有指数径向基核函数、小波核函数等其它一些核函数，应用相对较少。事实上，需要进行训练的样本集有各式各样，核函数也各有优劣。B.Bacsens和S.Viaene等人曾利用LS-SVM分类器，采用UCI数据库，对线性核函数、多项式核函数和径向基核函数进行了实验比较，从实验结果来看，对不同的数据库，不同的核函数各有优劣，而径向基核函数在多数数据库上得到略为优良的性能。

3. 实施分析步骤

Libsvm是一个简单的，易用的，高效的SVM分类和回归软件。它解决了 C-SVM 分类，nu-SVM 分类，one-class-SVM，epsilon-SVM 回归，nu-SVM 回归（的问题）。它也提供了一个自动的 C-SVM 分类的模型选择工具。

LIBSVM 使用的一般步骤是：

1）准备数据集，转化为 LIBSVM支持的数据格式 ：[label] [index1]:[value1] [index2]:[value2] ...即 [l类别标号] [特征1]:[特征值] [特征2]:[特征值] ...

2）对数据进行简单的缩放操作（scale）；（为什么要scale，这里不解释了）

3）考虑选用核函数（通常选取径函数，程序默认）；

4）采用交叉验证（一般采用5折交叉验证），选择最佳参数C与g ；

5）用得到的最佳参数C与g 对整个训练集进行训练得到SVM模型；

6）用得到的SVM模型进行测试

4. 输入输出参数设置

具体公式如第二部分模型原理所示，SVM最重要的参数有2个：C与核函数中的σ：

• C类似于正则化中1λ的作用。C越大，拟合非线性的能力越强。

large C: High Variance；

small C: High Bias；

• σ的大小对核函数形状的影响关系见下图

图 参数大小对核函数形状影响

σ越大，f越平滑，非线性效能越小，对噪声越不敏感

large σ: High Bias；

small σ: High Variance；

5. 运行效果评价

SVM具有以下特点：

1）非线性映射是SVM方法的理论基础，SVM利用内积核函数代替向高维空间的非线性映射；

2）对特征空间划分的最优超平面是SVM的目标，最大化分类边际的思想是SVM方法的核心；

3）支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。因此，模型需要存储空间小，算法鲁棒性强；

4）无任何前提假设，不涉及概率测度；

5）SVM算法对大规模训练样本难以实施

由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及N阶矩阵的计算（N为样本的个数），当N数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法

6）用SVM解决多分类问题存在困难

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。

6. 模型应用

SVM方法在理论上具有突出的优势，贝尔实验室率先对美国邮政手写数字库识别研究方面应用了SVM方法，取得了较大的成功。在随后的近几年内，有关SVM的应用研究得到了很多领域的学者的重视，在人脸检测、验证和识别、说话人/语音识别、文字/手写体识别、图像处理、及其他应用研究等方面取得了大量的研究成果，从最初的简单模式输入的直接的SVM方法研究，进入到多种方法取长补短的联合应用研究，对SVM方法也有了很多改进。

Osuna最早将SVM应用于人脸检测．并取得了较好的效果。其方法是汽接训练非线性SVM分类器完成人脸与非人脸的分类。由于SVM的训练需要大量的存储空间，并且非线性SVM分类器需要较多的支持向量，速度很慢。为此，马勇等提出了一种层次型结构的SVM分类器，它由一个线性SVM组合和一个非线性SVM组成。检测时，由前者快速排除掉图像中绝大部分背景窗口，而后者只需对少量的候选区域做出确认；训练时，在线性SVM组台的限定下，与“自举(bootstrapping)”方法相结合可收集到训练非线性SVM的更有效的非人脸样本，简化SVM训练的难度，大量实验结果表明这种方法不仅具有较高的检测率和较低的误检率，而且具有较快的速度。

人脸检测研究中更复杂的情况是姿态的变化。叶航军等提出了利用支持向量机方法进行人脸姿态的判定，将人脸姿态划分成6个类别，从一个多姿态人脸库中手工标定训练样本集和测试样本集，训练基于支持向量机姿态分类器，分类错误率降低到1.67％。明显优于在传统方法中效果最好的人工神经元网络方法。

在人脸识别中，面部特征的提取和识别可看作是对3D物体的2D投影图像进行匹配的问题。由于许多不确定性因素的影响，特征的选取与识别就成为一个难点。凌旭峰等及张燕昆等分别提出基于PCA与SVM相结合的人脸识别算法，充分利用了PCA在特征提取方面的有效性以及SVM在处理小样本问题和泛化能力强等方面的优势，通过SVM与最近邻距离分类器相结合，使得所提出的算法具有比传统最近邻分类器和BP网络分类器更高的识别率。王宏漫等在PCA基础上进一步做ICA，提取更加有利于分类的面部特征的主要独立成分；然后采用分阶段淘汰的支持向量机分类机制进行识别。对两组人脸图像库的测试结果表明，基于SVM的方法在识别率和识别时间等方面都取得了较好的效果。