Introduction
In the landscape of machine learning, decision trees remain a cornerstone due to their interpretability and efficiency. However, most practitioners rely on "greedy" algorithms like CART or C4.5, which make locally optimal splits at each node. While fast, these methods do not guarantee a globally optimal tree, often resulting in models that are less accurate, unnecessarily complex, or potentially biased.
Finding a mathematically optimal decision tree is an NP-hard problem. While recent attempts have utilized Mixed Integer Programming (MIP) and Constraint Programming (CP), these generic solvers often struggle with the exponential search space. This paper introduces DL8.5, a specialized algorithm that combines itemset mining with a novel caching branch-and-bound search to find optimal trees orders of magnitude faster than current state-of-the-art methods.
The DL8.5 Framework: Itemsets as Paths
The core innovation of DL8.5 lies in its foundational view of decision trees. Rather than treating tree construction as a recursive splitting process, the algorithm views every path from the root to a leaf as an "itemset"—a specific combination of features. This abstraction allows the algorithm to leverage highly efficient data structures and techniques from the field of association rule mining.
By mapping the tree-building problem onto a lattice of feature combinations, DL8.5 transforms the search into a graph-traversal problem. This perspective enables the use of "covers" (the set of transactions matching an itemset) to quickly calculate error and support, which are critical for evaluating potential splits.
Optimizing Search: Branch-and-Bound with Novel Caching
To navigate the massive search space of possible trees, DL8.5 employs several advanced optimization strategies:
- Branch-and-Bound Pruning: The algorithm maintains an upper bound on the error. If a specific branch of the search lattice cannot possibly yield a lower error than the current best solution, that entire branch is "pruned" and skipped.
- Novel Caching Strategy: Traditional caches store completed sub-problems. DL8.5 introduces a "secret sauce" by also caching incomplete results. If a search path is pruned because it hit a bound, the cache records this failure. If the algorithm encounters the same sub-problem later with a tighter or equal bound, it can immediately skip the computation.
- Heuristic Branching: By prioritizing attributes with high Information Gain, the algorithm finds low upper bounds early in the search, significantly increasing the effectiveness of subsequent pruning.
Experimental Performance
The authors evaluated DL8.5 against leading MIP and CP solvers across 24 binary datasets (e.g., mushroom, tic-tac-toe) and several continuous datasets from the UCI repository. The results demonstrate a clear advantage for specialized search:
- Speed and Scalability: DL8.5 solved 19 out of 24 binary instances to optimality within 10 minutes. In comparison, the leading MIP approach (BinOCT) solved only one, and a recent CP approach solved 11.
- Pruning Efficiency: The caching and bounding strategies led to massive reductions in the search space. In practical tests, DL8.5 visited significantly fewer nodes than its predecessor, DL8, with the benefits compounding as tree depth increased.
- Versatility: Despite being designed for Boolean data, DL8.5 outperformed specialized continuous-data solvers on binarized UCI datasets. Furthermore, its "any-time" property allows it to return the best-found tree if interrupted, making it practical for real-world applications.
Conclusion and Future Work
DL8.5 proves that specialized algorithms incorporating domain-specific insights—like the relationship between itemsets and decision paths—can vastly outperform generic optimization solvers. While the current implementation faces potential memory constraints on extremely high-dimensional data and overhead from binarization, it sets a new benchmark for optimal decision tree induction. Future research may extend this framework to incorporate additional constraints, such as fairness metrics or specific interpretability requirements, further bridging the gap between mathematical optimality and practical machine learning.
Summary updated