链接：https://pan.baidu.com/s/1-gtGwfUt8HZ8Lu9SEieVcQ 

提取码：jio1

支持向量机（ＳＶＭ）是 Ｃｏｒｔｅｓ等人于 １９９５年提出的，它在 解决小样本、非线性及高维模式识别中表现出许多特有的优 势，并能推广应用到函数拟合等其他机器学习问题中。 支持向量机［１］是建立在统计学习理论的 ＶＣ（ＶａｐｎｉｋＣｈｅｒ ｖｏｎｅｎｋｉｓ）维理论和结构风险最小原理基础上的，根据有限的样 本信息在模型的复杂性和学习能力之间寻求最佳折中，以期获 得最好的推广能力。支持向量机具有较强的理论基础，它能保 证找到的极值解是全局最优解而非局部最小值，这也就决定了 ＳＶＭ方法对未知样本有较好的泛化能力，正因为这些优点， ＳＶＭ能良好地应用到模式识别、概率密度函数估计、时间序列 预测、回归估计等领域，也被广泛应用到模式识别中的手写数 字识别［２］、文本分类［３］、图像分类与识别［４］等众多领域中。 ! 支持向量机理论 !! "# 维理论和结构风险最小原理 支持向量机是基于统计学习理论（ＳＬＴ）的新型机器学习 方法。机器学习主要研究的是计算机如何模拟或实现人类的 学习能力，以获取新的知识和技能，重新组织已有的知识结构， 使之不断改善自身的性能。机器学习的实现方法主要有以下 三种：统计预测方法、经验非线性方法、统计学习理论。 ＳＬＴ是一种专门研究小样本情况下机器学习规律的理 论［５］，该理论针对小样本统计问题建立了一套新的理论体系， 在这种体系下的统计推理规则不仅考虑了对渐进性能的要求， 而且追求在现有有限信息条件下能够得到最优结果。 ＳＶＭ是建立在 ＳＬＴ的 ＶＣ维理论和结构风险最小原理基 础上的。关于 ＶＣ维理论［６］的定义是：对一个指示函数集，如 果存在 ｈ个样本能够被一个函数集中的函数按所有可能的 ２ｈ 种形式分开，则称这个函数集能够把 ｈ个样本打散，函数集的 ＶＣ维就是它能打散的最大样本数目 ｈ。ＶＣ维本质上可以理 解为问题的复杂程度，ＶＣ维数越高，则该函数集的机器学习越 复杂。关于结构风险最小原理，ＳＬＴ引入了泛化误差界的概 念，该理论指出，机器学习的实际误差是由经验风险和置信风 险两部分组成。 泛化误差界的公式如下： Ｒ（ｗ）≤ｒｅｍｐ（ｗ）＋φ（ｎ／ｈ） （１） 其中：Ｒ（ｗ）是实际风险，ｒｅｍｐ（ｗ）是经验风险，φ（ｎ／ｈ）是置信 风险。置信风险与两个量相关：ａ）样本数量，样本数量越大，机 器学习结果越有可能正确，置信风险也就越小；ｂ）分类函数的 ＶＣ维，ＶＣ维的维数越大，泛化能力越差，置信风险就会越大。 统计学习的目标就是从寻求经验风险最小化转变为寻求经验 风险与置信风险的和最小，即结构风险最小。ＳＶＭ正是这样 一种使结构风险最小的算法。 !$ %"& 理论 ＳＶＭ理论的初衷是寻求一种处理两类数据分类问题的方 法。ＳＶＭ旨在寻找一个超平面，使得训练样本集中不同类别 第 ３１卷第 ５期 ２０１４年 ５月 计 算 机 应 用 研 究 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｖｏｌ．３１Ｎｏ．５ Ｍａｙ２０１４

