IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v188y2011i1p215-24910.1007-s10479-011-0850-2.html
   My bibliography  Save this article

A new column generation algorithm for Logical Analysis of Data

Author

Listed:
  • Pierre Hansen
  • Christophe Meyer

Abstract

We present a new column generation algorithm for the determination of a classifier in the two classes LAD (Logical Analysis of Data) model. Unlike existing algorithms who seek a classifier that at the same time maximizes the margin of correctly classified observations and minimizes the amount of violations of incorrectly classified observations, we fix the margin to a difficult-to-achieve target and minimize a piecewise convex linear function of the violation of incorrectly classified observations. Moreover a part of the training set, called control set, is reserved to select, among all feasible classifiers found by the algorithm, the one with highest performance on that set. One advantage of the proposed algorithm is that it essentially does not require any calibration. Computational results are presented that show the effectiveness of this approach. Copyright Springer Science+Business Media, LLC 2011

Suggested Citation

  • Pierre Hansen & Christophe Meyer, 2011. "A new column generation algorithm for Logical Analysis of Data," Annals of Operations Research, Springer, vol. 188(1), pages 215-249, August.
  • Handle: RePEc:spr:annopr:v:188:y:2011:i:1:p:215-249:10.1007/s10479-011-0850-2
    DOI: 10.1007/s10479-011-0850-2
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-0850-2
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10479-011-0850-2?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. Emilio Carrizosa & Belen Martin-Barragan & Dolores Romero Morales, 2010. "Binarized Support Vector Machines," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 154-167, February.
    2. Peter Hammer & Tibérius Bonates, 2006. "Logical analysis of data—An overview: From combinatorial optimization to medical applications," Annals of Operations Research, Springer, vol. 148(1), pages 203-225, November.
    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. Lejeune, Miguel & Lozin, Vadim & Lozina, Irina & Ragab, Ahmed & Yacout, Soumaya, 2019. "Recent advances in the theory and practice of Logical Analysis of Data," European Journal of Operational Research, Elsevier, vol. 275(1), pages 1-15.
    2. Maurizio Boccia & Antonio Sforza & Claudio Sterle, 2020. "Simple Pattern Minimality Problems: Integer Linear Programming Formulations and Covering-Based Heuristic Solving Approaches," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1049-1060, October.
    3. Chun-An Chou & Tibérius O. Bonates & Chungmok Lee & Wanpracha Art Chaovalitwongse, 2017. "Multi-pattern generation framework for logical analysis of data," Annals of Operations Research, Springer, vol. 249(1), pages 329-349, February.
    4. Réal Carbonneau & Gilles Caporossi & Pierre Hansen, 2014. "Globally Optimal Clusterwise Regression By Column Generation Enhanced with Heuristics, Sequencing and Ending Subset Optimization," Journal of Classification, Springer;The Classification Society, vol. 31(2), pages 219-241, July.
    5. Yasser Shaban & Mouhab Meshreki & Soumaya Yacout & Marek Balazinski & Helmi Attia, 2017. "Process control based on pattern recognition for routing carbon fiber reinforced polymer," Journal of Intelligent Manufacturing, Springer, vol. 28(1), pages 165-179, January.
    6. Guo, Cui & Ryoo, Hong Seo, 2021. "On Pareto-Optimal Boolean Logical Patterns for Numerical Data," Applied Mathematics and Computation, Elsevier, vol. 403(C).

    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. Maurizio Maravalle & Federica Ricca & Bruno Simeone & Vincenzo Spinelli, 2015. "Carpal Tunnel Syndrome automatic classification: electromyography vs. ultrasound imaging," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 23(1), pages 100-123, April.
    2. de Vos, Wout & Balvert, Marleen, 2023. "RPA : Learning Interpretable Input-Output Relationships by Counting Samples," Other publications TiSEM 70276b7f-9026-46ad-a8e8-1, Tilburg University, School of Economics and Management.
    3. Lejeune, Miguel & Lozin, Vadim & Lozina, Irina & Ragab, Ahmed & Yacout, Soumaya, 2019. "Recent advances in the theory and practice of Logical Analysis of Data," European Journal of Operational Research, Elsevier, vol. 275(1), pages 1-15.
    4. Marleen Balvert, 2024. "Iterative Rule Extension for Logic Analysis of Data: An MILP-Based Heuristic to Derive Interpretable Binary Classifiers from Large Data Sets," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 723-741, May.
    5. Martin-Barragan, Belen & Lillo, Rosa & Romo, Juan, 2014. "Interpretable support vector machines for functional data," European Journal of Operational Research, Elsevier, vol. 232(1), pages 146-155.
    6. Fawaz Alsolami & Talha Amin & Igor Chikalov & Mikhail Moshkov, 2018. "Bi-criteria optimization problems for decision rules," Annals of Operations Research, Springer, vol. 271(2), pages 279-295, December.
    7. Dursun Delen & Madhav Erraguntla & Richard Mayer & Chang-Nien Wu, 2011. "Better management of blood supply-chain with GIS-based analytics," Annals of Operations Research, Springer, vol. 185(1), pages 181-193, May.
    8. Pierre Lemaire, 2011. "Extensions of Logical Analysis of Data for growth hormone deficiency diagnoses," Annals of Operations Research, Springer, vol. 186(1), pages 199-211, June.
    9. de Vos, Wout & Balvert, Marleen, 2023. "RPA : Learning Interpretable Input-Output Relationships by Counting Samples," Discussion Paper 2023-015, Tilburg University, Center for Economic Research.
    10. Benítez-Peña, Sandra & Carrizosa, Emilio & Guerrero, Vanesa & Jiménez-Gamero, M. Dolores & Martín-Barragán, Belén & Molero-Río, Cristina & Ramírez-Cobo, Pepa & Romero Morales, Dolores & Sillero-Denami, 2021. "On sparse ensemble methods: An application to short-term predictions of the evolution of COVID-19," European Journal of Operational Research, Elsevier, vol. 295(2), pages 648-663.
    11. Elnaz Gholipour & B'ela Vizv'ari & Zolt'an Lakner, 2020. "Reconstruction Rating Model of Sovereign Debt by Logical Analysis of Data," Papers 2011.14112, arXiv.org.
    12. Miguel Lejeune, 2012. "Pattern definition of the p-efficiency concept," Annals of Operations Research, Springer, vol. 200(1), pages 23-36, November.
    13. Gambella, Claudio & Ghaddar, Bissan & Naoum-Sawaya, Joe, 2021. "Optimization problems for machine learning: A survey," European Journal of Operational Research, Elsevier, vol. 290(3), pages 807-828.
    14. Endre Boros & Yves Crama & Peter Hammer & Toshihide Ibaraki & Alexander Kogan & Kazuhisa Makino, 2011. "Logical analysis of data: classification with justification," Annals of Operations Research, Springer, vol. 188(1), pages 33-61, August.
    15. Ya-Ju Fan & Wanpracha Chaovalitwongse, 2010. "Optimizing feature selection to improve medical diagnosis," Annals of Operations Research, Springer, vol. 174(1), pages 169-183, February.
    16. Maurizio Boccia & Antonio Sforza & Claudio Sterle, 2020. "Simple Pattern Minimality Problems: Integer Linear Programming Formulations and Covering-Based Heuristic Solving Approaches," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1049-1060, October.
    17. Travaughn C. Bain & Juan F. Avila-Herrera & Ersoy Subasi & Munevver Mine Subasi, 2020. "Logical analysis of multiclass data with relaxed patterns," Annals of Operations Research, Springer, vol. 287(1), pages 11-35, April.
    18. Jonathan Eckstein & Noam Goldberg, 2012. "An Improved Branch-and-Bound Method for Maximum Monomial Agreement," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 328-341, May.
    19. Manojit Chattopadhyay & Subrata Kumar Mitra, 2017. "Applicability and effectiveness of classifications models for achieving the twin objectives of growth and outreach of microfinance institutions," Computational and Mathematical Organization Theory, Springer, vol. 23(4), pages 451-474, December.
    20. Bagchi, Prabir & Lejeune, Miguel A. & Alam, A., 2014. "How supply competency affects FDI decisions: Some insights," International Journal of Production Economics, Elsevier, vol. 147(PB), pages 239-251.

    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:annopr:v:188:y:2011:i:1:p:215-249:10.1007/s10479-011-0850-2. 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.