Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Learning optimal decision trees using constraint programming

  • Original Research
  • Published:
Constraints Aims and scope Submit manuscript

Abstract

Decision trees are among the most popular classification models in machine learning. Traditionally, they are learned using greedy algorithms. However, such algorithms pose several disadvantages: it is difficult to limit the size of the decision trees while maintaining a good classification accuracy, and it is hard to impose additional constraints on the models that are learned. For these reasons, there has been a recent interest in exact and flexible algorithms for learning decision trees. In this paper, we introduce a new approach to learn decision trees using constraint programming. Compared to earlier approaches, we show that our approach obtains better performance, while still being sufficiently flexible to allow for the inclusion of constraints. Our approach builds on three key building blocks: (1) the use of AND/OR search, (2) the use of caching, (3) the use of the CoverSize global constraint proposed recently for the problem of itemset mining. This allows our constraint programming approach to deal in a much more efficient way with the decompositions in the learning problem.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. The problem of embedding a decision tree as a constraint into a CP model has been studied in [11].

  2. https://bitbucket.org/helene_verhaeghe/classificationtree

  3. Available in the repository

  4. https://dtai.cs.kuleuven.be/CP4IM/datasets/

  5. https://archive.ics.uci.edu/ml/index.php

  6. Binarized versions available in the repository