的点正好落在超平面的两侧，同时还要求超平面两侧的空白区 域达到最大。对于二维两类线性可分数据，支持向量机理论上 是能够实现最优分类的，推广到高维空间，最优分类线就叫做最 优超平面。对于二维两类数据分类来说，给定的训练样本 Ｄｉ＝ （ｘｉ，ｙｉ），ｉ＝１，…，ｌ，ｙｉ∈｛＋１，－１｝，其中 ｘｉ为输入样本，ｙｉ为两 类的类别值，其超平面为 ｗｘ＋ｂ＝０，样本点到超平面的间隔为 δｉ＝ １‖ｗ‖｜ｇ（ｘｉ）｜。为使训练样本能正确分开，又要保证间隔 最大，这个两类分类问题被转换成了一个带约束的最小值问题： ｍｉｎ １２‖ｗ‖２ （２） ｓｕｂｊｅｃｔｔｏ ｙｉ［（ｗｘｉ）＋ｂ］－１≥０ ｉ＝１，…，ｌ（ｌ是样本数） （３） 本文也把式（２）和（３）的问题叫做二次规划（ｑｕａｄｒａｔｉｃｐｒｏ ｇｒａｍｍｉｎｇ，ＱＰ），由于它的可行域是一个凸集，也可以叫做凸二 次规划。在线性不可分的情况下，需要在条件式（３）中加入一 个松弛变量 ξｉ≥０、惩罚因子 Ｃ，则上面所述凸二次规划问题就 变成 ｍｉｎ １２‖ｗ‖２＋Ｃ∑ｌｉ＝１ξｉ （４） ｓｕｂｊｅｃｔｔｏ ｙｉ［（ｗｘｉ）＋ｂ］≥１－ξｉ ｉ＝１，…，ｌ（ｌ是样本数）；ξｉ≥０ （５） 其中：Ｃ＞０为一个常数，其大小决定了对错分样本惩罚的程度。 下面是上述二次规划问题的求解问题，为了求解，引入了 Ｌａｇｒａｎｇｅ函数：Ｌ＝１２‖ｗ‖２－∑ｌｉ＝１αｉｙｉ（ｗ·ｘｉ＋ｂ）＋∑ｌｉ＝１αｉ （６） 其中：αｉ＞０，为 Ｌａｇｒａｎｇｅ系数，求解上述问题后得出的最优分 类函数为 ｆ（ｘ）＝ｓｇｎ ∑ｌｊ＝１α { [ ｊ ｙｊ（ｘｊ·ｘｉ）] ＋ｂ }  （７） 对于线性不可分的情况，ＳＶＭ的主要思想是将输入向量映 射到一个高维的特征向量空间，并在该特征空间中构造最优分 类面。将 ｘ作非线性映射 Φ：Ｒｎ→Ｈ，Ｈ为高维特征空间，则有 ｘ→Φ（ｘ）＝（Φ１（ｘ），Φ２（ｘ），…，Φｌ（ｘ））Ｔ （８） 求解则可得到最优分类函数为 ｆ（ｘ）＝ｓｇｎ（∑ｌｉ＝１αｉｙｉΦ（ｘｉ）·Φ（ｘ）＋ｂ） （９） $ %"& 算法 ＳＶＭ研究的主要问题就是凸二次规划的求解，传统的 ＳＶＭ算法在计算上存在许多问题，包括训练算法速度慢、算法 复杂而难以实现、测试阶段运算量大、抗击噪声及孤立点能力 差等。所以在 ＳＶＭ算法的研究中，如何提高训练速度、减少训 练时间、建立实用的学习算法是亟待解决的问题。 为了优化凸二次规划求解问题，已有很多学者提出了相应 算法，典型的算法有选块算法（ｃｈｕｎｋｉｎｇａｌｇｏｒｉｔｈｍ）、分解算法 （ｄｅｃｏｍｐｏｓｉｔｉｏｎａｌｇｏｒｉｔｈｍ）、序列最小优化算法（ｓｅｑｕｅｎｔｉａｌｍｉｎｉ ｍａｌｏｐｔｉｍｉｚａｔｉｏｎ，ＳＭＯ），另外还有模糊 ＳＶＭ学习算法、采用光 滑化技巧的学习算法、基于标准 ＳＶＭ的变形算法；近年来比较 热门的还有多分类支持向量机（ｍｕｌｔｉｃｌａｓｓＳＶＭ）等。 $! 选块算法 选块算法最早是由 Ｂｏｓｅｒ等人［７］提出来的。它的主要思 想是去掉核矩阵中 Ｌａｇｒａｎｇｅ乘子为零的样本对应的行和列，这 样得到的结果与用之前矩阵计算得到的结果相同，这就使得大 型复杂的二次规划问题转换为一系列小的子问题。选块算法 的核心是预测样本集中哪些样本的 Ｌａｇｒａｎｇｅ乘子是零，为零的 被丢弃，那些非零（支持向量）的则需要保留下来。然而实际 的支持向量是未知的，于是引入了 ＫＫＴ（ＫａｒｕｓｈＫｕｈｎＴｕｃｋｅｒ） 条件进行逐步迭代，最终得到全局最优解。选块算法将矩阵规 模由训练样本数目的平方减少到非零 Ｌａｇｒａｎｇｅ乘子的样本数 的平方，在很大程度上降低了训练过程对存储容量的要求，因 此能够大大提高训练速度。然而这也只是在一定程度上解决 了大数据集的 ＱＰ问题，选块算法的最终目的是找出所有的支 持向量（ｓｕｐｐｏｒｔｖｅｃｔｏｒ），因而需要存储相应的核函数矩阵。所 以选块算法在本质上还是受 ｓｕｐｐｏｒｔｖｅｃｔｏｒ数目的影响，并未从 根本上解决内存不足问题。 $$ 分解算法 分解算法最早是由 Ｏｓｕｎａ等人［８］提出的，它的主要思想也 是把大型的 ＱＰ问题分解成一系列小的子问题，但是它与选块 算法又是不同的，它是活动集（ａｃｔｉｖｅｓｅｔ）方法的一个变形。它 的算法过程是：在每次迭代中，把 Ｌａｇｒａｎｇｅ乘子 αｉ分为工作集 和非工作集，非工作集在本次迭代中保持不变；工作集为自由 变量，在本次迭代中对这些自由变量进行优化，这个过程一直 进行下去，直到满足停止条件为止。这个算法的关键在于选择 最优工作集来提高该算法的收敛性和收敛速度，但在实际的过 程中工作集的选取是随机的，所以限制了其收敛速度。 对于上述算法中的不足，Ｊｏａｃｈｉｍｓ对 Ｏｓｕｎａ的方法进行了 一系列的改进，提出了选择工作集及其他的一些策略与技术， 并实现了这一算法，最终形成了软件 ＳＶＭｌｉｇｈｔ。在选择工作集 方面，其思想是从全部变量中挑选出 ｑ个变量，这些变量应满 足下述条件：不等于零且与目标函数可行的最速下降方向对 应，这个可以通过求解一个简单的线性优化问题解决。 ＳＶＭｌｉｇｈｔ算法还引入了 ｓｈｒｉｎｋｉｎｇ技术、ｃａｃｈｉｎｇ技术、梯度增 量修正技术等。它对大规模问题，尤其是支持向量比例较小或 者多数支持向量在边界上的情况效果明显。 $' 序列最小优化算法 ＳＭＯ算法 是 分 解 算 法 的 一 种 特 殊 情 况，它 最 早 是 由 Ｐｌａｔｔ［９］提出来的，这个算法的主要特点是其工作集中只有两个 样本，减少到两个的原因是等式线性约束的存在要求至少有两 个 Ｌａｇｒａｎｇｅ乘子发生变化。由于只有两个变量，迭代中这样的 ＱＰ子问题都能用解析方法得到最优解，从而避开了复杂的求 解优化过程，也提高了算法的收敛速度，又不需要大的矩阵存 储空间。ＳＭＯ对于工作集的选择采用的是启发式策略，具体 的办法可以参考文献［１０］。ＳＭＯ算法对线性核的情况最有 效，而对于非线性问题则达不到满意的结果，原因是在线性情 形下，每次最小优化后的重置都是简单运算，但是在非线性情 形下，误差的重置必须对全部支持向量逐个地计算核函数，而 核函数的计算比较复杂，也就需要占有较多的时间。 之后 Ｐｌａｔｔ又对 ＳＭＯ算法进行了一些改进，如借鉴 ＳＶＭｌｉｇｈｔ 对 ＳＭＯ算法进行优化，引入了 ｓｈｒｉｎｋｉｎｇ技术和 ｋｅｒｎｅｌｃａｃｈｅ思 想来提高收敛速度。但是由于 ｓｈｒｉｎｋｉｎｇ技术一般都是在优化 迭代即将结束时才使用，并且 ｓｈｒｉｎｋｉｎｇ中不完全包含集合的 最优非边界乘子，重构目标函数的梯度需要花费很大的代价， 所以基于 ｓｈｒｉｎｋｉｎｇ技术优化还是有其局限性的［１１］。 由于 Ｐｌａｔｔ启发式策略存在不确定性，人们将重心转移到 可行性方向方法上。Ｋｅｅｒｔｈｉ等人［１２］在后来的研究中提出了利 用双阈值优化条件来确定工作集的优化算法，并提出了基于 ｖｉｏｌａｔｉｎｇｐａｉｒ和 τｖｉｏｌａｔｉｎｇｐａｉｒ的 ＧＳＭＯ（ｇｅｎｅｒａｌｉｚｅｄＳＭＯ）的概 ·１２８２· 计 算 机 应 用 研 究 第 ３１卷

