支持向量机参数优化问题的研究
|
摘要
作为数据挖掘中的一项新技术,支持向量机是在统计学习理论基础上发展起来的一种性能优良的新型机器学习方法。它被认为是机器学习领域非常流行的方法和成功的例子。当支持向量机应用于实际问题时,首先面临的是模型参数的选择,包括支持向量机中的参数选择和核函数参数选择。参数的选择直接决定着支持向量机的训练效率和应用效果,因此如何选择参数是应用支持向量机的主要问题。
本文以优化理论为基础,以数学规划为手段,对支持向量机在实际应用中的参数优化问题进行研究。主要分成以下三个部分:
第一部分,在统计学习理论基础下分析了支持向量机和模糊一类支持向量机的基本模型和算法,并结合结构风险最小化理论,分析了模型中核参数和惩罚参数对分类机性能产生的影响。
第二部分,针对支持向量机中的参数优化问题,本文从不同角度出发对惩罚参数和核参数采用不同的优化更新规则。首先定义分离指标用以描述给定数据集的样本间的分离关系,从而建立以核参数为变量的无约束优化问题;然后将核函数参数的最优值代入到支持向量机中,从分类机的推广性能出发建立一个以惩罚参数为变量的有约束优化问题;最后采用遗传算法求解优化问题,与网格法的对比数值实验验证了本文方法的有效性。
第三部分,针对模糊一类支持向量机模型,本文首先从理论上解释了惩罚参数的物理意义,给出其取值范围,并分析了支持向量机与模糊一类支持向量机的关系。然后基于遗传算法,分别建立以核参数为变量的无约束优化问题和以惩罚参数为变量的有约束优化问题来确定最优参数值。数值实验的结果表明本文提出的参数优化方法的优越性。
As a technique of data mining, support vector machine (SVM), which is developedon the frame of the statistical learning theory, has been a new excellent machine learningmethod. SVM has been considered as an extraordinarily popular method and successfulexample in the field of machine learning. When it’s applied to practical applications, thefirst problem confronted is the choice of model parameters, including penalty parameterand kernel parameters. The choice of parameters, which directly determine the trainingefficiency and performance, is the key factor in the application of SVM directly.
In this paper, the choice of the parameter selection are considered by using theoptimization and mathematical programming methods. The main contents are dividedinto the following three parts:
In the first part, basic models and algorithms of SVM and fuzzy one-class supportvector machine (FOC-SVM) are analyzed on the framework of statistical learning theory.Combined with theory of the structural risk minimization, performance affected by thechoice of different penalty parameter and kernel parameter in SVM classification isanalyzed.
In the second part, in terms of parameter optimization problems for SVM, severaloptimization rules are applied to obtain the optimal penalty parameter and kernelparameter. Firstly, a separation index is defined to describe separation relationshipbetween two types of samples for given data sets. Then an unconstrained optimizationproblem on kernel parameter is established. Next, on the condition of fixing the kernelparameter of SVM to its optimal value obtained above, a constrained optimizationproblem whose variable is penalty parameter is established in terms of the generalizationability of classification with SVM. Then the genetic algorithm is used to resolve theoptimization problems obtains above. Finally, some numerical experiments are carriedout. The comparison results with the grid method show the effectiveness of proposedmethod.
In the third part, we explain the meaning of penalty parameter of FOC-SVMtheoretically and give its range which can be taken over. The relationship between SVMand FOC-SVM is analyzed. Then an unconstrained optimization model on nuclearparameter and a constrained optimization model on penalty parameter are establishedrespectively. Then the optimal parameter values are given using genetic algorithms.Numerical experiment results show the superiority of proposed methods.
本文以优化理论为基础,以数学规划为手段,对支持向量机在实际应用中的参数优化问题进行研究。主要分成以下三个部分:
第一部分,在统计学习理论基础下分析了支持向量机和模糊一类支持向量机的基本模型和算法,并结合结构风险最小化理论,分析了模型中核参数和惩罚参数对分类机性能产生的影响。
第二部分,针对支持向量机中的参数优化问题,本文从不同角度出发对惩罚参数和核参数采用不同的优化更新规则。首先定义分离指标用以描述给定数据集的样本间的分离关系,从而建立以核参数为变量的无约束优化问题;然后将核函数参数的最优值代入到支持向量机中,从分类机的推广性能出发建立一个以惩罚参数为变量的有约束优化问题;最后采用遗传算法求解优化问题,与网格法的对比数值实验验证了本文方法的有效性。
第三部分,针对模糊一类支持向量机模型,本文首先从理论上解释了惩罚参数的物理意义,给出其取值范围,并分析了支持向量机与模糊一类支持向量机的关系。然后基于遗传算法,分别建立以核参数为变量的无约束优化问题和以惩罚参数为变量的有约束优化问题来确定最优参数值。数值实验的结果表明本文提出的参数优化方法的优越性。
As a technique of data mining, support vector machine (SVM), which is developedon the frame of the statistical learning theory, has been a new excellent machine learningmethod. SVM has been considered as an extraordinarily popular method and successfulexample in the field of machine learning. When it’s applied to practical applications, thefirst problem confronted is the choice of model parameters, including penalty parameterand kernel parameters. The choice of parameters, which directly determine the trainingefficiency and performance, is the key factor in the application of SVM directly.
In this paper, the choice of the parameter selection are considered by using theoptimization and mathematical programming methods. The main contents are dividedinto the following three parts:
In the first part, basic models and algorithms of SVM and fuzzy one-class supportvector machine (FOC-SVM) are analyzed on the framework of statistical learning theory.Combined with theory of the structural risk minimization, performance affected by thechoice of different penalty parameter and kernel parameter in SVM classification isanalyzed.
In the second part, in terms of parameter optimization problems for SVM, severaloptimization rules are applied to obtain the optimal penalty parameter and kernelparameter. Firstly, a separation index is defined to describe separation relationshipbetween two types of samples for given data sets. Then an unconstrained optimizationproblem on kernel parameter is established. Next, on the condition of fixing the kernelparameter of SVM to its optimal value obtained above, a constrained optimizationproblem whose variable is penalty parameter is established in terms of the generalizationability of classification with SVM. Then the genetic algorithm is used to resolve theoptimization problems obtains above. Finally, some numerical experiments are carriedout. The comparison results with the grid method show the effectiveness of proposedmethod.
In the third part, we explain the meaning of penalty parameter of FOC-SVMtheoretically and give its range which can be taken over. The relationship between SVMand FOC-SVM is analyzed. Then an unconstrained optimization model on nuclearparameter and a constrained optimization model on penalty parameter are establishedrespectively. Then the optimal parameter values are given using genetic algorithms.Numerical experiment results show the superiority of proposed methods.
引文
1 S. R. Gunn. Support Vector Machines for Classification and Regression. TechnicalReport, Faculty of Engineering, Science and Mathematics School of Electronics andComputer Science. 1998:5~28
2邓乃扬,田英杰.数据挖掘中的新方法——支持向量机.科学出版社,2004:15~75
3 J. C. Christopher. A Tutorial on Support Vector Machines for Pattern Recognition.Data Mining and Knowledge Discovery. 1998, (2):121~167
4 Z. H. Sun, Y. X. Sun. Fuzzy Support Vector Machine for Regression Estimation.Systems, Man and Cybernetics, IEEE Conference on, 2003, 4:3336~3341
5 L. Zhao, N. Takagi. An Application of Support Vector Machines to ChineseCharacter Classification Problem. Systems, Man and Cybernetics, IEEE Conferenceon, 2007:3604~3608
6 R. Min, H. D. Cheng. Effective Image Retrieval using Dominant Color Descriptorand Fuzzy Support Vector Machine. Pattern Recognition. 2009, 42(1): 147~157
7李椼,朱靖波,姚天顺.基于SVM的中文组块分析.中文信息学报. 2004,18(2):1~7
8 K. R. Muller, A. J. Smola and B. Sch?lkopf. Predicting Time Series with SupportVector Machines. Lecture Notes in Computer Science, 1997: 999~1004
9张学工.关于统计学习理论与支持向量机.自动化学报. 2000, 26(1), 32~42
10 A. Shigeo. Analysis of Support Vector Machines. Neural Networks for SignalProcessing, IEEE Conference on, 2002:89~98
11 H. Z. Song, Z. C. Ding and C. C. Guo. Research on Combination Kernel Function ofSupport Vector Machine. IEEE Trans. on Computer Science and SoftwareEngineering. 2008, 1:838~841
12 D. X. Niu, W. Li and L. M. Cheng. Mid-term Load Forecasting Based on DynamicLeast Squares SVMS. Machine Learning and Cybernetics, IEEE Conference on, 2008,2: 800~804
13 Y. Zhang, Z. X. Chi and K. Q. Li. Fuzzy Multi-class Classifier Based on SupportVector Data Description and Improved PCM. Expert Systems with Applications.2008, 36(5):8714~8718
14 K. Y. Chen, H. Chia. An Improved Support Vector Regression Modeling for TaiwanStock Exchange Market Weighted Index Forecasting. Neural Networks and Brain,IEEE Conference on, 2005, 3:1633~1638
15 L. Xu, G. Z. Zhao. Improved Kernel Method for Clustering based on Fuzzy 1-SVM.Control and Decision. 2008, 23(9):1030~1034
16荣海娜,张葛祥.系统辨识中支持向量机核函数及其参数的研究.系统仿真学报.2006, 18(11):3204~3208
17 J. Wang, H. P. Lu and K. N. Plataniotis. Gaussian Kernel Optimization for PatternClassification. Pattern Recognition. 2009, 42(7):1237~1247
18 O. Chapelle, V. Vapnik and O. Bousquet. Choosing Multiple Parameters for SupportVector Machines. Machine Learning. 2002, 46:131~159
19 V. Cherkassky. Practical Selection of SVM Parameters and Noise Estimation forSVM Regression. Neural Networks. 2004,17(1): 113~126
20 O. Chapelle, V. Vapnik. Model Selection for Support Vector Machines. Advances inNeural Information Processing Systems. 2000:1~7
21 S. S. Keerthi. Efficient Tuning of SVM Hyper Parameters using Radius/MarginBound and Iterative Algorithms. IEEE Trans on Neural Networks. 2002,13(5):1225~1229
22 N. Ayat, M. Cheriet and C. Suen. Automatic Model Selection for the Optimization ofthe SVM Kernels. Pattern Recognition Journal. 2005, 38(10):1733~1745
23 L. Wang, P. Xue and K. L. Chan. Two Criteria for Model Selection in Multi-classSupport Vector Machines. IEEE Trans. on Systems, Man and Cybernetics, Part B:Cybernetics. 2008, 38(6):1432~1448
24 C. W. Hsu, C. C. Chang and C. J. Lin. A Practical Guide for Support VectorClassification. Technique report, National Taiwan University, 2003:1~15
25董春曦,饶鲜.支持向量机参数选择方法研究.系统工程与电子技术. 2004,8(26):1117~1120
26 M. Opper, O. Winther. Gaussian Processes and SVM: Mean Field and Leave-one-out.Advances in Large Margin Classifiers, MIT Press, 2000:311~326
27 G. Wahba, Y. Lin. Generalized Approximate Cross Validation for Support VectorMachine or Another Way to Look at Margin-like Quantities. Advances in LargeMargin Classifiers, MIT Press, 2000:297~309
28 T. Joachims. Estimating the Generalization Performance of a SVM Efficiently.Research Report, University of Dortmund, Germany, 1999:1~27
29 V. Vapnik, O. Chapelle. Bounds on Error Expectation for Support Vector Machines.Neural Computation. 2000, 12(9):2013~2036
30 R. C. Williamson, A. J. Somla and B. Sch?lkopf. Generalization Performance ofRegularization Networks and Support Vector Machines via Entropy Numbers ofCompact Operators. IEEE Trans. Information Theory. 2001, 47(6):2516~2532
31 H. Frohlich, O. Chapelle. Feature Selection for Support Vector Machines by Meansof Genetic Algorithms. Tools with Artificial Intelligence, IEEE Conference on,2003:142~148
32郭立力,赵春江.十折交叉检验的支持向量机参数优化算法.计算机工程与应用.2009, 45(8):55~57
33 T. F. Lee, M. Y. Cho and C. S. Shieh. Particle Swarm Optimization-based SVMApplication: Power Transformers Incipient Fault Syndrome Diagnosis. HybridInformation Technology, IEEE Conference on, 2006, 1:468~472
34 S. W. Lin, T. Y. Tseng and S. C. Chen. A SA-based Feature Selection and ParameterOptimization Approach for Support Vector Machine. Systems, Man, and Cybernetics,IEEE Conference on, Taipei, 2006:3144~3145
35方瑞明.支持向量机理论及其应用分析.中国电力出版社, 2007:47~56
36 H. T. Lin, C. J. Lin. A Study on Sigmoid Kernels for SVM and the Training ofnon-PSD Kernels by SMO-type Methods. Technical report, Department of ComputerScience, National Taiwan University. 2003:11~15
37 B. Sch?lkopf, R. Williamson and A. Smola. Support Vector Method for NoveltyDetection. MIT Press, 2000:582~588
38 H. Xu, D. S. Huang. One Class Support Vector Machines for DistinguishingPhotographs and Graphics. Networking, Sensing and Control, IEEE Conference on,2008:602~607
39 Y. Q. Chen, X. S. Zhou and T. S. Huang. One-class SVM for Learning in ImageRetrieval. Image Processing, IEEE Conference on, 2001, 1:34~37
40 X. M. Song, G. Iordanescu and A. M. Wyrwicz. One-class Machine Learning forBrain Activation Detection. Computer Vision and Pattern Recognition, IEEEConference on, 2007:1~6
41钟清流,蔡自兴.基于一类支持向量机的传感器故障诊断.计算机工程与应用.2006, 42(19):1~7
42 B. Sch?lkopf, A. J. Smola. Learning with Kernels: Support Vector Machines,Regularization, Optimization and Beyond. MIT Press, 2001:227~250
43 P. Y. Hao. Fuzzy One-Class Support Vector Machines. Fuzzy Sets and Systems. 2008,159(18):2317~2336
44 M. Bicego, A. T. Mario. Soft Clustering using Weighted One-Class Support VectorMachines. Pattern Recognition. 2009, 42(1):27~32
45 K. P. Wu, S. D. Wang. Choosing the Kernel Parameters for Support Vector Machinesby the Inter-Cluster Distance in the Feature Space. Pattern Recognition. 2009,42(5):710~717
46阳明盛,罗长童.最优化原理、方法及求解软件.科学出版社, 2006:128~140
2邓乃扬,田英杰.数据挖掘中的新方法——支持向量机.科学出版社,2004:15~75
3 J. C. Christopher. A Tutorial on Support Vector Machines for Pattern Recognition.Data Mining and Knowledge Discovery. 1998, (2):121~167
4 Z. H. Sun, Y. X. Sun. Fuzzy Support Vector Machine for Regression Estimation.Systems, Man and Cybernetics, IEEE Conference on, 2003, 4:3336~3341
5 L. Zhao, N. Takagi. An Application of Support Vector Machines to ChineseCharacter Classification Problem. Systems, Man and Cybernetics, IEEE Conferenceon, 2007:3604~3608
6 R. Min, H. D. Cheng. Effective Image Retrieval using Dominant Color Descriptorand Fuzzy Support Vector Machine. Pattern Recognition. 2009, 42(1): 147~157
7李椼,朱靖波,姚天顺.基于SVM的中文组块分析.中文信息学报. 2004,18(2):1~7
8 K. R. Muller, A. J. Smola and B. Sch?lkopf. Predicting Time Series with SupportVector Machines. Lecture Notes in Computer Science, 1997: 999~1004
9张学工.关于统计学习理论与支持向量机.自动化学报. 2000, 26(1), 32~42
10 A. Shigeo. Analysis of Support Vector Machines. Neural Networks for SignalProcessing, IEEE Conference on, 2002:89~98
11 H. Z. Song, Z. C. Ding and C. C. Guo. Research on Combination Kernel Function ofSupport Vector Machine. IEEE Trans. on Computer Science and SoftwareEngineering. 2008, 1:838~841
12 D. X. Niu, W. Li and L. M. Cheng. Mid-term Load Forecasting Based on DynamicLeast Squares SVMS. Machine Learning and Cybernetics, IEEE Conference on, 2008,2: 800~804
13 Y. Zhang, Z. X. Chi and K. Q. Li. Fuzzy Multi-class Classifier Based on SupportVector Data Description and Improved PCM. Expert Systems with Applications.2008, 36(5):8714~8718
14 K. Y. Chen, H. Chia. An Improved Support Vector Regression Modeling for TaiwanStock Exchange Market Weighted Index Forecasting. Neural Networks and Brain,IEEE Conference on, 2005, 3:1633~1638
15 L. Xu, G. Z. Zhao. Improved Kernel Method for Clustering based on Fuzzy 1-SVM.Control and Decision. 2008, 23(9):1030~1034
16荣海娜,张葛祥.系统辨识中支持向量机核函数及其参数的研究.系统仿真学报.2006, 18(11):3204~3208
17 J. Wang, H. P. Lu and K. N. Plataniotis. Gaussian Kernel Optimization for PatternClassification. Pattern Recognition. 2009, 42(7):1237~1247
18 O. Chapelle, V. Vapnik and O. Bousquet. Choosing Multiple Parameters for SupportVector Machines. Machine Learning. 2002, 46:131~159
19 V. Cherkassky. Practical Selection of SVM Parameters and Noise Estimation forSVM Regression. Neural Networks. 2004,17(1): 113~126
20 O. Chapelle, V. Vapnik. Model Selection for Support Vector Machines. Advances inNeural Information Processing Systems. 2000:1~7
21 S. S. Keerthi. Efficient Tuning of SVM Hyper Parameters using Radius/MarginBound and Iterative Algorithms. IEEE Trans on Neural Networks. 2002,13(5):1225~1229
22 N. Ayat, M. Cheriet and C. Suen. Automatic Model Selection for the Optimization ofthe SVM Kernels. Pattern Recognition Journal. 2005, 38(10):1733~1745
23 L. Wang, P. Xue and K. L. Chan. Two Criteria for Model Selection in Multi-classSupport Vector Machines. IEEE Trans. on Systems, Man and Cybernetics, Part B:Cybernetics. 2008, 38(6):1432~1448
24 C. W. Hsu, C. C. Chang and C. J. Lin. A Practical Guide for Support VectorClassification. Technique report, National Taiwan University, 2003:1~15
25董春曦,饶鲜.支持向量机参数选择方法研究.系统工程与电子技术. 2004,8(26):1117~1120
26 M. Opper, O. Winther. Gaussian Processes and SVM: Mean Field and Leave-one-out.Advances in Large Margin Classifiers, MIT Press, 2000:311~326
27 G. Wahba, Y. Lin. Generalized Approximate Cross Validation for Support VectorMachine or Another Way to Look at Margin-like Quantities. Advances in LargeMargin Classifiers, MIT Press, 2000:297~309
28 T. Joachims. Estimating the Generalization Performance of a SVM Efficiently.Research Report, University of Dortmund, Germany, 1999:1~27
29 V. Vapnik, O. Chapelle. Bounds on Error Expectation for Support Vector Machines.Neural Computation. 2000, 12(9):2013~2036
30 R. C. Williamson, A. J. Somla and B. Sch?lkopf. Generalization Performance ofRegularization Networks and Support Vector Machines via Entropy Numbers ofCompact Operators. IEEE Trans. Information Theory. 2001, 47(6):2516~2532
31 H. Frohlich, O. Chapelle. Feature Selection for Support Vector Machines by Meansof Genetic Algorithms. Tools with Artificial Intelligence, IEEE Conference on,2003:142~148
32郭立力,赵春江.十折交叉检验的支持向量机参数优化算法.计算机工程与应用.2009, 45(8):55~57
33 T. F. Lee, M. Y. Cho and C. S. Shieh. Particle Swarm Optimization-based SVMApplication: Power Transformers Incipient Fault Syndrome Diagnosis. HybridInformation Technology, IEEE Conference on, 2006, 1:468~472
34 S. W. Lin, T. Y. Tseng and S. C. Chen. A SA-based Feature Selection and ParameterOptimization Approach for Support Vector Machine. Systems, Man, and Cybernetics,IEEE Conference on, Taipei, 2006:3144~3145
35方瑞明.支持向量机理论及其应用分析.中国电力出版社, 2007:47~56
36 H. T. Lin, C. J. Lin. A Study on Sigmoid Kernels for SVM and the Training ofnon-PSD Kernels by SMO-type Methods. Technical report, Department of ComputerScience, National Taiwan University. 2003:11~15
37 B. Sch?lkopf, R. Williamson and A. Smola. Support Vector Method for NoveltyDetection. MIT Press, 2000:582~588
38 H. Xu, D. S. Huang. One Class Support Vector Machines for DistinguishingPhotographs and Graphics. Networking, Sensing and Control, IEEE Conference on,2008:602~607
39 Y. Q. Chen, X. S. Zhou and T. S. Huang. One-class SVM for Learning in ImageRetrieval. Image Processing, IEEE Conference on, 2001, 1:34~37
40 X. M. Song, G. Iordanescu and A. M. Wyrwicz. One-class Machine Learning forBrain Activation Detection. Computer Vision and Pattern Recognition, IEEEConference on, 2007:1~6
41钟清流,蔡自兴.基于一类支持向量机的传感器故障诊断.计算机工程与应用.2006, 42(19):1~7
42 B. Sch?lkopf, A. J. Smola. Learning with Kernels: Support Vector Machines,Regularization, Optimization and Beyond. MIT Press, 2001:227~250
43 P. Y. Hao. Fuzzy One-Class Support Vector Machines. Fuzzy Sets and Systems. 2008,159(18):2317~2336
44 M. Bicego, A. T. Mario. Soft Clustering using Weighted One-Class Support VectorMachines. Pattern Recognition. 2009, 42(1):27~32
45 K. P. Wu, S. D. Wang. Choosing the Kernel Parameters for Support Vector Machinesby the Inter-Cluster Distance in the Feature Space. Pattern Recognition. 2009,42(5):710~717
46阳明盛,罗长童.最优化原理、方法及求解软件.科学出版社, 2006:128~140