支持向量机算法

支持向量机算法（精选12篇）

支持向量机算法 第1篇

随着现代科技的进步,以及人们管理和知识水平的提高,现实世界中需要处理的数据量越来越大。2008年9月,《Nature》杂志出版了一个专刊,讨论大数据存储、管理和分析问题[1],之后麦肯锡公司、《Science》杂志也相继出版了大数据报告及研究专刊[2],围绕科学研究中大数据的问题进行了深入讨论,说明了大数据问题处理的重要性和必要性。因此,大数据问题的研究目前已经成为人工智能领域的热点问题。为了能够从规模庞大、联系紧密、结构复杂、类型多样的数据中提炼出有用知识,针对大数据的数据挖掘技术研究近年来受到了研究者的广泛关注。数据挖掘[3]是指从大规模的、不完整的、有噪声的、模糊的、随机的复杂数据集中提取潜在有用的信息或知识。

支持向量机[4](Support Vector Machine,SVM)是一种近年来受到广泛关注的机器学习方法,在模式识别[5]、函数回归[6]、图像识别[7]、时间序列预测[8]和生物信息学[9]等诸多领域得到成功的应用。然而,由于支持向量机的训练优化过程中需要构建和计算大规模的核矩阵,因此,当数据规模较大时,矩阵运算非常繁琐,学习器的效率很低。目前,采用支持向量机方法对大规模数据进行处理没有特别有效的方法,使其既能够提高学习效率,又可获得较好的泛化能力。因此,如何提高支持向量机处理大数据的能力成为近年来机器学习领域的一个研究热点[10]。

近年来,主动学习[11]由于其在降低样本复杂度方面比传统机器学习方法具有明显的优势,成为目前的一个提高学习器效率的常见手段。在主动学习过程中,学习器能够主动地选择包含信息量大的未标注样本,将其交由专家标记,然后加入训练集进行训练,从而在训练集较小的情况下获得较优秀的学习结果,有效降低构建学习器的代价[12]。

本文结合主动学习思想,提出了一种基于主动学习的支持向量机加速方法。该方法首先随机选择部分训练样本作为初始工作集,并采用支持向量机训练得到初始的分类器和初始支持向量,然后根据主动学习思想,选择初始分类器附近的样本点与已得到的初始支持向量合并构成新的工作集再次进行支持向量机的学习,并得到新的分类器和新的支持向量集合,以构建新的工作集进行训练,如此循环往复,直到得到的分类器达到要求时为止。由于基于主动学习的支持向量机方法仅保留了前一次训练得到的支持向量和前一次训练所得到的分类器附近的部分样本点,因此其训练样本规模较小,有效提高了其处理海量数据的分类能力。

1 支持向量机分类方法

支持向量机可用来解决分类和回归问题。支持向量机解决二分类问题的目的就是构造最优分类面,所谓最优分类面就是要求分类面不但能将两类示例无错误地分开,而且要使两类示例的分类间隔最大。

假设训练集为{(xi,yi)}li=1,xi∈Rd是空间的向量,yi表示分类标识,yi∈{-1,1}。如果输入向量集合是线性可分离的,则分类面方程为:

对式(1)进行归一化,使得训练集满足:

根据结构风险最小化(SRM)原理,即求解以下约束最优化问题:

对于该模型,采用Lagrange乘子法,上述问题可转化为求其对偶问题:

式中αi为拉格朗日乘子。

一般情况下,训练集不是完全线性可分的,此时分类器允许有一定的误差,因此引入非负变量ξi≥0,构造软间隔最优分类超平面,对应最优化问题变成如下形式:

式中C为软间隔惩罚参数,用于调节分类超平面宽度与分类允许误差的平衡。

对于复杂非线性可分问题,SVM通过引入核方法,将低维空间的训练数据通过映射函数Φ映射到高维空间,使其线性可分,但在实际问题中,显示的映射函数Φ是很难得到的,因此这里采用核函数K(x,x′)进行样本的映射,使得K(x,x′)=Φ(x)⋅Φ(x′)。常见的核函数包含高斯核、多项式核和线性核等[13]。

2 基于主动学习的支持向量机加速算法

设数据集X={x1,···,xi,···,xn}且xi∈Rd,其中n为样本个数,d为样本维度。首先从样本集X中随机选择1 s的样本作为初始训练集X0,以训练SVM得到初始的近似分类器f0及初始支持向量集SV0,然后在剩余的样本集X /X0中选择距离初始分类器f0最近的样本x′,并与初始向量集SV0合并,构成新的训练集 ,并训练新的SVM模型,得到新的分类器f1和新的支持向量集SV1,如此循环往复,直到所得到的学习器的泛化能力不再增强为止。

基于主动学习的支持向量机加速算法具体如下:

初始化:设初始训练数据集为X={x1,⋅⋅⋅,xi,⋅⋅⋅,xn}且xi∈Rd,其中n为样本个数,d为样本维度,设定初始训练样本集规模参数s,支持向量机的核函数为K,核参数为p,惩罚因子为C。

Step1:将初始训练集X随机划分为s个子集,即X→{X1,X2,⋅⋅⋅,Xs};

Step2:取其中任意一个子集作为初始训练集X(0)训练得到SVM学习器,得到初始的分类器f(0)和初始的支持向量集SV(0);并得到当前未处理样本集Xr(1)=X X(0);

Step3:计算当前未处理样本集Xr(t)中任意一个样本xj到当前最新得到的分类器f(t-1)的距离d(xj,f(t-1)),并选择出与f(t-1)距离d(xj,f(t-1))最小的样本x(t),即

Step4:将新计算得到的样本x(t)与上次SVM训练所得到的支持向量集SV(t-1)合并,构成新的训练样本集 ,并训练SVM学习器,得到新的分类器f(t)和新的支持向量样本集SV(t);

Step5:判断新得到的分类器f(t)的泛化性能(测试精度)g(f1),若g(f(t))>g(f(t-1)),则t=t+1并返回Step3继续迭代;否则执行Step6。

Step6:算法结束,得到最终的最优分类器f(t-1)。

3 实验结果及分析

为验证基于主动学习支持向量机加速算法的性能,本文在五个标准数据集[13]上进行实验,具体见表1。支持向量机的核函数采用高斯核,核参数及惩罚参数采用网格搜索的方式确定,核参数P的网格搜索范围为0.5,0.6,0.7,0.8,0.9,1.0,1.1,1.2,1.3,1.4,1.5;惩罚参数的搜索范围为10,100,1 000,10 000和100 000,取每个工作子集上对应精度最高的核函数参数P和惩罚参数C为训练的最优参数;初始训练集构造规模参数s均取5。

为检验本文所提的基于主动学习的SVM方法的性能,本文与标准SVM学习算法进行比较。表2为本文提出的AL_SVM算法与标准SVM算法在各数据集上的训练和测试结果的对比。

从表2可以看出,采用本文提出的基于主动学习的AL_SVM方法在数据集Banana与Letter上与传统SVM方法的测试精度相同,而在数据集Diabetis、Germany及Titanic上测试精度也相差不大,而在5个数据集上,训练所得到的支持向量个数却都减少了很多,这说明采用本文提出的基于主动学习的AL_SVM方法能够舍弃大量不重要的支持向量,使得原本复杂的学习器变得更为简单,一定程度上减少了过拟合效应。此外,从算法运行效率上看,在5个数据集上,本文提出的方法都有非常明显的提高,这是由于本文的方法通过主动学习模型,将原来大规模样本的二次优化问题转化成了一系列小规模的二次优化问题,因此节省了计算优化问题的时间和复杂度。

综上可看出,由于本文提出的基于主动学习的AL_SVM方法采用了主动学习模式,通过随机抽取部分训练集训练得到初始分类器,然后根据训练所得到的分类超平面信息来从剩余样本中选择对于改进学习器最有价值的样本加入训练集,并有效地提取了训练样本中包含重要分类信息的支持向量样本,删除了那些对模型复杂度影响较高而对于分类器泛化性能影响不大的样本,从而以较高的学习效率处理大规模数据的分类问题,同时保证了模型的泛化性能。

4 结论

支持向量机算法 第2篇

支持向量机(Support Vector Machines)是近年来热门的一种有监督学习的.方法,它广泛的应用于统计分类以及回归分析中.通过SVM模型,考察分析一系列影响因素对高速公路路面质量指标的影响,并对提高高速公路路面质量提出建议.

作 者：陶甄 吴元 梁晓辉 TAO Zhen WU Yuan LIANG Xiao-hui 作者单位：陶甄,TAO Zhen(上海交通大学,金融系,上海,30)

吴元,梁晓辉,WU Yuan,LIANG Xiao-hui(上海交通大学,计算机科学与工程系,上海,40)

改进支持向量机的商业银行评级算法 第3篇

【关键词】改进的支持向量机；参数自动寻优；商业银行评级

目前运用支持向量机的研究中，主要用传统的支持向量机，对评级分类器则较少考虑。如果传统支持向量机算法来对银行进行分评级，不考虑评级分类器的优化，则最终的评级效果不会达到最优。

一、SVM原理

支持向量机（SVM）的主要思想有两点：一是针对线性可分的情况来分析，对于线性不可分的情况，通过核函数将低维空间中的线性不可分的样本映射到高维空间使得其线性可分。二是基于结构风险最小化理论，能够求得全局最优解。

（1）假设训练集T={(x1,y1),(x2,y2),…,(xi,yi),…,(xk,yk)}∈(X,Y)k，其中，X=Rn，Y={-1,+1}，i=1,2,…，，k为训练样本的数量。（2）用非线性映射G(·)将线性不可分的低维空间X映射到高维线性空间Z中。将优化问题变为：

（1）

通过拉格朗日法，求得（1）的对偶式，再采用对称核函数K(xi,xj)代替点积G(xi)G(xi)，（1）式转化成（2）式：

（2）

然后，将训练样本代入式（2），求解出€%Zi、b之后，带入（3），就可用来对新样本数据进行分类。

分类器为=sgn（3）

二、基于改进的SVM企业银行评级分类器

在SVM中，核函数K(xi,x)的作用就是把低維空间中非线性的数据映射到高维空间，它代替了高维空间中的内积运算，不需要映射后的样本在高维空间进行运算。本文运用以下三种函数：多项式核函数：K(x,y)=[(x隯y)+]d；高斯径向基核函数（RBF核函数）：K(x,y)=e；神经网络核函数：K(x,y)=tanh(k隯x隯y)。进行组合得到新的组合核函数：

K组合核函数(x,y)=€%d1[(x隯y)+]d+€%d2e+€%d3tanh(k隯x隯y)其中€%di=1并且€%di＞0。

三、银行评级分类系统设计与实现

1．系统架构。本文以基于多核函数的SVM，设计和实现了一个能够对银行信用进行评级的系统，系统架构（如图1所示）：

２．系统实现。该系统硬件采用Inter Pentium D 3.0GHz CPU，1G内存，软件采用Eclipse3.6，JAVA语言来设计。系统共四个模块，功能和实现方法如下：（1）财务数据读取模块从财务数据集当中随机选取出4/5的数据作为训练数据，1/5的作为待评级数据，并且将读取的数据传到分类器模块。（2）分类器模块采用3.3所示基于改进的SVM企业银行评级算法来进行分类和泛化推广。（3）输出模块打印出训练财务数据类型、训练财务数据数目、训练时间、分类时间、被正确分到某一级的银行、被错误分到某一级的银行、属于某一级，但是被错误分到其它级的银行数目、准确率、召回率、F1值，以及相应的核函数参数。

四、实验结果与分析

