支持向量机的算法及应用综述

张松兰

摘要：支持向量机（SVM）是在统计学习的VC维理论和结构风险最小化原理基础上建立起来的机器学习方法，其训练算法本质上是一个二次规划的求解问题。首先简述了SVM的基本原理，然后对SVM算法进行了概括，如块算法、分解算法，序列最小优化算法及最小二乘支持向量机、模糊支持向量机和粒度支持向量机等。接着介绍了支持向量机的应用，最后对该领域存在的问题和发展趋势进行了展望。

关键词：支持向量机；统计学习理论；训练算法

中图分类号：O234 文献标识码：A 文章编号：2095-7394（2016）02-0014-04

支持向量机是在统计学习理论的基础上，以结构风险最小化为原则建立起来的机器学习算法，通过控制参数自动调节模型结构，实现经验风险和结构风险最小化。在解决小样本、高维问题和非线性问题等方面表现出良好的泛化能力和预测性能，在人脸检测、数据挖掘、图像处理、语音识别、故障诊断、网页分类、系统建模与辨识、模式识别等诸多领域有着广泛的应用。

1 支持向量机基本原理

对于线性可分问题，支持向量机运用优化算法实现最大化分类间隔；而对于非线性问题，支持向量机通过适当的核函数将输入空间映射到高维空间，实现高维空间线性可分，将非线性问题转化线性问题，然后在新空间中利用二次型寻优算法求取最优线性分类面，从而将两类样本区分开来，如图1所示。图中空心点和实心点分别表示两种不同类型的数据，H、H₁、H₂是区分两类数据的分类面。其中H₁，H₂是划分两类数据的边缘分类面，它们之间的距离margin就是两类之间的分类间隔，而图中位于分类面H₁，H₂上的空心点和实心点即为支持向量。支持向量机实现非线性映射的目的就是寻求一个最优的分类面使两类之间的分类间隔最大，同时在映射的复杂性和样本数据的学习泛化能力方面达到最佳。

对于由多个样本对构成的数据集{x_i，y_i}，X_i∈Rⁿ，Y_i∈{+1，-1}，SVM设计的目的是寻求一个具有最大间隔的超平面g（x）=ω^TX+b=0，将所有训练样本正确分类，并使分类的误差最小，因此实现最优分类面变成求解下列问题。

其中，Φ（X_i）是Rⁿ→R^m，m>n是非线性映射方程，实现样本数据从低维空间映射到高维空间的映射，在特征空间构造最优分类超平面实现最大化分类间隔。ε是松驰变量，表示数据点的误差度量；C为可调的惩罚参数，表示对分类错误的惩罚程度。

由于，L（ω）是二次型函数有唯一的极小点，利用拉格郎日优化方法将最优分类面问题转化为其对偶形式：

2 支持向量机的基本算法

基本的支持向量机算法基本思想是在二次规划的基础上不断迭代寻找支持向量，主要有块算法、分解算法、序列最小优化算法、增量算法等，下面介绍这几种基本的支持向量机算法。

2.1 块算法

块算法是通过KKT条件逐步迭代删除矩阵中Lagrange乘子为零的行和列，保留非零的支持向量部分，从图1中可知对于给定的整个样本数据而言，支持向量相对较少，这样通过不断迭代将一个大型二次规划问题分解为小规模的二次规划问题，将样本空间降为支持向量空间，样本数量减小，从而降低了训练过程对计算机的存储容量要求，加快了训练速度，其训练速度最终受支持向量数目的影响。

2.2 分解算法

分解算法也是对大型二次规划问题进行分解，迭代过程与块算法相似，但分解算法是将训练样本分成工作集和非工作集，选取Lagrange乘子分量的一个子集为工作集，每次迭代时只对工作集进行寻优，而非工作集保持不变，不断迭代找出最优工作集，此算法的收敛速度取决于最优工作集的选择算法。

2.3 序列最小优化算法

