Mining optimal decision trees from itemset lattices

By Siegfried Nijssen, Élisa Fromont. 2007

92 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).”
Three naive Bayes approaches for discrimination-free classification (2010, background): “For example, when learning a decision tree, an upper bound on the number of nodes in the tree can be imposed [11].”
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.”
Generalized and Scalable Optimal Sparse Decision Trees (2020, background): “The DL8 al-gorithm (Nijssen & Fromont, 2007) performs dynamic programming on the space of decision trees.”
Learning Optimal Decision Trees Using Caching Branch-and-Bound Search (2020, methodology): “However, earlier algorithms for finding optimal decision trees under constraints have been studied in the literature, of which we consider the DL8 algorithm of particular interest (Nijssen and Fromont 2007; 2010).”
Optimal Sparse Decision Trees (2019, methodology): “Problems with greedy splitting and pruning have been known since the early 1990’s, when mathematical programming tools had started to be used for creating optimal binary-split decision trees [3, 4], in a line of work [5, 6, 16, 18] until the present [20], however, these techniques use all-purpose to”
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.”
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 .”
Decision trees: a recent overview (2011, background): “Nijssen and Fromont (2007) presented DL8, an exact algorithm for finding a decision tree that optimizes a ranking function under size, depth, accuracy and leaf constraints.”
Born-Again Tree Ensembles (2020, background): “Bennett & Blue (1996) focused on building global optimal decision trees to avoid overﬁtting, while Nijssen & Fromont (2007) presented an exact algorithm to build a decision tree for speciﬁc depth, accuracy, and leaf requirements.”
MurTree: Optimal Classification Trees via Dynamic Programming and Search (2020, methodology): “Previous approaches either place no constraint on the number of nodes apart from the depth (Nijssen and Fromont (2007); Aglin et al. (2020)), limit the number of nodes by penalising the objective function for each node in the tree (Hu et al. (2019)), or allow constraints on the number of nodes but…”
Discrimination Aware Decision Tree Learning (2010, unknown): “For example, when learning a decision tree, an upper bound on the number of nodes in the tree can be imposed [13].”
Optimal Decision Trees for Nonlinear Metrics (2020, methodology): “(Demirović et al. 2020) advanced the DL8.”
Learning optimal decision trees using constraint programming (2020, methodology): “, 2017], the use of an AND/OR search tree [Dechter and Mateescu, 2007] and the use of caching as introduced in DL8 [Nijssen and Fromont, 2007].”
A Fast Way to Produce Optimal Fixed-Depth Decision Trees (2008, methodology): “The DL8 system (Nijssen & Fromont 2007) uses a dynamic program to produce a decision tree that optimizes the (cid:147)ranking function(cid:148), which is based on constraints that involve various properties of the decision tree, including its training set error, its expected generalization error,…”