（1）实验数据。在本文中，使用的财务数据来自于国泰安数据服务中心提供的企业财务数据数据（http://www.gtarsc.com/p/user/home.aspx）。（2）实验方案及实验结果。设算法I为基于传统的SVM企业银行评级算法，算法II为基于组合核函数的SVM银行评级算法。最后，采用准确率（设为p）、召回率（设为r）、F1指标来评价分类结果。其中，设a为被正确分到某一类的银行数，b为被错误分到某一类的银行数，c为属于某一类但是被错误分到其它类的银行数。则r、p被分别定义为r=，p=。F1指标定义为：F1=。（3）实验结果。从表1可以看出，分类算法II的准确率、召回率和F1值比分类算法I的都要高；从而提高了银行信用评级的准确度。

表1 不同银行评级算法的实验结果

支持向量机算法 第4篇

支持向量机(Support Vector Machines,简称SVM)是20世纪90年代由Vapnik等人提出的一种新的学习机器。它建立在学习统计理论和结构风险最小化原则的基础上,在理论上充分保证了其良好的泛化能力,具有坚实的理论基础和良好的推广能力。与传统的学习方法相比,支持向量机能够很好的克服小样本、维数灾难、局部极小点以及过拟合等问题,通过构造最优分类面,使得对未知样本的分类误差最小,表现出了极高的泛化能力。由于其良好的性能,所以支持向量机算法一经提出便受到了越来越多的研究人员的关注,近年来支持向量机被广泛应用于模式识别[1]、预测领域[2,3]、故障分类[4]等领域。但是,作为一种新兴的学习机器,支持向量机也有一些待完善的地方,比如其参数的选取至今仍然没有一个统一的标准,传统的参数选取大多依靠经验采取试凑的方法,这样不仅费时而且很难得到满意的结果,显然,传统的参数选取方法并不能适应支持向量机的发展。文献[5]利用PSO对SVM的参数进行优化,取得了比较好的效果,并且将其应用到建立聚丙烯腈数均分子测量模型;文献[6]在分析了几种评估SVM性能的方法之后,利用梯度下降法对SVM参数进行优化,取得了较好的效果,但是梯度下降法容易陷入局部极小值。

本文应用了基于改进遗传算法的参数优化的方法,利用遗传算法的全局搜索能力,而且这种搜索能力不依赖于特定的模型,所以该方法能够得到更好的支持向量机参数,从而使向量机具有更高的分类精度,为支持向量机参数选取提供一个有效的方法。仿真结果表明本方法是可行的。

1 支持向量机及其参数的影响

1.1 支持向量机简介

支持向量机就是通过某种事先选择的非线性映射将输入向量映射到一个高维特征空间,并在这个空间中构造最优分类超平面。所谓最优分类面就是要求分类面不但能将两类正确分开(训练错误率为0),而且使分类间隔最大,如图1所示。

训练集为非线性时,通过一个非线性函数将训练集数据映射到一个高维线性特征空间,在这个维数可能为无穷大的线性空间中构造最优分类超平面,并得到分类器的决策函数。

对于训练样本集:

$\left(y{}_1,x{}_1\right),\cdots ‚\left(y{}_{\xi },x{}_{\xi }\right)‚x\in R{}^n,y\in \left\{-1,1\right\}$

最优分类超平面的二次最优化问题为:

$\begin{array}{c}\underset{\psi ,b}{{\displaystyle \min }}\frac{1}{2}\parallel \psi \parallel {}^2+C{\displaystyle \sum _{i=1}^l\xi }{}_i\hfill \\ s.t.y{}_i((x{}_i\times \psi )+b)\ge 1-\xi {}_i,\hfill \\ \xi {}_i\ge 0,i=1,\cdots ,l\hfill \end{array}(1)$

其中C 称为惩罚因子,通过改变惩罚因子可以在分类器的泛化能力和误分类率之间进行折衷。

其Lagrange函数为

$\begin{array}{c}L(\psi ,b,\alpha ,\beta )=\frac{1}{2}(\psi \times \psi )+C{\displaystyle \sum _{i=1}^l\xi }{}_i-\hfill \\ {\displaystyle \sum _{i=1}^l\alpha }{}_i\left(y{}_i\left[\left(\phi (x{}_i)\times \psi \right)+b\right]-1+\xi {}_i\right)-{\displaystyle \sum _{i=1}^l\beta }{}_i\xi {}_i\hfill \end{array}(2)$

其对偶问题为

$\begin{array}{c}\text{m}\text{a}\text{x}W(\alpha )={\displaystyle \sum _{i=1}^l\alpha }{}_i-\frac{1}{2}{\displaystyle \sum _{i,j=1}^{l}y}{}_{i}y{}_j\alpha {}_i\alpha {}_j\left(\phi (x{}_i)\times \phi (x{}_j)\right)=\hfill \\ {\displaystyle \sum _{i=1}^l\alpha }{}_i-\frac{1}{2}{\displaystyle \sum _{i,j=1}^{l}y}{}_{i}y{}_j\alpha {}_i\alpha {}_j{\rm K}(x{}_i,x{}_j)\hfill \\ s.t.\text{C}\ge \alpha {}_i\ge 0\hfill \\ {\displaystyle \sum _{i=1}^{l}y}{}_i\alpha {}_i=0\hfill \end{array}(3)$

其中K(xi,xj)=φ(xi)×φ(xj)为核函数。

最终可以得到决策函数

$f(x,\alpha )=sign\left({\displaystyle \sum _{\text{支}\text{持}\text{向}\text{量}}y}{}_i\alpha {}_i^0{\rm K}(x{}_i,x{}_j)+b\right)(4)$

构造这一类决策函数的学习机器称为支持向量机.支持向量机的结构示意图如图2所示[7]。

1.2 支持向量机参数对其性能的影响

Vapnik等人在研究中发现,不同的核函数对SVM性能的影响不大,反而核函数的参数和误差惩罚因子C是影响SVM性能的关键因素。因此选择合适的核函数参数和误差惩罚因子C对学习机器的性能至关重要。本文针对目前使用最广泛的径向基函数SVM的核参数和误差惩罚因子C进行优化。

支持向量机的性能依赖于多个参数,核函数参数γ主要影响样本数据在高维特征空间中分布的复杂程度,核参数的改变实际上隐含着特征空间的VC维的改变,从而影响置信范围,最终影响结构风险范围。惩罚因子C控制间隔的最大化与分类误差之间的折衷,C越大,则对于错分样本的惩罚越大;C的取值小表示惩罚小,学习机器的复杂度小而经验风险值较大,前者称为“过学习”,而后者则为“欠学习”。除了在同一特征空间优化C以获得对应空间的最优SVM,还要优化核函数参数以获得全局最优的SVM。

2 基于改进遗传算法的SVM参数优化

2.1 遗传算法

遗传算法[8,9](Genetic Algorithms,简称GA)是基于达尔文进化论,在计算机上模拟生命进化机制而发展起来的搜索最优解方法。它根据“适者生存”、“优胜劣汰”等自然进化规则来进行搜索计算和问题求解。遗传算法对于复杂的优化问题无须建模和复杂运算,只要利用遗传算法的三种算子就能得到最优解。标准遗传算法的构成包括染色体的编码、种群规模、适应度函数、遗传算子。

2.1.1 染色体的编码

所谓编码就是指将问题的解空间转换成遗传算法所能处理的搜索空间。常用的编码方式有二进制编码、符号编码和浮点数编码。由于二进制编码、解码操作简单易行,遗传操作便于实现。所以本文采用二进制编码。

2.1.2 种群规模

群体规模直接影响遗传算法的性能,一般来说,种群规模在20-200之间时,能够很好地实现种群多样性与算法复杂度之间的折衷。

2.1.3 适应度函数

适应度函数是用于评价各码串对问题适应程度的准则,它是遗传算法指导搜索的唯一信息,它的好坏是衡量算法优劣的关键。

2.1.4 遗传算子

(1)选择算子:将父代中适应度值高(性能优良)的染色体(个体)选择复制到下一代中,并淘汰劣势个体,选择过程通常采用适应度比例选择法又称赌轮选择法,适应度越高的个体被复制到下一代的概率越高。

(2)交叉算子:从群体中随机选择一对个体,以交叉概率$p{}_c\left(0<p{}_c\le 1\right)$实施交叉操作,即互相交换各自的部分基因(表示染色体的数字串的某一位),从而形成一对新的个体,常见的交叉方式有单点交叉、两点交叉、多点交叉及均匀交叉等。交叉概率一般取pc=0.6～1.0。

(3)变异算子:以很小的概率随机地改变遗传基因的值,在染色体以二进制编码的算法中,它随机地将染色体的某一位基因由1变为0,或由0变为1。通过变异算子,可确保群体中基因类型的多样性,防止搜索停滞,一般取变异概率pm=0.001～0.1。

2.2 改进的方法

遗传算法虽然在理论上形成了一套较为完整的算法体系,然而在实践中还存在很多问题,如早熟问题,它使遗传算法搜索不到真正的最优值。对标准遗传算法作如下改进:

遗传算法初期个体之间的差异性比较大,较大的交叉概率和较小的变异概率有利于保存有用的遗传信息;而在遗传算法后期,个体之间适应度的差别很小,较小的交叉概率和较大的变异概率能够增加个体的多样性,有利于进行全局搜索和克服早熟现象。所以本文采用自适应的交叉概率和变异概率:

$p{}_c(G+1)=p{}_c(G)-\frac{[p{}_c(1)-0.6]}{G{}_{\max }}(5)$

$p{}_m(G+1)=p{}_m(G)+\frac{[0.08-p{}_m(1)]}{G{}_{\max }}(6)$

式中:G为遗传代数,Gmax为最大遗传代数,pc(1)和pm(1)分别是第一代交叉概率和变异概率,pc(G)和pm(G)分别是第G代交叉概率和变异概率。

2.3 基于改进遗传算法的SVM参数优化设计

为了实现应用遗传算法对SVM参数的优化,本文对标准遗传算法进行了改进,并在此基础上对SVM参数优化,其流程图设计如图3所示。

应用改进遗传算法对SVM进行参数优化的具体实现步骤如下:

Step 1:初始化SVM参数并对其进行二进制编码,产生遗传算法的初始群体;群体数量选取100,二进制编码码串的长度根据要搜索的SVM参数的范围与精度来确定。以利用RBF核函数为例,SVM需要优化的参数为C与γ,码串中包括两个参数的二进制码。

Step 2:设定遗传算法的参数,初始代数设为G=1,初始交叉概率pc(1)=0.8 ,初始变异概率pm(1)=0.008,最大遗传代数Gmax=100。

Step 3:将初始群体解码后送入SVM进行训练并计算个体的适应度,本文适应度函数采用SVM分类的正确率。

Step4:应用最优保存策略,在进行遗传操作之前先把适应度(正确率)最高的个体保存下来,以防止优秀基因因遗传算子操作而丢失;记录最差个体的序号 Index。

Step5:进行遗传操作,选择算子采用赌轮选择法,交叉算子采用单点交叉,经过遗传算子操作产生新群体,并用Step 4保存的最优个体替换序号为 Index 的新个体,并最终产生新的群体,然后返回Step 3进行训练。

Step6:检查是否满足算法终止条件,由于分类正确率(适应度)本身就是要搜索的结果,很难作为终止条件,但是当连续几代最优个体的适应度相等时则认为种群不能再进化,作为算法终止的条件之一,把设定的最大遗传代数也作为算法的终止条件之一,当满足上述两个条件中的任何一个时,则自动终止算法。

3 仿真结果与分析

为了验证算法的有效性,本文利用UCI[10]数据库中ionosphere、vehicle、zoo等数据在Matlab环境下进行仿真验证,各类数据的属性如表1所示。

