Mixed integer linear programming for feature selection in support vector machine. (English) Zbl 1420.90038

Summary: This work focuses on support vector machine (SVM) with feature selection. A MILP formulation is proposed for the problem. The choice of suitable features to construct the separating hyperplanes has been modeled in this formulation by including a budget constraint that sets in advance a limit on the number of features to be used in the classification process. We propose both an exact and a heuristic procedure to solve this formulation in an efficient way. Finally, the validation of the model is done by checking it with some well-known data sets and comparing it with classical classification methods.


90C11 Mixed integer programming


Full Text: DOI arXiv


[1] Alon, U.; Barkai, N.; Notterman, D.; Gish, K.; Ybarra, S.; Mack, D.; Levine, A., Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligo-nucleotide arrays, Proc. Natl. Acad. Sci., 6745-6750, (1999)
[2] Angelelli, E.; Mansini, R.; Grazia Speranza, M., Kernel search: A general heuristic for the multi-dimensional knapsack problem, Comput. Oper. Res., 37, 11, 2017-2026, (2010) · Zbl 1188.90207
[3] Angelelli, E.; Mansini, R.; Speranza, M., Kernel search: A new heuristic framework for portfolio selection, Comput. Optim. Appl., 51, 1, 345-361, (2012) · Zbl 1246.91119
[4] A. Asuncion, D. Newman, UCI machine learning repository, 2007. URL http://www.ics.uci.edu/ mlearn/MLRepository.html.
[5] Aytug, H., Feature selection for support vector machines using generalized benders decomposition, European J. Oper. Res., 244, 1, 210-218, (2015) · Zbl 1347.62105
[6] Belotti, P.; Bonami, P.; Fischetti, M.; Monacci, M.; Nogales-Gómez, A.; Salvagnin, D., On handling indicator constraints in mixed integer programming, Comput. Optim. Appl., 65, 1545-1566, (2016)
[7] Bradley, P. S.; Mangasarian, O. L., Feature selection via concave minimization and support vector machines, ICML, 98, 82-90, (1998)
[8] Burges, C. J.C., A tutorial on support vector machines for pattern recognition, Data Min. Knowl. Discov., 2, 2, 121-167, (1998)
[9] Carrizosa, E.; Martín-Barragán, B.; Morales, D. R., Binarized support vector machines, INFORMS J. Comput., 22, 1, 154-167, (2010) · Zbl 1243.62088
[10] Cortes, C.; Vapnik, V., Support-vector networks, Mach. Learn., 20, 3, 273-297, (1995) · Zbl 0831.68098
[11] Gaudioso, G. E.M.; Labbé, M.; Rodríguez-Chía, A. M., Lagrangian relaxation for svm feature selection, Comput. Oper. Res., 87, 137-145, (2017) · Zbl 1391.90430
[12] Golub, T.; Slonim, D.; Tamayo, P.; Huard, C.; Gaasenbeek, M.; Merisov, J.; Coller, H.; Loh, M.; Downing, J.; Caligiuri, M.; Bloomfield, C.; Lander, E., Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring, Science, 286, 531-537, (1999)
[13] Guastaroba, G.; Speranza, M., Kernel search for the capacitated facility location problem, J. Heuristics, 18, 6, 877-917, (2012)
[14] Guyon, I.; Gunn, S.; Nikravesh, M.; Zadeh, L., Feature Extraction, Foundations and Applications, (2006), Springer: Springer Berlin
[15] Guyon, I.; Weston, J.; Barnhill, S.; Vapnik, V., Gene selection for cancer classification using support vector machines, Mach. Learn., 46, 1-3, 389-422, (2002) · Zbl 0998.68111
[16] Maldonado, S.; Pérez, J.; Weber, R.; Labbé, M., Feature selection for support vector machines via mixed integer linear programming, Inform. Sci., 279, 163-175, (2014) · Zbl 1354.68226
[17] Mangasarian, O., Linear and nonlinear separation of patterns by linear programming, Oper. Res., 13, 444-452, (1965) · Zbl 0127.36701
[18] Mangasarian, O., Multi-surface method of pattern separationg, IEEE Trans. Inform. Theory., 14, 801-807, (1968) · Zbl 0169.51108
[19] Notterman, D.; Alon, U.; Sierk; Levine, A., Transcriptional gene expression profiles of colorectal adenoma, adenocarcinoma, and normal tissue examined by oligonucleotide arrays, Cancer Res., 61, 3124-3130, (2001)
[20] Shipp, M.; Ross, K.; Tamayo, P.; Weng, A. P.; Kutok, J.; Aguiar, R.; Gaasenbeek, M.; Angelo, M.; Reich, M.; Pinkus, G.; Ray, T.; Koval, M.; Last, K.; Norton, A.; Lister, T.; Mesirov, J.; Neuberg, D.; Lander, E.; Aster, J.; G., T. R., Diffuse large b-cell lymphoma outcome prediction by gene-expression profiling and supervised machine learning, Nat. Med., 8, 68-74, (2002)
[21] Vapnik, V., Statistical Learning Theory, (1998), John Wiley and Sons · Zbl 0935.62007
[22] Zhou, W.; Zhang, L.; Jiao, L., Linear programming support vector machines, Pattern Recog., 35, 2927-2936, (2002) · Zbl 1010.68108
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.