支持向量机并行训练算法与基于遗传算法的参数优化研究
|
摘要
随着支持向量机的广泛应用,其在大数据集上训练效率问题以及通过参数优化提高其性能的问题受到人们的广泛关注,本文就这两个问题做了以下研究：
首先提出了一种基于多核并行的支持向量机并行训练算法用来解决其在大数据集上的训练效率问题。该并行训练算法以LIBSVM为基础,对其中的核矩阵计算、更新梯度、工作集选择模块均进行了并行化处理,并使用OpenMP、Intel线程构建模块、Intel并行函数库等多核并行工具和技术对其进行实现。
其次提出了一种基于嵌套式遗传算法的SVM参数优化方法。该方法首先针对核函数参数优化构建遗传算法,在其适用度函数中针对惩罚因子优化问题构建遗传算法,用惩罚因子遗传算法搜索到的解的训练结果作为其适应度值。实验表明,该方法比普通的基于遗传算法的参数优化方法有着更好优化性能。
最后通过以上两种方法有效的提高了支持向量机的效率和性能,并将其应用在人脸性别识别系统中,获得了较好的效果。
With the extensive application of support vector machines, the efficiency of its training with large-data and improve its performance through the optimization problems are brought to wide attention.In this paper, two problems do the following research:
Frist of all, this paper present a multi-core parallel based support vector machine parallel training algorithm used to improve the efficiency of training with large-data. The parallel training algorithm based on LIBSVM, on which the nuclear matrix calculation, update gradient, worked-sample selection modules for parallel processing. Using OpenMP、Intel Threading Building Blocks、Intel multi-core parallel libraries and other tools and techniques to achieve them.
Secondly, this paper was proposed based on genetic algorithm nested parameters optimization method of SVM. In this method, Kernel Parameter Optimization for the construction of genetic algorithm, in its application to function in the penalty factor for the construction of genetic algorithm optimization, genetic algorithms using penalty factor the optimal solution to the training result as the fitness value. Experiments show that this method is better than ordinary based on the genetic algorithm is optimized parameters optimization method has better performance.
Finally, through the above two methods improves the support vector machine efficiency and performance, and its application in the face of gender recognition system, good results were obtained.
首先提出了一种基于多核并行的支持向量机并行训练算法用来解决其在大数据集上的训练效率问题。该并行训练算法以LIBSVM为基础,对其中的核矩阵计算、更新梯度、工作集选择模块均进行了并行化处理,并使用OpenMP、Intel线程构建模块、Intel并行函数库等多核并行工具和技术对其进行实现。
其次提出了一种基于嵌套式遗传算法的SVM参数优化方法。该方法首先针对核函数参数优化构建遗传算法,在其适用度函数中针对惩罚因子优化问题构建遗传算法,用惩罚因子遗传算法搜索到的解的训练结果作为其适应度值。实验表明,该方法比普通的基于遗传算法的参数优化方法有着更好优化性能。
最后通过以上两种方法有效的提高了支持向量机的效率和性能,并将其应用在人脸性别识别系统中,获得了较好的效果。
With the extensive application of support vector machines, the efficiency of its training with large-data and improve its performance through the optimization problems are brought to wide attention.In this paper, two problems do the following research:
Frist of all, this paper present a multi-core parallel based support vector machine parallel training algorithm used to improve the efficiency of training with large-data. The parallel training algorithm based on LIBSVM, on which the nuclear matrix calculation, update gradient, worked-sample selection modules for parallel processing. Using OpenMP、Intel Threading Building Blocks、Intel multi-core parallel libraries and other tools and techniques to achieve them.
Secondly, this paper was proposed based on genetic algorithm nested parameters optimization method of SVM. In this method, Kernel Parameter Optimization for the construction of genetic algorithm, in its application to function in the penalty factor for the construction of genetic algorithm optimization, genetic algorithms using penalty factor the optimal solution to the training result as the fitness value. Experiments show that this method is better than ordinary based on the genetic algorithm is optimized parameters optimization method has better performance.
Finally, through the above two methods improves the support vector machine efficiency and performance, and its application in the face of gender recognition system, good results were obtained.
引文
[1]Nello Cristianini, John Shawe-Taylor.李国正,王猛,曾华军译.支持向量机导论[M].北京：电子工业出版社,2004
[2]Yi-Min Wen, Bao-Liang Lu. A cascade method for reducing training time and the number of support vector[A]. Advances in Neural Networks-ISNN2004, Lecture Notes in Computer Science[C].2004,3173(1):480-485
[3]Yi-Min Wen, Bao-Liang Lu. A hierarchical an parallel method for training support vector machines[A]. Proceedings of Second International Symposium on Neural Networks(ISNN'05), LNCS[C]. Chongqing, china,2005,881-886
[4]H. P. Graf, E. Cosatto, L. Bottou, I. Durdanovic, V. N. Vapnik. Parallel support vector machines:The cascade SVM[A]. Advances in Neural Information Processing Systems 17 Saul, L.K.(eds.)[C]. MIT Press, Cambridge, MA,2005,521-528
[5]Jing Yang. An Improved Cascade SVM Training Algorithm with Crossed Feedbacks[C] IEEE Computer Society Washington, DC, USA,2006.735-738
[6]张新.并行支持向量机算法研究[D].山东：山东科技大学,2009
[7]安平.基于线性SVM的级联检测器的构造及其在目标检测中的应用[D].黑龙江：国防科学技术大学,2007
[8]贾华丁,游志胜,王磊.基于MTC结构的支持向量机并行训练算法[J].四川大学学报,2007,39(6),123-128
[9]叶菲,罗景青,俞志富.一种改进的并行处理SVM学习算法[J].微电子学与计算机,2009,26(2),40-43
[10]史晓涛.并行支持向量机平台的研究和实现[D].北京：北京工业大学,2008
[11]王雄.基于支持向量机的文本并行分类算法研究[D].上海：上海大学,2008
[12]叶志飞.并行化最小最大模块化支持向量机及其在专利分类中的应用[D].上海：上海交通大学,2009
[13]G. Zanghirati, L. Zanni. A parallel solver for large quadratic programs in training support vector machines[J]. Parallel Computing,2003,29(4),535-551
[14]T. Serafini, G Zanghirati, L. Zanni. Parallel decomposition approaches for training support vector machines[A]. Parallel Computing：Software Technology, Algorithms, Architectures and Applications, Advances in Parallel Computing 13[C]. Amsterdam, Nether lands:Elsevier, 2004,259-266
[15]T. Serafini, L. Zanni, G Zanghirati. Some improvements to a parallel decomposition technique for training support vector machines[A]. Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science 3666[C]. Germany：Springer-Verlag,2005,9-17
[16]T. Serafini, L. Zanni, G. Zanghirati. Parallel software for training large scale support vector machines on multiprocessor system[J]. Journal of Machine Learning Research 7,2006, 1467-1492
[17]L. J. Cao, S. S. Keerthi, C. J. Ong, J. Q. Zhang, U. Periyathamby, Xiu Ju Fu, H. P. Lee. Parallel sequential minimal optimization for the training of support vector machines[J]. IEEE Transactions on Neural Networks 2006,17(4):1039-1039
[18]L. J. Cao, S. S. Keerthi, C. J. Ong, P. Uvaraj, Xiu Ju Fu, H. P. Lee. Developing parallel sequential minimal optimization for fast training support vector machine[J]. Neuro-computing,2006,70(1-3):93-104
[19]曹丽娟,王小明.训练支持向量机的并行序列最小优化方法[J].计算机工程,2007,33(18)：184-186
[20]Jing Yang, Xue Yang, Jianpei Zhang. A parallel multi-class classification support vector machine based on sequential minimal optimization[C]. Computer and Computational Sciences,2006,443-446
[21]曹丽娟,王小明.快速训练支持向量机的并行结构[J].微电子学与计算机,2006,23(10)：96-103
[22]李锐妍,李华鹏.并行SMO改进算法的研究与实现[J].计算机工程与设计,2009,30(22)：5162-5165
[23]Do Thanh-Nghi, Nguyen Van-Hoa, Poulet Francois. GPU-based parallel svm algorithm [J] Journal of Frontiers of Computer Science and Technology,2009,3(4):368-377
[24]林继鹏,刘君华,凌振宝.并行支持向量机算法及其应用[J].吉林大学学报,2004,22(5)：453-457
[25]Kristian Woodsend, Jacek Gondzio. Hybrid MPI/OpenMP parallel linear support vector machine training[J] Journal of Machine Learning Research 10,2009,1937-1953
[26]V.Vapnik.张学工译.统计学习理论的本质[M].北京：清华大学出版社,2000
[27]李春香,张为民,钟碧良.最小二乘支持向量机的参数优化算法研究[J].杭州电子科技大学学报,2010,30(4),213-216
[28]O.Chapelle, V.Vapnik, O.Bousquet, S.Mukherjee. Choosing multiple parameters for support vector machines[J]. Machine Learning,2002,46(3):31-159
[29]刘昌平,范明钰,王光卫,马素丽.基于梯度算法的支持向量机参数优化方法[J].控制与决策,2008,23(11),1291-1295
[30]Hsu, C.-W. Chang, C.-C.,& Lin, C.-J. A practical guide to support vector classification.[R]. University of National Taiwan, Department of Computer Science and Information Engineering. July,2003,1-12
[31]Zheng Chunhong, Jiao Licheng. Automatic parameters selection for SVM based on GA[C] Proc of the 5th World Congress on Intelligent Control and Automation. Piscataway, NJ：IEEE Press,2004:1869-1872
[32]刘东平,单甘霖,张岐龙,段修生.基于改进遗传算法的支持向量机参数优化[J].微计算机应用,2010,31(5),11-15
[33]于青,赵辉.基于GA的ε-支持向量机参数优化研究[J].计算机工程与应用,2008, 44(5),139-141
[34]张炜,张磊,李亮.基于GA优化的SVM涡轮泵故障诊断[J].液压与气动,2009(1),84-86
[35]王东霞,张楠,路晓丽.基于育种算法的SVM参数优化[J].安徽大学学报,2009,33(4),26-28
[36]Chih-Hung Wu, Gwo-Hshiung Tzeng, Yeong-Jia Goo, Wen-Chang Fang. A real-valued genetic algorithm to optimize the parameters of support vector machine for predicting bankruptcy[J]. Expert System with Application,2007(32),397-408
[37]Xing-Ming Zhao, De-Shuang Huang, Yiu-ming Cheung, Hong-qiong Wang, Xin Huang. A novel hybrid GA/SVM system for protein sequences classification[J]. Lecture Notes in Computer Science,2004 (3177),11-16
[38]袁玉萍,胡亮,周志坚.基于遗传算法对支持向量机模型中的参数优化[J].计算机工程与设计,2008,29(19),5016-5018
[39]郭立力,赵春江.十折交叉检验的支持向量机参数优化算法[J].计算机工程与应用,20095,45(8),55-57
[40]Tsair-Fwu Lee, Ming-Yuan Cho, Chin-Shiuh Shieh, Fu-Min Fang. Particle swarm optimization-based SVM application：power transformers incipient fault syndrome diagnosis[C]. International Conference on Hybrid Information Technology,2006:468-472
[41]邵信光,杨慧中,陈刚.基于粒子群优化算法的支持向量机参数选择及其应用[J].控制理论与应用.2006,23(5),740-743
[42]李明,张勇,李军权,张亚芬.改进PSO-SVM在说话人识别中的应用[J].电子科技大学学报.2007,36(6),1345-1349
[43]武华锋,李著信,苏毅,吕宏庆.一种基于多组PSO的支持向量机参数优化算法[J].后勤工程学院学报.2007,23(4),92-94
[44]Huang Ch L, Wang Ch J. A GA-based feature selection and parameters optimization for support vector machines[J]. Expert Systems with Applications,2006,31,231-240
[45]Shih-Wei Lin, Kuo-Ching Ying, Shih-Chieh Chen, Zne-Jung Lee. Particle swarm optimization for parameter determination and feature selection of support vector machines[J]. Expert Systems with Applications 35 (2008),1817-1824
[46]John C. Platt. Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines[J]. Advances in Kernel Methods,1998,185～208.
[47]Thorsten Joachims. Making large-scale support vector machine learning practical[J]. Advances in kernel methods.1999,169～184
[48]Chih-Chung Chang, Chih-Jen Lin. LIBSVM:a Library for Support Vector Machines[EB/01]. http://www.csie.ntu.edu. tw/～cjlin/libsvm,2009-2-27
[49]James Reinders.聂雪军译.Intel Threading Building Blocks编程指南[M],北京：机械工业出版社,2009
[50]陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用[M],北京：人民邮电出版社,1996
[2]Yi-Min Wen, Bao-Liang Lu. A cascade method for reducing training time and the number of support vector[A]. Advances in Neural Networks-ISNN2004, Lecture Notes in Computer Science[C].2004,3173(1):480-485
[3]Yi-Min Wen, Bao-Liang Lu. A hierarchical an parallel method for training support vector machines[A]. Proceedings of Second International Symposium on Neural Networks(ISNN'05), LNCS[C]. Chongqing, china,2005,881-886
[4]H. P. Graf, E. Cosatto, L. Bottou, I. Durdanovic, V. N. Vapnik. Parallel support vector machines:The cascade SVM[A]. Advances in Neural Information Processing Systems 17 Saul, L.K.(eds.)[C]. MIT Press, Cambridge, MA,2005,521-528
[5]Jing Yang. An Improved Cascade SVM Training Algorithm with Crossed Feedbacks[C] IEEE Computer Society Washington, DC, USA,2006.735-738
[6]张新.并行支持向量机算法研究[D].山东：山东科技大学,2009
[7]安平.基于线性SVM的级联检测器的构造及其在目标检测中的应用[D].黑龙江：国防科学技术大学,2007
[8]贾华丁,游志胜,王磊.基于MTC结构的支持向量机并行训练算法[J].四川大学学报,2007,39(6),123-128
[9]叶菲,罗景青,俞志富.一种改进的并行处理SVM学习算法[J].微电子学与计算机,2009,26(2),40-43
[10]史晓涛.并行支持向量机平台的研究和实现[D].北京：北京工业大学,2008
[11]王雄.基于支持向量机的文本并行分类算法研究[D].上海：上海大学,2008
[12]叶志飞.并行化最小最大模块化支持向量机及其在专利分类中的应用[D].上海：上海交通大学,2009
[13]G. Zanghirati, L. Zanni. A parallel solver for large quadratic programs in training support vector machines[J]. Parallel Computing,2003,29(4),535-551
[14]T. Serafini, G Zanghirati, L. Zanni. Parallel decomposition approaches for training support vector machines[A]. Parallel Computing：Software Technology, Algorithms, Architectures and Applications, Advances in Parallel Computing 13[C]. Amsterdam, Nether lands:Elsevier, 2004,259-266
[15]T. Serafini, L. Zanni, G Zanghirati. Some improvements to a parallel decomposition technique for training support vector machines[A]. Recent Advances in Parallel Virtual Machine and Message Passing Interface, Lecture Notes in Computer Science 3666[C]. Germany：Springer-Verlag,2005,9-17
[16]T. Serafini, L. Zanni, G. Zanghirati. Parallel software for training large scale support vector machines on multiprocessor system[J]. Journal of Machine Learning Research 7,2006, 1467-1492
[17]L. J. Cao, S. S. Keerthi, C. J. Ong, J. Q. Zhang, U. Periyathamby, Xiu Ju Fu, H. P. Lee. Parallel sequential minimal optimization for the training of support vector machines[J]. IEEE Transactions on Neural Networks 2006,17(4):1039-1039
[18]L. J. Cao, S. S. Keerthi, C. J. Ong, P. Uvaraj, Xiu Ju Fu, H. P. Lee. Developing parallel sequential minimal optimization for fast training support vector machine[J]. Neuro-computing,2006,70(1-3):93-104
[19]曹丽娟,王小明.训练支持向量机的并行序列最小优化方法[J].计算机工程,2007,33(18)：184-186
[20]Jing Yang, Xue Yang, Jianpei Zhang. A parallel multi-class classification support vector machine based on sequential minimal optimization[C]. Computer and Computational Sciences,2006,443-446
[21]曹丽娟,王小明.快速训练支持向量机的并行结构[J].微电子学与计算机,2006,23(10)：96-103
[22]李锐妍,李华鹏.并行SMO改进算法的研究与实现[J].计算机工程与设计,2009,30(22)：5162-5165
[23]Do Thanh-Nghi, Nguyen Van-Hoa, Poulet Francois. GPU-based parallel svm algorithm [J] Journal of Frontiers of Computer Science and Technology,2009,3(4):368-377
[24]林继鹏,刘君华,凌振宝.并行支持向量机算法及其应用[J].吉林大学学报,2004,22(5)：453-457
[25]Kristian Woodsend, Jacek Gondzio. Hybrid MPI/OpenMP parallel linear support vector machine training[J] Journal of Machine Learning Research 10,2009,1937-1953
[26]V.Vapnik.张学工译.统计学习理论的本质[M].北京：清华大学出版社,2000
[27]李春香,张为民,钟碧良.最小二乘支持向量机的参数优化算法研究[J].杭州电子科技大学学报,2010,30(4),213-216
[28]O.Chapelle, V.Vapnik, O.Bousquet, S.Mukherjee. Choosing multiple parameters for support vector machines[J]. Machine Learning,2002,46(3):31-159
[29]刘昌平,范明钰,王光卫,马素丽.基于梯度算法的支持向量机参数优化方法[J].控制与决策,2008,23(11),1291-1295
[30]Hsu, C.-W. Chang, C.-C.,& Lin, C.-J. A practical guide to support vector classification.[R]. University of National Taiwan, Department of Computer Science and Information Engineering. July,2003,1-12
[31]Zheng Chunhong, Jiao Licheng. Automatic parameters selection for SVM based on GA[C] Proc of the 5th World Congress on Intelligent Control and Automation. Piscataway, NJ：IEEE Press,2004:1869-1872
[32]刘东平,单甘霖,张岐龙,段修生.基于改进遗传算法的支持向量机参数优化[J].微计算机应用,2010,31(5),11-15
[33]于青,赵辉.基于GA的ε-支持向量机参数优化研究[J].计算机工程与应用,2008, 44(5),139-141
[34]张炜,张磊,李亮.基于GA优化的SVM涡轮泵故障诊断[J].液压与气动,2009(1),84-86
[35]王东霞,张楠,路晓丽.基于育种算法的SVM参数优化[J].安徽大学学报,2009,33(4),26-28
[36]Chih-Hung Wu, Gwo-Hshiung Tzeng, Yeong-Jia Goo, Wen-Chang Fang. A real-valued genetic algorithm to optimize the parameters of support vector machine for predicting bankruptcy[J]. Expert System with Application,2007(32),397-408
[37]Xing-Ming Zhao, De-Shuang Huang, Yiu-ming Cheung, Hong-qiong Wang, Xin Huang. A novel hybrid GA/SVM system for protein sequences classification[J]. Lecture Notes in Computer Science,2004 (3177),11-16
[38]袁玉萍,胡亮,周志坚.基于遗传算法对支持向量机模型中的参数优化[J].计算机工程与设计,2008,29(19),5016-5018
[39]郭立力,赵春江.十折交叉检验的支持向量机参数优化算法[J].计算机工程与应用,20095,45(8),55-57
[40]Tsair-Fwu Lee, Ming-Yuan Cho, Chin-Shiuh Shieh, Fu-Min Fang. Particle swarm optimization-based SVM application：power transformers incipient fault syndrome diagnosis[C]. International Conference on Hybrid Information Technology,2006:468-472
[41]邵信光,杨慧中,陈刚.基于粒子群优化算法的支持向量机参数选择及其应用[J].控制理论与应用.2006,23(5),740-743
[42]李明,张勇,李军权,张亚芬.改进PSO-SVM在说话人识别中的应用[J].电子科技大学学报.2007,36(6),1345-1349
[43]武华锋,李著信,苏毅,吕宏庆.一种基于多组PSO的支持向量机参数优化算法[J].后勤工程学院学报.2007,23(4),92-94
[44]Huang Ch L, Wang Ch J. A GA-based feature selection and parameters optimization for support vector machines[J]. Expert Systems with Applications,2006,31,231-240
[45]Shih-Wei Lin, Kuo-Ching Ying, Shih-Chieh Chen, Zne-Jung Lee. Particle swarm optimization for parameter determination and feature selection of support vector machines[J]. Expert Systems with Applications 35 (2008),1817-1824
[46]John C. Platt. Sequential Minimal Optimization：A Fast Algorithm for Training Support Vector Machines[J]. Advances in Kernel Methods,1998,185～208.
[47]Thorsten Joachims. Making large-scale support vector machine learning practical[J]. Advances in kernel methods.1999,169～184
[48]Chih-Chung Chang, Chih-Jen Lin. LIBSVM:a Library for Support Vector Machines[EB/01]. http://www.csie.ntu.edu. tw/～cjlin/libsvm,2009-2-27
[49]James Reinders.聂雪军译.Intel Threading Building Blocks编程指南[M],北京：机械工业出版社,2009
[50]陈国良,王熙法,庄镇泉,王东生.遗传算法及其应用[M],北京：人民邮电出版社,1996