Proceedings of the AAAI Conference on Artificial Intelligence · 2020 · 107 citations · 10 references
ComputingComputer ScienceAlgorithmsData MiningOptimizationBranch And BoundCombinatorial OptimizationDecision TreesDiscrete OptimizationInteger ProgrammingSearching AlgorithmsFrequent Itemset MiningMixed-integer Programming
Several recent publications have studied the use of Mixed Integer Programming (MIP) for finding an optimal decision tree, that is, the best decision tree under formal requirements on accuracy, fairness or interpretability of the predictive model. These publications used MIP to deal with the hard computational challenge of finding such trees. In this paper, we introduce a new efficient algorithm, DL8.5, for finding optimal decision trees, based on the use of itemset mining techniques. We show that this new approach outperforms earlier approaches with several orders of magnitude, for both numerical and discrete data, and is generic as well. The key idea underlying this new approach is the use of a cache of itemsets in combination with branch-and-bound search; this new type of cache also stores results for parts of the search space that have been traversed partially.
10
Classification and Regression Trees.
Alexander Gordon, Leo Breiman, Jerome H. Friedman et al. · Biometrics · 1984 · 23.9K citations
Fast discovery of association rules
Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant et al. · Knowledge Discovery and Data Mining · 1996 · 2.3K citations
Dimitris Bertsimas, Jack Dunn · Machine Learning · 2017 · 632 citations · Full text