Optimal arrangements of hyperplanes for SVM-based multiclass classification. (English) Zbl 1474.62213

Summary: In this paper, we present a novel SVM-based approach to construct multiclass classifiers by means of arrangements of hyperplanes. We propose different mixed integer (linear and non linear) programming formulations for the problem using extensions of widely used measures for misclassifying observations where the kernel trick can be adapted to be applicable. Some dimensionality reductions and variable fixing strategies are also developed for these models. An extensive battery of experiments has been run which reveal the powerfulness of our proposal as compared with other previously proposed methodologies.


62H30 Classification and discrimination; cluster analysis (statistical aspects)
90C11 Mixed integer programming
68T05 Learning and adaptive systems in artificial intelligence
32S22 Relations with arrangements of hyperplanes
Full Text: DOI arXiv


[1] Agarwal, N.; Balasubramanian, Vn; Jawahar, C., Improving multiclass classification by deep networks using DAGSVM and triplet loss, Pattern Recognit Lett, 112, 184-190 (2018)
[2] Allwein, El; Schapire, Re; Singer, Y., Reducing multiclass to binary. Reducing multiclass to binary: a unifying approach for margin classifiers, J Mach Learn Res, 1, 113-141 (2001) · Zbl 1013.68175
[3] Bagirov, Am; Ugon, J.; Webb, D.; Ozturk, G.; Kasimbeyli, R., A novel piecewise linear classifier based on polyhedral conic and max-min separabilities, TOP, 21, 1, 3-24 (2013) · Zbl 1263.65051
[4] Bahlmann C, Haasdonk B, Burkhardt H (2002) On-line handwriting recognition with support vector machines-a kernel approach. In: Eighth international workshop on frontiers in handwriting recognition, pp 49-54
[5] Benders, Jf, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302
[6] Benítez-Peña, S.; Blanquero, R.; Carrizosa, E.; Ramírez-Cobo, P., On support vector machines under a multiple-cost scenario, Adv Data Anal Classif (2018) · Zbl 1474.62211
[7] Bennett, Kp; Demiriz, A., Semi-supervised support vector machines, Adv Neural Inf Process Syst, 11, 368-374 (1999)
[8] Blanco, V.; Ben Ali, S.; Puerto, J., Revisiting several problems and algorithms in continuous location with \(\ell_p\) norms, Comput Optim Appl, 58, 3, 563-595 (2014) · Zbl 1297.90073
[9] Blanco, V.; Puerto, J.; Salmerón, R., Locating hyperplanes to fitting set of points: a general framework, Comput Oper Res, 95, 172-193 (2018) · Zbl 1458.90467
[10] Blanco V, Japón A, Puerto J (2019) Optimal arrangements of hyperplanes for multiclass classification. arXiv preprint: arXiv:1810.09167
[11] Blanco V, Puerto J, Rodríguez-Chía A M (2019) On \(\ell_p \)-Support Vector Machines and Multidimensional Kernels. arXiv preprint: arXiv:1711.10332
[12] Cortes, C.; Vapnik, V., Support-vector networks, Mach Learn, 20, 3, 273-297 (1995) · Zbl 0831.68098
[13] Cover, T.; Hart, P., Nearest neighbor pattern classification, IEEE Trans Inf Theory, 13, 21-27 (1967) · Zbl 0154.44505
[14] Crammer, K.; Singer, Y., On the algorithmic implementation of multiclass kernel-based vector machines, J Mach Learn Res, 2, 265-292 (2001) · Zbl 1037.68110
[15] Dietterich, Tg; Bakiri, G., Solving multiclass learning problems via error-correcting output codes, J Artif Intell Res, 2, 263-286 (1995) · Zbl 0900.68358
[16] Geoffrion, Am, Generalized Benders decomposition, J Optim Theory Appl, 10, 4, 237-260 (1972) · Zbl 0229.90024
[17] Ghaddar, B.; Naoum-Sawaya, J., High dimensional data classification and feature selection using support vector machines, Eur J Oper Res, 265, 3, 993-1004 (2018) · Zbl 1381.62170
[18] Guermeur, Y.; Monfrini, E., A quadratic loss multi-class SVM for which a radius-margin bound applies, Informatica, 22, 1, 73-96 (2011) · Zbl 1263.68132
[19] Harris, T., Quantitative credit risk assessment using support vector machines: broad versus narrow default definitions, Expert Syst Appl, 40, 11, 4404-4413 (2013)
[20] Horn, D.; Demircioglu, A.; Bischl, B.; Glasmachers, T.; Weihs, C., A comparative study on large scale kernelized support vector machines, Adv Data Anal Classif, 12, 4, 867-883 (2016) · Zbl 1416.68144
[21] Ikeda, K.; Murata, N., Geometrical properties of Nu support vector machines with different norms, Neural Comput, 17, 11, 2508-2529 (2005) · Zbl 1075.68074
[22] Ikeda, K.; Murata, N., Effects of norms on learning properties of support vector machines, Proc IEEE Int Conf Acoust Speech Signal Process, 5, 241-244 (2005)
[23] Kašćelan, V.; Kašćelan, L.; Novović Burić, M., A nonparametric data mining approach for risk prediction in car insurance: a case study from the montenegrin market, Econ Res Ekonomska istraživanja, 29, 1, 545-558 (2016)
[24] Labbé, M.; Martínez-Merino, Li; Rodríguez-Chía, Am, Mixed integer linear programming for feature selection in support vector machine, Discrete Appl Math, 261, 276-304 (2018) · Zbl 1420.90038
[25] Lauer, F.; Guermeur, Y., MSVMpack: a multi-class support vector machine package, J Mach Learn Res, 12, 2269-2272 (2011) · Zbl 1280.68175
[26] Lee, Y.; Lin, Y.; Wahba, G., Multicategory support vector machines: theory and application to the classification of microarray data and satellite radiance data, J Am Stat Assoc, 99, 465, 67-81 (2004) · Zbl 1089.62511
[27] Lewis, David D., Naive (Bayes) at forty: The independence assumption in information retrieval, Machine Learning: ECML-98, 4-15 (1998), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg
[28] Lichman M (2013) UCI machine learning repository. https://archive.ics.uci.edu. Accessed Oct 2018
[29] López, J.; Maldonado, S.; Carrasco, M., Double regularization methods for robust feature selection and SVM classification via DC programming, Inf Sci, 429, 377-389 (2018)
[30] Majid, A.; Ali, S.; Iqbal, M.; Kausar, N., Prediction of human breast and colon cancers from imbalanced data using nearest neighbor and support vector machines, Comput Methods Progr Biomed, 113, 3, 792-808 (2014)
[31] Maldonado, S.; Pérez, J.; Weber, R.; Labbé, M., Feature selection for support vector machines via mixed integer linear programming, Inf Sci, 279, 163-175 (2014) · Zbl 1354.68226
[32] Mangasarian, Ol, Arbitrary-norm separating plane, Oper Res Lett, 24, 1-2, 15-23 (1999) · Zbl 1028.90037
[33] Meyer D, Dimitriadou E, Hornik K, Weingessel A, Leisch F (2017) e1071: misc functions of the department of statistics, probability theory group (Formerly: E1071), TU Wien. R package version 1.6-8. https://CRAN.R-project.org/package=e1071. Accessed Oct 2018
[34] Ortigosa-Hernández, J.; Inza, I.; Lozano, Ja, Semisupervised multiclass classification problems with scarcity of labeled data: a theoretical study, IEEE Trans Neural Netw Learn Syst, 27, 12, 2602-2614 (2016)
[35] Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learn: machine learning in Python, J Mach Learn Res, 12, 2825-2830 (2011) · Zbl 1280.68189
[36] Platt, Jc; Cristianini, N.; Shawe-Taylor, J.; Solla, Sa; Leen, Tk; Mülle, K., Large margin DAGs for multiclass classification, Advances in neural information processing systems, 547-553 (2000), Cambridge: The MIT Press, Cambridge
[37] Radhimeenakshi S (2016) Classification and prediction of heart disease risk using data mining techniques of support vector machine and artificial neural network. In: International conference on computing for sustainable global development, INDIACom, pp 3107-3111
[38] Tang, X.; Xu, A., Multi-class classification using kernel density estimation on k-nearest neighbours, Electron Lett, 52, 8, 600-602 (2016)
[39] Üney, F.; Türkay, M., A mixed-integer programming approach to multi-class data classification problem, Eur J Oper Res, 173, 3, 910-920 (2006) · Zbl 1131.90435
[40] Van Den Burg, Gjj; Groenen, Pjf, GenSVM: a generalized multiclass support vector machine, J Mach Learn Res, 17, 225, 1-42 (2016) · Zbl 1404.68127
[41] Weston J, Watkins C (1999) Support vector machines for multi-class pattern recognition. In: European symposium on artificial neural networks, pp 219-224
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.