Computer Science ›› 2018, Vol. 45 ›› Issue (5): 220-223.doi: 10.11896/j.issn.1002-137X.2018.05.037

Previous Articles     Next Articles

Multi-class Classification Algorithm for SVM Based on Hybrid Binary Tree Structure

LENG Qiang-kui, LIU Fu-de and QIN Yu-ping   

  • Online:2018-05-15 Published:2018-07-25

Abstract: In order to improve the classification efficiency of mutli-class support vector mechine,a multi-class classification algorithm for support vector machine(SVM) based on hybrid binary tree structure was proposed.In the structure,each internal node corresponds to a partition hyperplane,which is obtained as perpendicular bisectors of linking two centroid segements of the two farthest classes from each other.Each terminal node(i.e.,decision node) is associated with a SVM,whose training set is two sets of samples instead of two centroids.In general,the resulting classification model represents a hybrid form,consisting of hyperplanes and SVMs.The approximate hyperplanes by centroids can provide fast partition in the early stages of the training phase,whereas the SVMs will perform the final precise decision.Experimental results show that compared with the classical multi-class SVM,the proposed algorithm can reduce the computational time and improve the classification efficiency with similar classification accuracy.

Key words: SVM,Multi-class classification,Hybrid binary tree,Centroid representation

[1] VAPNIK V.The nature of statistical learning theory[M].New York:Springer-Verlag,1995.
[2] VAPNIK V.Statistical learning theory[M].New York:Wiley-Interscience,1998.
[3] HSU C W,LIN C J.A comparison of methods for multiclass support vector machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-425.
[4] ROKACH L.Ensemble-based classifiers[J].Artificial Intelli-gence Review,2010,33(1/2):1-39.
[5] KREβEL U H G.Pairwise classification and support vector machines[M]∥Advances in Kernel Methods.MIT Press,1999:255-268.
[6] LORENA A C,DE CARVALHO A C,GAMA J M P.A review on the combination of binary classifiers in multiclass problems[J].Artificial Intelligence Review,2008,30(1):19-37.
[7] PLATT J C,CRISTIANINI N,SHAWE-TAYLOR J.Largemargin DAGs for multiclass classification[C]∥12th International Conference on Neural Information Processing Systems,MIT Press.1999:547-553.
[8] KIJSIRIKUL B,USSIVAKUL N.Multiclass support vector machines using adaptive directed acyclic graph[C]∥2002 International Joint Conference on Neural Networks.IEEE,2002:980-985.
[9] BENNETT K P,BLUE J A.A support vector machine approach to decision trees[C]∥1998 IEEE International Joint Conference on Neural Networks.IEEE,1998:2396-2401.
[10] FEI B,LIU J.Binary tree of SVM:a new fast multiclass training and classification algorithm[J].IEEE Transactions on Neural Networks,2006,17(3):696-704.
[11] CHEONG S,SANG H,LEE S Y.Support vector machines with binary tree architecture for multi-class classification[J].Neural Information Processing Letters and Reviews,2004,2(3):47-51.
[12] KANG S,CHO S,KANG P.Multi-class classification via hetero-geneous ensemble of one-class classifiers[J].Engineering Applications of Artificial Intelligence,2015,43(C):35-43.
[13] TOMAR D,AGARWAL S.A comparison on multi-class classification methods based on least squares twin support vector machine[J].Knowledge-Based Systems,2015,81(C):131-147.
[14] YANG Z,WU H,LI C,et al.Least squares recursive projection twin support vector machine for multi-class classification[J].International Journal of Machine Learning and Cybernetics,2016,7(3):411-426.
[15] LIU M,ZHANG D,CHEN S,et al.Joint binary classifier lear-ning for ecoc-based multi-class classification[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,38(11):2335-2341.
[16] SONG Q,XIAO X,JIANG H,et al.A new multi-class classification method based on minimum enclosing balls[J].Journal of Mechanical Science and Technology,2015,29(8):3467-3473.
[17] KOSTIN A.A simple and fast multi-class piecewise linear pattern classifier[J].Pattern Recognition,2006,39(11):1949-1962.
[18] ARONSZAJN N.Theory of reproducing kernels[J].Transactions of the American Mathematical Society,1950,68(3):337-404.
[19] SNYDER W E,TANG D A.Finding the extrema of a region[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1980,2(3):266-269.
[20] BRAZDIL P,GAMA J.Statlog datasets [OL/DB].[2016-10-25].http://www.liacc.up.pt/ml/old/statlog/datasets.html.
[21] FRANK A,ASUNCION A.UCI machine learning repository [OL/DB].[2016-10-20].http://archive.ics.uci.edu/ml.
[22] CHANG C C,LIN C J.Libsvm:a library for support vector machines .[2016-10-26].http://www.csie.ntu.edu.tw/cjlin/libsvm.
[23] HSU C W,LIN C J.A comparison of methods for multiclasssupport vector machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-425.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!