×

Imbalanced data classification using second-order cone programming support vector machines. (English) Zbl 1339.68227

Summary: Learning from imbalanced data sets is an important machine learning challenge, especially in Support Vector Machines (SVM), where the assumption of equal cost of errors is made and each object is treated independently. Second-order cone programming SVM (SOCP-SVM) studies each class separately instead, providing quite an interesting formulation for the imbalanced classification task. This work presents a novel second-order cone programming (SOCP) formulation, based on the LP-SVM formulation principle: the bound of the VC dimension is loosened properly using the \(l_\infty\)-norm, and the margin is directly maximized using two margin variables associated with each class. A regularization parameter \(C\) is considered in order to control the trade-off between the maximization of these two margin variables. The proposed method has the following advantages: it provides better results, since it is specially designed for imbalanced classification, and it reduces computational complexity, since one conic restriction is eliminated. Experiments on benchmark imbalanced data sets demonstrate that our approach accomplishes the best classification performance, compared with the traditional SOCP-SVM formulation and with cost-sensitive formulations for linear SVM.

MSC:

68T05 Learning and adaptive systems in artificial intelligence

Software:

UCI-ml; KEEL; SeDuMi; Spider
Full Text: DOI

References:

[1] Alcalá-Fdez, J.; Sánchez, L.; García, S.; del Jesus, M. J.; Ventura, S.; Garrell, J. M.; Otero, J.; Romero, C.; Bacardit, J.; Rivas, V. M.; Fernández, J. C.; Herrera, F., Keel: A software tool to assess evolutionary algorithms to data mining problems, Soft Comput., 13, 3, 307-318 (2009)
[2] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Progr., 95, 3-51 (2003) · Zbl 1153.90522
[3] Alvarez, F.; López, J.; Ramírez, H. C., Interior proximal algorithm with variable metric for second-order cone programmingapplications to structural optimization and support vector machines, Optim. Methods Softw., 25, 6, 859-881 (2010) · Zbl 1226.90041
[5] R Bach, F.; Heckerman, D.; Horvitz, E., Considering cost asymmetry in learning classifiers, J. Mach. Learn. Res., 7, 1713-1741 (2006) · Zbl 1222.68137
[7] Bhattacharyya, C., Second order cone programming formulations for feature selection, J. Mach. Learn. Res., 5, 1417-1433 (2004) · Zbl 1222.68147
[8] Chawla, N. V.; Hall, L. O.; Bowyer, K. W.; Kegelmeyer, W. P., SmoteSynthetic minority oversampling technique, J. Artif. Intell. Res., 16, 321-357 (2002) · Zbl 0994.68128
[9] Chawla, N. V.; Japkowicz, N.; Kotcz, A., Editorialspecial issue on learning from imbalanced data sets, SIGKDD Explor., 6, 1-6 (2004)
[10] Cortes, C.; Vapnik, V., Support-vector networks, Mach. Learn., 20, 273-297 (1995) · Zbl 0831.68098
[12] Fawcett, T.; Provost, F., Adaptive fraud detection, Data Min. Knowl. Discov., 1, 291-316 (1997)
[13] Fernández-Navarro, F.; Hervás-Martínez, C.; Gutiérrez, P. A., A dynamic over-sampling procedure based on sensitivity for multi-class problems, Pattern Recognit., 44, 1821-1833 (2011) · Zbl 1218.68121
[14] He, H.; García, E., Learning from imbalanced data, IEEE Trans. Knowl. Data Eng., 21, 1263-1284 (2009)
[16] Khoshgoftaar, T. M.; Van Hulse, J.; Napolitano, A., An exploration of learning when data is noisy and imbalanced, Intell. Data Anal., 15, 215-236 (2011)
[17] Kumar, D. A.; Ravi, V., Predicting credit card customer churn in banks using data mining, Int. J. Data Anal. Tech. Strateg., 1, 4-28 (2008)
[18] Lanckriet, G.; Ghaoui, L. E.; Bhattacharyya, C.; Jordan, M., A robust minimax approach to classification, J. Mach. Learn. Res., 3, 555-582 (2003) · Zbl 1084.68657
[19] Maldonado, S.; Weber, R., A wrapper method for feature selection using support vector machines, Inf. Sci., 179, 2208-2217 (2009)
[20] Maldonado, S.; Weber, R.; Basak, J., Kernel-penalized SVM for feature selection, Inf. Sci., 181, 1, 115-128 (2011)
[21] Mangasarian, O. L., A finite newton method for classification, Optim. Methods Softw., 17, 5, 913-929 (2002) · Zbl 1065.90078
[23] Peng, X., Building sparse twin support vector machine classifiers in primal space, Inf. Sci., 181, 18, 3967-3980 (2011)
[24] Pichara, K.; Soto, A., Active learning and subspace clustering for anomaly detection, Intell. Data Anal., 15, 151-171 (2011)
[26] Raskutti, B.; Kowalczyk, A., Extreme rebalancing for SVMSa case study, ACM SIGKDD Explor. Newslett., 6, 60-69 (2004), (Special Issue on Learning from Imbalanced Datasets)
[28] Schölkopf, B.; Smola, A. J., Learning with Kernels (2002), MIT Press
[29] Shivaswamy, P. K.; Bhattacharyya, C.; Smola, A. J., Second order cone programming approaches for handling missing and uncertain data, J. Mach. Learn. Res., 7, 1283-1314 (2006) · Zbl 1222.68305
[31] Sturm, J. F., Using sedumi 10.2, a matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 12, 625-653 (1999), (Special Issue on Interior Point Methods (CD supplement with software)) · Zbl 0973.90526
[32] Sun, Y. M.; Kamel, M. S.; Wong, A. K.C.; Wang, Y., Cost-sensitive boosting for classification of imbalanced data, Pattern Recognit., 40, 3358-3378 (2007) · Zbl 1122.68505
[34] Tax, D. M.J.; Duin, R., Support vector data description, Mach. Learn., 54, 45-66 (2004) · Zbl 1078.68728
[35] Vapnik, V., Statistical Learning Theory (1998), John Wiley and Sons · Zbl 0935.62007
[36] Wang, J.; You, J.; Li, Q.; Xu, Y., Extract minimum positive and maximum negative features for imbalanced binary classification, Pattern Recognit., 45, 1136-1145 (2012)
[37] Weiss, G. M., Mining with raritya unifying framework, ACM SIGKDD Explor. Newslett., 6, 7-19 (2004)
[39] Zheng, Z.; Wu, X.; Srihari, R., Feature selection for text categorization on imbalanced data, SIGKDD Explor., 6, 80-89 (2004)
[40] Zhou, W.; Zhang, L.; Jiao, L., Linear programming support vector machines, Pattern Recognit., 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.