支持向量机与多核算法

所需积分/C币:37 2018-10-14 11:14:36 861KB PDF

学习多核与支持向量机,在数据处理,数据融合,故障诊断方面
第6期 李仁兵等:支持向量机的进化多核设计 795 32个体的算法树表示( Expression tree of the in-33初始种群产生与适应度计算( Populat dividual) tilization and fitness computation 为说明EMK的算法树表示,首先介绍核函数构 初始种群采用生长法( grow method,GM)产生, 造方法 产生过程中必须遵循以下原则 核函数的构造主要有两种途径:第1种方法是根 1)根节点必须从函数集FS中选择元素; 据具体问题,直接构造满足核函数定义的新函数.这 2)某一节点元素来自函数集FS,则其子节点既 种方法比较难,一般很少使用;第2种方法是选择 些比较常用的单核函数进行合理组合,从而构成新可以从函数集FS中选取,也可以从终端集TS中选 的核函数,并有如下定理4 3)叶节点必须从终端集TS中选择元素; 定理1设K1和K2是X×X上的核,X∈R” 设常数a≥0,则下面的函数均是核: 4)每棵算法树至少包含一个单核函数元素; 1)K(x;,m;)=K1(x,m)+K2(x;,m) 5)当算法树达到设定的最大深度,初始化过程 2)K(x;,x)=aK1(x;,x) 结束; 3)K(x;,m)=K1(x2,x)K2(x1,c); 6)设定的算法树最大深度必须足够大,以保证 4)K(ai, i )=exp(K, (i, a)) 算法树的性能 个体适应度是驱使GP算法进化的源动力.由于 定理的证明可参考文献4此处略去由定理支持向量机分类精度很好地描述了核函数性能,本 1可知,核函数对{+,×,exp}3种运算封闭 基于GP的EMK设计中,个体是一棵对进化多文中采用分类精度作为相应个体的适应度 数学表达式进行编码的算法树,由根节点、中间34遗传操作( genetic operation) 结点和叶节点构成.个体的生成就是在给定的函 遗传程序设计中的遗传操作与遗传算法中的遗 数集( function set,FS)和终端集 (terminal set,Ts中随传操作相同,主要包括复制、交叉和变异,文中不再 机选择元素,逐层生成算法树.本文中,函数集取赘述 FS={+,x,exp},终端集取 4算法描述与复杂度分析( Algorithm de TS=Kpol, KRBF, Ksig, ci, i=1, 2, ..,n, scription and complexity analysis) 其中:Kpd,KBp和K是带有参数的单核函数,41算法描述( Algorithm description) a;是正常数.在生成算法树过程中,一般将根节点的 本算法中,以是否达到最大进化代数或同一代中 选择限制在函数集FS中,以便生成层次化的复杂结个体适应度的最大差值是否小于设定值作为终止准 构.如果从函数集FS中选出的函数f有arg()个自则,并以进化过程中保存的最佳个体作为运行结果 变量,则该节点有arg(f)个分支.对于每个分支,需具体算法描述如下: 要从终端集TS和函数集FS的并集C= FSU TS中 随机选出一个元素作为该分支的尾节点.如果选出 1)设定核参数取值范围和正常数a取值,建立 的元素是一个函数,则重复执行上述过程;如果选出终端集TS: 的是终端集中的元素,或算法树深度达到了设定的 2)设定控制参数,包括种群规模M、最大进 最大深度值,则该分支上的树就终止生长 化代数G、算法树最大深度D、复制概率P、交叉概 树形结构增强了个体的非线性表达能力和对层率P、变异概率P和选代停止条件等; 次化问题的描述能力.图2描述了一个个体为(K1+ 3)按生长法产生初始个体集合; a1K2)exp(K3)的算法树模型,定理1保证了生成的 4)设置l=0 个体是一个核函数 5)利用SVM和训练数据集、测试数据集计算 初始个体的分类精度,并作为个体的适应度f,其 中=1,2,…,M,记携带适应度的初始个体集合 为初始种群EMKs; ③⑧ 色⑤⊙ 6)若maxf0-f<ε或达到最大进化代 数G,则算法停止;否则对种群EMKs进行遗传操 作,产生新的个体集合,同时置l=l+1,并返回5) 42复杂度分析 Complexity analysis) 进化多核算法计算时间来源于两部分:遗传操 图2个体的算法树结构 作和SM训练.遗传操作部分以遗传算法为核心, Fig 2 Tree-structure of individual 其时间复杂度为O(Tm2),其中:T为进化代数,m为 796 控制理论与应用 第28卷 种群规模.在种群规模为M、最大进化代数为G的其建议取值范围为[0,1.本文在,1区间内随机 情况下,遗传操作部分最大时间复杂度为O(GM2).选取10个值,与单核函数组成终端集TS.控制参数 SVM训练部分用于计算每个个体对应的SVM分类用来控制算法的运行过程,EMK算法中主要控制参 精度,并作为适应度,驱动遗传操作进行迭代.因此,数有种群规模M、最大进化代数G、算法树最大深 每一个个体的适应度计算都是一个标准的sVM训度D、复制概率P、交叉概率P和变异概率Pa,具体 练过程,其实质是求解二次规划问题,时间复杂度设置如表4所示 为O(m3),其中n是训练样本数.在种群规模为M,最 大进化代数为G的情况下,SVM训练部分的最大时 表3核参数设定 间复杂度为O(MGn3).因此,进化多核算法的最 Table 3 Settings of kernel parameters 大时间复杂度为O(GM2)+O(MGm3).由于一般 核函数 核参数 情况下M《n,所以进化多核算法的实际复杂度 Pol c=1,d={1,2,……,10} 为O(MGm3). KRBE =n·103,7={1,2,…,10} 5数据实验( Numerical experiments) T={-5,-4,…,-1} A,U 为验证进化多核算法的有效性和优越性,本部 K=0,U={0.1,1,10} 分将所提算法与单核函数以及部分有代表性的多 表4控制参数设定 核函数进行对比实验.实验中单核函数选择鲁棒性 Table 4 Settings of control parameters 较强的高斯径向基核函数,多核算法选择SILP78和 SimpleMKL2实验数据选用UC数据库中的6组 参数名称参数设定值 二分类数据集 ionosphere, Breast-cancer,Ala,Mush 种群规模 M=100 rooms,Pima, Liver-disorders'η,数据特征描述见表2 最大进化代数G=50 所有实验均在酷睿双核30G,2G内存的微机上进 算法树最大深度D= 行,并采用 MATLAB R2007a编程实现 复制概率 P=0.1 交叉概率 =0.9 表2UCI数据集特征描述 变异概率 Pn=0.01 Table 2 Feature description of UCi datasets 本文提出的EMK算法采用 MATLAB编程实现, 数据集#样本群属性#类别 文献[8提供了SILP算法的源代码下载地址,文献 ionosphere 351 1提供了 SimpleMKL算法的源代码下载地址,两 Breast-cancer 683 10 者均采用 MATLAB编程实现 Ala 1605 123 为增加可比性,所有算法中采用相同的停机准 Mushrooms 8124112 则,即对偶间隙小于001或者迭代次数超过1000时, Pima 768 8 222222 Liver-disorders 345 算法停止 针对每一个数据集,算法运行50次,每次从数据 为了更好地分析实验结果,将实验分为两组:第集中随机选取70%作为训练样本,30%作为测试样 1组实验中正则化参数C固定.固定正则化参数C本,记录平均实验结果.实验之前,已对所有样本进 虽然没有考虑模型选择问题,但可以更好地对比分行归一化处理 析不同算法的性能;第2组则不固定正则化参数C, 表5记录了上述算法的实验结果.其中:M表示 通过寻优准则寻找最佳的C,并分析不同算法在寻训练样本数,N表示单核函数个数 优过程中的性能差异 51固定正则化参数C( Fixed regularization pa 表5UCI数据集实验结果 Table 5 Experimental results on uci datasets rameter C) 固定正则化参数C=100,并按表3对核参数进 ionosphere M= 246, N= 210 行设定 算法 RBF SILP SimpleMKL EMK 由核参数的设定可知,实验中用到的单核函 测试精度%898±23922士1.8924±1.7941±1.5 数KPa有10个,Kn有50个,K有150个,总共210 训练时间/s47±19408±91114±3579±28 个单核函数.此外,EMK算法中还有TS集非负常 单核函数个数1±018±3.221±3625±42 数o和控制参数需要设定。由文献[5,9可知,终端 迭代的次数21±6382±44104±3362±20 集TS中非负常数a代表了单核函数的相对权值,且 (转下页) 第6期 李仁兵等:支持向量机的进化多核设计 797 (接上页) 从分类精度来看,RBF单核算法的分类精度最 Breast-cancer M= 478N=210 低,SⅡP和 SimpleMKI基本相同,EMK算法的分类 算法 精度最高.这一点充分说明了多核函数能够更好地 RBF SILP SimpleMKL EMK 描述数据特征尤其是EMK函数由干其且有较强 测试精度90.11.1926±1492.5±1.5951408的非线性表达能力而大大提高了算法的分类精度 训练时间/s35±11192±3586±2253±19 这一点也可以从基于不同核函数算法中用到的单核 单核函数个数1017±1.618±1226±12 函数个数进行分析,由表5可以看出, SimpleMKL选 迭代的次数18±7104±2233±1621±17 择的单核函数略多于SILP,而EMK选择的单核函数 AlaM=1124,N=210 最少比 SimpleMKL多出15%以上( Mushrooms),最多 算法 RBF SILP SimpleMKL EMK 的则达到了44%( Breast-cancer).由前文分析可知,不 同核函数对应不同映射函数和特征空间,因此,单核 测试精度/%82.1±3.9843±1.1843±1.287.5±09 函数选择越多,组合的非线性越强,算法对实际问题 训练时间/s70±12547±49213±33111±22 的描述能力也就越强.这也是EMK算法分类精度高 单核函数个数1021±2.125±2829±27 于其他多核算法的原因 迭代的次数20±2179±2968±1838±15 从训练时间来看,RBF单核算法的训练时间最 Mushrooms M=5687N= 210 少,3种多核算法中以EMK训练速度最快,SIP最慢 算法 RBF SILP SimpleMKL EMK 这一点可以从迭代次数来分析,由表5可以看出,单 核函数RBF迭代次数最少,而多核算法中SLP迭代 测试精度%8931.192.61.092.5±14951±1.6 训练时间/s533+882011±1061861±118844±96 次数最多, SimpleMKL次之,EMK迭代次数最少.由 单核函数个数1±032±4.1393.645±3.4 于上述算法的迭代过程即是支持向量机训练过程, 迭代的次数14±11221±26992958±18 因此,迭代次数的多少直接反映了训练速度的大小 52寻优正则化参数C( Searching optimal regu Pima A=538.N=210 larization parameter C) 算法 RBFSⅢ P SimpleMKL EMK 实际应用中,正则化参数C的最优值并不知道 测试精度闯746±1.8772±2.27.2±2481.1±29只能通过多次求解支持向量机,在一定范围内搜索 训练时间/38±9205±3299±1966±14 其最优值,而交叉验证方法是其常用的判断准则 单核函数个数1+014±1.615±2.121+33 本节实验用到的数据与51节相同,目的是通 选代的次数18±5113±1938±1125±8 过实验对比分析不同核函数在正则化参数C的 Liver-disorders M=242,N= 210 寻优过程中所耗费的时间差异.实验中采用5-折 交叉验证方法作为判断准则,在区间001,1000内 算法 RBF SILP SimpleMKL EMK 以10的幂次级均匀抽样获得C值.表6记录了不同算 测试精度%60.11965926659±23668±25法在10次C寻优过程中耗费的平均时间 训练时间/s14.8±8.256.6±10.526.7±14.318.4±14.1 由表6结果可以看出,多核算法中,EMK的寻优 单核函数个数140166±1.317.8±1.2249±1.5 效率最高, SimpleMKL次之,SLP最差.同时,多核算 迭代的次数19±6106±22441931±15 法的寻优时间均高于单核函数RBF 表6寻优正则化参数耗时对比 Table 6 Comparison of consuming time in searching optimal regularization coefficient 数据集 RBF SILP SimpleMKL EMK ionosphere242±1067980±19121189±762866±641 Breast- cancer I8l±973120±867 967±536 802±443 Ala 396±1458641±14212017±12111113±988 Mushrooms2663±91214771±56629982±21105321±1449 Pima 210815906士1163 986±201 667±186 Liver-disorders 62±8 824±119 132±31 89士22 53结果讨论( Result and discussion) 有更高的分类精度和更快的训练速度,这一结论 显然,进化多核算法EMK比现有多核算法具可以从实验结果得出.但还应注意到,与单核算 798 控制理论与应用 第28卷 法RBF相比,多核算法在提高分类精度的同时,却81 SONNENBURG S. RATSCH C. SCHAFER O.eta. Large scale 降低了训练效率 multiple kernel learning[]. Journal of Machine Learning Research 2006,707):1531-1565 限于篇幅,文中没有给出进化多核算法EMK在 191 DIOSAN L, OLTEAN M, ROGOZAN A, et al. Improving SVM Per- 大规模数据集上的性能讨论,以及随着单核函数 formance Using a Linear Combination of Kernels[MI. Heidelberg 集合数量的变化,EMK性能变化情况.有兴趣的读 Springer, 2007. 者可与作者进一步交流 [101 CRAMMER K, KESHET J, SINGER Y, Kernel design using boost g[M] ADvances in Neural Infonnation Processing Systems. Cam- 结论( Conclusion) bridge, MA: MIT Press. 2003 本文借助GP思想,构造了进化多核函数.算法 [l] BENNETT K P, MOMMA M, EMBRECHTS M J. MARK: a boost- 中采用树形结构对多核函数的数学表达式进行编 ing algorithm for heterogeneous kernel models[C] /Proceedings of the &th ACM SIGKDD International Conference on Knowledge Dis 码,丰富了多核函数的层次化结构,提高了其非线 covery and Data Mining. Edmonton: ACM Press, 2002: 24-31 性表达能力.此外,由于GP算法是在搜索空间中t2] RAKOTOMAMONJYA. BACH F, CANU S et al. Simple MKI 进行全局搜索,因而可以在没有具体问题先验知 Journal of Machine Learning Research, 2008, 9(11): 2491-2521 识的前提下得到最优解.对比实验结果表明:进化 [131 CRISTIANINI N, SHAWE-TAYLOR J. An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods[MI 多核算法EMK比现有多核算法具有更高的泛化能 Cambridge: Cambridge University Press, 2000 力和收敛速度 14]邓乃扬,田英杰.数据挖掘中的新方法:支持向量机M]北京:科 学出版社,2006. 下一步将研究如何根据具体问题确定最佳的 (DENG Naiyang, TIAN Yingjie, New Approach for Data Mining: 算法树最大深度,并将EMK方法应用到回归问题 Support Vector Machine[M]. Beijing: Science Press, 2006) 和多分类问题中 [15] KOZA JR Genetic Programming: on the Programming of Comput. ers by Means of Natural Selection[M). Cambridge: MIT Press, 1992. 参考文献( References 16王四春,GP技术及应用研究[D长沙:中南大学,2006 (WANG Sichun. Research on GP technologies and applications [I] VAPNIK V. The Nature of Statistical Learning Theor[M]. New Changsha: Central South University, 2006) York: Springer-Verlag, 1995 [17] ASUNCION A, NEWMAN D J. UCI Machine Learning Repos [2] CHAPELLE O, VAPNIK V, BOUSQUET O, et al. Choosing multiple itory[db/ol].http://www.ics.uci.edw/wmlearn/mlrepository.html parameters for support vector machines[JI Machine Learning, 2002 Irvine, CA: University of California, 2007 461/3)131-159 [3] ONG CS, SMOLA AJ, WILLIAMSON R C. Hyperkernels[M]/Ad- nces in Neural Infornation Processing Systems, Cambridge, MA作者简介 MIT Press,2003:478-485 李仁兵(1982),男,博士研究生,主要研究方向为模式识 [4] HU M Q, CHEN Y Q, KwOK Y Building sparse multiple-kermel SVM classifiers[JI. IEEE Transactions on Neural Network,2009,别、机器学习算法及导弹故障诊断, E-mail: pioneerbullc@ sina con 205):827-839 李艾华(1966—).男,教授,博士生导师,主要研究方向为智能 15 LANCKRIET G, CRISTIANINI N, BARTLETT P, et al. Learning the kernel matrix with semidefinite programming[J]. Journal of Ma- 控制、信号处理及故障诊断,Emai:plamissile@Sina.com chine learning research, 2004. 5(1): 27-72 白向峰(1981-),男,博士研究生,主要研究方向为目标检測 [6] BACH F R, LANCKRIET G R G, JORDAN M L Multiple kermel 与跟踪, E-mail:bxf2024@163com learning, conic duality and the smo algorithmIc Proceedings of the 21st International Conference on Machine Learning. Banff: ACM 蔡艳平(1982—),男,博士研究生,主要研究方向为故障诊断 Press.2004:6-13 与信号处理Emal:287468105@qcom: [7] SONNENBURG S, RATSCH G, SCHAFER C. A general and effi- cient multiple kernel learming algorithm[J]. Advances in Neural in 王德生(1984),男,讲师,主要研究方向为导弹发动机故障 formation Processing Systems, 2006, 18(1): 1273-1280 检测与诊断,E-mal:287290889@qgc0n

...展开详情

评论 下载该资源后可以进行评论 1

qq_24531883 写的是算法 其实就是一片文章 没有代码。。
2019-02-20
回复
上传资源赚积分,得勋章
最新资源