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.
Bessiere is supported by the project CANAR (ANR-06-BLAN-0383-02). Hebrard and O’Sullivan are supported by Science Foundation Ireland (Grant number 05/IN/I886).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Esmeir, S., Markovitch, S.: Anytime learning of decision trees. Journal of Machine Learning Research 8, 891–933 (2007)
Hyafil, L., Rivest, R.L.: Constructing optimal binary decision trees is NP-complete. Inf. Process. Lett. 5(1), 15–17 (1976)
Katsirelos, G., Walsh, T.: A compression algorithm for large arity extensional constraints. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 379–393. Springer, Heidelberg (2007)
Prosser, P., Unsworth, C.: Rooted tree and spanning tree constraints. In: Workshop on Modelling and Solving Problems with Constraints, held at ECAI 2006 (2006)
Quinlan, J.R.: Induction of decision trees. Machine Learning 1(1), 81–106 (1986)
Quinlan, R.J.: C4.5: programs for machine learning. Morgan Kaufmann Publishers Inc., San Francisco (1993)
Utgoff, P.E., Berkman, N.C., Clouse, J.A.: Decision tree induction based on efficient tree restructuring. Machine Learning 29, 5–44 (1997)
Witten, I.H., Frank, E.: Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, San Francisco (2005)
Yüksektepe, F.Ü., Türkay, M.: A mixed-integer programming approach to multi-class data classification problem. European Journal of OR 173(3), 910–920 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bessiere, C., Hebrard, E., O’Sullivan, B. (2009). Minimising Decision Tree Size as Combinatorial Optimisation . In: Gent, I.P. (eds) Principles and Practice of Constraint Programming - CP 2009. CP 2009. Lecture Notes in Computer Science, vol 5732. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04244-7_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-04244-7_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04243-0
Online ISBN: 978-3-642-04244-7
eBook Packages: Computer ScienceComputer Science (R0)