基于RBF核的SVM学习算法的优化计算

基于汉科技大学计算机科学与技术学院，武汉430081)摘 要在文对基于，y)的选定做了深入研究。分别探讨了网格搜索法和双线性搜索法以对它们进行了改进。通过结合双线性搜索法和网格搜索法。提出了一种双线性网格搜索法。实验表明，双线性网格搜索法能有效地结合双线性搜索法训练量小和网格搜索法学习精度高的优点提高学习精度和学习性能。关键词 支持向量机331(2006)29019003 文献标识码A 中图分类号VM 3008 1)VM，is no a to n to VM BF a of to BF 言支持向量机(VM)结构风险最小化原则为理论基础的一种新的机器学习方法。统计学习理论对有限样本情况下模式识别中的一些根本性问题进行了系统的理论研究，很大程度上解决了模型选择与过学习问题、非线性和维数灾难问题、局部极小点等问题。支持向量机在手写字符识别、网页或文本自动分类、说话人识别、人脸检测、计算机入侵检测、基因分类、函数回归、估计、函数逼近、时间序列预测及数据压缩、文本过滤、数据挖掘、非线性系统控制等问题中，都有非常成功的应用121。但是，没有形成一个统一的模式。验对比、大范围的搜寻或者利用交叉验证功能进行寻优。本文针对此现状，分析了现有的模型选择方法，并对其中的网格搜索法和双线性搜索法进行了改进，改进后的方法减少了且具有比网格搜索法更高的学习精度。本文第二章简单地介绍了支持向量机的原理和支持向量机解决实际问题的基本步骤：第三章介绍了网格搜索和双线性搜索两种方法进行参数选择提出了对两者的改进方法：第四章详细介绍了本文提出的双线性网格搜索法。第五章为实验，通过实验对六章为结论。2支持向量机学习方法21支持向量机简介二维两类线性可分情况下，有很多可能的线性分类器可以把这组数据分割开，但是只有一个使两类的分类间隔个线性分类器就是最优分类超平面，与其它分类器相比，具有更好的泛化性。若样本集x。，i=1，8(一1，+1)是线性可分的。则存在分类超平面b=O菇样本集，b+l b一1舻一1在空间尺4中样本搿=(筇1，一，舶)到分类超平面的距离d=x+|W 0，其中扩埘。当存在茗使得加；+6=1，则超平面的分类间隔m 】l W 1|。使分类间隔m 找最优分类超平面的问题将转化为求如下一个二次规划问题：)=(矿戈。舶)1，i=1，2，式如下：f )=嘶一昙y(1)i=1 z 满足约束条件：0nf，i=1，=ol=据育部留学回国人员科研启动基金资助；湖北省教育厅重点项目(编号：2004者简介：李琳(1981一)，女，硕士研究生，主要研究方向：机器学习和数据挖掘；张晓龙(1963一)，男，教授，研究生导师，主要研究方向：机器学习、数据挖掘和生物信息学。190 200629计算机工程与应用万方数据个优化的解必须满足：啦(“矿省舶卜1)=0，i=1，为O少部分不为0的a对应的样本就是支持向量。最后得到分类判别函数为：1 g(x)=。，省)+6) (2)支持向量以通过两类中任意一对支持向量取中值求得。根据上述易知，对于空间R。中任意样本髫=(算l-，当If(x)因为以处理当类标签(特征之间的关系是非线性时的样例。，y)(其中某些参数，1。另外，为参数的个数直接影响到模型选择的复杂性。非常重要的一点是01)或者O。+rl，跨度非常大。而且，必须注意的是如，没有两个向量的内积)163。(4)用交叉验证找到最好的参数使用考虑两个参数为参数的选择并没有一定的先验知识，必须做某种类型的模型选择(参数搜索)。目的是确定好的(C，y)使得分类器能正确地预测未知数据(即测试集数据)，有较高的学习精度。值得注意的是得到高的训练正确率(即是分类器预测类标签已知的训练数据的正确率)不能保证在测试集上具有高的预测精度。因此，通常采用交叉验证方法提高预测精度。将训练集合分成中一个子集用于测试。其它|一1个子集用于对分类器进行训练。这样，整个训练集中的每一个子集被预测一次，交叉验证的正确率是可以防止过拟合的问题。本文使用了网格搜索和双线性搜索两种方法进行参数(C，y)的选择，通过综合两种方法的优点，对原有的方法进行了改进。(5)用第(4)步得出的适合于此分类问题的最好参数6)在数据集上进行测试得出该分类问题的学习精度。3 ，y)，有多种方法可以选择171。本文主要应用网格搜索法和双线性搜索两种方法来取得最佳(C，y)。31双线性搜索法双线性搜索法求解最优参数是利用不同的(C，y)取值对应的不同献4】中提到，参数空间可分为欠训练过训练区和“好区”。以作为参数空间的坐标，经大量实验证明，学习精度最高的参数组合(C，y)将集中出现在“好区”中的直线附近。由此，双线性搜索法采用如下步骤81：(1)对线性得以之为参数的线性之为C。(2)对定C，对满足y=，y)，训练据对其学习精度的估算，得到最优参数。32网格搜索法网格搜索法是将值，对M个(C，y)的组合，分别训练不同的估计其学习精度，从而在，y)的组合中得到学习精度最高的一个组合作为最优参数。本文取M=N=27，4，2“，216】，7的取值范围为【2。5，2。14，210 2“】，共729个(C，7)的组合。由此可知，完成一个完全的网格搜索是非常费时的，作为网格搜索法的一种改进我们可以设定：首先用一个步长为22的(C，y)组合，得到学习精度最高的的值。然后在这两个值旁的一定范围内进行一次更细致的网格搜索。为详细说明此方法，我们将其应用于数据库文对于所有学习精度的估计，均采用k=5)。在对该数据集进行归一化后先用网格搜索法对数据集进行交叉验证求得最高的学习精度为99243 9，最好的参数组合为(23，22)。对于改进的网格搜索法，先用一个步长为22的(C，y)组合，求得最高的学习精度为986767，最好的参数为(24，2-)(见图1)。然后在这个最好参数旁正负22的范围内，以磐25为步长进行一次更精细的网格搜索。如第一步求得最好的参数为(24，21)，图2即第二步在C22 26】，【2，23的范围内以2”为步长求得最高的学习精度为99432 9，最好的参数为(24，2蟛)。从图可以看出，改进的网格搜索法在减少了训练量的情况下，可以达到比网格搜索法更高的学习精度。计算机工程与应用200629 191万方数据表1 不同方法得到的学习精度，括号中列出了对应的参数(C，)圈l 改进的网格搜索法第一步(4，26 y=2“，2“，211】lg(0 990，985980一20 9751510|g(5O0一1)图2改进的网格搜索法第二步(C=22，2”，26 T=2一，24”，23)4双线性网格搜索法41 双线性搜索法与网格搜索法的比较与双线性搜索法相比网格搜索法的优点是可以并行处理每个为它们是相互独立的。而双线性搜索法需要先得到线性能开始计算量上(基于网格搜索法为O(双线性搜索法仅为O(N)。但由于双线性搜索法对线性C、05C、2练相应参数的为改进的双线性搜索法圈。42双线性网格搜索法由以上的比较可知：网格搜索法具有较高的学习精度但计算量较大，费时较多；双线性搜索法计算量较小，费时少，但与网格搜索法相比，学习精度略低。为了在计算量小、费时少的基础上，得到较高的学习精度，现将以上两种方法的优点结合起来，称为双线性网格搜索法。具体步骤如下：(1)对线性得以之为参数的线性之为C。由于双线性搜索法对线性C、05C、2练相应参数的2)对别将上一步中得到的C、05001629计算机工程与应用2满足，y)，训练据对其学习精度的估算，得到最优参数。(3)在上一步中得到的最优参数(C，y)旁正负22的范围内，以202见3。2节中改进的网格搜索法第二步)，此时得到的就是双线性网格搜索法的学习精度。由以上步骤可见。该方法是将双线性搜索法和网格搜索法结合起来。首先用改进的双线性搜索法得到最优参数(C，y)，然后用改进的网格搜索法第2步进行网格搜索(即在这个最好参数旁以20这样就得到了双线性网格搜索法的学习精度。5 实验该文的实验样本采用别用网格搜索法、双线性搜索法、改进的双线性搜索法和双线性网格搜索法进行了测试。测试结果如表1、表2所示。袭2不同方法导致的训练量(训练练量 网格搜索法双线性搜索法改进的双线性搜索法双线性网格搜索法表1中列出了4种不同方法的学习精度。其中双线性网格搜索法与网格搜索法相比。数据集据集线性网格搜索法与改进的双线性搜索法相比，6个数据集的学习精度前者均高于后者。而从表2列出的这4种不同方法的训练量可以看出双线性网格搜索法的训练量较网格搜索法有了较大的减少，因此总的来说它的性能是最好的。从以上实验可以看出网格搜索法训练量最大，有较高的学习精度。双线性搜索法训练量最小，与其它方法相比，学习精度略低：而双线性网格搜索法综合了双线性搜索法和网格搜索法的优点，训练量介于两者之问，而学习精度几乎全部达到网格搜索法的高度。因此，对训练样例少的数据集，可以采用网格搜索法或者双线性网格搜索法，得到高的学习精度；对训练样例庞大的数据集。网格搜索法常常非常耗时，此时可采用双线性网格搜索法在相对较少的时间内获得相似的学习精度。6结论本文提出以非线性函数为核的学习情形中双线性网格搜索法可以有效地改进学习性能和提高学习精度。对转204页)|I|三505050鳐鸲卯卯贴万方数据(4)每一个任务树和服务实例都注册了一个监听器(采用异步通知机制(现任务的协同工作。服务实例运行期间可以发送数据给客户端任务树的监控器，从而指导任务树结构的动态更新以执行新的任务，也可以在客户端将接收到的数据进行处理，再发给指定子服务节点集，实现服务节点集之间的协同工作。任务监控器还可以发送监控命令(例如通过各服务节点查询服务运行状态。(5)全局信息中心(务器上的全局资源监控器对所有相关注册资源进行监控当发现已分配资源不可用、或无法保证服务质量(，采用选)。(6)所有的服务及系统控制管理器和服务提供者组件可以通过全局信息中心服务器的版本控制服务(行在线升级。4系统基本流程根据上述系统逻辑层次结构和基本框架，本系统的基本流程如图3所示。(1)系统将前端设备收集到的各种数据或经过整理的数据进行预处理。主要包括文件格式识别、不同编码格式的解码、码制归一和格式清洗、多语种自动识别和自动分词等处理，如果是加密信息还需对其进行解密。(2)使用分布式数据库或数据仓库技术对预处理后的数据进行存储并建立索引。(3)对数据库中的数据进行分类和聚类处理，以利快速检索和数据挖掘处理。(4)利用图2所示基本框架对反洗钱线索进行数据检索和关联挖掘。(5)对检索和挖掘的结果进行评价，并使用用户可识别的知识表达方式将结果返回给用户。前端收集的文件或经整理的数据数据预处理经锯密、码制归一后的数据数据存储与建立索据分类与聚类、数据检索与挖掘时将使用数据库，在进行数据分类和聚类、数据检索与关联挖掘、结构评价与知识表达处理时将使用专家系统和知识库。(收稿日期：2006年4月)参考文献1李瑞轩，卢正鼎多数据库系统原理与技术【M】北京：电子工业出版社，20042“u u u 001；5(4)3H G W H in I 9989984陈云开电汇监控：反洗钱利器金融电子化，2004；(6)：58595李东荣，冯菊平，陈云开等澳大利亚反洗钱与信息技术应用【J中国外汇管理，2004；(8)：24255陈云开，罗强】金融电子化，2004；(8)：7476(上接186页)4A 997：4275，a in 000：33446 HA 005；(173)：227达时间序列数据挖掘与应用M浙江：浙江大学出版社，20048 R，in 1of an994：4194299a 994(上接192页)最优参数(C，7)的选定中，比较了网格搜索法、双线性搜索法以及双线性阑格搜索法。实验证明双线性网格搜索法将双线性搜索法训练量小和网格搜索法学习精度高的优点很好地集于一身，可以改进学习性能、提高学习精度。我们将来的：进一步验证它的实用性。(收稿日期：2005年12月)参考文献1V N 9952张晓龙，李琳支持向量机及其应用研究【J】计算机应用研究200522(增刊)：912204 200629计算机工程与应用3 Sto i 9974 S， Ja003；15：166716895 T， JA VM MO0036，995；20：27329370 et 002；46：1311598王鹏，朱小燕基于计算机工程与应用，2003；39(24)：72739重墅戛鲤赢万方数据基于李琳， 张晓龙， 武汉科技大学计算机科学与技术学院,武汉,430081刊名： 计算机工程与应用英文刊名： (期)： 2006,42(29)被引用次数： 17次参考文献(9条) 持向量机及其应用研究 2005( S to J 文期刊 J A VM 文期刊 于刊论文003(24)条)1. 于刊论文9(24)2. 种快速的刊论文6(15)3. 刊论文7(11)4. 于刊论文然科学版）2009,26(3)引证文献(17条)用两级分