Efficient algorithms for constructing decision trees with constraints

By Minos N. Garofalakis, Dongjoon Hyun, Rajeev Rastogi, Kyuseok Shim. 2000

41 citations recorded by the source corpus.

Classi cation is an important problem in data mining. A number of popular classi ers construct decision trees to generate class models. Frequently, however, the constructed trees are complex with hundreds of nodes and thus di cult to comprehend, a fact that calls into question an oftencited bene t that decision trees are easy to interpret. In this paper, we address the problem of constructing \simple" decision trees with few nodes that are easy for humans to interpret. By permitting users to specify constraints on tree size or accuracy, and then building the \best" tree that satis es the constraints, we ensure that the nal tree is both easy to understand and has good accuracy. We develop novel branch-and-bound algorithms for pushing the constraints into the building phase of classi ers, and pruning early tree nodes that cannot possibly satisfy the constraints. Our experimental results with real-life and synthetic data sets demonstrate that signi cant performance speedups and reductions in the number of nodes expanded can be achieved as a result of incorporating knowledge of the constraints into the building step as opposed to applying the constraints after the entire tree is built.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Learning Certifiably Optimal Rule Lists (2017, background): “Another work close to ours is that of Garofalakis et al. (2000), who introduce an algorithm to generate more interpretable decision trees by allowing constraints to be placed on the size of the decision tree.”
Scalable Bayesian Rule Lists (2016, background): “There are a series of works from the mid-1990’s onwards on finding optimal decision trees using dynamic programming and search techniques (e.g., Bennett & Blue, 1996; Auer et al., 1995; Dobkin et al., 1996; Boros et al., 2000; Garofalakis et al., 2000; Farhangfar et al., 2008), mainly working with f”
An experimental evaluation of simplicity in rule learning (2008, background): “(25) present a system that takes constraints regarding the decision tree’s size or training accuracy into account.”