文献提出的序列最小优化（sequential mini-mal optimization，SMO）算法是在分解算法的基础上发展起来的，它将工作集减少为只有2个样本。通过两个嵌套的循环寻找待优化的两个样本，外层循环主要寻找工作集的第一个样本；然后采用启发式规则选择第二个样本，选择的原则是使目标函数靠近最优点的速度达到最快；最后用解析的方法快速对选定的样本进行优化。工作集的选择采用启发式选择策略加快了算法的收敛速度，同时减小了矩阵存储空间，适合于稀疏样本。

2.4 增量算法

增量学习在处理新增样本时，只对新样本有关的部分进行增加修改或删除操作，抛弃与之无关的部分。增量训练算法的学习过程不是一次离线完成的，而是逐一加入数据不断反复优化的过程。Ralaivola提出的增量式学习方法只更新对学习结果影响最大的Lagrange系数，以减少计算复杂度。文献提出了一种快速增量学习算法，先找出支持向量进行支持向量机的增量学习，进而求出最优分类面，加快学习速度。

以上几种基本算法本质上都是将一个大规模的二次规划问题分解为小的二次规划问题，不同的是分解策略和工作集的选取方法，这也是导致算法收敛速度快慢的原因。

3 支持向量机的改进算法

随着研究的深入基本支持向量机的算法产生了各自的缺陷，根据实际研究问题的需要通过线性化方法、增加函数项、方法融合等进行处理，因而SVM训练算法也不断发展和改进，减弱缺陷的影响程度。

3.1 最小二乘支持向量机

在求解大型QP问题时，基本支持向量机算法中的块算法和分解算法会存在维数灾难和求解速度过慢等问题，在支持向量机的求解过程中约束条件为不等式约束，为简化寻优过程并保证一定的学习速度，用等式约束来代替式（1）中的不等式约束，用最小二乘损失函数代替不敏感损失函数来简化求解过程，从而得到最小二乘支持向量机算法。

3.2 模糊支持向量机

由于实际样本检测时存在不同程度的噪声，需要从样本数据中将非正常数据筛以除降低其影响。具体实施方法为：通过在训练样本数据集中增加每个样本的隶属度项，如对样本中的噪声数据和孤立点给予较小的隶属度，正常的样本赋予较大的隶属度，从而对不同的样本起到惩罚作用，降低噪声数据对分类最优平面的影响。模糊支持向量机算法结合模糊数学方法通过在基本支持向量机算法的基础上增加隶属度值对最优平面起到调节作用，提高分类精度。但样本数据中如果异常数据较多时，会影响支持向量机的泛化学习能力，另外由于增加了隶属度项，使得核函数计算复杂，训练速度降低。

3.3 粒度支持向量机

粒度支持向量机在支持向量机学习算法中加入了粒度计算，通过关联规则及聚类等方式来划分粒度，构建粒度空间的信息粒，再利用信息粒上的信息得到SVM目标函数。目前，粒度划分的主要研究有：基于关联规则的粒度支持向量机，利用关联规则挖掘样本数据集的频繁模式，分割样本特征空间建立粒度空间，最后在粒度特征空间上进行训练学习。基于聚类的粒度支持向量机是对样本空间的数据利用聚类方法进行粒度划分，然后从中选择携带有较多信息的粒来学习样本信息，从而实现分类或回归问题。

3.4 多类训练算法

随着研究问题的复杂化，现实的分类问题不单纯是正反两类，会存在多类的现象。对多分类问题需构造多类SVM分类器，主要通过目标函数和分类器来完成。对应的实现途径主要有两种：一种是通过选取合适的目标函数来实现k类分类支持向量机。由于实际问题存在多类，因而选择的目标函数变量多，求解过程复杂，一般只用于解决小型问题。另一种实现方法基于两分类器的分类思想，将多个两分类器进行组合，主要方法有一对多算法、一对一算法、决策导向无环图。一对多算法对k个类的样本需构造k个分类器，样本对应的决策函数最大即为所对应的类。一对一算法对k类训练样本中的任两类构造一个分类器，两两组合构造多个分类器，然后在这些分类器中使用投票法累计各个类的投票数，其中得票数最多的类即为样本点所属的类。当类别较大时组合分类器数量较多，影响分类预测速度。对此Platt等提出了一个新的学习架构：决策导向无环图。每个分类器有两类，类似于二叉树，在分类过程中由根部开始经各层中间节点逐步向叶节点分类，这种分类方法能提高支持向量机的分类速度和性能。

