9.1 背景介绍
9.1.1 SVM 概述
支持向量机(Support Vector Machine, SVM) 由Vapnik首先提出，像多层感知器网络和径向基函数网络一样，支持向量机可用于模式分类和非线性回归。支持向量机的主要思想是建立一个分类超平面作为决策曲面，使得正例和反例之间的隔离边缘被最大化。支持向量机的理论基础是统计学习理论，更精确的说，支持向量机是结构风险最小化的近似实现。这个原理基于这样的事实：学习机器在测试数据上的误差率(即泛化误差率)以训练误差率和一个依赖于VC维数(Vapnik-Chervonenkis dimension)的项的和为界，在可分模式情况下，支持向量机对于前一项的值为零，并且使第二项最小化。因此，尽管它不利用问题的领域内部问题，但在模式分类问题上支持向量机能提供好的泛化性能，这个属性是支持向量机特有的。
支持向量机具有以下的优点:
(1) 通用性(能够在很广的各种函数集中构造函数)。
(2) 鲁棒性(不需要微调)。
(3) 有效性(在解决实际问题时总是属于最好的方法之一)。
(4) 计算简单(方法的实现只需要利用简单的优化技术)。
(5) 理论上完善(基于vc推广性理论的框架)。
在支持向量x(i)和输入空间抽取的向量x之间的内积核这一个概念是构造支持向量机学习算法的关键。支持向量机由算法从训练、数据中抽取的小子集构成。
支持向量机的体系结构如图9-1所示。
2. 多分类支持向量机
SVM算法最初是为二值分类问题设计的，在处理多类问题时需要构造合适的多类分类器。目前构造SVM多类分类器的方法主要有两类：一类是直接法，直接在目标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题"一次性"实现多类分类。这种方法看似简单，但计算复杂度比较高，实现起来比较困难，只适用于解决小型问题；另一类是间接法，主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有一对多和一对一两种。
(1) 一对多法(one-versus-rest，简称l-v-r SVMs)。训练时依次把某个类别的样本归为一类，其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本归入具有最大分类函数值的那类。
(2) 一对一法(one-versus-one，简称l-v-l SVMs)。其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。下面要介绍的LIBSVM工具箱中的多分类就是根据这个方法实现的。
(3) 层次支持向量机(H-SVMs)。层次分类法首先将所有类别分成两个子类，再将子类进一步划分成两个次级子类，如此循环，直到得到一个单独的类别为止。
(4) 其他多类分类方法。除了以上几种方法外，还有有向无环图SVM(DirectedAcyclic Graph SVMs，简称DAG-SVMs)和对类别进行二进制编码的纠错编码SVMs。
实现SVM的工具箱有很多种，比如较新版本的MATLAB自带SVM实现、LIBSVM、LSSVM、SVMlight、Weka等，不同的SVM实现工具箱或函数各有利弊，本章的SVM的实现采用的是LIBSVM工具箱，下面介绍LIBSVM工具箱。
9.1.2 LIBSVM工具箱
使用和快速有效的SVM模式识别与回归的软件包，不但提供了编译好的可在Windows系列系统的执行文件，还提供了源代码，方便改进、修改以及在其他操作系统上应用。该软件还有一个特点，就是对SVM所涉及的参数调节相对比较少，提供了很多的默认参数，利用这些默认参数可以解决很多问题；另外也提供了交互检验(Cross Validation)的功能。该软件包可以在htttp://www.csie.ntu.edu.tw/~cjlin免费获得。该软件可以解决C-SVC(C-support vector classification)、nu-SVC(nu-support vector classification)、one-classSVM(distribution estimation)、epsilon-SVR(epsilon-support vector regression)、nu-SVR(nu-support vector regression)等问题，包括基于一对一算法的多类模式识别问题。SVM用于模式识别或回归时，SVM方法及其参数、核函数及其参数的选择目前国际上还没有形成一个统一的模式，也就是说最优SVM算法参数选择还只能是凭借经验、实验对比、大范围的搜寻或者利用软件包提供的交互检验功能进行寻优。
目前，LIBSVM拥有Java、Matlab、C#、Ruby、Python、R、Perl、CommonLISP、Labview等数十种语言版本。最常使用的是Matlab、Java和命令行的版本。截止到2014年6月1日，LIBSVM的最新版本为3.18(2014年4月1日更新)，可在http://www.csie.ntu.edu.tw/~cjlin/libsvm/下载。
下面介绍LffiSVM工具箱中的主要函数。
1. 训练函数
model=svmtrain(train_label, train_data, options)；
输入参数如下。
● train data：训练集属性矩阵，大小为n×m，n表示样本数，m表示属性数目(维数)，数据类型为double。
● train label：训练集标签，大小为n×1，n表示样本数，数据类型为double。
● options：参数选项，比如'-c 1 -g 0.1'。
输出参数model指训练得到的模型，是一个结构体。当使用-v参数时，返回的model不再是一个结构体，分类问题返回的是交叉验证下的平均分类准确率，回归问题返回的是交叉检验下的平均均方根误差(MSE)。
2. 预测函数
[predict_label, accuracy/mse, dec_value]=svmpredict(test_label, test_data, model)；
输入参数如下。
● test_data：测试集属性矩阵，大小为N×m，N表示测试集样本数，m表示属性数目(维数)，数据类型为double。
● test_label：测试集标签，大小为N×1，N表示样本数，数据类型为double。如果没有测试集标签，则可以用任意的N×1的列向量代替，此时的输出accuracy/mse就没有参考价值。
● model：训练得到的模型。
输出参数如下：
● predict_label：预测的测试集的标签，大小为N×1，N表示样本数，数据类型为double。
● accuracy/mse：一个3×1的列向量，第一个数表示分类准确率(分类问题使用)，第二个数表示mse(回归问题使用)，第三个数表示平方相关系数(回归问题使用)。如果测试集的真实标签事先无法得知，则此返回值没有参考意义。
● dec_value：决策值。