×
Le Thi, Hoai An; Le, Hoai Minh; Pham Dinh, Tao; Van Huynh, Ngai

Binary classification via spherical separator by DC programming and DCA. (English) Zbl 1275.90093

J. Glob. Optim. 56, No. 4, 1393-1407 (2013).
Summary: 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 A. Astorino et al. [J. Glob. Optim. 48, No. 4, 657–669 (2010; Zbl 1206.90120)]. 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 by Astorino et al. [loc. cit.].

Cited in 10 Documents

MSC:

90C30 Nonlinear programming
90C90 Applications of mathematical programming

Keywords:

classification; spherical separation; DC programming; DCA

Citations:

Zbl 1206.90120
PDF BibTeX XML Cite
\textit{H. A. Le Thi} et al., J. Glob. Optim. 56, No. 4, 1393--1407 (2013; Zbl 1275.90093)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Astorino, A.; Gaudioso, M., Ellipsoidal separation for classification problems, Optim. Methods Softw., 20, 267-276, (2005) · Zbl 1072.90027
[2] Astorino, A.; Gaudioso, M., A fixed-centre spherical separation algorithm with kernel transformations for classification problems, Comput. Manag. Sci., 6, 357-372, (2009) · Zbl 1170.90530
[3] Astorino, A.; Fuduli, A.; Gaudioso, M., DC models for spherical separation, J. Glob. Optim., 48, 657-669, (2010) · Zbl 1206.90120
[4] Audet, C.; Hansen, P.; Karam, A.; Ng, C.D.; Perron, S., Exact L2-norm plane separation, Optim. Lett., 2, 483-495, (2008) · Zbl 1159.90514
[5] 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) · Zbl 0913.65054
[6] Barnes, E.R., An algorithm for separating patterns by ellipsoids, IBM. J. Res. Dev., 26, 759-764, (1982) · Zbl 0504.68058
[7] DC Programming and DCA:http://lita.sciences.univ-metz.fr/ lethi/ · Zbl 0905.90131
[8] Fuduli, A.; Gaudioso, M.; Giallombardo, G., Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM J. Optim., 14, 743-756, (2004) · Zbl 1079.90105
[9] Le Thi, H.A.; Pham, D.T., Solving a class of linearly constrained indefinite quadratic problems by DC algorithms, J. Glob. Optim., 11, 253-285, (1997) · Zbl 0905.90131
[10] 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, 77-114, (2003) · Zbl 1075.90071
[11] 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) · Zbl 1116.90122
[12] 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) · Zbl 1149.90117
[13] 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, 85-104, (2007) · Zbl 1301.90072
[14] 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) · Zbl 1149.90117
[15] 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) · Zbl 1198.90327
[16] 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, 259-278, (2008) · Zbl 1284.90057
[17] Mangasarian, O.L., Solution of general linear complementarity problems via nondifferentiable concave minimization, Acta Math. Vietnam., 22, 199-205, (1997) · Zbl 0895.90167
[18] 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)
[19] Pardalos, P.M., Hansen, P.: Data Mining and Mathematical Programming, CRM vol. 45. American Mathematical Society, ISBN-10: 0821843524 (2008) · Zbl 1137.68011
[20] Pham, D.T.; Le Thi, H.A., Convex analysis approach to DC programming: theory, algorithms and applications, Acta Math. Vietnam., 22, 289-355, (1997) · Zbl 0895.90152
[21] Pham, D.T.; Le Thi, H.A., DC optimization algorithms for solving the trust region subproblem, SIAM J.Optim., 8, 476-505, (1998) · Zbl 0913.65054
[22] Rosen, J.B., Pattern separation by convex programming, J. Math. Anal. Appl., 10, 123-134, (1965) · Zbl 0134.37503
[23] 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)
[24] Wu, Y.; Liu, Y., Variable selection in quantile regression, Stat. Sin., 19, 801-817, (2009) · Zbl 1166.62012
[25] Yuille, A.L.; Rangarajan, A., The concave-convex procedure, Neural Comput., 15, 915-936, (2003) · Zbl 1022.68112
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.