Optimal Classification Tree

Introduction

This project aims to better understand the computational and prediction performance of MIP-based classification tree learning approaches proposed by recent research papers. In particular, the OCT, binOCT, and flowOCT formulations are implemented and evaluated on publicly available classification datasets. Moreover, we propose a stable classification tree formulation incorporating the training and validation split decision into the model fitting processes. Computational results suggest flowOCT has the most consistent performance across datasets and tree complexity. OCT is competitive on small datasets and shallow trees, while binOCT yields the best performance on large datasets and deep trees. The proposed stable classification tree achieves stronger out-of-sample performance than flowOCT under random training and validation set splits.

Dependencies

• Python 3.7
• Gurobi 9.1
• scikit-learn 0.24.2
• SciPy 1.6.3

MIP Models

• Optimal Classification Trees (OCT) - Bertsimas, D., & Dunn, J. (2017). Optimal classification trees. Machine Learning, 106(7), 1039-1082.
• Optimal Classification Tree with Binary Encoding (binOCT) - Verwer, S., & Zhang, Y. (2019). Learning optimal classification trees using a binary linear program formulation. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 1625-1632).
• Max-Flow Optimal Classification Trees (flowOCT) - Aghaei, S., Gómez, A., & Vayanos, P. (2021). Strong optimal classification trees. arXiv preprint arXiv:2103.15965.

Stable Classification Tree

With the ideas come from Bertsimas and Paskov (2020), we also implemented a stable classification tree (SOCT) formulation incorporating the training and validation set split decision into the decision tree learning processes. The model can be regardded as training the decision tree on the "hardest" sub-set of the training dataset. The SOCT is solved using a robust optimization method and a cutting plane method.

• Bertsimas, D., & Paskov, I. (2020). Stable Regression: On the Power of Optimization over Randomization in Training Regression Problems. Journal of Machine Learning Research, 21, 1-25.

Parameters

• max_depth: The maximum depth of the tree.
• min_samples_split: The minimum number of samples required to split an internal node.
• alpha: The penalty term coefficients for the number of splitting nodes.
• warmstart: Warm start with skLearn decision tree or not.
• timelimit: The time limit for running the MIP solver.
• output: Show the optimizing output or not.

Sample Code

import tree as miptree
octree = miptree.optimalDecisionTreeClassifier(max_depth=3, min_samples_split=2, alpha=0.01, warmstart=True, timelimit=600, output=True)
octree.fit(x_train, y_train)
y_test_pred = octree.predict(x_test)

Data

• Balance Scale
• Breast Cancer
• Car Evaluation
• Hayes-Roth
• House Votes 84
• Soybean (small)
• SPECT Heart
• Tic-Tac-Toe Endgame
• MONK's Problems

Report

Details about the project report is here.

Attention: The experiment results in the report is old version.

Results

All the tests are conducted on Intel(R) Core(TM) CPU i7-7700HQ @ 2.80GHz and a memory of 16 GB. Algorithms are implemented in Python 3.7 with Gurobi 9.1 as an optimization solver. The time limit is set to 600 seconds and solver is ran without warmstarting.

Out-of-Sample Prediction Performance for OCT, binOCT, flowOCT, and CART

Optimality Gap for OCT, binOCT, flowOCT

Training Time for OCT, binOCT, flowOCT and CART

Average Solution for flowOCT and SOCT Solved with Robust Optimization and Cutting Plane Methods