Experiments for Comparing Optimal Decision Trees with Greedy Decision Trees

By: Jacobus G. M. van der Linden (e-mail/website), Daniël Vos, Mathijs M. de Weerdt, Sicco Verwer, and Emir Demirović

This repository hosts the experiments for the following paper:

• Van der Linden, Jacobus G. M., Daniël Vos, Mathijs M. de Weerdt, Sicco Verwer, and Emir Demirović. "Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance" Transactions of Machine Learning Research (2026). pdf

The methods to train optimal decision trees are STreeD and ConTree, from the following papers:

• Van der Linden, Jacobus G. M., Mathijs M. de Weerdt, and Emir Demirović. "Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming." Advances in Neural Information Processing Systems (2023). pdf / source
• Briţa, Cătălin E., Jacobus G. M. van der Linden, and Emir Demirović. "Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound." In Proceedings of AAAI-25 (2025). pdf / source

Installing the requirements

Install the requirements in requirements.txt.

Preparing data

cd data
./fetch.py      # Fetch datasets
./split.py      # Split the data sets into training and test sets (using 5 folds)
./binarize.py   # Create binary features from continuous features
./synthetic.py  # Generate the synthetic data

Preparing the experiments

./experiments/setup_real.py
./experiments/setup_synthetic.py
./experiments/setup_inc_nodes.py
...

Before running, you can update the MAX_DEPTH and TIMEOUT variables in the script.

The experiment can be extended by appending methods to the methods list.

These files produce .json files in the experiments/runs directory. An important setting in these files is the mode parameter. Setting it to "write" will overwrite the current results file. Setting it to "append" will append the results to the current results file.

Run the experiments

./experiments/sync_runner.py --in-file real_experiments-d3.json

Use the lab_runner.py to run the experiments on a slurm server

./experiments/lab_runner.py build --in-file real_experiments-d3.json
./experiments/lab_runner.py start --in-file real_experiments-d3.json

After all tasks are finished, you should check if errors happened:

./experiments/lab_finderr.py

Then aggregate the results with

./experiments/lab_aggregate.py

Plot the results

./experiments/plot/plot_real.py
./experiments/plot/plot_synthetic.py
./experiments/plot/plot_inc_nodes.py
...