1.华南理工大学 计算机科学与工程学院 广州 510641 2.Faculty of Information Technology, University of Technology, Sydney, NSW 2007, Australia 3.广州亚运会组委会 信息技术部 广州 510623
Alternating Iterative One-against-One Algorithm
LIU Bo1, 2, HAO Zhi-Feng1, XIAO Yan-Shan3
1.College of Computer Science and Engineering, South China University of Technology, Guangzhou 5106402. Faculty of Information Technology, University of Technology, Sydney, NSW 2007, Australia3. Department of Information Technology, Guangzhou Asian Games Organizing Committee, Guangzhou 510623
Abstract:One-against-one algorithm shows good performance in the multi-class classification algorithm based on SVMs. However, the existing middle unclassifiable region in the algorithm has a bad influence on its performance. To overcome this drawback, a method called alternating iterative one-against-one algorithm is proposed. And the validity analysis and computational complexity of the proposed algorithm are presented. Finally, one-against-one, fuzzy support vector machine (FSVM), decision directed acyclic graph (DDAG) and the proposed algorithm are compared on UCI datasets. The experimental results show that the proposed algorithm resolves the unclassifiable region problem effectively and its performance is better than that of the others.
[1] Vapnik V N. The Nature of Statistical Learning Theory. London, UK: Springer-Verlag, 1995 [2] Allwein E L, Schapire R E, Singer Y. Reducing Multiclass to Binary: A Unifying Approach for Margin Classifiers. Journal of Machine Learning Research, 2001, 1(2): 113-141 [3] Rifkin R, Klautau A. In Defense of One-vs-All Classification. Journal of Machine Learning Research, 2004, 5(2): 101-141 [4] Bredensteniner E J, Bennett K P. Multicategory Classification by Support Vector Machines. Computational Optimization and Applications, 1999, 12(1/2/3): 53-79 [5] Vapnik V N. Statistical Learning Theory. New York, USA: John Wiley & Sons, 1998 [6] Inoue T, Abe S. Fuzzy Support Vector Machines for Pattern Classification // Proc of the International Joint Conference on Neural Networks. Washington, USA, 2001, Ⅱ: 1449-1454 [7] Abe S. Analysis of Multiclass Support Vector Machines // Proc of the International Conference on Computational Intelligence for Modelling Control and Automation. Vienna, Austria, 2003: 385-396 [8] KreBel U H G. Pairwise Classification and Support Vector Machines // Schlkopf B, Burges C J, Smola A J, eds. Advances in Kernel Methods: Support Vector Learning. Cambridge, USA: MIT Press, 1999: 255-268 [9] Platt J C, Cristianini N, Shawe-Jaylor J. Large Margin DAGs for Multiclass Classification // Solla S A, Leen T K, Müller K R, eds. Advances in Neural Information Processing Systems. Cambridge, USA: MIT Press, 2000, 12: 547-553 [10] Pontil M, Verri A. Support Vector Machine for 3D Object Recognition. IEEE Trans on Pattern Analysis and Machine Intelligence, 1998, 20(6): 637-646 [11] Kijsirikul B, Ussivakul N. Multiclass Support Vector Machines Using Adaptive Directed Acyclic Graph // Proc of the International Joint Conference on Neural Networks. Honolulu, USA, 2002, Ⅰ: 980-985 [12] Tsujinishi D, Abe S. Fuzzy Least Squares Support Vector Machines for Multiclass Problems. Neural Network, 2003, 16(5/6): 785-792 [13] Angulo C, Parra X, Català A. K-SVCR: A Support Vector Machine for Multi-Class Classification. Neurocomputing, 2003, 55(1/2): 57-77 [14] Hao Zhifeng, Liu Bo, Yang Xiaowei, et al. Twi-Map Support Vector Machine for Multi-Classification Problems // Proc of the 2nd International Symposium on Neural Networks. Chongqing, China, 2005, Ⅰ: 869-874 [15] Dietterich T G, Bakiri G. Solving Multiclass Learning Problems via Error-Correcting Output Code. Journal of Artificial Intelligence Research, 1995, 2: 263-286 [16] Tomonori K, Shigeo A. Comparison between Error Correcting Output Codes and Fuzzy Support Vector Machines. Pattern Recognition Letters, 2005, 26(12): 1937-1945 [17] Fürnkranz J. Round Robin Classification. Journal of Machine Learning Research, 2002, 2(4): 721-747 [18] Hsu C W, Lin C J. A Comparison of Methods for Multiclass Support Vector Machines. IEEE Trans on Neural Networks, 2002, 13(2): 415-425 [19] Gestel T V, Suykens J A K. Benchmarking Least Squares Support Vector Machine Classifiers. Machine Learning, 2004, 54(1): 5-32 [20] Murphy P M, Aha D W. UCI Repository of Machine Learning Database [DB/OL]. [2004-02-18]. http://www.ics.uci.edu/~mlearn/MLRepository.html.