支持向量机原理

第3章支持向量机基础ByDean支持向量机（SupportVectorMachies）是由Vapnik等人于1995年提出来的。之后随着统计理论的发展，支持向量机也逐渐受到了各领域研究者的关注，在很短的时间就得到很广泛的应用。支持向量机是建立在统计学习理论的VC维理论和结构风险最小化原理基础上的，利用有限的样本所提供的信息对模型的复杂性和学习能力两者进行了寻求最佳的折衷，以获得最好的泛化能力。SVM的基本思想是把训练数据非线性的映射到一个更高维的特征空间（Hilbert空间）中，在这个高维的特征空间中寻找到一个超平面使得正例和反例两者间的隔离边缘被最大化。SVM的出现有效的解决了传统的神经网络结果选择问题、局部极小值、过拟合等问题。并且在小样本、非线性、数据高维等机器学习问题中表现出很多令人注目的性质，被广泛地应用在模式识别，数据挖掘等领域(张学工2000；崔伟东2001)。支持向量机可以用于分类和回归问题，本章着重介绍分类相关的知识。3.1SVM的基本思想3.1.1最优分类面SVM是由线性可分情况的最优分类面发展而来的，用于两类问题的分类。下面用一个二维两类问题来说明SVM基本思想(白鹏等，2008)。图3.1最优超平面示意图C1和C2代表两类数据样本，各样本在二维中显示如图3.1，图中的直线P0,P1就是分类函数。如果一个线性函数就完全可以把两类所有样本分开，那么就称这些数据是线性可分的；否则称非线性可分。假设两类线性可分的训练数据样本{(𝑥1,𝑦1),(𝑥2,𝑦2),…(𝑥𝑁,𝑦𝑁)},x𝑖∈𝑅𝑑(d代表样本x𝑖的长度),y𝑖∈{+1,−1},𝑖=1,2,…,𝑁.其线性判别函数的一般表达式是f(𝑥)=w∗x+b,该函数对应的分类面方程是：w∗x+b=0(3-1)线性判别函数的值一般是连续的实数，而分类问题需要输出的是离散值。例如利用数值-1表示类别C1，而用数值+1表示类别C2.所有的样本都只能用数值-1和+1表示。这时我们可以通过设置一个阀值，通过判断判别函数的值是大于或者小于这个阀值来判断属于某一类。若我们取这个阀值为0，即当f(x)≤0时，判别样本为类别C1(即-1)；当f(x)≥0时，判别样本为类别C2(即+1).现在将判别函数进行归一化，使两类所有样本都满足|𝑓(𝑥)|≥1，这时离分类面近的样本都有|𝑓(𝑥)|=1。若要对所有样本正确分类需满足，𝑦𝑖[(𝑤∗𝑥)+𝑏]−1≥0,i=1,…N(3-2)这时分类间隔为2‖𝑤‖⁄.寻求最优的分类面即使得分类间隔最大化。可以发现间隔最大等价于12‖𝑤‖2最小。因此最优化分类面问题可以表示成如下的约束优化问题，如下：MinΦ(𝑤)=12‖𝑤‖2(3-3)约束条件为：𝑦𝑖[(𝑤∗𝑥)+𝑏]−1≥0,i=1,…N(3-4)定义如下Lagrange函数:L(𝑤,𝑏,𝛼)=12‖𝑤‖2−∑𝛼𝑖[𝑦𝑖(𝑤∗𝑥𝑖+𝑏)−1]𝑁𝑖=1(3-5)式中，α𝑖≥0为Lagrange乘子。为了求得函数式(3-5)的最小值，我们对𝑤,𝑏,𝛼分别求导有：{𝜕𝐿𝜕𝑤=0⇒𝑤=∑𝛼𝑖𝑦𝑖𝑥𝑖𝑁𝑖=1𝜕𝐿𝜕𝑏=0⇒∑𝛼𝑖𝑦𝑖𝑁𝑖=1=0𝜕𝐿𝜕𝛼=0⇒𝛼𝑖[𝑦𝑖(𝑤∗𝑥𝑖+𝑏)−1]=0(3-6)由式(3-6)和(3-2)可将上述的最优化分类面的求解问题转化为一个凸二次规划寻优的对偶问题，如下：Max∑𝛼𝑖−12𝑁𝑖=1∑∑𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗(𝑥𝑖,𝑥𝑗)𝑁𝑗=1𝑁𝑖=1(3-7)约束条件为：{𝛼𝑖≥0∑𝛼𝑖𝑦𝑖=0𝑁𝑖=1(3-8)这个二次函数寻优的问题存在唯一解，若𝛼𝑖∗为最优解，则：w∗=∑𝛼𝑖∗𝑁𝑖=1𝑦𝑖𝑥𝑖(3-9)其中𝛼𝑖∗不为0对应的即为支持向量(SupportVector).并且最优分类面的权系数向量是支持向量的线性组合。分类阀值𝑏∗可由(3-6)式求得，b∗=−12〈w∗,𝑥𝑟+𝑥𝑠〉(3-10)式中𝑥𝑟,𝑥𝑠分别是两类中任意支持向量，𝛼𝑟,𝛼𝑠0,𝑦𝑟=−1,𝑦𝑠=1.由于除了支持向量外，非支持向量所对应的𝛼𝑖=0,所以最优分类面函数可简写为：𝑓(𝑥)=sgn{∑𝛼𝑖∗𝑦𝑖(𝑥𝑖,𝑥)+𝑏∗𝑠𝑣}(3-11)此时SVM最一般的表达式已经被求得。3.1.2广义的最优分类面但当有少数样本使得原来线性可分的问题变成不可分问题，从而影响了分类器的性能。有时这少数的样本也是噪声，或是奇异值点，是我们在人工对数据分类错分的，为了忽略这些点对分类器的影响，和在经验风险和泛化性能之间求得平衡，松弛因子ξ被引入。它容许错分样本的存在，这时分类面满足：𝑦𝑖[(𝑤∗𝑥)+𝑏]≥1−𝜉𝑖,𝑖=1,…𝑁(3-12)当0≤ξ𝑖≪1时，样本𝑥𝑖可以正确分类；当𝜉𝑖≫1时，样本𝑥𝑖会被错分。由于松弛因子的引入，式（3-3）的目标函数被改写为:Φ(𝑤,𝜉)=12‖𝑤‖2+𝐶∑𝜉𝑖𝑁𝑖=1(3-13)式中C是惩罚因子(一个正常数).此时，式目标函数凸二次规划寻优的对偶问题约束条件(3-8)可被变换为如为：{0≤𝛼𝑖≤𝐶∑𝛼𝑖𝑦𝑖=0𝑁𝑖=1(3-14)3.2核函数3.2.1核函数变换基本思想对于非线性分类问题，在原始空间中最优化分类面也许不能得到令人满意的分类结果。针对这种情况，一个解决的思想是把原始空间中的非线性样本数据投影到某个更高维的空间中，在高维的空间中寻找一个最优超平面能线性地将样本数据分开，但是这种变化可能非常复杂。支持向量机利用核函数巧妙地解决了这个问题。核函数变换的基本思想是将一个n维空间中矢量x映射到更高维的特征空间中去，然后在高维空间中进行线性地分类。核函数变换的基本原理示意图如图3.2所示。由（3-7）、（3-11）可看出，都只涉及训练样本之间的点积运算〈𝑥𝑖,𝑥𝑗〉。假设存在一个非线性映射Φ将𝑅𝑛空间的样本映射到更高维的H空间中，即：Φ：𝑅𝑛→𝐻在特征空间H中构造最优分类面时，计算的过程中仅使用了空间中的点积〈Φ(𝑥𝑖),Φ(𝑥𝑗)〉，而没有用到单独的Φ(𝑥𝑖)。如果存在一个“核函数”K，且K(𝑥𝑖,𝑥𝑗)=〈Φ(𝑥𝑖),Φ(𝑥𝑗)〉，那么在训练算法是，我们将仅仅需要使用核函数K，且不需要知道具体的Φ是什么。这样在高维空间中只需要进行点积运算，且这种运算是用原来空间中的函数实现的。根据泛函的相关理论，只要核函数K(𝑥𝑖,𝑥𝑗)满足Mercer条件，它就可以对应某一变换空间的点积，这样就能德奥原输入空间中对应的非线性算法。图3.2核函数变换示意图3.2常见核函数核函数作为支持向量机理论的重要的组成部分引起了很多研究者的兴趣。常用的满足Mercer条件的核函数有线性函数，多项式函数，径向基函数，Sigmoid函数等，选择不同的核函数可以构造不同的支持向量机(张浩然2002)。下面对这四种常见的核函数进行简单地介绍.（1）线性函数K(𝑥,𝑥𝑖)=〈𝑥,𝑥𝑖〉（2）多项式函数K(𝑥,𝑥𝑖)=[〈𝑥,𝑥𝑖〉+1]𝑑（3）径向基函数K(𝑥,𝑥𝑖)=𝑒𝑥𝑝{−|𝑥−𝑥𝑖|2𝜎2}（4）Sigmoid函数K(𝑥,𝑥𝑖)=𝑡𝑎𝑛ℎ[𝑣〈𝑥,𝑥𝑖〉+𝑎]由这四种核函数可以构造出线性SVM、多项式SVM、RBFSVM和感知SVM。满足Mercer条件核函数很多，这样又带来另外一个问题，即SVM的核函数如何选择。目前没有明确的标准来指导核函数的选择。在模型不确定的情况下，RBF核函数是一个不错的选择。3.3SVM参数优化问题在实际应用的过程中，选择合适的支持向量机的参数是一项艰巨而又重要的一步，它会影响分类器的泛化能力和分类性能。ＳＶＭ参数选择实际上是一个优化搜索的过程，搜索空间中的每一个点都有可能是最佳模型的潜在解，并可由推广能力估计值做出相应的评估。所以，参数优化求解的过程在本质上是泛化误差最小化的求解问题。3.3.1常见SVM的寻优方法一般情况下，人们会使用简单并且直观的方法（如网格划分），通过大量的实验比较获得较优的参数。这种方法可以找到在交叉验证意义下的最高的分类准确率，但是当想在更大的范围内寻找最佳的参数ｃ和ｇ时，这会有很大的计算量。Chapelle等人采用了一种梯度下降(gradientdescend,GD)的方法（Chapelle2002）来对参数进行选择，这种方法虽然在计算时间上获得有效改善。但是梯度下降方法是一种线性的搜索方法，并且对初始点要求比较高，所有在寻优的过程中容易陷入局部最优。遗传算法(GA,GeneticAlgorithm)是Michigan大学的Holland教授及其学生受生物模拟技术启发，提出的一种基于生物遗传和进化机制的自适应概率优化的技术。作为一种实用、高效、鲁棒性强的优化方法，遗传算法很快收到国内外学者的高度重视并迅速发展。Chen(2004)和Zheng(2004)用不同的推广能力估计作为遗传算法的适应度函数对SVM的参数进行优化。结果表明：基于GA对SVM参数进行优化的方法大大的缩小了计算的时间，并且减小了对初始值的依赖度。但是遗传算法的操作往往比较复杂，对不同的优化问题需要设计不同的交叉或变异方式。粒子群算法(particleswarmoptimization,PSO)是计算智能领域的一种群体智能优化算法，该算法最早是由Kenedy和Eberhat在对鸟类捕食行为研究时所提出的。PSO算法是从这种生物种群行为特征中得到启发，并应用于优化问题的求解。与遗传算法不同，PSO是通过个体间的协作来寻找最优解,这使得粒子群算法更加简单,效率更高,更容易实现,因为它的显著的优点已被广泛应用于函数优化、模式分类等领域。杨慧中等人(2006)将粒子群算法应用于对SVM参数的优化，仿真结果表明PSO算法强劲的全局搜索能力大大提高了模型的准确率。3.3.2PSO寻优算法PSO算法首先在搜索空间中初始化一群粒子，每一个粒子都有可能是极值优化问题的潜在最优解。我们可以用位置，速度和适应度值来三项指标来表示粒子的特征，并通过适应度值可以用来衡量粒子的好坏。其中，适应度值是通过适应度函数来计算得到的。假设在d维的搜索空间中，由n个粒子组成的种群X=(𝑋1,𝑋2,…,𝑋𝑛),其中第i个粒子表示一个d维向量X𝑖=(𝑥𝑖1,𝑥𝑖2,…,𝑥𝑖𝑑)。根据目标函数可以计算出每个粒子位置所对应的适应度值。设第i个粒子的速度为V𝑖=(𝑉𝑖1,𝑉𝑖2,…,𝑉𝑖𝑑)𝑇,其个体极值为𝑃𝑖=(𝑃𝑖1,𝑃𝑖2,…,𝑃𝑖𝑑)𝑇，种群的群体极值为𝑃𝑔=(𝑃𝑔1,𝑃𝑔2,…,𝑃𝑔𝑑)𝑇。在每次迭代中，粒子的速度和位置的更新公式可以表示为：𝑉𝑖𝑗𝑘+1=𝑤𝑉𝑖𝑗𝑘+𝑐1𝑟1(𝑃𝑖𝑗𝑘−𝑋𝑖𝑗𝑘)+𝑐2𝑟2(𝑃𝑔𝑗𝑘−𝑋𝑖𝑗𝑘)(3-15)𝑋𝑖𝑗𝑘+1=𝑋𝑖𝑗𝑘+𝑉𝑖𝑗𝑘+1(3-16)这里w为惯性权重,j=1,2,…,d,i=1,2,…,n;k是当前迭代的次数。𝑉𝑖𝑗是粒子速度，加速度因子𝑐1,𝑐2≥0；随机数𝑟1,𝑟2∈[0,1].为了防止粒子盲目搜索，一般将其位置和速度限制在一定的范围[−𝑋𝑚𝑎𝑥,𝑋𝑚𝑎𝑥],[−𝑉𝑚𝑎𝑥,𝑉𝑚𝑎𝑥]。3.3.2基于PSO算法的SVM参数优化推广能力估计是参数选择的基础，通常的方法包括：留一法(leave-one-out),k-fold交叉验证法，支持向量率法等。由于k-fold交叉验证法的估计是无偏的，通常选用k-fold交叉验证支持向量机参数选择的目标值。由于本文中选择径向