Learning Optimal Decision Trees using Constraint Programming (Extended Abstract)

Decision trees are among the most popular classification models in machine learning. Traditionally, they are learned using greedy algorithms. However, such algorithms have their 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.

Authors

• Hélène Verhaeghe UCLouvain, Belgium KU Leuven, Belgium
• Siegfried Nijssen
• Gilles Pesant
• Claude-Guy Quimper Université Laval, Quebec City, Canada
• Pierre Schaus

Keywords

• Constraints and SAT: Constraint Optimization
• Constraints and SAT: Constraints and Data Mining; Constraints and Machine Learning
• Constraints and SAT: Constraints: Modeling, Solvers, Applications
• Constraints and SAT: Global Constraints