支持向量机的快速分类方法研究
|
摘要
支持向量机是Vapnik等人提出的一类新型机器学习方法,它是基于统计学习理论,借助最优化方法来解决机器学习问题的新工具,支持向量机目前还存在许多局限性,研究有待进一步探索和完善。本文以统计学习理论(Statistic Learning Theory-SLT)和支持向量机(Support Vector Machine-SVM)为基础,开展了以下研究工作：
首先,对统计学习理论和支持向量机分类器进行了全面的总结和概括。
其次,总结了现有的几种有代表性的多类支持向量机方法,这些方法包括：一对多(one-against-all)、一对一(one-against-one)、有向无环图支持向量机(DAG-SVMs)、决策树分类和全局优化分类(MSVM);还介绍了两种模糊多类支持向量机方法。
第三,总结了适合于求解大型问题的训练算法：选块算法(Chuncking),分解算法(Decomposing)和序列最小最优化算法(Sequential Minimal Optimization-SMO)等,这些都是专门针对支持向量机设计的快速算法。提出了一种改进的模糊多类支持向量机方法,它是在全局优化分类(MSVM)的基础上,引入模糊隶属函数；然后利用改进的序列最小最优化算法求解模糊多类支持向量机,实验结果显示运行时间减少了,方法是可行的和有效的。
Support vector machine (SVM), which was proposed by Vapnik and some other scholars, is one of the standard tools for machine learning and data mining. It is an implementation of structure risk minimization principle in the statistical learning theory. Based on the statistical learning theory and optimization theory, SVM has been successfully applied to many fields. But, SVM, which still has some limitations, needs to be further explored and perfected. In this thesis, several issues are addressed, which are based on statistic learning theory (SLT) and support vector machine (SVM). The main work and results are outlined as follows:
Firstly, the statistical learning theory and SVM are summarized and analyzed.
Secondly, five major kinds of multicategory support vector machine methods are systematically summarized and analyzed. These multicategory classification methods include--One-against-All, One-against-One, Directed Acyclic Graph SVMs (DAG-SVMs), Decision-Tree-Based Multiclass Support Vector Machines and Multiclass Support Vector Machines. Two kinds of Fuzzy Support Vector Machines are analyzed.
Thirdly, the training algorithms of SVM for large-scale training set are summarized and analyzed. These methods include-Chuncking, Decomposing and Sequential Minimal Optimization-SMO. An improved fuzzy multicategory support vector machines are presented. We extend to the Multiclass Support Vector Machines method, and with the fuzzy membership of data samples of a given class, to improve classification performance with high generalization capability. We used the improved Sequential Minimal Optimization to solve fuzzy multicategory support vector machine. The experimental results show that the computational load be reduced greatly and with high generalization capability.
首先,对统计学习理论和支持向量机分类器进行了全面的总结和概括。
其次,总结了现有的几种有代表性的多类支持向量机方法,这些方法包括：一对多(one-against-all)、一对一(one-against-one)、有向无环图支持向量机(DAG-SVMs)、决策树分类和全局优化分类(MSVM);还介绍了两种模糊多类支持向量机方法。
第三,总结了适合于求解大型问题的训练算法：选块算法(Chuncking),分解算法(Decomposing)和序列最小最优化算法(Sequential Minimal Optimization-SMO)等,这些都是专门针对支持向量机设计的快速算法。提出了一种改进的模糊多类支持向量机方法,它是在全局优化分类(MSVM)的基础上,引入模糊隶属函数；然后利用改进的序列最小最优化算法求解模糊多类支持向量机,实验结果显示运行时间减少了,方法是可行的和有效的。
Support vector machine (SVM), which was proposed by Vapnik and some other scholars, is one of the standard tools for machine learning and data mining. It is an implementation of structure risk minimization principle in the statistical learning theory. Based on the statistical learning theory and optimization theory, SVM has been successfully applied to many fields. But, SVM, which still has some limitations, needs to be further explored and perfected. In this thesis, several issues are addressed, which are based on statistic learning theory (SLT) and support vector machine (SVM). The main work and results are outlined as follows:
Firstly, the statistical learning theory and SVM are summarized and analyzed.
Secondly, five major kinds of multicategory support vector machine methods are systematically summarized and analyzed. These multicategory classification methods include--One-against-All, One-against-One, Directed Acyclic Graph SVMs (DAG-SVMs), Decision-Tree-Based Multiclass Support Vector Machines and Multiclass Support Vector Machines. Two kinds of Fuzzy Support Vector Machines are analyzed.
Thirdly, the training algorithms of SVM for large-scale training set are summarized and analyzed. These methods include-Chuncking, Decomposing and Sequential Minimal Optimization-SMO. An improved fuzzy multicategory support vector machines are presented. We extend to the Multiclass Support Vector Machines method, and with the fuzzy membership of data samples of a given class, to improve classification performance with high generalization capability. We used the improved Sequential Minimal Optimization to solve fuzzy multicategory support vector machine. The experimental results show that the computational load be reduced greatly and with high generalization capability.
引文
[1]V. N. Vapnik. Statistical learning theory. New York:Wiley,1998.
[2]V. N. Vapnik. The nature of statistical learning theory. New York:Springer, second edition,2000.
[3]G. M. Fung and O. L. Mangasarian. A feature selection Newton method for support vector machine classification. Computational Optimization and Applications,2004,28:185-202.
[4]G Fung and O. L. Mangasarian. Finite Newton method for Lagrangian support vector machine classification. Technical Report 02-01, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin,2002.
[5]Kreβel.U. H.-G. Pairwise classification and support vector machines. In B. Scholkopf, C. J. C. Burges and A. J. Smola (Eds.), Advances in kernel methods:Support vector learning, Cambridge, MA:MIT Press,1999,255-268.
[6]Bottou L, Cortes C, Dcnkcr J, et al. Comparison of Classifier Methods:A case study handwriting digit recognition. In International Conference on Pattern Recognition. IEEE Computer Society Press, 1994,77-87.
[7]J. C. Platt, N. Cristianini and J. Shawe-Taylor. Large margin DAG's for multiclass classification. In Advances in neural Information Processing Systems. Cambridge, MA:MIT Press,2000,12: 547-553.
[8]J. Weston and C. Watkins. Multi-class support vector machines. Technical report csd-tr-98-04, Royal Holloway, University of London, Surrey, England,1998.
[9]Takuya Inoue and Shigeo Abe. Fuzzy support vector machines for pattern classification. Neural Networks, Proceedings of IJCNN'01 International Joint Conference on 2001,2:1449-1454.
[10]Shigeo Abe and Takuya Inoue. Fuzzy support vector machines for multiclass problems. ESANN'2002 proceedings-European Symposium on Artificial Neural Networks. Bruges (Belgium), d-side public, ISBN-2-930307-02-1,2002,113-118.
[11]C. F. Lin and S. D. Wang. Fuzzy support vector machines. IEEE Transactions on Neural Network, 2002,13(2):464-471.
[12]H. P. Huang and Y. H. Liu. Fuzzy support vector machines for pattern recognition data mining. International Journal of Fuzzy Systems,2002,4(3):826-835.
[13]Kijsirikul. B., Ussivakul, Tsujinishi, D., et al. Fuzzy least squares support vector machines for multiclass problems, Neural Networks,2003,16:785-792.
[14]C. F. Lin, S. D. Wang. Training algorithm for fuzzy support vector machines with noisy data. Pattern Recognition Letters,2004,25:1647-1656.
[15]Joachims T. Making large-scale svm learning practical. In:Scholkopf B, Burges C J C, Smola Aeds., Advances in Kernel Methods - Supprot Vector Learning, Cambridge, MA:MIT Press,1998, 169-184.
[16]Platt J. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods - Support Vector Learning, edited by B. Scholkopf, C.J.C.Surges, and A.J. Smola, MIT Press,1999,185-208.
[17]J. Platt. Sequential minimal optimization:a fast algorithm for training support vector machines, Microsoft Research Technical Report MSR-TR-98-14,1998.
[18]S. K. Shevade, S. S. Keerthi, C. Bhattacharyya, et al. Improvements to the SMO algorithm for SVM regression, IEEE Trans. Neural Network,2000,11(5):1188-1193.
[19]S. S. Keerthi, S. K. Shevade, C. Bhattaacharyya, et al. Improvements to Platt's SMO algorithm for SVM classifier design, Neural Comput.,2001,13:637-649.
[20]B. H. Guang, K. Z. Mao, C. K. Siew, et al. Fast modular network implementation for support vector machines. IEEE Trans. Neural Network,2005,16(6):1651-1663.
[21]L. J. Cao, S. S. Keerthi, C. J. Ong, et al. Parallel sequential minimal optimization for the training of support vector machines. IEEE Transactions on Neural Networks,2006,17(4):1039-1049.
[22]Alfonso Rojas and Asoke K. Nandi. Practical scheme for fast detection and classification of rolling-element bearing faults using support vector machines. Mechanical Systems and Signal Processing,2006,20:1523-1536.
[23]J. X. Dong, Adam Krzyzak and C. Y. Suen. Fast SVM training algorithm with decomposition on very large data sets. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(4): 603-618.
[24]P. H. Chen, R. E. Fan and C. J. Lin. A study on SMO-type decomposition methods for support vector machines. IEEE Trans. Neural Network,2006,17:893-908.
[25]R. E. Fan, P. H. Chen and C.J. Lin. Working set selection using the second order information for training SVM. Technical report. Department of Computer Science, National Taiwan University, 2005.
[26]UCI Repository of machine learning databases and domain theories, FTP address:ftp:// ftp.ics.uci.edu/pub/machine-learning-databases.
[27]C. C. Chang and C. J. Lin. LIBSVM:A library for support vector machines [online]. Available: http://www.csie.ntu.edu.tw/-cjlin/libsvm/.
[2]V. N. Vapnik. The nature of statistical learning theory. New York:Springer, second edition,2000.
[3]G. M. Fung and O. L. Mangasarian. A feature selection Newton method for support vector machine classification. Computational Optimization and Applications,2004,28:185-202.
[4]G Fung and O. L. Mangasarian. Finite Newton method for Lagrangian support vector machine classification. Technical Report 02-01, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin,2002.
[5]Kreβel.U. H.-G. Pairwise classification and support vector machines. In B. Scholkopf, C. J. C. Burges and A. J. Smola (Eds.), Advances in kernel methods:Support vector learning, Cambridge, MA:MIT Press,1999,255-268.
[6]Bottou L, Cortes C, Dcnkcr J, et al. Comparison of Classifier Methods:A case study handwriting digit recognition. In International Conference on Pattern Recognition. IEEE Computer Society Press, 1994,77-87.
[7]J. C. Platt, N. Cristianini and J. Shawe-Taylor. Large margin DAG's for multiclass classification. In Advances in neural Information Processing Systems. Cambridge, MA:MIT Press,2000,12: 547-553.
[8]J. Weston and C. Watkins. Multi-class support vector machines. Technical report csd-tr-98-04, Royal Holloway, University of London, Surrey, England,1998.
[9]Takuya Inoue and Shigeo Abe. Fuzzy support vector machines for pattern classification. Neural Networks, Proceedings of IJCNN'01 International Joint Conference on 2001,2:1449-1454.
[10]Shigeo Abe and Takuya Inoue. Fuzzy support vector machines for multiclass problems. ESANN'2002 proceedings-European Symposium on Artificial Neural Networks. Bruges (Belgium), d-side public, ISBN-2-930307-02-1,2002,113-118.
[11]C. F. Lin and S. D. Wang. Fuzzy support vector machines. IEEE Transactions on Neural Network, 2002,13(2):464-471.
[12]H. P. Huang and Y. H. Liu. Fuzzy support vector machines for pattern recognition data mining. International Journal of Fuzzy Systems,2002,4(3):826-835.
[13]Kijsirikul. B., Ussivakul, Tsujinishi, D., et al. Fuzzy least squares support vector machines for multiclass problems, Neural Networks,2003,16:785-792.
[14]C. F. Lin, S. D. Wang. Training algorithm for fuzzy support vector machines with noisy data. Pattern Recognition Letters,2004,25:1647-1656.
[15]Joachims T. Making large-scale svm learning practical. In:Scholkopf B, Burges C J C, Smola Aeds., Advances in Kernel Methods - Supprot Vector Learning, Cambridge, MA:MIT Press,1998, 169-184.
[16]Platt J. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods - Support Vector Learning, edited by B. Scholkopf, C.J.C.Surges, and A.J. Smola, MIT Press,1999,185-208.
[17]J. Platt. Sequential minimal optimization:a fast algorithm for training support vector machines, Microsoft Research Technical Report MSR-TR-98-14,1998.
[18]S. K. Shevade, S. S. Keerthi, C. Bhattacharyya, et al. Improvements to the SMO algorithm for SVM regression, IEEE Trans. Neural Network,2000,11(5):1188-1193.
[19]S. S. Keerthi, S. K. Shevade, C. Bhattaacharyya, et al. Improvements to Platt's SMO algorithm for SVM classifier design, Neural Comput.,2001,13:637-649.
[20]B. H. Guang, K. Z. Mao, C. K. Siew, et al. Fast modular network implementation for support vector machines. IEEE Trans. Neural Network,2005,16(6):1651-1663.
[21]L. J. Cao, S. S. Keerthi, C. J. Ong, et al. Parallel sequential minimal optimization for the training of support vector machines. IEEE Transactions on Neural Networks,2006,17(4):1039-1049.
[22]Alfonso Rojas and Asoke K. Nandi. Practical scheme for fast detection and classification of rolling-element bearing faults using support vector machines. Mechanical Systems and Signal Processing,2006,20:1523-1536.
[23]J. X. Dong, Adam Krzyzak and C. Y. Suen. Fast SVM training algorithm with decomposition on very large data sets. IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(4): 603-618.
[24]P. H. Chen, R. E. Fan and C. J. Lin. A study on SMO-type decomposition methods for support vector machines. IEEE Trans. Neural Network,2006,17:893-908.
[25]R. E. Fan, P. H. Chen and C.J. Lin. Working set selection using the second order information for training SVM. Technical report. Department of Computer Science, National Taiwan University, 2005.
[26]UCI Repository of machine learning databases and domain theories, FTP address:ftp:// ftp.ics.uci.edu/pub/machine-learning-databases.
[27]C. C. Chang and C. J. Lin. LIBSVM:A library for support vector machines [online]. Available: http://www.csie.ntu.edu.tw/-cjlin/libsvm/.