Source code for the Algorithm Branches described in the paper Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees that is currecntly under review.

We recommend creating a conda virtual environment from our .yml file as follows:

conda env create -f dependencies.yml
conda activate branches

To visualize Decision Trees, we need the svgling package, which is not currenlty supported by conda. Thus we install it with pip:

pip install svgling

.
├── data                         # Data used for benchmarking
├── src                          # Source files
│   ├── branch_ordinal.py        # Source file for classification problems with ordinally encoded data
│   ├── branch_binary.py         # Source file for binary classification problems with binary data
│   ├── branch_binary_multi.py   # Source file for classification problems with binary data
│   ├── branches.py              # Source file for the Branches algorithm
│   └── tutorial.ipynb           # Tutorial .ipynb notebook
├── trees                        # SVG files of optimal decision trees
├── LICENSE
└── README.md

File src/tutorial.ipynb contains a tutorial on how to use Branches with illustrative examples.

The MONK's Problems are standard datasets for benchmarking Optimal Decision Trees algorithms. We use the first of these problems to illustrate how to use Branches.

from branches import *
from sklearn.preprocessing import OneHotEncoder, OrdinalEncoder, LabelEncoder

# Reading the data
data = np.genfromtxt('data/monks-1.train', delimiter=' ', dtype=int)
data = data[:, :-1] # Getting rid of the last column, it contains only ids.
data = data[:, ::-1] # Reorder the columns to put the predicted variable Y at the end.

# Ordinal Encoding of the data
encoder = OrdinalEncoder()
encoder.fit(data)
data = encoder.transform(data).astype(int)

# Running Branches
alg = Branches(data)
alg.solve(lambd=0.01)

# Printing the accuracy, number of branches and number of splits
branches, splits = alg.lattice.infer()
print('Number of branches :', len(branches))
print('Number of splits :', splits)
print('Accuracy :', ((alg.predict(data[:, :-1]) == data[:, -1]).sum())/alg.n_total)

Using the nltk and svgling packages, we can plot the optimal Decision Tree via the code below. $\color{red}{\textsf{Please note that if you do not see the figures, it is probably due to a contrast issue and you should set a light theme for Github.}}$

tree = alg.plot_tree()
svgling.draw_tree(tree)

If we are only interested in the tree structure regardless of the predicted classes at the leaves, we can set show_classes=False in the plot_tree method.

tree = alg.plot_tree(show_classes=False)
svgling.draw_tree(tree)

Here are some more examples of optimal Decision Trees we find for different problems.

The tutorial file src/tutorial.ipynb contains more examples on how to use Branches, especially with its micro-optimisation techniques that allow for significant computational gains.

Branches optimises the regularised accuracy $\mathcal{H}_{\lambda}\left( T\right) = \textrm{Accuracy}\left( T\right) - \lambda \mathcal{S}\left( T\right)$, where $\mathcal{S}\left( T\right)$ is the number of splits (internal nodes) of Decision Tree $T$ and $\lambda \in \left[ 0, 1 \right]$ is a penalty parameter. The table below summarises the empirical comparison between Branches and the state of the art. $\mathcal{T}$ is the execution time in seconds (TO indicates time out after 5 minutes), and $\mathcal{I}$ the number of iterations, ___ indicates the inapplicability of the method to the setting. Branches clearly outperforms the Python implementations OSDT and PyGOSDT. Branches also outperforms the C++ implementation GOSDT in many cases, and even when it is slower, Branches always converges in significantly fewer iterations. A future C++ implementation of Branches will likely lead to a significant improvement of Branches' computational performance, just as we notice when comparing PyGOSDT and GOSDT.