3.6 基于支持向量机的分类法
3.6.1 支持向量机简介
从观测数据中学习归纳出系统运动规律，并利用这些规律对未来数据或无法观测到的数据进行预测一直是智能系统研究的重点。传统学习方法中采用的经验风险最小化方法（ERM）虽然将误差最小化，但不能最小化学习过程的泛化误差。ERM方法不成功的例子就是神经网络中的过学习问题。为此，由Vapnik领导的贝尔实验室研究小组于1963年提出了一种新的非常有潜力的分类技术，支持向量机（support vector machine, SVM）是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域。
支持向量机的基本思想是在样本空间或特征空间构造出最优超平面，使得超平面与不同类样本集之间的距离最大，从而达到最大的泛化能力。
3.6.2 支持向量机基本思想
图3-12 两类线性分割图
SVM是从线性可分情况下的最优分类面方法发展而来的，基本思想可用图3-12的两类线性可分情况说明。在图3-12中，实心点和空心点代表两类样本，实线P0、P1为分类线。两条虚线分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫作分类间隔。所谓最优分类线就是要求分类线不但能将两个类正确分开（训练错误率为0），而且使分类间隔最大。
分类线方程为
此时分类间隔为2/‖ω‖，使间隔最大等价于使‖ω‖2最小，则可以通过求‖ω‖2/2的极小值获得分类间隔最大的最优超平面。
这里的约束条件为
该约束优化问题可以用Lagrange方法求解，令
其中αi≥0为每个样本的拉氏乘子，由L分别对b和ω导数为0，可以导出
因此，解向量有一个由训练样本集的一个子集样本向量构成的展开式，该子集样本的拉氏乘子均不为0，即支持向量。拉氏乘子为0的样本向量的贡献为0，对选择分类超平面是无意义的。于是，就从训练集中得到了描述最优分类超平面的决策函数即支持向量机，它的分类功能由支持向量决定。这样决策函数可以表示为
3.6.3 支持向量机的几个主要优点
（1）它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值。
（2）算法最终将转化成为一个二次型寻优问题。从理论上说，得到的将是全局最优点，解决了在神经网络方法中无法避免的局部极值问题。
（3）算法将实际问题通过非线性变换转换到高维的特征空间（feature space）。在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关。
3.6.4 训练集为非线性情况
对于实际上难以线性分类的问题，待分类样本可以通过选择适当的非线性变换映射到某个高维的特征空间，使得在目标高维空间的这些样本线性可分，从而转化为线性可分问题。Cover定理表明，通过这种非线性转换将非线性可分样本映射到足够高维的特征空间，非线性可分的样本将以极大的可能性变为线性可分。如果这个非线性转换为ф（x），则超平面决策函数式可重写为
3.6.5 核函数
在上面的问题中只涉及训练样本之间的内积运算。实际上在高维空间只需进行内积运算，用原空间中的函数即可实现，甚至没有必要知道变换的形式。根据泛函的有关理论，只要一种K（x，xi）核函数满足Mercer条件，它就对应某一变换空间中的内积。因此，在最优分类面中采用适当的内积函数K（x，xi）就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加。核函数存在性定理表明：给定一个训练样本集，就一定存在一个相应的函数，训练样本通过核函数映射到高维特征空间的相是线性可分的。
对于一个特定的核函数，给定的样本集中的任意一个样本都可能成为一个支持向量。这意味着在一个支持向量机算法下观察到的特征在其他支持向量机算法下（其他核函数）并不能保持。因此对于解决具体问题来说，选择合适的核函数是很重要的。
常见的核函数有3类。
（1）多项式核函数。
（2）径向基函数（RBF）。
（3）采用Sigmoid函数作为内积。
3.6.6 多类分类问题
基本的支持向量机仅能解决两类分类问题。一些学者从两个方向研究用支持向量机解决多类分类问题：一个方向是将基本的两类支持向量机（Binary-class SVM, BSVM）扩展为多类分类支持向量机（multi-class SVM, MSVM），使支持向量机本身成为解决多类分类问题的多类分类器；另一方向则相反，将多类分类问题逐步转化为两类分类问题，即用多个两类分类支持向量机组成的多类分类器。
1．多类分类支持向量机MSVM
实际应用研究中多类分类问题更加常见，只要将目标函数由两类改为多类（k类）情况，就可以很自然地将BSVM扩展为多类分类支持向量机MSVM，以相似的方式可得到决策函数。
2．基于BSVM的多类分类器
这种方案是为每个类构建一个BSVM，如图3-13所示。对于每个类的BSVM，其训练样本集的构成是：属于该类的样本为正样本，而不属于该类的其他所有样本为负样本，即该BSVM分类器将该类样本和其他样本分开。在1-a-1分类过程中训练样本需要重新标注，因为一个样本只有在对应类别的BSVM分类器才是正样本，对其他的BSVM分类器都是负样本。
1）1-a-1分类器（One-against-one classifiers）
对于1-a-1分类器，解决k类分类问题就需要用到BSVM，这种方案是每两个类别训练一个BSVM分类器，如图3-14所示。最后一个待识别样本的类别是由所有k（k-1）/2个BSVM“投票”决定的。
图3-13 BSVM分类原理图
图3-14 1-a-1分类原理图
2）多级BSVM分类器
这种方案是把多类分类问题分解为多级的两类分类子问题，如图3-15所示。两种典型方案中，A、B、C、D、E、F分别表示7个不同的类。
图3-15 BSVM多级分类
3.6.7 基于SVM的MATLAB实现
1．建立模型流程图
基于SVM的数据分类设计流程如图3-16所示。
图3-16 基于SVM的数据分类设计流程
2．数据预处理
对训练集和测试集进行归一化预处理，采用［0，1］区间归一化。
3．训练和预测
以下是MATLAB中LibSVM工具箱中自带的SVM训练和预测的语句。
4．LibSVM工具箱简介
LibSVM是台湾大学林智仁教授等人开发设计的一个简单、易于使用且快速有效的SVM模式识别与回归的软件包。它不但提供了编译好的可在Windows系统中执行的文件，还提供了源代码，方便用户改进、修改以及在其他操作系统上应用。该软件还有一个特点，就是对SVM所涉及的参数调节相对比较少，提供了很多的默认参数，利用这些默认参数就可以解决很多问题；同时还提供了交互检验的功能。
以下是LibSVM工具箱的安装过程。
（1）下载libsvm-mat-2.91-1的压缩文件，将其解压到MATLAB→toolbox的安装路径下。
（2）在MATLAB软件中执行“设置路径”→“添加文件夹”命令，将该压缩包解压后添加到工具箱即可。
5．MATLAB源程序
在程序开始时要将数据进行归一化处理，归一化程序如下：
SVM的MATLAB完整源程序如下：
程序运行完之后，出现如图3-17所示的分类结果图界面。
图3-17 支持向量机分类结果图界面
在MATLAB命令窗口将出现如下结果：
从程序运行结果可以看出分类正确率为96.6667%，有一个样本分错了。
3.6.8 结论
SVM具有优良的学习能力和推广能力，能够有效克服“维数灾难”和“过学习”问题，而SVM的参数是影响分类精度、回归预测的重要因素。仿真结果表明，预测结果可靠，可以为数据提供很好的参考信息。