Abstract
In this paper, we consider a binary supervised classification problem, called spherical separation, that consists of finding, in the input space or in the feature space, a minimal volume sphere separating the set \({\mathcal{A}}\) from the set \({\mathcal{B}}\) (i.e. a sphere enclosing all points of \({ \mathcal{A}}\) and no points of \({\mathcal{B}}\)). The problem can be cast into the DC (Difference of Convex functions) programming framework and solved by DCA (DC Algorithm) as shown in the works of Astorino et al. (J Glob Optim 48(4):657–669, 2010). The aim of this paper is to investigate more attractive DCA based algorithms for this problem. We consider a new optimization model and propose two interesting DCA schemes. In the first scheme we have to solve a quadratic program at each iteration, while in the second one all calculations are explicit. Numerical simulations show the efficiency of our customized DCA with respect to the methods developed in Astorino et al.
Similar content being viewed by others
References
Astorino A., Gaudioso M.: Ellipsoidal separation for classification problems. Optim. Methods Softw. 20, 267–276 (2005)
Astorino A., Gaudioso M.: A fixed-centre spherical separation algorithm with kernel transformations for classification problems. Comput. Manag. Sci. 6(3), 357–372 (2009)
Astorino A., Fuduli A., Gaudioso M.: DC models for spherical separation. J. Glob. Optim. 48(4), 657–669 (2010)
Audet C., Hansen P., Karam A., Ng C.D., Perron S.: Exact L2-norm plane separation. Optim. Lett. 2(4), 483–495 (2008)
Boser, B.E., Guyon, I., Vapnik, V.: A training algorithm for optimal margin classifiers. COLT’92, Proceedings of the fifth annual workshop on Computational learning theory, pp. 144–152 (1992)
Barnes E.R.: An algorithm for separating patterns by ellipsoids. IBM. J. Res. Dev. 26, 759–764 (1982)
DC Programming and DCA:http://lita.sciences.univ-metz.fr/~lethi/
Fuduli A., Gaudioso M., Giallombardo G.: Minimizing nonconvex nonsmooth functions via cutting planes and proximity control. SIAM J. Optim. 14, 743–756 (2004)
Le Thi H.A., Pham D.T.: Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. J. Glob. Optim. 11(3), 253–285 (1997)
Le Thi H.A., Pham D.T.: Large scale global molecular optimization from exact distance matrices by a DC optimization approach. SIAM J. Optim. 14(1), 77–114 (2003)
Le Thi H.A., Pham D.T.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)
Le Thi, H.A., Van Nguyen, N., Pham D.T.: Convergence Analysis of DCA for DC programming with Subanalytic Data. Research Report, National Institute for Applied Sciences, Rouen-France (2008)
Le Thi H.A., Le H.M., Pham D.T.: Fuzzy clustering based on nonconvex optimisation approaches using difference of convex (DC) functions algorithms. Adv. Data Anal. Classif. 1(2), 85–104 (2007)
Le Thi H.A., Le H.M., Pham D.T.: Optimization based DC programming and DCA for Hierarchical clustering. Eur. J. Oper. Res. 183, 1067–1085 (2007)
Le Thi H.A., Belghiti M.T., Pham D.T.: A new efficient algorithm based on DC programming and DCA for clustering. J. Glob. Optim. 37, 593–608 (2007)
Le Thi H.A., Le H.M., Van Nguyen V., Pham D.T.: A DC programming approach for feature selection in support vector machines learning. J. Adv. Data Anal. Classif. 2(3), 259–278 (2008)
Mangasarian O.L.: Solution of general linear complementarity problems via nondifferentiable concave minimization. Acta Math. Vietnam. 22, 199–205 (1997)
Mamadou, T., Pham D.T., Le Thi, H.A.: A DC programming approach for sparse eigenvalue problem. Proceedings of International Conference on Machine learninh ICML 2010, pp. 1063–1070 (2010)
Pardalos, P.M., Hansen, P.: Data Mining and Mathematical Programming, CRM vol. 45. American Mathematical Society, ISBN-10: 0821843524 (2008)
Pham D.T., Le Thi H.A.: Convex analysis approach to DC programming: theory, algorithms and applications. Acta Math. Vietnam. 22(1), 289–355 (1997)
Pham D.T., Le Thi H.A.: DC optimization algorithms for solving the trust region subproblem. SIAM J.Optim. 8, 476–505 (1998)
Rosen J.B.: Pattern separation by convex programming. J. Math. Anal. Appl. 10, 123–134 (1965)
Sriperumbudur, B.K., Torres, D.A., Lanckriet, G.R.G.: Sparse Eigen methods by DC programming. In: Proceedings of the 24 th International Conference on Machine Learning, Corvallis, OR (2007)
Wu Y., Liu Y.: Variable selection in quantile regression. Stat. Sin. 19, 801–817 (2009)
Yuille A.L., Rangarajan A.: The concave-convex procedure. Neural Comput. 15(4), 915–936 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was presented at ICOTA8 Special Session—SS09A Hoai Minh Le, Hoai An Le Thi, Tao Pham Dinh, Ngai Van Huynh, “Efficient DCA for Spherical Separation”.
Rights and permissions
About this article
Cite this article
Le Thi, H.A., Le, H.M., Pham Dinh, T. et al. Binary classification via spherical separator by DC programming and DCA. J Glob Optim 56, 1393–1407 (2013). https://doi.org/10.1007/s10898-012-9859-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9859-6