支持向量机原理

第3章支持向量机基础

By Dean

支持向量机（SupportVectorMachies）是由Vapiiik等人于1995年提出来的。 之后随着统计理论的发展，支持向量机也逐渐受到了各领域研究者的关注，在很 短的时间就得到很广泛的应用。支持向量机是建立在统计学习理论的VC维理论 和结构风险最小化原理基础上的，利用有限的样本所提供的信息对模型的复杂性 和学习能力两者进行了寻求最佳的折衷，以获得绘好的泛化能力。SVM的基本 思想是把训练数据非线性的映射到一个更高维的特征空间（Hilbert空间）中，在 这个高维的特征空间中寻找到一个超平而使得正例和反例两者间的隔离边缘被 最大化。SVM的出现有效的解决了传统的神经网络结果选择问题、局部极小值、 过拟合等问题。并且在小样本、非线性、数据高维等机器学习问题中表现出很多 令人注目的性质，被广泛地应用在模式识别，数据挖掘等领域（张学工2000：崔 伟东2001） o支持向量机可以用于分类和回归问题，本章着重介绍分类相关的知 识。

3. 1 SVM的基本思想

3.1.1最优分类面

SVM是由线性可分情况的最优分类而发展而來的，用于两类问题的分类。下 而用一个二维两类问题來说明SVM基本思想（白鹏 等，2008） o 图3・1最优超平面示意图

C1和C2代表两类数据样本，各样本在二维中显示如图3. 1,图中的直线PO,P1 就是分类函数。如果一个线性函数就完全可以把两类所有样本分开，那么就称这 些数据是线性可分的：否则称非线性可分。假设两类线性可分的训练数据样本 {(巾力),(尢2』2)，…(祁珈)}，焉G Rd (d代表样本人的长度)，刃6 {+1,-1}, i = 其线性判别函数的一般表达式是f(x) = w*x + b,该函数对应的分 类而方程是：

w * x + b = 0 (3-1)

线性判别函数的值一般是连续的实数，而分类问题需要输出的是离散值。例如利 用数值-1表示类别C1,而用数值+1表示类别C2.所有的样本都只能用数值-1 和+1表示。这时我们可以通过设置一个阀值，通过判断判别函数的值是大于或 者小于这个阀值來判断属于某一类。若我们取这个阀值为0,即当f(x)W0时， 判别样本为类别C1 (即-1)；当f(x)N0时，判别样本为类别C2(即+1).

现在将判别函数进行归一化，使两类所有样本都满足|/(%)| > 1，这时离分类面 近的样本都有|/(x)| = lo若要对所有样本正确分类需满足，

y,[(w * %) 4- b] — 1 > 0, i=l,…N (3-2) 这时分类间隔为2/||w||.寻求最优的分类面即使得分类间隔最大化。可以发现间 隔最大等价于#121卩最小。

因此最优化分类面问题可以表示成如下的约束优化问题，如下：

MiiVP (w) = y ||w|F (3-3)

约束条件为：

y([(w * %) 4- b] — 1 > 0, i=l,…川彳-4) 定义如卜Lagiange函数：

L(w,bg) = |||w||2 一* Xi + /?)-!] (3-5)

式中,at N 0为Lagrange乘子。为了求得函数式(3-5)的最小值,我们对w,b,a分 别求导有：

券=0 => w =

篇=0 => 爲 3

鈴=0 n al[yt(w*xi + b)-l] = 0

由式(3-6)和(3-2)可将上述的最优化分类面的求解问题转化为一个凸二次规划 寻优的对偶问题，如下：(3-6)

约束条件为:

U：X o 3

这个二次函数寻优的问题存在唯一解，若为最优解，则：

W，=理(3-9) 其中不为0对应的即为支持向M(SuppoitVector).并且最优分类面的权系数向量 是支持向量的线性组合。分类阀值ZT可由(3-6)式求得，

b* = -i(w\xr + xs) (3-10)

