Decision tree enhancer (DTE): Improving decision trees with optimization

Abstract

Decision trees are off-the-shelf machine learning models widely used for classification and regression tasks in medical, logistics, financial, and other critical areas where interpretability is a key factor. They can efficiently handle numerical and categorical variables, making them a versatile choice for various applications. However, traditional decision-tree training methods are based on greedy heuristics, which cannot provide guarantees regarding whether further improvements could be achieved. We propose Decision Tree Enhancer (DTE), which employs optimization as a post-training step to improve previously trained decision trees. Moreover, the proposed method precludes the need for a pre-processing step for continuous features such as discretization or bucketization, and can be applied regardless of the model used to first train the decision tree. Lastly, DTE’s mathematical programming formulation enables, for example, the consideration of recall thresholds and class prioritization. Tested on 63 classification datasets from the UCI Machine Learning Repository, using tree depths from 1 to 5, four time limits (1, 5, 10, and 30 seconds), and 5 randomized train-test splits cross-validation, the proposed post-training step demonstrated superior performance over CART (Classification And Regression Tree), for both in- and out-of-sample data. With a 30-second time limit, DTE was able to improve the weighted recall in 83.2% of the datasets with an average improvement of 9.0% in training and 5.0% in testing.

Flávio Araújo Lim-Apo

Visiting Doctoral Researcher

Flávio Araújo Lim-Apo is a visiting researcher from Pontifical Catholic University of Rio de Janeiro (Brazil), where he is doing a PhD in the field of Operations Research.

Fabricio Oliveira

Associate Professor of Operations Research

Fabricio Oliveira is an Associate Professor of Operations Research at DTU Management. He also holds a position of Adjunct Professor in the Department of Mathematics and Systems Analysis at Aalto University