Learning Optimal Decision Trees using Constraint Programming

By Hélène Verhaeghe, Siegfried  Nijssen, Gilles Pesant, Claude-Guy Quimper, Pierre Schaus

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 i
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.

This article was presented to CP2019, Stamford, Connecticut, USA, Sep. 30 to Oct 4

About authors :

Hélène Verhaeghe is a PhD student at the INGI department at the UCLouvain, Belgium. Her current work focuses on improving the extensional constraint (Table and MDD constraints).

Siegfried Nijssen is an assistant professor of data mining and artificial intelligence at the Université catholique de Louvain (UCLouvain) in Belgium. His research aims to make data analysis simpler for both end-users and programmers; it studies intersections between pattern mining, exploratory data analysis, and programming paradigms in Artificial Intelligence, such as constraint programming and probabilistic programming. He has developed techniques for analysing a wide range of data types, including graphs, networks and multi-relational data.

Gilles Pesant is a Professor at the Polytechnique Montreal, Canada.

Claude-Guy Quimper is a Professor at Université Laval in Québec, Canada.

Pierre Schaus obtained his Ph.D. from the UCLouvain University in 2009. He spent 5 months at Brown University. Then he joined the Dynadec startup to work on Comet during two years before working two more years at N-SIDE. September 2012, he is Professor of Computer Science, UCLouvain, Department of Computing Science and Engineering of the Institute.

Published on September 17, 2019