式中心，心分别是两类中任意支持向量，”心> 0,yr = -lfy5 = 1.由于除了支持向量 外，非支持向量所对应的如=0,所以最优分类面函数可简写为：

fix) = sgnEsv a^ytCxp %) + (3-11)

此时SVM最一般的表达式已经被求得。

3.1.2广义的最优分类面

但当有少数样本使得原來线性可分的问题变成不可分问题，从而影响了分类 器的性能。有时这少数的样本也是噪声，或是奇异值点，是我们在人工对数据 分类错分的，为了忽略这些点对分类器的影响，和在经验风险和泛化性能之间 求得平衡，松弛因子g被引入。它容许错分样本的存在，这时分类面满足： yj(w*x) + d] > 1-<, i = (3-12)

当吋，样本匕可以正确分类；当» 1时，样本兀会被错分。由于松 弛因子的引入，式(3-3)的目标函数被改写为：

式中C是惩罚因子(一个正常数).此时，式目标函数凸二次规划寻优的对偶问 题约束条件(3-8)可被变换为如为:

(3-14)

3.2核函数

3・2.1核函数变换基本思想

对于非线性分类问题，在原始空间中最优化分类面也许不能得到令人满意的 分类结果。针对这种情况，一个解决的思想是把原始空间中的非线性样本数据投 影到某个更高维的空间中，在高维的空间中寻找一个最优超平面能线性地将样本 数据分开，但是这种变化可能非常复杂。支持向量机利用核函数巧妙地解决了这 个问题。核函数变换的皋本思想是将一个n维空间中矢最x映射到更高维的特征①3,C = "w||2 + C 器& (3-13) 空间中去，然后在高维空间中进行线性地分类。核函数变换的基本原理示意图如 图3. 2所示。由（3-7）、（3-11河看出，都只涉及训练样本之间的点积运算〈七,切。 假设存在一个非线性映射①将R"空间的样本映射到更高维的H空间中，即：

在特征空间H中构造最优分类面时，计算的过程中仅使用了空间中的点积 〈6（忑）,①（马）〉，而没有用到单独的①（无）。如果存在一个“核函数” K,且 K（X1,X/） =

（＜P（X1）,＜P（A））＞,那么在训练算法是，我们将仅仅需要使用核函数K, 且不需要知道具体的①是什么。这样在高维空间中只需要进行点积运算，且这种 运算是用原來空间中的函数实现的。根据泛函的相关理论，只要核函数K（x,,；9）满 足Mercer条件，它就可以对应某一变换空间的点积，这样就能徳奥原输入空间 中对应的非线性算法。

图3.2核函数变换示总图

3. 2常见核函数

核函数作为支持向最机理论的重要的组成部分引起了很多研究者的兴趣。常

用的满足Mercer条件的核函数有线性函数，多项式函数，径向基函数，Sigmoid 函数等，选择不同的核函数可以构造不同的支持向量机（张浩然2002） o下而对 这四种常见的核函数进行简单地介绍.

(4) Sigmoid 函数

K(x, %j) = tanh[v(x, xt) + a] 由这四种核函数可以构造出线性SVM、多项式(1)

线性函数

K(x,石)=(xtXi)

(2) 多项式函数

K(x,%i)=[仪,看＞ + 1]"

(3) 径向基函数