在划分各数据的训练样本和测试样本时,以一半的数据进行训练,另一半数据进行测试。支持向量机的核函数采用径向基核函数:

${\rm K}(x,x{}_i)=\exp \{-\gamma \left|x-x{}_i\right|{}^2\}(7)$

本文同时利用网格搜索的方法对SVM参数优化进行了仿真,仿真结果如表2所示。

由以上仿真结果可以看出,改进的遗传算法比网格搜索的方法有更高的分类正确率, ionosphere、vehicle、zoo三类数据的分类正确率分别提高了1.11%、0.81%、2.12%,这表明改进的遗传算法比网格搜索的方法搜索能力更强,能够搜索到更优的参数值;而两种方法的支持向量数(SVs)基本一致,所以运算速度基本一致,这表明算法的运算速度并没有因为算法的复杂化而降低;还可以看到,无论是在两类分类(ionosphere)还是多类分类(vehicle、zoo)问题中,分类正确率都得到了提高,这表明改进的遗传算法具有良好的泛化性能。

4 结束语

(1)本文在简单介绍支持向量机和遗传算法的基本原理之后,针对所存在的问题设计了一种基于改进遗传算法的支持向量机参数优化方法。

(2)在Matlab环境下对所提出的算法进行了仿真,总的来说,支持向量机的总体性能得到了提高,仿真结果验证了本文所提出的算法的有效性,为支持向量机的参数优化提供了一种切实可行的方法。

摘要：支持向量机是一种非常有前景的学习机器,但是,支持向量机参数的选取一直没有一套成熟的理论,这给支持向量机的应用带来了很大的不便。为此,本文提出了基于改进遗传算法的支持向量机的参数优化方法,利用遗传算法的全局搜索能力得到支持向量机的最优参数值。仿真实验结果表明,得到的参数可使支持向量机具有良好的泛化性能,此方法切实有效。

关键词：支持向量机,改进遗传算法,参数优化

参考文献

[1]李杰,楚恒,朱维乐,彭静.基于支持向量机和遗传算法的纹理识别[J].四川大学学报(工程科学版),2005,37(4):104-108

[2]张伟,胡昌华,焦李成,薄列峰.克隆规划-交叉验证参数优化的LSSVM及惯性器件预测[J].西安电子科技大学学报(自然科学版),2007,34(3):428-437

[3]周辉仁,郑丕谔,赵春秀.基于遗传算法的LS-SVM参数优选及其在经济预测中的应用[J].计算机应用,2007,27(6):1418-1429

[4]张周锁,李凌均,何正嘉.基于支持向量机故障分类器的参数优化研究[J].西安交通大学学报,2003,37(11):1101-1109

[5]邵信光,杨慧中,陈刚.基于粒子群优化算法的支持向量机参数选择及其应用[J].控制理论与应用,2006,23(5):740-748

[6]CHAPELLE O,VAPNIK V,BOUSQUET O,et al.Choosing Multiple Parameters for Support Vector Machines[J].MachineLearning,2002,(46):131-159

[7]Vapnik著,许建华,张学工,译.统计学习理论[M].北京:电子工业出版社,2004.

[8]李人厚.智能控制理论和方法[M].陕西:西安电子科技大学出版社,2005.

[9]杨淑莹,著.模式识别与智能计算———Matlab技术实现[M].北京:电子工业出版社,2008.

支持向量机算法 第5篇

针对现有的.外场数据统计法在确定飞机机载产品寿命指标上的局限性,建立了机载产品使用影响因素体系,利用某型机载产品在不同典型使用环境下的故障率数据,建立支持向量机回归分析模型,通过机器学习掌握已知机载产品使用影响因素向量和故障率数据的相互关系,根据已知的产品故障率数据对未知寿命进行预测.利用8个单位的产品故障率来预测另一单位的产品故障率,并给出了算例分析.计算结果与实际情况相吻合,表明该方法具有一定的应用价值.

作 者：李郑琦 何宇廷 邵青 魏鹏 作者单位：李郑琦(中国飞行试验研究院,陕西,西安,710089)

何宇廷,邵青,魏鹏(空军工程大学,工程学院,陕西,西安,710038)

支持向量机算法 第6篇

1引言：

入侵检测系统（intrusion detection system，IDS）作为防火墙之后的第二道安全闸门，能够发现网络入侵行为，因此网络入侵检测已成为网络安全领域的研究热点[1]。网络入侵检测分为误用检测（misuse intrusion detection，MID）和异常检测（anomaly intrusion detection，AID）两类[2]。误用检测技术只可以检测已知入侵行为，不能对未知或变入侵行为进行检测，而异常检测可以较好对未知入侵行为进行检测，成为入侵检测中的主要研究方向[3]。传统网络入侵异常检测算法有：模式匹配算法、BM算法、QS算法等，这些算法均属于单模式的网络入侵检测算法，难以适应现代大规模网络安全检测要求[4]。近年来，随着人工智能技术的发展，出现了隐马尔可夫模型、支持向量机和神经网络等入侵检测模型，其中支持向量机（support vector machine，SVM）较好的克服了神经网络等传统机器学习算法的过拟合、泛化推广能力差等缺陷，对于高维、小样本的网络入侵检测具有明显优势[5-7]。大量实验表明，基于SVM的网络入侵检测模型性能与其参数：惩罚因子C和核函数参数等直接相关。为了获得较优SVM参数，学者们提出采用遗传算法（GA）、粒子群算法（PSO），在一定程度上优化了SVM的入侵检测性能[8-10]。蚁群算法（ant colony optimization algorithm，ACO）是一种源于大自然中生物世界的新仿生类算法，吸收了蚂蚁的行为特性，通过其内在的搜索机制，易于与其他启发式方法相结合[11，12]。

为了提高网络入侵检测率，提出一种变异蚁群算法（mutation ant colony optimization algorithm，MACO优化支持向量机的网络入侵检测模型（MACO-SVM），并通过仿真实验对其有效性进行检验。

变异蚁群算法

蚁群算法是由意大利学者M Dorigo等人在1991年受到蚂蚁搜索食物过程中依据同伴遗留下的信息激素进行最短路径选择的启发而提出的一种新的仿生优化计算方法，具有正反馈、分布式计算和贪婪启发式搜索等特点，但是基本蚁群算法存在过早收敛以及局部聚集等问题，为此，本文探路过程中，对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），产生一种变异蚁群算法（MACO），以便探索新的路径，提高问题求解的效率。

MACO算法优化SVM参数原理

采用MACO算法对SVM的参数C和σ优化过程，节点值表示C和σ，以入侵检测率作为目标函数，激素物质遗留在蚂蚁所走过的每个节点上，MACO算法所搜索出的最终路径表示最优网络入侵模型参数。SVM 参数优化的蚁群系统根据目标函数值来更新信息素的浓度，目标函数中包含各蚂蚁所爬行过的全部节点信息以及所建模型的网络入侵检测率。待优化的变量为SVM的参数C和σ，程序终止时，从蚁群的最优化路径中得到相对应的SVM的参数C和σ值，原理如图1所示。

MACO算法优化SVM参数过程

1）设蚁群规模为m，每只蚂蚁k均有一维数组pathk。其中依次存放第k只蚂蚁经过n个节点的纵坐标，n为所优化参数的总有效位，这些纵坐标连接在一起组成该蚂蚁的爬行路径。

2）全部蚂蚁置于起始点O，循环次数N=0，时间计数器t=0，最大迭代次数为：Nmax，初始化节点上信息量△τ（xi，yi，j，0），并设Δτ（xi，yi，j）=0。

3）设置变量i=1。

4）根据式（7）计算蚂蚁的转移概率，在线段Li上，根据概率以赌轮算法选择每只蚂蚁下一个转移节点，并将蚂蚁转移到相应节点上，并将该节点的纵坐标存入pathk的第i个元素中。

5）i=i+1，如果i>n，跳转到步骤6），不然跳转到步骤4）继续爬行。

6）根据数组pathk计算该路径对应的C和σ。

7）将训练集平均分成k个子集S1，S2，…，Sk。

8）SVM根据获得的{C，σ}对训练集进行学习，计算kfold交叉验证的检测率。

9）以kfold交叉验证中最优检测率作为适应度值，检测率最高对应路径作为本次循环的最优路径。

10）N=N+1，t=t+n，更新每个节点上的信息浓度，pathk中的全部元素置零。

11）对蚂蚁进行高斯变异，打破蚁群严重聚集的情况（局部极值），以便探索新的路径，并将新的路径与原有路径进行比较，选出最优蚂蚁。

12）如果迭代次数大于最大迭代数，则表示算法结束，并计算输出最优路径对应的SVM参数C和σ值。

13）SVM根据最优C和σ值对训练集重新学习，建立最优的网络入侵检测模型。

网络入侵检测多分类器构建

网络入侵检测实质上一个多分类问题，但SVM只能求解两分类问题，必须通过组合策略构建网络入侵检测器，本文采用有向无环图将两分类的SVM组合在一起，构造的网络入侵检测器如图2所示。

在CPU 2.8 GHz，RAM 1 GB 环境上，采用Libsvm 2，98实现仿真实验。按照一般的做法，实验采用KDD CUP 99数据集中的10%的数据（约10万条记录）中随机抽取的的正常连接记录作为训练样本。MACO算法的参数为：蚂蚁数m=10，最大迭代次数Nmax=100，Q=100，α=2，β=4。

为了使MACO-SVM模型检测更具说服力，在相同条件下，采用遗传算法优化SVM（GA-SVM）和基本蚁群算优化SVM（ACO-SVM）作为对比实验。模型性能评价指标为：检测率、误报率和运行速度。检测率和误报率定义如下：

检测结果对比

GA、ACO、MACO算法对SVM参数选择的结果见表3。然后采用表3的参数建立相应的网络入侵检测模型，GASVM、ACOSVM和MACOSVM的检测结果见表3。从表3可知，相对于对比模型GASVM、ACOSVM，MACOSVM的中支持向量数更少，但检测结果最佳，这表明 MACO算法比GA、ACO在SVM参数优化方面具有更好的较强的全局搜索能力，获得更优的SVM参数C，σ，可以降低网络入侵检测误报率，有效提高了网络入侵检测率。

运行速度对比

为了检测模型的运行速度，采用模型对验证集的检测时间（秒，s）作为衡量指标，各模型的检测时间见图3。从图3可知，相对于GASVM、ACOSVM，MACOSVM检测速度大幅度提高，主要由于MACOSVM减少了支持向量点数量，收敛速度加快，满足了现代网络入侵检测系统的实时性要求。

支持向量机算法 第7篇

统计学习理论[1] ( Statistical Learning Theory, SLT) 是20世纪70年代由Vapnik等人提出来的专门用于研究在有限样本情况下机器学习规律的理论, 该理论既考虑了对推广能力的要求, 又追求在有限信息下得到最优结论。支持向量机 ( Support Vector Machine, SVM) 正是在这种理论基础上并结合结构风险最小化原则不断形成和发展起来的, 它克服了传统机器学习模型容易陷入局部极小、过拟合、大样本和过分依赖经验等弊端。SVM在解决有限样本、非线性和高维度问题中表现出良好的性能和独特的优势[2,3]。SLT和SVM正在成为继人工神经网络后机器学习方面新的研究热点和重要分支领域, 将有力推动机器学习理论和技术的发展。支持向量机作为一种较新颖的机器学习模型, 有待进一步研究、发展和完善。在支持向量机模型研究过程中, 如何提高模型的学习精度、学习能力以及在两者之间寻求最佳折中以期获得最好的推广能力始终是支持向量机研究的重要方面。支持向量机的参数对模型的分类精度、学习效率和泛化能力有重要影响[4,5]。传统的参数选择方法都是通过反复的实验, 人工选出令人满意的值, 这些方法需要人的经验作指导, 并且需要付出很大的时间代价。梯度下降法[6]是一种相对比较理想的方法, 具有强大的局部寻优的能力, 不过梯度下降法的优越性很大程度上取决于初始值的选择, 如果初始值的选择不当, 则也容易陷入局部极小点[7]。文献[8]利用普通遗传算法 ( GA) 来进行SVM参数的优化, 获得了较好的效果, 但是普通遗传算法本身也存在计算存储量大、无法保证收敛到全局最优、群体中最好染色体的丢失和进化过程过早收敛等缺陷。

