licketysplit 0.1.6

Near-optimal decision trees via LicketySPLIT

LicketySPLIT

LicketySPLIT is a Python package with a C++ backend for learning sparse decision trees for classification and regression. It builds on the LicketySPLIT algorithm from Near Optimal Decision Trees in a SPLIT Second and generalizes it with recursive pilot ideas as in From Rashomon Theory to PRAXIS: Efficient Decision Tree Rashomon Sets. For continuous features, we recommend the included binarization techniques from Fast Sparse Decision Tree Optimization via Reference Ensembles, which preserve optimality with respect to a gradient-boosted tree ensemble.

The package supports binary and multi-class classification, regression, optional sample weights, efficient subproblem caching, and threshold-based binarization for continuous features.

See the example notebook here.

Objective

LicketySPLIT learns a sparse decision tree by attempting to minimize a regularized empirical training objective.

For an unweighted classification dataset with n training samples, the objective is

objective(tree) = training_mistakes(tree) + lambda_leaf * n * number_of_leaves(tree)

where:

• training_mistakes(tree) is the number of training samples misclassified by the tree
• number_of_leaves(tree) is the number of leaves in the tree
• lambda_leaf is the leaf regularization parameter
• n is the number of training samples

For a weighted dataset, n is replaced with the sum of weights and the training_mistakes(tree) penalizes incorrect points by their weight instead of by 1.

For a regression dataset, training_mistakes(tree) is replaced with the sum of squared between the target values and the tree predictions. Our leaves predict a constant value: the (possibly weighted) mean of the training sample target values in that leaf.

Classification and Regression specifics

Labels should be encoded as contiguous nonnegative integers:

0, 1, 2, ..., num_classes - 1

For regression, targets should be numeric values.

Features

LicketySPLIT expects binary input features. For continuous data, use the included ThresholdGuessBinarizer to generate binary threshold features.

from licketysplit import ThresholdGuessBinarizer

binarizer = ThresholdGuessBinarizer(
    learning_rate=0.1,
    n_estimators=100,
    max_depth=3,
    random_state=0,
    column_elimination=False,
)

X_train_bin = binarizer.fit_transform(X_train_raw, y_train)
X_test_bin = binarizer.transform(X_test_raw)

feature_names = binarizer.get_feature_names_out()

Each generated feature has the form

original_feature <= threshold

Full example

A complete notebook showing loading data, binarization, fitting, prediction, tree inspection, plotting, caching, and sample weights is available here.

References

This package builds on the LicketySPLIT algorithm from:

Near Optimal Decision Trees in a SPLIT Second

and generalizes it with a pilot algorithm approach as in:

From Rashomon Theory to PRAXIS: Efficient Decision Tree Rashomon Sets

For continuous-feature binarization, we recommend:

Fast Sparse Decision Tree Optimization via Reference Ensembles