Computer Science ›› 2022, Vol. 49 ›› Issue (6A): 297-300.doi: 10.11896/jsjkx.210400149

• Big Data & Data Science • Previous Articles     Next Articles

Acceleration of SVM for Multi-class Classification

CHEN Jing-nian   

  1. Department of Information and Computing Science,Shandong University of Finance and Economics,Jinan 250014,China
  • Online:2022-06-10 Published:2022-06-08
  • About author:CHEN Jing-nian,born in 1970,Ph.D,professor,supervisor,is a senior member of China Computer Federation.His main research interests include big data analysis,intelligent information processing.
  • Supported by:
    National Natural Science Foundation of China(61773325).

Abstract: With excellent classification effect and solid theoretical foundation,support vector machines have become one of the most important classification method in the field of pattern recognition,machine learning and data mining in recent years.How-ever,their training time becomes much longer with the increase of training instances.In the case of multi-class classification,the training process will become even more complex.To deal with above problems,a fast data reduction method named as MOIS is proposed for multi-class classification.With cluster centers being used as reference points,redundent instances can be deleted,bound instances crucial for the trainning can be selected,and the distribution imbalance between classes can also be relieved by the proposed method.Experiments show that MOIS can enormously improve the training efficiency while keeping or even improving the classification accuracy.For example,on Optdigit dataset,the classification accuracy is increased from 98.94% to 99.05%,while the training time is reduced to 0.15% of the original.What's more,on the dataset formed by the first 100 classes of HCL2000,the training time of the proposed method is reduced to less than 6% of original,while the accuracy is improved slightly from 99.29% to 99.30%.Furthermore,MIOS is highly efficient.

Key words: Clustering, Data reduction, Instance seletion, Multi-class classification, Support vector machines

CLC Number: 

  • TP391
[1] VAPNIK V.The nature of statistical learning theory[M].New York:Springer,1995.
[2] DONG J,KRZYZAK A,SUEN C Y.Fast SVM training algorithm with decomposition on very large data sets[J].IEEE Trans. Pattern Analysis and Machine Intelligence,2005,27(4):603-618.
[3] YANG B Q,GUAN X P,ZHU J W,et al.SVMs multi-class loss feedback based discriminative dictionary learning for image classification[J].Pattern Recognition,2020,112(12):76-90.
[4] ZHANG X D,LI A,PAN R.Stock trend prediction based on new status box method and adaboost probabilistic support vector machine[J].Applied Soft Computing,2016,49:385-398.
[5] RAMÍREZ J,GÓRRIZ J,SALAS-GONZALEZ D,et al.Com-puter-aided diagnosis of alzheimer's type dementia combining support vector machines and discriminant set of features[J].Information Sciences,2013,237:59-72.
[6] KEERTHI S S,SHEVADE S K,BHATTACHARYYA C,et al.Improvements to platt's SMO algorithm for SVM classifier design[J].Neural Computation,2001,13(3):637-649.
[7] MANGASARIAN O L,MUSICANT D R.Successive overrela-xation for support vector machines[J].IEEE Transactions on Neural Networks,1999,10(5):1032-1037.
[8] VAPNIK V.Estimation of dependences based on empirical data[M].New York:Springer,2006.
[9] CHANG C C,LIN C J.LIBSVM:A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):1-27.
[10] BURGES C J.A tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery,1998,2:121-167.
[11] ALMEIDA M B,BRAGA A P,BRAGA J P.SVM-KM:Spee-ding SVMs learning with a priori cluster selection and k-means[C]//Brazilian symposium on neural networks.Brazil Computer Society,2000:162-167.
[12] LI H L,WANG C H,YUAN B Z,et al.A Learning Strategy of SVM Used to Large Training Set[J].Chinese Journal of Computers,2004,27(5):715-719.
[13] SHIN H,CHO S.Neighborhood property based pattern selection for support vector machines[J].Neural Computation,2007,19(3):816-855.
[14] ANGIULLI F,ASTORINO A.Scaling up support vector machines using nearest neighbor condensation[J].IEEE Transactions on Neural Networks,2010,21(2):351-357.
[15] LI Y,MAGUIRE L.Selecting critical patterns based on local geometrical and statistical information[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(6):1189-1201.
[16] KIM D,KANG S,CHO S.Expected margin-based pattern selection for support vector machines[J].Expert Systems With Applications,2020,139:1-12.
[17] HETTICH S,BLAKE C L,MERZ C J.UCI Repository of machine learning databases[EB/OL].http//
[18] ZHANG H,GUO J,CHEN G,et al.HCL2000—A Large-scale Handwritten Chinese Character Database for Handwritten Character Recognition[C]//International Conference on Document Analysis and Recognition.IEEE Computer Society,2009:286-289.
[19] LIU C L,NAKASHIMA K,SAKO H,et al.Handwritten digit recognition:investigation of normalization and feature extraction techniques[J].Pattern Recognition,2004,37(2):265-279.
[1] CHAI Hui-min, ZHANG Yong, FANG Min. Aerial Target Grouping Method Based on Feature Similarity Clustering [J]. Computer Science, 2022, 49(9): 70-75.
[2] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[3] YU Shu-hao, ZHOU Hui, YE Chun-yang, WANG Tai-zheng. SDFA:Study on Ship Trajectory Clustering Method Based on Multi-feature Fusion [J]. Computer Science, 2022, 49(6A): 256-260.
[4] MAO Sen-lin, XIA Zhen, GENG Xin-yu, CHEN Jian-hui, JIANG Hong-xia. FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition [J]. Computer Science, 2022, 49(6A): 285-290.
[5] CHEN Jia-zhou, ZHAO Yi-bo, XU Yang-hui, MA Ji, JIN Ling-feng, QIN Xu-jia. Small Object Detection in 3D Urban Scenes [J]. Computer Science, 2022, 49(6): 238-244.
[6] Ran WANG, Jiang-tian NIE, Yang ZHANG, Kun ZHU. Clustering-based Demand Response for Intelligent Energy Management in 6G-enabled Smart Grids [J]. Computer Science, 2022, 49(6): 44-54.
[7] XING Yun-bing, LONG Guang-yu, HU Chun-yu, HU Li-sha. Human Activity Recognition Method Based on Class Increment SVM [J]. Computer Science, 2022, 49(5): 78-83.
[8] ZHU Zhe-qing, GENG Hai-jun, QIAN Yu-hua. Line-Segment Clustering Algorithm for Chemical Structure [J]. Computer Science, 2022, 49(5): 113-119.
[9] ZHANG Yu-jiao, HUANG Rui, ZHANG Fu-quan, SUI Dong, ZHANG Hu. Study on Affinity Propagation Clustering Algorithm Based on Bacterial Flora Optimization [J]. Computer Science, 2022, 49(5): 165-169.
[10] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[11] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[12] HAN Jie, CHEN Jun-fen, LI Yan, ZHAN Ze-cong. Self-supervised Deep Clustering Algorithm Based on Self-attention [J]. Computer Science, 2022, 49(3): 134-143.
[13] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[14] ZHANG Ya-di, SUN Yue, LIU Feng, ZHU Er-zhou. Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index [J]. Computer Science, 2022, 49(1): 121-132.
[15] LUO Yue-tong, WANG Tao, YANG Meng-nan, ZHANG Yan-kong. Historical Driving Track Set Based Visual Vehicle Behavior Analytic Method [J]. Computer Science, 2021, 48(9): 86-94.
Full text



No Suggested Reading articles found!