4 支持向量机算法的应用

4.1 模式识别

支持向量机在模式识别领域的应用最广泛，已成功地解决了诸如手写体、图像处理、语音识别等许多识别和分类问题。

在手写字体识别方面，当采用5层神经网络算法时，其识别的错误率为5.1%；贝尔实验室最先将SVM应用于手写字体识别研究，选取三种不同的核函数时，得到的误识率分别为4.0%，4.1%和4.2%，可看出支持向量机方法比神经网络算法具有更好的分类准确性。柳回春等在SVM的基础上结合与RBF神经网络将其用于UK心理测试自动分析系统的手写体数字识别问题。

在人脸识别方面，由于人脸图像存储和SVM训练需要大量的存储空间，周志明等人将小波变换与支持向量机相结合，由小波变换提取人脸特征，减小特征向量维数并将其输入到SVM中，并结合最近邻分类器进行分类，提高了分类器的鲁棒性和分类精度。

在语音识别方面，由于背景环境中存在不同程度的噪杂声，根据支持向量机和隐式马尔可夫模型相结合的特点，忻栋等建立SVM和隐式马尔可夫模型两者相结合的混合模型，算法比较复杂，用来解决语音识别问题。

4.2 网页分类

在中文网页分类问题上，贺海军等在网页文本的特征表示和二分类问题的基础上，把二叉决策树和SVM算法相结合构成多类分类器，实现网页文本的分类，取得了较好的分类效果和训练速度。

在网络入侵检测分类方面，网络入侵检测其实也是一种网页分类。徐文龙等提出了一种基于从特殊到特殊的直推式支持向量机，从获取的网络数据中进行归纳式学习和标记样本，从中提出特征输入到TSVM学习机中进行学习，检测其异常的网络入侵，提高了测试样本的分类准确度。

4.3 系统建模与系统辨识

在未知非线性系统建模方面，张浩然等利用对象的输入输出数据集，在非线性系统的控制结构设计中采用支持向量机建模来获取对象的动态特性，以SVM作为辨识器在控制器中采用指数梯度法实现控制作用。

在非线性系统的辨识方面，崔万照等刚将最小二乘方法应用于支持向量机算法中并选择小波函数作为支持向量机的核函数，构造最小二乘小波支持向量机来解决单输入单输出（SISO）非线性系统的辨识问题，仿真结果表明此方法能提高辨识效果，加快系统响应时间。

5 结论与讨论

SVM以统计学习理论为基础，存在全局优化、泛化性能好等优点，同时也存在诸多缺陷，有很多问题需深入研究。

（1）支持向量机算法的核心是核函数及其参数，它们的正确选取对SVM的预测及泛化性能影响很大。对于具体的研究问题，究竟选择哪种核函数并找到最优的参数对求解问题至关重要。因此，如何快速准确地选择核函数及对应的参数来满足快速性和准确性要求是迄待解决的问题。

（2）在大规模及实时性要求较高的系统中，SVM算法受制于求解问题的收敛速度和系统规模的复杂程度。在非线性系统的SVM训练算法中，尤其要处理大规模数据时，需要解决样本规模和速度间的矛盾，提高训练算法的效率和精度。

（3）如何有效地将二类别分类器有效地扩展到多类别问题上，多类SVM的优化设计也是今后研究的内容。

（4）针对特定问题如何实现支持向量机与其他算法的融合，从而顺利解决待求问题也是需要研究的方向。

（5）目前的SVM研究侧重于理论研究，真正的实践应用还有一段距离。

目前，SVM仍然存在很多问题需进一步的研究，可将SVM与离散余弦变换、小波包分解、主元分析、独立分量分析、聚类、粗糙集理论等方法结合，提高应用效果并不断探索SVM新的应用领域。

责任编辑 祁秀春