针对以上问题, 本文引入梯度下降法结合量子遗传算法 ( QGA) 对支持向量机参数 ( 核参数和惩罚因子) 进行优化选取, 基本思想概括为首先利用量子遗传算法在全局范围内选择一个较优的值作为梯度法的初始值, 再利用梯度法进行局部优化得到最优值。

2 支持向量机基本理论

支持向量机是用非线性映射把输入数据映射到一个高维特征空间, 在高维特征空间中构造线性判别函数来实现原空间中的非线性判别。本文采用Suykens和Vandewalle提出的支持向量机的最小二乘模型, 也即支持向量机的二次损失函数形式, 其分类原理可以表示为如下推导过程。

其中, b∈R表示分类阀值; ω是特征空间中的分类超平面的一维系数向量; ξi是考虑分类误差而引入的误差扰动因子; γ是平衡最小分类边界和最小分类误差的惩罚因子; φ ( xi) 是将样本输入x从原空间映射到高维特征空间的非线性变换函数。采用拉格朗日乘数法解上述凸二次规划问题, 首先得到问题的对偶问题:

上式中, ai是拉格朗日乘子, K ( xi, xj) =φ ( xi) Tφ ( xj) 是核函数。若设

则上述优化问题 ( 2) 可以转化为求

由 ( 4) 看出, 通过采用核函数 ( 3) 转化, 最小二乘形式的支持向量机具有与线性可分支持向量机完全相同的形式[4]。在采用了核函数后, 原问题则相应地变为

上式中, zi是xi在核函数 ( 3) 对应的特征空间中的投影, 即在最优解处式 ( 5) 和式 ( 4) 同解, 即最后得到的最优分类函数是

这就是支持向量机, 式 ( 6) 中, sgn ( ) 为符号函数。由于非支持向量对应的αi均为0, 因此式中的求和实际上只对支持向量进行。b可由任意一支持向量求得。

3 支持向量机的性能估计和梯度推演

支持向量机参数优化的目的就是利用一切有效的方法选择适当的参数, 使得支持向量机的期望风险最小。期望风险描述的是学习机器对参数空间所有数据的逼近能力, 仅仅利用已知的、有限数目的训练样本不能直接和准确地计算期望风险, 现有的方法是通过计算期望风险上界的某种估计来选择参数。估计和计算期望风险上界的方式和算法有很多种, 包括LOO ( Leave - One - Out) 估计和K重交叉校验估计在内的一些方法都存在计算量大的问题, 因为它们都需要在同一参数组合上重复多次训练和测试。近年来一些专家学者提出来的RM ( Radius -Margin bound) 界、CACA界、Xi - Alpha界等期望风险上界的估计方法很好地解决了计算量大的问题。它们在对SVM训练后, 只需较小计算量就可以估计出参数处的期望风险。

Vapnik提出针对硬间隔形式SVM期望风险的RM界[4], 定义为式中, LOOError为LOO方法估计的期望风险, l为训练样本的数目, R为特征空间中包含所有训练样本的最小球半径; ω为SVM的权向量。

RM界表明SVM的期望风险取决于两个因素: 样本在特征空间中的分布形状和最优分类面的权向量。R可由以下优化问题求得:

由于ω与核函数和惩罚因子有关, R也和核参数相关, 因此RM界实际上是核参数和惩罚因子的隐函数。

在γ >0, σ >0的约束条件下, RM界 ( 泛化能力的估计函数) 可以表示为此时, 问题的关键变为如何求R2, ︱︱ω︱︱2关于 ( γ, σ) 的梯度。若给定一对 ( γ, σ) , 就可以通过计算得到相应的α, χ, R2, ︱︱ω︱︱2。在不考虑α, χ关于 ( γ, σ) 的梯度情况下, 求R2, ︱︱ω︱︱2关于 ( γ, σ) 的梯度推算如下:

将式 ( 9) 和 ( 10) 代入式 ( 8) 中, 这样一来就可以求出参数空间中任意一点处RM界的梯度, 然后, 利用标准的梯度下降算法优化SVM的参数。

4 支持向量机参数优化的混合梯度下降算法

梯度下降法选取SVM参数受初始值的影响很大, 所以本文先利用量子遗传算法 ( QGA) 以避免运用梯度下降法选取SVM参数时初始值选择不理想致使算法陷入局部极小点, 最终影响SVM的性能。

QGA基本思想来源于量子理论和遗传算法的结合, 是新发展起来的一种基于量子计算原理的概率优化搜索方法[9,10]。QGA在传统遗传算法中引入量子理论, 以解决传统遗传算法存在的计算存储量大、无法保证收敛到全局最优解、群体中最好染色体的丢失和进化过程过早收敛等缺陷, 在群体多样性和全局优化能力方面要明显优于传统量子遗传算法。量子遗传算法采用量子比特编码, 用量子门作用和更新来完成进化和搜索, 具有种群规模小但不影响算法性能、同时兼有“勘探”和“开采”的能力、收敛速度快和强大的全局寻优能力等优势。量子遗传算法结合了量子计算和遗传算法的双重优点。本文融合梯度法的局部寻优能力和量子遗传算法的全局搜索能力构成混合梯度下降算法对SVM参数进行优化选择, 以使得SVM的各种性能和效率得到大的改善。混合梯度下降算法的具体操作步骤如下:

步骤1: 确定种群规模为n, 即第t代种群pt= { p1t, p2t, …, ptn} 。首先进行初始化 ( 取t =0) , 因为多态问题量子染色体的量子比特编码可表示如下:

又本文是对惩罚因子γ和核参数σ进行优化, 所以对应式 ( 11) qtj中的m =2, 并确定s以及所有的αij和βij的值 ( αij和βij的初始值一般取1/槡2, 表示在初始搜索时所有状态以相同的概率进行叠加) ;

步骤2: 根据量子染色体到二进制染色体的测量原则 ( 对应量子染色体中每一位, 产生一个随机数λ ( λ∈[0, 1]) , 若λ≥|αtij|2, 则相应测量值取1, 否则取0, 若以|βtij|2为基准, 则取值刚好相反) 对pt中各个个体进行测量, 得到量子叠加态的测量值yt= { y1t, y2t, …, ytn} , ytj ( j =1, 2, …, n) 为相应个体的测量值 ( 二进制串) ;

步骤3: 解码过程, 由测量值yt换算成γ和σ 的当前实际值;

步骤4: 把γ和σ 的当前实际值输入到SVM训练系统中训练, 根据SVM的实际应用和目的确定适应度函数 ( 识别率、分类精度等) , 并对所有个体进行适应度评价;

步骤5: 保留最佳个体, 并判断是否符合终止条件。若符合, 则转入步骤8, 否则转入步骤6;

步骤6: 根据预设定的量子门, θ为旋转角度, 其大小和方向根据事先设计的旋转策略而定。) 旋转策略进行量子的更新操作 ( 更新过程为:U ( t) 为第t代的量子门。ptj和pt + 1j分别表示第t和t +1代的几率幅) , 也可以根据需要对量子染色体进行一定概率的交叉和变异操作, 最后得到多样化的新一代种群pt;

步骤7: 进化代数t =t +1, 算法回到步骤2继续执行, 直到满足量子遗传操作的收敛条件为止 ( 达到预设定的进化代数、种群趋于收敛或者收敛缓慢) ;

步骤8: 将量子遗传操作的最终结果作为梯度下降法的初始值, 假设为 ( γ0, σ0) , 用梯度下降法继续局部寻优;

步骤9: 在 (γ0, σ0) 处训练SVM并计算梯度

步骤10: 利用标准梯度下降算法, 计算求出使得f ( γ, σ) 减少的新 ( γ, σ) 的值 ( γi, σi) ;

步骤11: 用 ( γi, σi) 作为新参数值, 计算f ( γi, σi) , 若f ( γi, σi) 达到极小值或者满足终止条件, 则终止收敛, 否则返回步骤9用 ( γ, σ) 替代 ( γ0, σ0) 继续循环直到收敛为止。

5实例验证

本文选择经典双螺旋分类问题进行实验。为验证混合梯度下降算法选择的SVM参数对分类精度的影响, 本文选取标准的数据集进行实验, 数据集为

( 1) 训练样本集数目为400个, 在直角平面xoy上。此时我们设: θ ( i) =i× ( π÷16) , r ( i) =6.5× ( 104- i) ÷104, x ( i) = r ( i) ×sinθ ( i) , y ( i) = r ( i) ×cosθ ( i) , i = 0, 1, 2, …, 199。

由点 ( x ( i) , y ( i) ) ( i =0, 1, …, 199) 组成第一类, 标记为“+1”; 第二类标记为“-1”, 由点 ( - x ( i) , - y ( i) ) ( i = 0, 1, …, 199) 组成。

( 2) 测试样本集数目为200个, 在直角平面xoy上设: ( i =0, 1, …, 99) , ( i +0. 5) × ( π÷16) , r ( i) =6. 5× ( 104 - i - 0. 5) ÷104, x ( i) = r ( i) ×sinθ ( i) , y ( i) = r ( i) ×cosθ ( i) 。标记为“ + 1”的一类由点 ( x ( i) , y ( i) ) ( i = 0, 1, …, 99) ; 标记为“+ 1”的一类由点 ( - x ( i) , - y ( i) ) ( i = 0, 1, …, 99) 组成。本文设定进化代数t≤1000, 以RM界估计作为适应度函数。量子遗传算法部分收敛的条件为ftsu+m 1- ftsum≤ε ( ε取0. 001) , ftsum表示第t代种群适应度之和, 相应地ftsu+m 1表示第t +1代种群适应度之和, ε表示极小的正常数。梯度法迭代终止的条件是相邻两迭代点的下降量的相对值充分小, 即|f ( θi + 1) -f ( θi) |≤10- 6| f ( θi) |。

最后, 在计算机上运行, 最后得到的优化参数为γ =100, σ =0.235, 分类精度达到100%。对于双螺旋这样的经典分类难题, 很多文献都有详细研究, 一般研究结果表明常规的BP网络很难获得好的推广能力, Baum等人使用了2 - 50 - 1BP网络, 结果也不是很理想[11], Chen等人提出生成一个收缩算法来训练2 20 - 20 - 1的BP网络, 经过3000次迭代后, 分类精度只有89. 6%[12]。而本文的实验得到了最优的一组SVM参数, 整个过程是在很短的时间内迅速自动完成, 这说明混合梯度下降算法在优化选择SVM参数方面的有效性, 并且具有很大的优势。

6 结束语

本文提出了一种基于混合梯度下降算法的支持向量机参数优化方法, 该方法结合了梯度法的局部寻优能力和量子遗传算法的全局优化能力, 既克服了一般梯度法易受初始值影响的缺陷, 也较好地克服了普通遗传算法容易陷入局部最小、耗时长等弊端。最后的实例验证了这种方法在支持向量机参数选择方面的有效性。

