IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v56y2013i4p1393-1407.html
   My bibliography  Save this article

Binary classification via spherical separator by DC programming and DCA

Author

Listed:
  • Hoai Le Thi
  • Hoai Le
  • Tao Pham Dinh
  • Ngai Van Huynh

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. Copyright Springer Science+Business Media, LLC. 2013

Suggested Citation

  • Hoai Le Thi & Hoai Le & Tao Pham Dinh & Ngai Van Huynh, 2013. "Binary classification via spherical separator by DC programming and DCA," Journal of Global Optimization, Springer, vol. 56(4), pages 1393-1407, August.
    • Handle: RePEc:spr:jglopt:v:56:y:2013:i:4:p:1393-1407
    DOI: 10.1007/s10898-012-9859-6
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-012-9859-6
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-012-9859-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hoai Le Thi & Hoai Le & Van Nguyen & Tao Pham Dinh, 2008. "A DC programming approach for feature selection in support vector machines learning," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 2(3), pages 259-278, December.
    2. A. Astorino & A. Fuduli & M. Gaudioso, 2010. "DC models for spherical separation," Journal of Global Optimization, Springer, vol. 48(4), pages 657-669, December.
    3. Le An & Pham Tao, 2005. "The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems," Annals of Operations Research, Springer, vol. 133(1), pages 23-46, January.
    4. A. Astorino & M. Gaudioso, 2009. "A fixed-center spherical separation algorithm with kernel transformations for classification problems," Computational Management Science, Springer, vol. 6(3), pages 357-372, August.
    5. Hoai An, Le Thi & Minh, Le Hoai & Tao, Pham Dinh, 2007. "Optimization based DC programming and DCA for hierarchical clustering," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1067-1085, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Annabella Astorino & Antonio Fuduli, 2015. "Support Vector Machine Polyhedral Separability in Semisupervised Learning," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 1039-1050, March.
    2. Le Thi, H.A. & Pham Dinh, T. & Le, H.M. & Vo, X.T., 2015. "DC approximation approaches for sparse optimization," European Journal of Operational Research, Elsevier, vol. 244(1), pages 26-46.
    3. Welington Oliveira, 2020. "Sequential Difference-of-Convex Programming," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 936-959, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Hoai An Le Thi & Manh Cuong Nguyen, 2017. "DCA based algorithms for feature selection in multi-class support vector machine," Annals of Operations Research, Springer, vol. 249(1), pages 273-300, February.
    2. Jun Sun & Wentao Qu, 2022. "DCA for Sparse Quadratic Kernel-Free Least Squares Semi-Supervised Support Vector Machine," Mathematics, MDPI, vol. 10(15), pages 1-17, August.
    3. Hoai Le Thi & Tao Pham Dinh & Huynh Ngai, 2012. "Exact penalty and error bounds in DC programming," Journal of Global Optimization, Springer, vol. 52(3), pages 509-535, March.
    4. Liming Yang & Laisheng Wang, 2013. "A class of semi-supervised support vector machines by DC programming," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 7(4), pages 417-433, December.
    5. Annabella Astorino & Antonio Fuduli & Manlio Gaudioso, 2012. "Margin maximization in spherical separation," Computational Optimization and Applications, Springer, vol. 53(2), pages 301-322, October.
    6. Le Thi, H.A. & Pham Dinh, T. & Le, H.M. & Vo, X.T., 2015. "DC approximation approaches for sparse optimization," European Journal of Operational Research, Elsevier, vol. 244(1), pages 26-46.
    7. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2015. "Optimal Replenishment Order Placement in a Finite Time Horizon," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 1078-1089, March.
    8. A. Astorino & A. Fuduli & M. Gaudioso, 2010. "DC models for spherical separation," Journal of Global Optimization, Springer, vol. 48(4), pages 657-669, December.
    9. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico & Adil M. Bagirov, 2018. "Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations," Journal of Global Optimization, Springer, vol. 71(1), pages 37-55, May.
    10. A. M. Bagirov & N. Hoseini Monjezi & S. Taheri, 2021. "An augmented subgradient method for minimizing nonsmooth DC functions," Computational Optimization and Applications, Springer, vol. 80(2), pages 411-438, November.
    11. Kaisa Joki & Adil M. Bagirov & Napsu Karmitsa & Marko M. Mäkelä, 2017. "A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes," Journal of Global Optimization, Springer, vol. 68(3), pages 501-535, July.
    12. A. Astorino & M. Gaudioso & W. Khalaf, 2014. "Edge detection by spherical separation," Computational Management Science, Springer, vol. 11(4), pages 517-530, October.
    13. Welington Oliveira, 2020. "Sequential Difference-of-Convex Programming," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 936-959, September.
    14. Laura Girometti & Martin Huska & Alessandro Lanza & Serena Morigi, 2024. "Convex Predictor–Nonconvex Corrector Optimization Strategy with Application to Signal Decomposition," Journal of Optimization Theory and Applications, Springer, vol. 202(3), pages 1286-1325, September.
    15. J. X. Cruz Neto & P. R. Oliveira & A. Soubeyran & J. C. O. Souza, 2020. "A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem," Annals of Operations Research, Springer, vol. 289(2), pages 313-339, June.
    16. M. Bierlaire & M. Thémans & N. Zufferey, 2010. "A Heuristic for Nonlinear Global Optimization," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 59-70, February.
    17. Bai, Jushan & Liao, Yuan, 2016. "Efficient estimation of approximate factor models via penalized maximum likelihood," Journal of Econometrics, Elsevier, vol. 191(1), pages 1-18.
    18. William Haskell & J. Shanthikumar & Z. Shen, 2013. "Optimization with a class of multivariate integral stochastic order constraints," Annals of Operations Research, Springer, vol. 206(1), pages 147-162, July.
    19. Jean-Paul Penot, 2011. "The directional subdifferential of the difference of two convex functions," Journal of Global Optimization, Springer, vol. 49(3), pages 505-519, March.
    20. Astorino, Annabella & Avolio, Matteo & Fuduli, Antonio, 2022. "A maximum-margin multisphere approach for binary Multiple Instance Learning," European Journal of Operational Research, Elsevier, vol. 299(2), pages 642-652.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:56:y:2013:i:4:p:1393-1407. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.