念，证明了 ＧＳＭＯ在任何迭代停止标准和停止容忍范围内可 以在有限步骤停止并收敛。文献［１３］中的两种优化改进都是 ＧＳＭＯ的特殊情况。 在核函数占主要地位的 ＳＭＯ算法中，合适的缓存替换策 略在算法的性能改进中扮演了非常重要的角色，但是大多数 ＳＭＯ算法中工作集的选择如 Ｐｌａｔｔ的启发式、Ｋｅｅｒｔｈｉ的改进和 可行方向方法，目的都是使目标函数尽可能多地下降，最快找 到目标函数的最小值。文献［１４］利用边界支持向量数据变化 平缓、缓存更新带来的计算小于重复计算 ＢＳＶ核函数的特征， 提出了一种针对非线性可分样本的高效缓存策略，并把它推广 到 ＳＭＯ之外的分解算法中。文献［１５］在可行性方向策略的 基础上考虑 ｋｅｒｎｅｌｃａｃｈｅ的利用效率，给出了一种收益代价平 衡的工作集选择方法。文献［１６］提出了 ＳＭＯ工作集选择算 法的通用框架模型，即选取与最大违反对成一定函数关系的乘 子为工作集，并提出了基于未定的 Ｑ矩阵的分解算法。文献 ［１７］提出了一种基于目标函数二阶展开 ＳＭＯ算法的工作集 选择法。文献［１８］提出了基于微粒群优化的 ＳＭＯ算法的双 层优化原理，并通过仿真进行了应用研究，验证了其有效性。 文献［１９］对 ＳＭＯ算法进行改进的办法是在选取工作集时，选取 优化步长最大的违反 ＫＫＴ条件的样本和其配对样本，并且对求 解过程进行简化，从而使训练过程速度更快。文献［２０］从变量 优化和变量选择等多个方面对 ＳＭＯ算法进行改进，并且基于改 进后的算法进行了仿真实验，取得了满意的效果。 $( 模糊支持向量机 在进行数据挖掘的时候，数据集中会存在很多的噪声，也 称为模糊信息，这些信息在用 ＳＶＭ算法进行预测的时候，使得 其性能不能得到好的发挥，甚至是无能为力，在这种情况下 Ｌｉｎ等人提出了 ＦＳＶＭ［２１］。该算法将模糊数学与 ＳＶＭ相结合， 主要用于处理训练样本中的噪声数据［２２］，其核心思想是用异 常数据检测方法对训练数据集中的数据进行检测，检测出来异 常数据并赋予它很小的隶属度，这些异常数据也就是噪声或孤 立点；而对支持向量赋予较大的隶属度，这样做的目的就是把 噪声或孤立点从有效样本中分离出去。 模糊支持向量机能够提高分类精度，又能解决异常数据造 成的过学习问题，但是在实际的应用中，也存在一些不足之处， 如异常数据可能会有很多，或者这些异常数据服从某种分布， 在这种情况下如果还按上述算法并分离出这些异常数据，就会 造成信息的丢失，从而使支持向量机的泛化能力受到影响。另 外，模糊支持向量机还存在核函数计算量大、所需内存大、训练 时间长等问题，所以如何优化模糊 ＳＶＭ的训练速度也是至关 重要的。针对上述问题，有很多学者对模糊支持向量机进行了改 进，文献［２３］针对模糊支持向量机普遍存在训练时间过长的 难题，提出了使用截集 Ｃ均值聚类的方法对训练样本进行聚 类处理，以聚类中心作为新的样本进行训练，并用数值进行了 实验，实验结果证明，与一般的 ＦＳＶＭ相比，有效提高了分类速 度和精度。文献［２４］针对 Ｌｉｎ等人提出的基于类中心距离的 模糊隶属度设计方法不能有效区分噪声或孤立点，而且可能降 低支持向量的隶属度等不足，通过引入一个半径控制因子，提 出了一种改进的隶属度函数设计方法，这种方法在不增加时间 复杂度的情况下能有效提高 ＦＳＶＭ的分类精度。文献［２５］针 对传统 ＦＳＶＭ对非球形分布数据不合理的现象，使用类内超平 面代替类中心，提出了基于样本到超平面距离的新隶属度函数 设计方法，该方法克服了传统方法的不足，降低隶属度函数对 样本集几个形状的依赖，提高模糊支持向量机的泛化能力。 $) 最小二乘支持向量机 ＬＳＳＶＭ最早是由 Ｓｕｙｋｅｎｓ等人［２６］于 １９９９年提出的。ＬＳ ＳＶＭ将不等式约束换成了等式约束，将凸二次规划问题转变 成了一个线性方程组，从而能够明确得到解的表达式，ＬＳＳＶＭ 由以下优化问题刻画：