摘要：在解决有限样本、非线性和高维度问题中, 建立在统计学习理论和结构风险最小化原则上的支持向量机表现出良好的性能和独特的优势。然而, 支持向量机参数对模型的识别精度和泛化能力有很大影响, 基于这样的事实, 运用混合梯度下降算法对支持向量机的参数进行优化选择, 结合量子遗传算法出色的全局优化能力和梯度下降法局部寻优能力, 较好地解决了传统的支持向量机中参数优化的难题。最后, 用实例验证了该算法的有效性。

关键词：支持向量机 (SVM) ,混合梯度下降,梯度下降法,量子遗传算法,参数优化

参考文献

[1]VAPNIK V.The nature of statistical learning theory[M].New York:wiley, 1998.

[2]Smola A J, Scholkopf B.A tutorial on support vector regression, NC-TR-98-030[R], UK:Royal Holloway Collage University of London, 1998.

[3]Burges C J C.A tutorial on support vector machines for pattern recognition[J].Knowledge Discovery and Date Mining, 1998, 2 (2) :121-167

[4]CHAPELLE O, VAPNIK V, MUKHERJEE S.Choosing multiple parameters for support vector machines[J]

[5]AYAT N E, CHERET M, SUEN C Y.Automatic model selection for the optimization of SVM kernels[J].Pattern Recongnition, 2005, 38 (5) :1733-1745

[6]KEERTHI S S.Efficient tuning of SVM hyerparameters using radius/margin bound and iterative algorithms[J].IEEE Trans Neural Networks, 2002, 13 (5) :1225-1229

[7]IMBAULT F, LEBART K.A stochastic optimization approach for parameters tuning of support vector machines[C]/Proceeding of the 17th International Conference on Pattern Recognition.Cambridge, United Kingdom:[s.n.], 2004:981-984

[8]陈果.基于遗传算法的支持向量机分类器模型参数优化, 机械科学与技术第3期第26卷, 2007.3.

[9]Hey T.Quantum computing:An introduction[J].Computing&Control Engineering Journal, 1996, 10 (3) :105-112

[10]Narayanan A.An introductory tutorial to quantum computing.Proc of IEE Colloquium on Quantum Computing:Theory, Applications and Implications[C].London:IEE Press, 1997.

[11]Baum E B, Lang K L.Cinstructing hidden units using examples and queries[A].In:Advances in Neural Information Processing System 3[C], San Maeto.CA:Morgan Kaufmann, 1991:904-910

约简数据集的支持向量分类机算法 第8篇

支持向量机SVM (Support Vector Machine) [6]是近年来机器学习研究的一项重大成果。由于SVM具有较为完美的数学形式、直观的几何解释和良好的泛化能力, 其解决了神经网络结构难以确定与欠学习、过学习问题, 避免了局部最优解, 且人为设定的参数少, 便于使用, 因此, 它迅速成为智能计算领域的研究热点之一, 并成功地应用于许多分类和回归问题中。

SVM算法实质上是求解一个凸二次规划 (QP) 问题, 这需要计算和存储核函数矩阵, 其大小与训练样本数的平方相关, 随着样本数目的增多, 所需要的内存增加。例如, 当训练样本数目超过4000时, 存储核函数矩阵需要多达128兆内存。其次, SVM在二次型寻优过程中要进行大量的矩阵运算, 多数情况下, 寻优算法是占用算法运行时间的主要部分。因此, 提出有效的针对大规模训练样本集的SVM算法意义深远。近年来, 关于该方面的研究已经有了一些成果。例如, Osuna等人[4]提出了分解算法;Joachims[2]基于Osuna的分解思想用软件SVMLight实现了分解算法;Platt[5]提出了SMO算法;文献[3,9]对SMO算法做了改进。特别地, 文献[1]提出一种加速算法, 后来, 王文剑[10]推广该算法至回归问题, 她通过引入一个“阈值”来调整训练样本的数目, 在不影响泛化能力的基础上, 达到加速训练的目的。最近, 奉国和等[8]提出一种边界邻近支持向量分类机算法, 该算法类似文献[1]对分类样本进行数据约简的处理, 只是不需计算每类样本的类中心, 实现方法直观有效。但是, 遗憾的是该文仅仅对线性可分问题适用, 而对现实中大量存在的线性不可分问题不适用。

本文在文献[8,10]的基础上给出一种新的约简数据集的支持向量分类机算法。该算法对线性可分、线性不可分的分类问题均适用。

1 算法的理论分析与设计

1.1 相似度与特征相似度的定义

我们用相似度 (Similarity) 来衡量两个样本间的接近程度。为此, 定义相似度函数如下:

$S(x,y)=f\left(\frac{1}{\parallel x-y\parallel {}_2}\right)=f\left(\left[{\displaystyle \sum _{i=1}^{{\rm M}}(}x{}_i-y{}_i){}^2\right]{}^{-\frac{1}{2}}\right)$

其中x, y表示两个不同样本, M表示样本的维数。为了简单起见, 令f (x) =x, 这时

$S(x,y)=\frac{1}{\parallel x-y\parallel {}_2}=\left[{\displaystyle \sum _{i=1}^{{\rm M}}(}x{}_i-y{}_i){}^2\right]{}^{-\frac{1}{2}}=\frac{1}{d(x,y)}$

