Optimal constraint-based decision tree induction from itemset lattices

By Siegfried Nijssen, Élisa Fromont. 2010

72 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, Algorithms & Complexity

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

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Efforts to fully optimize decision trees, solving problems related to (2), have been made since the 1990s (Bennett and Blue, 1996; Dobkin et al., 1996; Farhangfar et al., 2008; Nijssen and Fromont, 2007, 2010; Hu et al., 2019; Lin et al., 2020).”
Learning Certifiably Optimal Rule Lists (2017, background): “A particularly interesting paper along these lines is that of Nijssen and Fromont (2010), who created a “bottom-up” way to form optimal decision trees.”
MurTree: Optimal Decision Trees via Dynamic Programming and Search (2020, methodology): “Caching has been used in previous works (Nijssen and Fromont (2007, 2010) We adapt and extend the caching techniques from the literature for our algorithm, i.e., our cache takes into account constraints both on depth and the number of nodes.”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, methodology): “5 can be modiﬁed for use in other constraint-based decision tree learning problems, using ideas from DL8 (Nijssen and Fromont 2010).”
Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, methodology): “For example, Nijssen and Fromont (2010) use itemset mining algorithms and Narodytska et al. (2018) use satisﬁability (SAT) solvers.”
Learning customized and optimized lists of rules with mathematical programming (2018, background): “An exception is that of Nijssen and Fromont [49,50], which can be used with pre-mined rules.”
Scalable Bayesian Rule Lists (2016, background): “Nijssen and Fromont (2010) has the user pre-mine all possible leaves , enumerating all conditions leading to that leaf.”
Recent advances in decision trees: an updated survey (2022, methodology): “DL8 (Nijssen and Fromont 2010) frames DT induction as a frequent itemset mining problem: each path corresponds to an itemset, and ideas similar to dynamic programming can be employed to find the optimal tree.”
On Explaining Decision Trees (2020, background): “Motivated by this perception, there has been extensive work on learning DTs (and related logic ML models) with properties deemed important for interpretability, e.g. number of nodes, maximum/average depth, etc. [2,68,25,32,1,7,57,24,26,70,67,58,44,30,17,5,73,35,4,78,69,10,34,72,71,36,46,11,45] 2 .”