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.
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
OSDT | PyGOSDT | GOSDT | Branches | |||||||||
Dataset | ||||||||||||
monk1-l | ||||||||||||
monk1-f | TO | TO | ||||||||||
monk1-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
monk2-l | TO | TO | ||||||||||
monk2-f | TO | TO | ||||||||||
monk2-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
monk3-l | TO | TO | ||||||||||
monk3-f | TO | TO | ||||||||||
monk3-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
tic-tac-toe | TO | TO | ||||||||||
tic-tac-toe-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
car-eval | ___ | ___ | ___ | ___ | ___ | ___ | ||||||
car-eval-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
nursery | ___ | ___ | ___ | ___ | ___ | ___ | TO | TO | ||||
nursery-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
mushroom | TO | TO | TO | TO | ||||||||
mushroom-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
kr-vs-kp | TO | TO | TO | TO | ||||||||
kr-vskp-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | TO | ||
zoo | ___ | ___ | ___ | ___ | ___ | ___ | ||||||
zoo-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
lymph | ___ | ___ | ___ | ___ | ___ | ___ | TO | TO | ||||
lymph-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | |||
balance | TO | TO | ||||||||||
balance-o | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ | ___ |