S (x, y) 称为样本x与y的相似度, 其值越大表示两个样本越相似。通常, 支持向量机算法需要通过引入核函数K (x, y) 将训练样本映射到一个高维的Hilbert空间, 这样训练样本集变成TH={ (Φ (x1, y1) , (Φ (x2, y2) , …, (Φ (xl, yl) }, 然后在Hilbert特征空间利用线性可分或者近似线性可分的算法求解该分类问题, 所以, 我们更加关心特征空间中两个样本的相似度。定义相应的特征空间中的相似度函数如下:

$\begin{array}{l}S(\Phi (x),\Phi (y))=\frac{1}{\parallel \Phi (x)-\Phi (y)\parallel {}_2}\\ =(\Phi {}^2(x)+\Phi {}^2(y)-2\Phi (x)\Phi (y)){}^{-\frac{1}{2}}\\ =({\rm K}(x,y)+{\rm K}(y,y)+2{\rm K}(x,y)){}^{-\frac{1}{2}}(1)\end{array}$

这样我们就可以利用核函数来计算特征空间中样本之间的相似度, 我们称其为样本x与y的特征相似度。

1.2 支持向量分类机算法 (C-SVC)

算法C-SVC见文献[7]。本算法关键在于求解一个凸二次规划问题, 考虑其原始问题, 并引入Lagrange函数,

$\begin{array}{l}L(\omega ,b,\xi ,\alpha ,r)=\frac{1}{2}\parallel \omega \parallel {}^2+C{\displaystyle \sum _{i=1}^l\xi }{}_i-{\displaystyle \sum _{j=1}^l\alpha }{}_j(y{}_j((\omega \cdot x{}_j)+b)\\ -1+\xi {}_j)-{\displaystyle \sum _{i=1}^{l}r}{}_i\xi {}_i\end{array}$

其中, αi≥0, ri≥0, 从而可以求出该对偶问题, 即支持向量分类机算法中的凸二次规划问题。由文献[7]中定理5.3.8和Wolfe定理1.3.12可知, 若 (ω, b, ξ) 是原始问题的解, 则对偶问题必有解α= (α1, …, αl) 。由于αi又对应于原始问题中约束的Lagrange乘子, 利用KKT互补松弛条件, 即αi (yi ( (ω·xi) +b) -1+ξi) =0, 得到如下关系:

(i) 若αi=0, 则yi ( (ω·xi) +b) ≥1, 且对应ξi=0;

(ii) 若0<αi<C, 则yi ( (ω·xi) +b) =1, 且对应ξi=0;

(iii) 若αi=C, 则yi ( (ω·xi) +b) <1, 且对应ξi≥0。

另一方面, 根据算法中决策函数的形式:

$f(x)=\mathrm{sgn}({\displaystyle \sum _{i=1}^{l}y}{}_i\alpha {}_i^{*}{\rm K}(x{}_i,x)+b{}^{*})(2)$

可以看到只有 (ii) (iii) 中的αi才有效, 对最后的结果产生影响, 而 (i) 中所对应的大量的间隔外正确划分的样本点来说, 它们是否参与训练, 对最后结果并不影响。因此, 我们可以酌情对这些样本点进行删减, 从而达到约简训练样本集的目的。

1.3 样本点集的分配与压缩

根据1.2节 (i) (ii) (iii) 的结果, 将训练样本集T={ (x1, y1) , (x2, y2) , …, (xl, yl) }分成三类:第一类为满足yi ( (ω·xi) +b) ≥1的样本点, 称为可去支持向量RSV (Removed Support Vectors) , 记为R;第二类是满足yi ( (ω·xi) +b) =1的样本点, 称为边界支持向量BSV (Boundry Support Vectors) , 记为B;第三类为满足yi ( (ω·xi) +b) <1的样本点, 称为错误支持向量ESV (Error Support Vectors) , 记为E。留心到公式 (2) , 显然只有第二类样本集B和第三类样本集E对最后的结果有“贡献”。一方面, 对于第三类样本点集αi=C, 则不必参与训练;另一方面, 根据支持向量的几何分布, 支持向量分布在超平面或者超曲面的附近, 所以对于第一类样本点集R, 则可以有选择地约简数据集, 这里根据不同类样本点的最大特征相似度的计算对样本集进行约简。

1.4 噪声数据的检测

设已知T={ (x1, y1) , (x2, y2) , …, (xl, yl) }表示l个训练样本点的集合, 其中xi∈Rn, yi={-1, 1}, i=1, …, l, 下面分别用pos (T) ={xiyi=1, i=1, …, l}, neg (T) ={xiyi=-1, i=1, …, l}来记录正负两类不同的样本点集。任意选择样本 (xi*, yi*) , 并设定合适的阈值s (也称相似度阈值) , 计算其他的训练样本与样本 (xi*, yi*) 的特征相似度, 分别记属于两类样本点集且特征相似度≥s的样本点个数为k1, k2:如果yi*∈pos (T) 并且k1<k2, 或者yi*∈neg (T) 并且k1>k2, 则 (xi*, yi*) 为噪声数据点。

1.5 样本最大特征相似度的计算

将给定的数据样本集T={ (xi, yi) }${}_{i=1}^l$分为如下两类样本集:T1=pos (T) ={ (x${}_i^{(1)}$, yi) }${}_{i=1}^{l{}_1}$与T2=neg (T) ={ (x${}_i^{(2)}$, yi) }${}_{i=1}^{l{}_2}$, 按照下面的程序可以得到样本集T2中与x${}_i^{(1)}$, (i=1, …, l1) 具有最大特征相似度的样本Ui, i=1, 2, …, l1。

主要程序如下:

for i=1:l1

Ui=x${}_1^{(2)}$;

for j=1:l2

$\begin{array}{l}\text{i}\text{f}\left(\text{S}\left(\text{Φ}\left(\text{x}{}_{\text{i}}^{(1)}\right),\text{Φ}\left(\text{x}{}_{\text{j}}^{(2)}\right)\right)>\text{S}\left(\text{Φ}\left(\text{x}{}_{\text{i}}^{(1)}\right),\text{Φ}\left(\text{U}{}_{\text{i}}\right)\right)\right)\\ \text{U}{}_{\text{i}}=\text{x}{}_{\text{j}}^{(2)}；\end{array}$

end

end

end

这里特征相似度S按照1.1中 (1) 式的方法计算。记$\underset{{\rm T}{}_2}{{\displaystyle \max }}U(x{}_i^{(1)})=U{}_i$, 称为样本x${}_i^{(1)}$关于样本集T2的最大特征相似度。

1.6 RS-C-SVC算法的设计

下面将给出RS-C-SVC算法具体的执行过程:

Step 1 (初始化)

Step 1.1 将给定的数据集T={ (xi, yi) }${}_{i=1}^l$分为

T1=pos (T) 和T2=neg (T) 。

Step 1.2 初始化空间A, B分别用来存放压缩后的新训练样本集和噪声数据样本集, 初始化相似度阈值s=0。

Step 2 确定训练样本集和噪声样本集

Step 2.1 找出T2中的训练样本和噪声数据点

for i=1:l1

temp1=x${}_i^{(1)}$;

$temp2=\underset{{\rm T}{}_2}{{\displaystyle \max }}U(x{}_i^{(1)})$;[见1.5]

s=0.8S (temp1, temp2) ;

if (temp2是噪声数据) [见1.4]

copy (temp2, B) ;

else

copy (temp2, A) ;

end

end

Step 2.2 找出T1中的训练样本和噪声数据同Step 2.1。这样我们就得到了约简后的训练样本集A={ (ui, yi) }${}_{i=1}^m$和噪声样本集B={ (vi, yi) }${}_{i=1}^n$。

Step 3 训练支持向量分类机

对新产生的训练样本集A, 执行算法C-SVC。

Step 4 最终输出结果

$f(x)=\mathrm{sgn}({\displaystyle \sum _{i=1}^{m}y}{}_i\alpha {}_i^{*}{\rm K}(u{}_i,x)+C{\displaystyle \sum _{i=1}^{n}y}{}_i{\rm K}(v{}_i,x)+b{}^{*})$

这里选择α*的一个正分量α${}_j^{*}$, 据此计算$b{}^{*}=y{}_j-{\displaystyle \sum _{i=1}^{m}y}{}_i\alpha {}_i^{*}{\rm K}(u{}_{i,}u{}_j)$。

2 仿真实验

例1 (线性可分问题)

这里选用一个具有180个初始数据点的分类问题[12], 进行试验, 图1、图2分别给出了算法C-SVC和算法RS-C-SVC运行的结果, 表1给出了两种智能算法运行的结果比较。

例2 (非线性可分问题)

选一个具有220个初始样本点的非线性可分的分类问题[12]进行试验, 这里采用多项式核函数, 且惩罚参数C=5, ε=0.1, 图3、图4、表2给出了两种智能算法运行的效果比较。

本文实验在Window XP系统Matlab6.5环境下完成, 其中CPU为Pentium M 1400MHz, 内存为DDR256MB, 仿真软件使用Steve Gun SVM[11]。通过表1、表2数据看出, 采用了算法RS-C-SVC以后, 训练样本集规模大大地减少, 从图1-4的效果来看, 最后产生的超平面或者超曲面与未约简前的训练结果基本保持不变, 从而也不会影响所要解决的分类问题的最终结果。

3 结 论

本文给出了一种基于相似度的约简数据集的支持向量分类机算法 RS-C-SVC, 本算法一方面通过引入相似度阈值的办法检测噪声数据点, 从而产生噪声数据样本集, 另一方面根据不同类样本的最大特征相似度来确定超平面附近的样本点, 进而大幅度地约简了初始样本点集。 虽然在确定噪声数据和进行约简数据集的过程中需要耗费一定的时间, 但是考虑到约简后的训练样本数目大大地减少, 节省了训练支持向量机的内存空间, 同时由于求解的规模大幅度减少而加速了算法的运行, 这种代价是值得的。

摘要：支持向量机是当前智能计算研究领域的热点之一。基于支持向量机的大样本学习一直是一个非常具有挑战性的研究课题。对于分类问题给出一种基于相似度的约简数据集的方法。给出的新算法大大地减少了训练样本的数目和所求解的支持向量机算法的规模, 有效地加快了支持向量机算法的训练速度。仿真实验表明:新算法较为简单、实用。

关键词：支持向量机,约简数据集,相似度

参考文献

[1]Burges C, Scholkopf B.Improving the accuracy and speed of support vector learning machines[C].M.Mozer, M.Jordan, T.Petsche, eds, Advance in Neural Information Processing Systems9, Cambrige, MA:MITPress, 1997:375-381.

[2]Joachims T.Making large-scale support vector machine learning practi-cal[C].In:Advances in Kernel Methods Support Vector Learning, Cambridge:MITPress, 1998:169-184.

[3]Keerthi S S, Shevade S K, Bhattacharyya C, et al.Improvements to Platt s SMO Algorithm for SVMClassifier Design[J].Neural Computa-tion, 2001, 13 (3) :637-649.

[4]Osuna E, Freund R, Girosi F.An improved training algorithm for sup-port vector machines[C].In:IEEE Workshop on Neural Networks and Signal Processing, New York:IEEE Press, 1997:276-285.

[5]Platt J C.Sequential minimal optimization a fast algorithm for training support vector machines[C].In:Advances in Kernel Methods Support Vector Learning, Cambridge:MITPress, 1998:185-208.

[6]Vapnik N.The Nature of Statistical Learning Theory[M].New York:Springer Verlag, 2000.

[7]邓乃阳, 田英杰.数据挖掘中的新方法—支持向量机.科学出版社, 北京, 2004.

[8]奉国和, 李拥军, 朱思铭.边界临近支持向量机.计算机应用, 2006 (4) :11-12.

[9]李建民, 张钹, 林福宗.序贯最小优化的改进算法[J].软件学报, 2003, 14 (5) :918-924.

[10]王文剑.关于支持向量机的若干问题的研究和应用.西安交通大学博士学位论文, O29, 2003.

[11]http://www.kernel-machines.org/.

支持向量机算法 第9篇

1 SMO算法简介

支持向量机的学习训练算法是求解一个二次凸规划问题。Edgar Osuna在1997年提出一个求解SVM中QP问题的分解算法[4]。即把一个大型QP问题分解为一个小型QP问题组成的序列,在上一步的QP子问题中至少加入一个违反KKT条件的点构成下一步的QP子问题,每一步优化目标函数的值并始终满足约束条件,从而使这些QP子问题的序列收敛,直到最后所有的点都满足KKT条件,也就得到了原问题的解。1998年,J.C.Platt提出了一个称为SMO的分解算法[1]。该方法将QP问题分解为一系列尽可能小的QP子问题,使得该问题可以直接求解,不用额外存储矩阵与数值迭代过程,节约了机时。

SMO算法是对违反KKT约束的Lagrange乘子两两优化。直到所有的Lagrange乘子都满足KKT条件为止[1,5,6]。1.1 SMO算法的过程

输入:样本点互异的训练集{xi,yi|i=1,2,…,N},Mercer核函数k(x,y)=exp(-||x-y||2/2σ2)。σ为核参数。

输出:Lagrange乘子λi(i=1,2,…,N),权值向量w和偏置b。

Step 1:初始化Lagrange乘子λi(i=1,2,…,N)和偏置b,并计算权值向量

作所有乘子的集合S={λi|i=1,2,…,N}。

Step 2:如果所有的乘子都满足KKT条件即S=准,则终止。否则Step 3

Step 3:取α1∈S,如果α1满足KKT条件,那么S:={α1}并转向Step 2。否则转向Step 4。

为方便叙述,设在训练集中待优化乘子α1,α2相应的样本点为x1,x2,相应的类别为y1,y2。

Step 4:取α2∈S,如果α2满足KKT条件,那么S:={α2},做Step 4。否则判断α2是否满足即选取α2使得误差函数E(α1),E(α2)相差最大。其中:

f(x)表示判别函数,y1表示x1的样本类别,y2表示x2的样本类别。

如果满足则执行Step 5,否则Step 4,继续选取α2。

Step 5:设在训练集中α1,α2相应的样本点x2,x2。计算

Step 6:计算α1,α2的优化值α1*,α2*。其中误差函数E(α1),E(α2)的意义同Step 4。

其中,H表示α1,α2的上界,L表示α1,α2的下界,s表示符号参数,定义如下:

如图:图1为当s=-1时,直线α1-α2=h平移,上下界变化情况,图2为当s=1时,直线α1+α2=h平移,上下界变化情况。

Step 7:更新权值w和偏置b。(Δ表示增量,也表示差分算子,下同)

当α1*,α2*都不在边界上时,上面两式相等;当α1*,α2*都在边界上时,取上面两式的均值。

Step 8:S=S{α1,α2},并转向Step 3。

2 SMO算法推导的改进

以前的SMO算法推导方法是:当其它乘子都不变,只有乘子α1,α2变化时,在对偶规划式[5,6]。

中,因为乘子α1,α2满足线性约束条件,把优化函数W(α)看作乘子α2的一元二次函数,展开为二次函数的一般形式,通过一般形式来求α2的增量。

下面对传统的推导做如下改进。针对乘子α1,α2的对称性,利用求导的链式法则求W(α)对α2的导数,减少计算量。又利用W'(α2是α2的一次函数,并根据“一次函数的微商等于差商”,算出α2的增量。证明如下:

在(18)中,当其它乘子不变时,因为

所以,W(α)可以看作α2的一元函数,从(18)式可以知道W(α2)是一个二次函数。

下面通过求导的链式法则求W(α2)对α2的导数来求α2的最优解。把W(α)对αi求偏导数可得:

将和式(21)代入上式(22)可以得到:

因为其它乘子都不变,优化α1,α2,使得W(α2)取得极大值,α2*为极大值点,于是有W'(α2*)=0。

因为W(α2)是α2的二次函数,W'(α2)是α2的一次函数,而一次函数的微商等于差商,所以

而ΔW'(α2)=W'(α2*)-W'(α2)=0-W'(α2)=-W'(α2),和(25)(26)一起代入上式(28),可以得到:

即证得(8)式。

即证得(10)式。

从式(1)两边求差分可以推得:

即证得(14)式。

如果Lagrange乘子λi(i=1,2,…,N)都满足KKT条件,那么最好选择使得优化后的误差函数E'(xi)为0,即E'(xi)=E(xi)+ΔE(xi)=0,可以得到ΔE(xi)=-E(xi),

式(2)中两边差分可以得到:

把式(32)代入式(33)可以得到:

即证得(16)式。

3 结束语

相对于以前的推导方法而言。在文章中给出的推导过程要简单得多,而且除了误差函数以外,不需引入其它任何中间变量。

参考文献

[1]Platt J.Fast training of support vector machines using sequential minimal optimization[M].Cambridge,MA:MIT Press,1999:185-208.

[2]Keerthi S S,Shevade S K,Bhattacharyya C,et al.Improvements to Platt’s SMO algorithm for SVM classifier design[R/OL].Nat.Univ.Singa-pore,Tech.Rep.CD-99-14,http://guppy.mpe.nus.edu.sg/～mpessk.

[3]Keerthi S S,Shevade S K,Bhattacharyya C,et al..Improvements to platt's SMO algorithm for SVM classi_er design[J].Neural Computation,2001,13(3):637.

[4]Osuna E,Freund R,Girosi F.Training Support Vector Machines:an Application to Face Detection[C].Washington,DC,USA:Proceedings of the1997Conference on Computer Vision and Pattern Recognition(CVPR'97),IEEE Computer Society,1997.

[5]Cristianini N.支持向量机导论[M].李国正,译.北京:电子工业出版社,2004.

支持向量机算法 第10篇

Vapnik等人于上世纪90年代提出了针对“小样本”的学习方法—支持向量机[1,2,3] SVM(Support Vector Machine)。为了降低传统支持向量机的计算复杂性,Suykens等人提出了最小二乘支持向量机[4]LSSVM(Least Square Support Vector Machine),通过把求解二次规划问题转化为求解线性方程组的问题,使得计算速度明显加快。但是,这些研究主要还是针对多输入、单输出的样本进行的,对于多输入、多输出的情况研究较少。而现实当中存在着大量的多输出问题,例如,反映某个产品的质量好坏往往需要好几项指标,于是该产品的质量指标就可以作为多个因变量的输出。金融市场上的股票、期货交易预测、时间序列数据预测等问题都属于多元回归问题,即多输出问题。如果对每一个输出单独设计一个支持向量机,然后并行起来势必增加算法难度,也有可能破坏了数据之间本来存在的内在关系。因此,研究多输出支持向量机算法具有重要的理论价值和实际意义。

文献[5]把ε-SVR推广到多输出的形式。文献[6]在多输出ε-SVR中引入超球体损失函数,提高了算法的预测精度和抗噪性能。文献[7]在多输出ε-SVR中引入分段损失函数,对落在不同区间的误差采用不同的惩罚,实验表明其算法优于并行单输出的ε-SVR算法。

本文研究了多输出LSSVM回归算法,将单输出LSSVM推广到多输出情形,同时给出一种多输出LSSVM回归机的增量学习算法。最后,利用模拟数据对该算法进行了测试,并对实验结果进行了分析和讨论。

1 最小二乘支持向量回归机模型

已知样本集D={(xi,yi)}${}_{i=1}^l$,其中xi∈X⊆Rn,yi∈R。利用一个非线性映射ϕ(·)将样本的输入空间映射到高维的特征空间H,使得输入空间中样本的非线性学习问题转化为高维特征空间中的线性学习问题。借助最小二乘思想,非线性拟合问题可以转化为如下二次规划问题:

$\underset{w,b,\xi }{{\displaystyle \min }}\left\{\frac{1}{2}\parallel w\parallel {}^2+\frac{C}{2}{\displaystyle \sum _{i=1}^l\xi }{}_i^2\right\}(1)$

s.t:yi=wTϕ(xi)+b+ξii=1,2,…,l

其中常数C>0。为了求解优化问题式(1),建立Lagrange函数:

$L(w,b,\xi ,\alpha )=\frac{1}{2}\parallel w\parallel {}^2+\frac{C}{2}{\displaystyle \sum _{i=1}^l\xi }{}_i{}^2-{\displaystyle \sum _{i=1}^l\alpha }{}_i[w{}^{{\rm T}}\text{ϕ}(x{}_i)+b+\xi {}_i-y{}_i]$

根据最优性条件有:

$\{\begin{array}{l}\frac{\partial L}{\partial w}=0\Rightarrow w={\displaystyle \sum _{i=1}^l\alpha }{}_i\text{ϕ}(x{}_i)\\ \frac{\partial L}{\partial b}=0\Rightarrow {\displaystyle \sum _{i=1}^l\alpha }{}_i=0\\ \frac{\partial L}{\partial \xi {}_i}=0\Rightarrow \alpha {}_i=C\xi {}_i\\ \frac{\partial L}{\partial \alpha {}_i}=0\Rightarrow w{}^{{\rm T}}\text{ϕ}(x{}_i)+b+\xi {}_i=y{}_i\end{array}(2)$

消去方程组式(2)中的w、ξi得到:

$\left(\begin{array}{cc}Q+C{}^{-1}E& e\\ e{}^{{\rm T}}& 0\end{array}\right)\left(\begin{array}{l}\alpha \\ b\end{array}\right)=\left(\begin{array}{l}y\\ 0\end{array}\right)(3)$

其中Q=(Qij)l×l,Qij=K(xi,xj)=<ϕ(xi),ϕ(xj)>,<·,·>表示内积。E为l×l阶单位矩阵,y=(y1,y2,…,yl)T,e为长度为l,元素为1的列向量。求解方程组式(3)得到最优解α*、b*,于是,回归函数可以表达成如下形式:

$y(x)={\displaystyle \sum _{i=1}^l\alpha }{}_i^{*}{\rm K}(x{}_i,x)+b{}^{*}(4)$

在LSSVM回归机中二次规划问题转化为线性方程组式(3)。而求解线性方程组要比求解二次规划简单快速,因此,LSSVM回归机与ε-SVR相比,计算复杂度更小。

2多输出最小二乘支持向量回归机增量学习算法

2.1 多输出最小二乘支持向量回归机模型

给定多输出样本集D={(xi,yi)}${}_{i=1}^l$,其中xi∈X⊆Rn,而yi∈Rm。推广单输出LSSVM回归机可以得到多输出LSSVM回归机:

$\underset{W,b,\xi }{{\displaystyle \min }}\left\{\frac{1}{2}\parallel W\parallel {}^2+\frac{C}{2}{\displaystyle \sum _{j=1}^m{\displaystyle \sum _{i=1}^l\xi }}{}_{ji}^2\right\}(5)$

s.t:yji=w${}_j^{{\rm T}}$ϕ(xi)+bj+ξjii=1,2,…,l j=1,2,…,m

其中式(5)中的W不再像 (1)式中的w是个向量,而是一个m×n的矩阵,W=(w1,w2,…,wm)T,wj=(wj1,wj2,…,wjn)T,j=1,2,…,m;b=(b1,b2,…,bm)T。令ξj=(ξj1,ξj2,…,ξjl)T,j=1,2,…,m。

建立Lagrange函数:

$\begin{array}{l}L(W,b,\xi ,\alpha )=\frac{1}{2}\parallel W\parallel {}^2+\frac{C}{2}{\displaystyle \sum _{j=1}^m{\displaystyle \sum _{i=1}^l\xi }}{}_{ji}^2-\\ {\displaystyle \sum _{j=1}^m{\displaystyle \sum _{i=1}^l\alpha }}{}_{ji}[w{}_j^{{\rm T}}\text{ϕ}(x{}_i)+b{}_j+\xi {}_{ji}-y{}_{ji}]\\ =\frac{1}{2}{\displaystyle \sum _{j=1}^{m}w}{}_j^{{\rm T}}w{}_j+\frac{C}{2}{\displaystyle \sum _{j=1}^m\xi }{}_j^{{\rm T}}\xi {}_j-{\displaystyle \sum _{j=1}^m{\displaystyle \sum _{i=1}^l\alpha }}{}_{ji}[w{}_j^{{\rm T}}\text{ϕ}(x{}_i)+b{}_j+\xi {}_{ji}-y{}_{ji}]\end{array}$

根据最优性条件有:

$\frac{\partial L}{\partial w{}_j}=0\Rightarrow w{}_j={\displaystyle \sum _{i=1}^l\alpha }{}_{ji}\text{ϕ}(x{}_i)(6)$

$\frac{\partial L}{\partial b{}_j}=0\Rightarrow {\displaystyle \sum _{i=1}^l\alpha }{}_{ji}=0(7)$

$\frac{\partial L}{\partial \xi {}_{ji}}=0\Rightarrow \alpha {}_{ji}=C\xi {}_{ji}(8)$

$\frac{\partial L}{\partial \alpha {}_{ji}}=0\Rightarrow w{}_j^{{\rm T}}\text{ϕ}(x{}_i)+b{}_j+\xi {}_{ji}=y{}_{ji}(9)$

将式(6)、式(8)代入式(9),并记Kpi=<φ(xp),φ(xi)>,p,i=1,2,…,m。则有:

$({\rm K}{}_{1i},{\rm K}{}_{2i},\cdots ,{\rm K}{}_{li})\left(\begin{array}{l}\alpha {}_{j1}\\ \alpha {}_{j2}\\ ⋮\\ \alpha {}_{jl}\end{array}\right)+b{}_j+\frac{\alpha {}_{ji}}{C}=y{}_{ji}(10)$

其中j=1,2,…,m;i=1,2,…,l。式(7)和式(10)组成的线性方程组可以写成如下形式:

$\left(\begin{array}{cc}\overline{Q}+C{}^{-1}E& e\\ e{}^{{\rm T}}& 0\end{array}\right)\left(\begin{array}{l}A\\ b{}^{{\rm T}}\end{array}\right)=\left(\begin{array}{l}Y\\ {\rm O}{}_{1\times m}\end{array}\right)(11)$

其中$\overline{Q}=({\rm K}{}_{pi}){}_{l\times l}^{{\rm T}}$;A是一个l×m矩阵,即A=(α1,α2,…,αm),αj=(αj1,…,αjl)T,j=1,2,…,m;b=(b1,b2,…,bm)T。O为m维的零向量,Y是一个l×m矩阵,Y=(y1,y2,…,ym), yj=(yj1,…,yjl)T,j=1,…,m。注意到在式(11)中,$\overline{Q}$是一个对称半正定矩阵,因此$\overline{Q}+C{}^{-1}E$是对称正定阵,可以证明方程组式(11)有唯一解。通过求解线性方程组式(11),得到最优解A*、b*,因此,可以写出如下形式的回归函数:

$y{}_j(x)={\displaystyle \sum _{i=1}^l\alpha }{}_{ji}^{*}{\rm K}(x{}_i,x)+b{}_j^{*}j=1,2‚\cdots ,m(12)$

2.2 多输出最小二乘支持向量回归机增量学习算法

现实中数据往往是按照时间递增的。文献[8]假设随时间t推移,每次有一个新增样本加入,建立了一种单输出最小二乘支持向量机增量学习算法。这里将其推广到多输出的情形。

记${\rm H}(t)=\overline{Q}(t)+C{}^{-1}E$,式(11)可以分别写成:

H(t)A(t)+ebT=Y(t) (13)

eTA(t)=O (14)

注意到H(t)是对称正定阵,所以可以令U(t)=H(t)-1,在式(13)两端左乘eTU(t)得到:

eTA(t)+eTU(t)ebT=eTU(t)Y(t) (15)

根据式(14)和式(15)有:

eTU(t)ebT=eTU(t)Y(t) (16)

从而得到:

bT=(eTU(t)e)-1eTU(t)Y(t) (17)

由式(13)和(17)求得:

A(t)=U(t)[Y(t)-e(eTU(t)e)-1eTU(t)Y(t)] (18)

从式(17)和式(18)发现,求出b和A(t)的关键在于得到U(t),即H(t)-1。下面利用矩阵计算的技巧来求得H(t)-1。

对于分块矩阵

${\rm P}=\left(\begin{array}{cc}{\rm P}{}_{11}& {\rm P}{}_{12}\\ {\rm P}{}_{21}& {\rm P}{}_{22}\end{array}\right)$

,如果P、P11均可逆,则有R=P22-P21P${}_{11}^{-1}$P12可逆,且有:

$\begin{array}{l}{\rm P}{}^{-1}=\left(\begin{array}{cc}{\rm P}{}_{11}^{-1}+{\rm P}{}_{11}^{-1}{\rm P}{}_{12}R{}^{-1}{\rm P}{}_{21}{\rm P}{}_{11}^{-1}& -{\rm P}{}_{11}^{-1}{\rm P}{}_{12}R{}^{-1}\\ -R{}^{-1}{\rm P}{}_{21}{\rm P}{}_{11}^{-1}& R{}^{-1}\end{array}\right)\\ =\left(\begin{array}{cc}{\rm P}{}_{11}^{-1}& 0\\ 0& 0\end{array}\right)+\left(\begin{array}{l}{\rm P}{}_{11}^{-1}{\rm P}{}_{12}\\ -E\end{array}\right)R{}^{-1}({\rm P}{}_{21}{\rm P}{}_{11}^{-1},-E)(19)\end{array}$

比较H(t)和H(t+1),可以发现:

${\rm H}(t+1)=\left(\begin{array}{cc}{\rm H}(t)& V(t+1)\\ V(t+1){}^{{\rm T}}& v(t+1)\end{array}\right)$

其中

$\begin{array}{l}{\rm H}(t)=\left(\begin{array}{ccc}\overline{Q}{}_{11}+1/C& \cdots & \overline{Q}{}_{1t}\\ ⋮& \ddots & ⋮\\ \overline{Q}{}_{t1}& \cdots & \overline{Q}{}_{tt}+1/C\end{array}\right)\\ V(t+1)=(\overline{Q}{}_{1,t+1},\cdots ,\overline{Q}{}_{t,t+1}){}^{{\rm T}}v(t+1)=\overline{Q}{}_{t+1,t+1}+1/C\end{array}$

根据式(19)可以得到:

$\begin{array}{l}U(t+1)={\rm H}(t+1){}^{-1}=\left(\begin{array}{cc}U(t)& 0\\ 0& 0\end{array}\right)+\\ \left(\begin{array}{l}U(t)V(t+1)\\ -1\end{array}\right)S{}^{-1}(V(t){}^{{\rm T}}U(t),-1)(20)\end{array}$

其中S=v(t+1)-V(t+1)TU(t)V(t+1)。U(t+1)可以利用U(t)求得,这种递推关系使得式(11)中矩阵的求逆可以通过较小规模的矩阵的逆实现,甚至可以通过U(2)得到,避免了大矩阵的求逆,效率非常高。

综合分析上面的过程,得到多输出最小二乘支持向量机增量学习算法:

算法:

(1) 初始化令t=2;

(2) 计算U(2),取t=3;

(3) 加入新数据(xt,yt),利用式(20)计算U(t);

(4) 令t=t+1,转(3),直到学习完,所有训练样本转(5);

(5) 由式(11)得到b*、A*.构造回归函数。

这种增量学习算法在每次迭代过程中加入一个样本,直到最后一次迭代,才包含了所有训练样本,通过利用前一次迭代的运算结果,降低了离线学习算法的计算复杂性。同时,适合样本的增量式学习。

3 数值实验

为了检验本文增量学习算法的有效性,实验在P4、3.06GHz、512MB内存、WindowsXP、Matlab7.0环境下进行。实验中核函数采用RBF核:

$k(x{}_i,x{}_j)=\exp (-\frac{\parallel x{}_i-x{}_j\parallel {}^2}{2\sigma {}^2})$

测试指标采用均方误差:

$({\rm M}SE)=\sqrt{\frac{1}{{\rm N}}{\displaystyle \sum _{i=1}^{{\rm N}}(}x{}_i-\widehat{x}{}_i){}^2}$

其中xi为实际值,$\widehat{x}$i为预测值,N为测试样本数。

实验中的模拟数据参考文献[9],不带噪声的数据集S={(x,y)∈X×Y⊂R×R3},输入数据x∈(0,10),三维输出数据分别为:

y1=x-1sinx

y2=|x-1|/8+|sin(0.75+0.25x)π|/2+0.5

y3=|x-1|(1+10|sin(x+1)|)/100

S中包含了200个样本,在实验中,分别对输入和输出加入均值为0、标准差为0.03的白噪声。随机选取N个训练样本,剩余的T个作为测试样本,选择参数C=100,σ=1.6。试验结果比较如表1所示。

从表1可以看出,本文的增量学习算法与传统意义上的直接求逆算法相比较,学习速度明显加快,提高了20多倍,而均方误差相同。

图1、图2和图3分别显示的是测试样本数为T=50,T=100,T=150时的不带噪音的测试数据、带有噪音的测试数据、采用直接求逆方法进行预测以及采用本文增量学习算法进行预测得到的结果比较情况。

从图1、图2和图3中可以发现,本文的增量学习算法与直接求逆方法得到的预测效果相近。同时,两种方法的预测结果与不带噪音的测试数据相比,趋势也基本一致。因此,本文的增量学习算法可以有效地处理这种多输出问题。

4 结 论

本文在回归LSSVM模型的基础上,推广得到多输出LSSVM回归机模型,并对多输出LSSVM回归问题进行了推理,给出了它的一种增量学习算法。扩展了LSSVM的应用范围,提高了学习速度。数值实验表明该方法能有效地对多输出问题进行增量学习,为把其应用到实际问题提供了依据。

参考文献

[1]Vapnik VN.The Nature of Statistical Learning[M].Berlin:Springer1995.

[2]Cortes C,Vapnik VN.Support vector networks[J].Machine Learning,1995,20(3):273-297.

[3]Smola J,Sch lkopf B.A tutorial on support vector regression[R].Lon-don:University of London,1998.

[4]Suykens J A K,Vandewalle J.Least Squares Support Vector MachineClassifiers[J].Neural Processing Letters 1999,9:293-300.

[5]张永清,孙德山.多输出支持向量回归算法[J].辽宁师范大学学报(自然科学版),2006,29(3):267-270.

[6]胡蓉.多输出支持向量回归算法[J].华东交通大学学报,2007,24(1):129-132.

[7]胡根生,邓飞其.具有多分段损失函数的多输出支持向量回归[J].控制理论与研究,2007,24(5):711-714.

[8]张浩然,汪晓东.回归最小二乘支持向量机的增量和在线式学习算法[J].计算机学报,2006,29(3):400-406.

基于光滑支持向量机的经济预测模型 第11篇

关键词：经济预测模型；支持向量机；加函数；光滑函数；Newton-Armijo算法

1.引言

支持向量机算法 第12篇

支持向量机在解决小样本分类问题中存在一定技术优势，因而已然应用在图像检索中。为了缩小高层特征与低层特征的语义鸿沟，相关反馈的算法则已应用在图像检索中。涉及的研究有:郭士会提出基于FSVM的相关反馈检索算法[1]，采用语义相关矩阵提高查询准确度;欧阳军林等提出用先验知识的Boosting方法与SVM相结合[2]，有效解决了SVM存在样本数量少、反馈准确率低的问题;郭金旭等提出基于多类SVM相关反馈算法，检索准确性优于传统SVM算法[3];针对标注样本不足，鲁珂提出近邻保留回归算法[4]，解决了过适应问题;符保龙提出基于改进布谷鸟搜索算法的相关算法，较遗传算法、粒子群算法有较高的准确度[5]。

本实验融合了图像的颜色与纹理综合特征，根据检索结果，选择不同数量的正负例图像作为训练样本，以支持向量机学习算法构造分类器，并引入主动学习进行再反馈。实验表明，主动学习可提高检索准确性，能够满足用户的不同需求。

1 特征提取

1.1 颜色特征

颜色矩[6]于1995年由Stricker和Orengo首次提出，是一种简单且有效的图像颜色特征描述方法。图像的颜色分布信息主要集中在低阶矩中，因此，图像的颜色特征可采用颜色直方图的一阶矩、二阶中心矩和三阶中心矩来表示。相对于颜色直方图，该提取方法的优点是不需对颜色空间进行量化，且颜色特征维数降低。式(1)就是颜色矩的三个低阶矩:

1.2 纹理特征

图像的纹理可理解为多个奇异点的连接组成的边界，而小波变换能够有效检测图像的边界和奇异点[7]。因此，可用于提取图像的纹理特征。小波变换是指将信号分解为一系列的子函数，表达为一种子函数累加的形式。小波变换需要有二维小波函数和尺度函数才能应用在图像处理中，二维小波变换往往通过可分离变量的方法由一维小波函数和尺度函数构造。尺度函数和小波函数也可以理解为一个伸缩和平移的基函数，该基函数沿着图像的水平方向和垂直方向滤波和采样，得到一个含带四子图的系数矩阵，对其中的逼近子图不断进行滤波与采样，可构成多尺度的小波分解。采用小波变换表示图像纹理特征是由每个小波分解层上能量的分布信息来予以表示和呈现，即均值与标准方差。使用均值与标准方差的分量构成纹理特征向量实现纹理特征的检索。目前，Haar小波变换，Daubechies小波变换方法等易受到图像尺寸的限制，Dwong等人[8]提出的一种进行多分辨率分析的W变换克服了尺寸限制，可进行整幅图像的检索，实验表明该方法精确、有效。为了获得更好的检索效果，往往采用小波变换结合其他技术的方法。为了实现简捷品质，本实验采用MATLAB软件中自带了小波函数。

2 相关算法

2.1 SVM

支持向量机是建立在统计学习理论上的分类算法，较神经网络分类器算法，其在求解最优值时不易陷入局部最优解。通过选择合适的惩罚系数和核函数，可获得更优分类面。因此，在解决小样本问题中存在独有优势。在训练小样本情况下，不需要特定问题的先验知识，就可以良好有效地控制学习机器的推广能力，因此在图像检索中可以有效提高检索准确性[9]。SVM在解决分类问题上往往都是低维空间不可分，因此，需要引入核函数在高维空间实现度量可分。核函数在一定程度上却会影响检索准确性[10,11]。工作中多采用LIBSVM工具[12]，常用的核函数有线性核、多项式核和RBF核，一般选择RBF核即径向基核函数。

2.2 SVM训练步骤

SVM训练步骤详细如下:

(1)采用多特征融合的低层特征对待检索图像进行相似度测量;

(2)对检索结果进行正例图像和负例图像的标记，得到相关图像集和不相关图像集;

(3)构造样本训练集(xi,yi)，其中，xi代表样本图像的特性向量，如式(2)所示;

(4)对训练样本进行学习并构造分类器如式(3)所示:

(5)对于正类样本的图像，分别计算每幅图像的子图到分类面的距离，取其中最大的距离作为该图像到分类面的距离。正类图像的特征向量x到分类面的距离可表示为d(x)，即如式(4)所示:

(6)计算待检索图像与剩余图像的距离，按照距离大小排序，最终返回检索结果。

2.3 主动学习

主动学习的思想就是学习机在已知的测试样本集中自动选择学习样本，具体就是在反馈过程中由算法自动选择供用户标记的样本，通过用户的检索结果判断用户的检索意图，为用户提供一些歧义性较大的反馈样本[13]。在这些样本中，标记出感兴趣与不感兴趣的样本，经过如此反复操作，歧义性大的图像就排在后面，在反馈给用户的结果中与待检索图像的相关图像就越多，更加符合了用户的查询需求。相似度测量方法较多，常用的有欧式距离等，文献[14,15]采用了EMD距离，文献[16]在此基础上提出了相应的改进，使检索率获得了一定的提高。实验中采用EMD-Ck NN距离测量方法。

3 实验分析

本实验采用微软的Corel图像库，包含20类的2 000张图片，每类100张。实验分别选取标记正负例样本图像数量为5、10、20、30、40、50、60、70。为了测试方便，正负例图像完全选择一样数量。同时为了测试主动学习对检索结果的影响，采取了同样的测试方法。抽取同一幅待检索图像，随机测试8组实验，对比效果如表1所示。

通过表1可知，选择反馈图像的数量越多，检索准确率并不一定随之增加。为了获得更为科学的对比结果，这里采用测试100组求均值的方法，对比结果如图1所示。

从图1结果可以看出，在相关反馈中加入主动学习可以提高检索准确性。通过引入主动学习，在每次检索结果中显示歧义较大的图像范围内，选择感兴趣与不感兴趣的图像作为反馈的样本图像集，如此即使得样本图像集在进行支持向量机学习中，会获得最优分类面，从而可将不同类图像尽可能最大程度地实现分离。研究将获得更加符合用户意愿的检索结果，因此解决了在大量图像数据库中快速准确地检索到用户所需图像的重点研究难题，满足用户的不同需求。研究可知，在实际的应用中，可通过加入主动学习来提高检索准确性。

4 结束语