Skip to Main content Skip to Navigation
Conference papers

Minimising Decision Tree Size as Combinatorial Optimisation

Christian Bessière 1 Emmanuel Hébrard 2 Barry O'Sullivan 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Decision tree induction techniques attempt to find small trees that fit a training set of data. This preference for smaller trees, which provides a learning bias, is often justified as being consistent with the principle of Occam's Razor. Informally , this principle states that one should prefer the simpler hypothesis. In this paper we take this principle to the extreme. Specifically, we formulate decision tree induction as a combinatorial optimisation problem in which the objective is to minimise the number of nodes in the tree. We study alternative formulations based on satisfiability, constraint programming, and hybrids with integer linear programming. We empirically compare our approaches against standard induction algorithms, showing that the decision trees we obtain can sometimes be less than half the size of those found by other greedy methods. Furthermore, our decision trees are competitive in terms of accuracy on a variety of well-known benchmarks , often being the most accurate. Even when post-pruning of greedy trees is used, our constraint-based approach is never dominated by any of the existing techniques.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00545531
Contributor : Martine Peridier <>
Submitted on : Monday, September 16, 2019 - 11:45:38 AM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Document(s) archivé(s) le : Saturday, February 8, 2020 - 3:10:15 PM

File

Minimising_Decision_Tree_Size_...
Files produced by the author(s)

Identifiers

Collections

Citation

Christian Bessière, Emmanuel Hébrard, Barry O'Sullivan. Minimising Decision Tree Size as Combinatorial Optimisation. CP: Principles and Practice of Constraint Programming, Sep 2009, Lisbon, Portugal. pp.173-187, ⟨10.1007/978-3-642-04244-7_16⟩. ⟨lirmm-00545531⟩

Share

Metrics

Record views

175

Files downloads

68