Abstract
In large-scale multi-label classification framework, applications of non-linear kernel extended one-versus-rest multi-label support vector machine (OVR-ESVM) classification algorithm are severely restricted by excessive training time. To deal with this problem, we improve the OVR-ESVM classification algorithm and propose fast OVR-ESVM classification algorithm based on approximate extreme points (AEML-ESVM). The AEML-ESVM classification algorithm integrates the advantages of OVR-ESVM classification algorithm and binary approximate extreme points support vector machine (AESVM) classification algorithm. In other words, it can not only shorten the training time greatly, but also reflect label correlation of individual instance explicitly. Meanwhile, its classification performance is similar to that of the OVR-ESVM classification algorithm. Experiment results on three public data sets show that AEML-ESVM classification algorithm can substantially reduce training time and its classification performance is comparable with that of the OVR-ESVM classification algorithm. It also outperforms existing fast multi-label SVM classification algorithms in both training time and classification performance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Tsoumakas, G., Katakis, I., Vlahavas, I.: Mining multi-label data. In: Maimon, O., Rokach, L. (eds.) Data Mining and Knowledge Discovery Handbook, pp. 667–685. Springer, Heidelberg (2009)
Elghazel, H., Aussem, A., Gharroudi, O., Saadaoui, W.: Ensemble multi-label text categorization based on rotation forest and latent semantic indexing. Expert Syst. Appl. 57(C), 1–11 (2016)
Hou, S., Zhou, S., Chen, L., Feng, Y., Awudu, K.: Multi-label learning with label relevance in advertising video. Neurocomputing 171(C), 932–948 (2016)
Jing, X.Y., Wu, F., Li, Z., Hu, R., Zhang, D.: Multi-label dictionary learning for image annotation. IEEE Trans. Image Process. 25(6), 2712–2715 (2016)
Zufferey, D., Hofer, T., Hennebert, J., Schumacher, M., Ingold, R., Bromuri, S.: Performance comparison of multi-label learning algorithms on clinical data for chronic diseases. Comput. Biol. Med. 65(C), 34–43 (2015)
Liu, Y., Liu, Y., Wang, C., Wang, X.: What strikes the strings of your heart?-multi-label dimensionality reduction for music emotion analysis via brain imaging. IEEE Trans. Autonom. Mental Dev. 7(3), 176–188 (2015)
Gibaja, E., Ventura, S.: A tutorial on multi-label learning. ACM Comput. Surv. 47(3), 1–38 (2015)
Xu, J.: An extended one-versus-rest support vector machine for multi-label classification. Neurocomputing 74(17), 3114–3124 (2011)
Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20(3), 273–297 (1995)
Nandan, M., Khargonekar, P.P., Talathi, S.S.: Fast SVM training using approximate extreme points. J. Mach. Learn. Res. 15(1), 59–98 (2014)
Fürnkranz, J., Hüllermeier, E., Mencía, E.L., Brinker, K.: Multilabel classification via calibrated label ranking. Mach. Learn. 73(2), 133–153 (2008)
Tsang, I.W., Kwok, J.T., Cheung, P.M.: Core vector machines: fast SVM training on very large data sets. J. Mach. Learn. Res. 6(1), 363–392 (2005)
Wang, S., Wang, J., Wang, Z., Ji, Q.: Enhancing multi-label classification by modeling dependencies among labels. Pattern Recogn. 47(10), 3405–3413 (2014)
Zhou, Z.H., Zhang, M.L., Huang, S.J., Li, Y.F.: Multi-instance multi-label learning. Artif. Intell. 176(1), 2291–2320 (2012)
Luaces, O., Díez, J., Barranquero, J., Coz, J.J., Bahamonde, A.: Binary relevance efficacy for multilabel classification. Prog. Artif. Intell. 1(4), 303–313 (2012)
Clare, A., King, R.D.: Knowledge discovery in multi-label phenotype data. In: Raedt, L., Siebes, A. (eds.) PKDD 2001. LNCS (LNAI), vol. 2168, pp. 42–53. Springer, Heidelberg (2001). doi:10.1007/3-540-44794-6_4
Elisseeff, A., Weston, J.: A kernel method for multi-labelled classification. In: Advances in Neural Information Processing Systems, pp. 681–687 (2001)
Xu, J.: Fast Multi-label core vector machine. Pattern Recogn. 46(3), 885–898 (2013)
Zhang, M.L., Zhou, Z.H.: Multi-label neural networks with applications to functional genomics and text categorization. IEEE Trans. Knowl. Data Eng. 18(10), 1338–1351 (2006)
Boutell, M.R., Luo, J., Shen, X., et al.: Learning multi-label scene classification. Pattern Recogn. 37(9), 1757–1771 (2004)
Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(3), 27 (2011)
Platt, J.C.: Fast training of support vector machines using sequential minimal optimization. In: Advances in Kernel Methods, pp. 185–208 (1999)
LIBSVM datasets. https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/
Zhang, M.L., Zhou, Z.H.: A review on multi-label learning algorithms. IEEE Trans. Knowl. Data Eng. 26(8), 1819–1837 (2014)
Schapire, R.E., Singer, Y.: BoosTexter: a boosting-based system for text categorization. Mach. Learn. 39(2), 135–168 (2000)
Acknowledgments
This work is supported by the National Natural Science Foundation of China (NSFC) under the grant number 61170258, 61103196, 61379127, 61379128, 61572448, by the National Key R&D Program of China under the grant number 2016YFC1401900 and by the Shandong Provincial Natural Science Foundation of China under the grant number ZR2014JL043.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Sun, Z., Guo, Z., Wang, X., Liu, J., Liu, S. (2017). Fast Extended One-Versus-Rest Multi-label SVM Classification Algorithm Based on Approximate Extreme Points. In: Candan, S., Chen, L., Pedersen, T., Chang, L., Hua, W. (eds) Database Systems for Advanced Applications. DASFAA 2017. Lecture Notes in Computer Science(), vol 10177. Springer, Cham. https://doi.org/10.1007/978-3-319-55753-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-55753-3_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55752-6
Online ISBN: 978-3-319-55753-3
eBook Packages: Computer ScienceComputer Science (R0)