References

  1. Breiman, L. (1984). Classification and regression trees. Routledge.

  2. Quinlan, J.R. (1986). Induction of decision trees. Machine Learning, 1(1), 81–106. https://doi.org/10.1023/A:1022643204877.

  3. Quinlan, J.R. (1993). C4.5: programs for machine learning. Morgan Kaufmann.

  4. Aghaei, S., Azizi, M.J., & Vayanos, P. (2019). Learning optimal and fair decision trees for non-discriminative decision-making.

  5. Bertsimas, D., & Dunn, J. (2017). Optimal classification trees. Machine Learning, 106(7), 1039–1082.

    Article  MathSciNet  Google Scholar 

  6. Bessiere, C., Hebrard, E., & O’Sullivan, B. (2009). Minimising decision tree size as combinatorial optimisation. In Gent, I. P. (Ed.) Principles and Practice of Constraint Programming - CP 2009, 15th International Conference, CP 2009, Lisbon, Portugal, Proceedings, Lecture Notes in Computer Science, (Vol. 5732 pp. 173–187): Springer. https://doi.org/10.1007/978-3-642-04244-7_16.

  7. Narodytska, N., Ignatiev, A., Pereira, F., & Marques-Silva, J. (2018). Learning optimal decision trees with SAT. In Lang, J. (Ed.) Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, Stockholm, Sweden, ijcai.org (pp. 1362–1368). https://doi.org/10.24963/ijcai.2018/189.

  8. Nijssen, S., & Fromont, E. (2007). Mining optimal decision trees from itemset lattices, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 530–539): ACM.

  9. Nijssen, S., & Fromont, E. (2010). Optimal constraint-based decision tree induction from itemset lattices. Data Min. Knowl. Discov., 21(1), 9–51.

    Article  MathSciNet  Google Scholar 

  10. Verwer, S., & Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019 (pp. 1625–1632). Honolulu: AAAI Press. https://doi.org/10.1609/aaai.v33i01.33011624.

  11. Bonfietti, A., Lombardi, M., & Milano, M. (2015). Embedding decision trees and random forests in constraint programming. In Michel, L (Ed.) Integration of AI and OR Techniques in Constraint Programming - 12th International Conference, CPAIOR 2015, Barcelona, Spain, Proceedings, Lecture Notes in Computer Science, (Vol. 9075 pp. 74–90): Springer. https://doi.org/10.1007/978-3-319-18008-3_6.

  12. Hyafil, L., & Rivest, R.L. (1976). Constructing optimal binary decision trees is np-complete. Information Processing Letters, 5(1), 15–17. https://doi.org/10.1016/0020-0190(76)90095-8.

    Article  MathSciNet  Google Scholar 

  13. Hancock, T., Jiang, T., Li, M., & Tromp, J. (1996). Lower bounds on learning decision lists and trees. Information and Computation, 126(2), 114–122.

    Article  MathSciNet  Google Scholar 

  14. Schaus, P., Aoga, J.O.R., & Guns, T. (2017). Coversize: a global constraint for frequency-based itemset mining. In International Conference on Principles and Practice of Constraint Programming (pp. 529–546): Springer.

  15. Dechter, R., & Mateescu, R. (2004). The impact of AND/OR search spaces on constraint satisfaction and counting. In Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, Proceedings (pp. 731–736).

  16. Babaki, B., Guns, T., & De Raedt, L. (2017). Stochastic constraint programming with and-or branch-and-bound. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia (pp. 539–545).

  17. Rossi, F., Van Beek, P., & Walsh, T. (2006). Handbook of constraint programming. Elsevier.

  18. Laurent Michel, P.S. (2018). MiniCP: A lightweight solver for constraint programming. Available from https://minicp.bitbucket.io.

  19. Dechter, R., & Mateescu, R. (2007). And/or search spaces for graphical models. Artificial intelligence, 171(2-3), 73–106.

    Article  MathSciNet  Google Scholar 

  20. Marinescu, R., & Dechter, R. (2004). And/or tree search for constraint optimization. In Proceedings of the 6th International Workshop on Preferences and Soft Constraints: Citeseer.

  21. Demeulenaere, J., Hartert, R., Lecoutre, C., Perez, G., Perron, L., Régin, J.-C., & Schaus, P. (2016). Compact-table: efficiently filtering table constraints with reversible sparse bit-sets, International Conference on Principles and Practice of Constraint Programming (pp. 207–223): Springer.

  22. Cover, T.M., & Thomas, J.A. (2012). Elements of information theory. New York: Wiley.

    MATH  Google Scholar 

  23. OscaR Team. (2012). OscaR: Scala in OR. Available from https://bitbucket.org/oscarlib/oscar.

  24. Rothberg, E. (2007). An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS Journal on Computing, 19(4), 534–541.

    Article  Google Scholar 

  25. Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., & Schaus, P. (2019). Learning optimal decision trees using constraint programming. In Beuls, K., Bogaerts, B., Bontempi, G., Geurts, P., Harley, N., Lebichot, B., Lenaerts, T., Louppe, G., & Eecke, P. V. (Eds.) Proceedings of the 31st Benelux Conference on Artificial Intelligence (BNAIC 2019) and the 28th Belgian Dutch Conference on Machine Learning (Benelearn 2019), Brussels, Belgium, CEUR Workshop Proceedings, Vol. 2491: CEUR-WS.org. http://ceur-ws.org/Vol-2491/abstract109.pdf.

  26. Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., & Schaus, P. (2020). Learning optimal decision trees using constraint programming (extended abstract). In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, Tokyo, Japan.

Download references

Author information

Authors and Affiliations

  1. UCLouvain, ICTEAM, Place Sainte Barbe 2, 1348, Louvain-la-Neuve, Belgium

    Hélène Verhaeghe, Siegfried Nijssen & Pierre Schaus

  2. Polytechnique Montréal, Montréal, Canada

    Gilles Pesant

  3. Université Laval, Québec, Canada

    Claude-Guy Quimper

Authors
  1. Hélène Verhaeghe
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Siegfried Nijssen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Gilles Pesant
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Claude-Guy Quimper
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Pierre Schaus
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hélène Verhaeghe.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Verhaeghe, H., Nijssen, S., Pesant, G. et al. Learning optimal decision trees using constraint programming. Constraints 25, 226–250 (2020). https://doi.org/10.1007/s10601-020-09312-3

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-020-09312-3

Keywords

Search

Navigation