K(x,xJ = expl — 核函数0 SVM、RBFSVM和感知SVM。 满足Mercer条件核函数很多，这样乂带來另外一个问题，即SVM的核函数如何 选择。目前没有明确的标准來指导核函数的选择。在模型不确定的情况下，RBF 孩函数是一个不错的选择。

3. 3 SVM参数优化问题

在实际应用的过程中，选择合适的支持向量机的参数是一项艰巨而乂重要的 一步，它会影响分类器的泛化能力和分类性能。SVM参数选择实际上是一个优 化搜索的过程，搜索空间中的每一个点都有可能是最佳模型的潜在解，并可由推 广能力估计値做出相应的评估。所以，参数优化求解的过程在本质上是泛化误差 最小化的求解问题。

3. 3. 1常见SVM的寻优方法

一般情况下，人们会使用简单并且直观的方法(如网格划分)，通过大量的实 验比较获得较优的参数。这种方法可以找到在交义验证意义下的最高的分类准确 率，但是当想在更大的范围内寻找最佳的参数c和g时，这会有很大的计算最。 Chapelle等人采用

了 一种梯度下降(gradientdescend, GD)的方法(Chapelle 2002) 來对参数进行选择，这种方法虽然在计算时间上获得有效改善。但是梯度下降方 法是一种线性的搜索方法，并且对初始点要求比较高，所有在寻优的过程中容易 陷入局部最优。

遗传算法(GA, GeneticAlgoritlmi)足Micliigan大学的Holland教授及其学生受 生物模拟技术启发，提出的一种基于生物遗传和进化机制的门适应概率优化的技 术。作为一种实用、髙效、鲁棒性强的优化方法，遗传算法很快收到国内外学者 的高度重视并迅速发展。Chen (2004)和Zheng (2004)用不同的推广能力估计作 为遗传算法的适应度函数对SVM的参数进行优化。结果表明：基于GA对SVM参 数进行优化的方法大大的缩小了计算的时间，并且减小了对初始值的依赖度。但 是遗传算法的操作往往比较复杂，对不同的优化问题需要设计不同的交义或变异 方式。

粒子群算法(particleswannoptimization, PSO)是计算智能领域的一种群体智 能优化算法，该算法最早是由Kenedy和Eberlwt在对鸟类捕食行为研究时所提出 的。PSO算法是从这种生物种群行为特征中得到启发，并应用优化问题的求解。 与遗传算法不冋，PSO是通过个体间的协作來寻找最优解，这使得粒子群算法更 加简单，效率更高，更容易实现，因为它的显苦的优点己被广泛应用于函数优 化、模式分类等领域。杨慧中等人（2006）将粒子群算法应用于对SVM参数的优 化，仿真结果表明PSO算法强劲的全局搜索能力大大提高了模型的准确率。

3. 3. 2 PS0寻优算法 PSO算法首先在搜索空间中初始化一群粒子，每一个粒子都有可能是极值优 化问题的潜在最优解。我们可以用位置，速度和适应度值来三项指标來表示粒子 的特征，并通过适应度值可以用來衡星粒子的好坏。其中，适应度值是通过适应 度函数来计算得到的。

假设在d维的搜索空间中，由I】个粒子组成的种群X = ，…,XJ其中第i

个粒子表示一个d维向量X, = （xilfxi2，…,和）。根据目标函数可以计算出每个粒 子位買所对应的适应度值。设第i个粒子的速度为V, = dV，其个体极

值为R = （P“,R2,・・・,Rd）T，种群的群体极值为马=（P^,Pg2,…,Pgd）T。在每次迭 代中，粒子的速度和位置的更新公式可以表示为：

= wV/j + c.r^j - 4）+ C2厂2（脇—X$ ） （3-15）

xf = xfj + V^+i （3-16）

这里w为惯性权重,j = 1,2, i = 1,2,…,n;k是当前迭代的次数。VtJ是粒子

速度，加速度因子clfc2>0,随机数rbr2G[O,l].为了防止粒子盲目搜索，一般 将其位置和速度限制在一定的范围[-^nax^maxlt-Knax^naxlo

3. 3. 2基于PSO算法的SVM参数优化

推广能力估计是参数选择的基础，通常的方法包括：留一法（leave-one-out）, k-fold交义验证法，支持向童率法等。由J k-fold交义验证法的估计是无偏的， 通常选用k-fold交义验证支持向屋机参数选择的目标值。由于本文中选择径向基 孩函数，所以PSO需优化的参数有惩罚系数C和核参数°,具体的步骤如下（邵信 光等,2006）:

1） 读取训练样本，然后随机产生一组｛C,。｝作为粒子的初始位置；

2） 把所以训练样本均匀地分割成k个互不包含的子集…,Si