ConTreeClassifier

ConTreeClassifier finds the decision tree of at most max_depth levels with the fewest training errors, directly on continuous features: no binarisation is needed. The error can be replaced by any cost you define for a leaf (error_function). Candidate thresholds lie halfway between consecutive distinct values of each feature, and a row goes left when x[feature] <= threshold.

The exact search is ConTree, a depth-first branch-and-bound. Its key idea is that moving a threshold only moves rows from one child to the other, so the errors already computed for some thresholds bound the errors of their neighbours, and whole intervals of thresholds can be skipped at once.

from pytrees import ConTreeClassifier

clf = ConTreeClassifier(max_depth=3, min_sup=5, max_time=60).fit(X, y)
clf.status_        # "optimal", "time_limit", ...

Anytime search

The exact search completes the left subtree of a split before looking at the right one, so when the time limit is short it can end with a poor tree. With use_lds=True (or fit_anytime), the search runs in passes of growing limited discrepancy budget instead: the first pass only follows the features and thresholds ranked best by the Gini index, and each pass allows more deviations from that ranking. A good tree is available after the first passes, and a pass that completes without being cut proves the tree optimal.

clf = ConTreeClassifier(max_depth=5, sort_by_heuristic=True, split_selection="first")
clf.fit_anytime(X, y, callback=lambda error, seconds, status: print(seconds, error))

Set sort_by_heuristic=True with the anytime search, since the discrepancy budget follows the Gini ranking.

Parameters

Fitted attributes

Custom error functions

As in DL8.5, the search finds the tree that minimises the sum of the costs of its leaves, for any cost you define for a leaf. Pass it as error_function, a function that receives the content of a leaf as a list and returns (error, prediction): a non-negative number, and the index of the predicted class in classes_.

What the function receives depends on error_function_input:

• "class_counts" (the default): the number of rows of each class in the leaf, in the order of classes_, as ints.
• "indices": the indices of the rows of the leaf in X. Wrap the list with np.asarray to index arrays, as in y[np.asarray(rows)].

Misclassifying class 2 can cost ten times more, for instance:

import numpy as np
from pytrees import ConTreeClassifier

costs = np.array([1.0, 1.0, 10.0])   # cost of misclassifying a row of each class

def cost_sensitive(class_counts):
    counts = np.asarray(class_counts)
    per_prediction = [(costs * counts).sum() - costs[k] * counts[k] for k in range(len(counts))]
    best = int(np.argmin(per_prediction))
    return per_prediction[best], best

clf = ConTreeClassifier(max_depth=3, error_function=cost_sensitive).fit(X, y)

A few things change with a custom error:

• Threshold skipping is off by default (see below), so the search is slower.
• With "indices", the depth-2 solver is not used, because it works from class counts.
• The function is called from Rust for every leaf the search evaluates, often thousands of times, so keep it cheap. An exception raised inside it stops the search and is raised again by fit. A negative or NaN error, or a prediction that is not the index of a class, is a ValueError.
• train_error_ is the cost your function measured.

Threshold skipping

Most of ConTree’s speed comes from skipping thresholds without evaluating them: interval pruning in the general search, and skipping in the depth-2 solver’s scan. Both rest on one assumption, which the built-in error meets: moving n rows into a leaf never lowers its error and raises it by at most n, and moving them out never raises it and lowers it by at most n.

threshold_skipping chooses whether the search relies on it:

• "auto" (the default): on for the built-in error, off for an error_function, which may not meet the assumption.
• True: on, also for an error_function. Use it when you know your function meets the assumption, as misclassification does. fit warns with ThresholdSkippingWarning. The depth-2 solver then checks the assumption on the leaves it evaluates; if your function breaks it, fit warns again, statistics_["skipping_violations"] counts the cases, and status_ is "not_proven". The check catches a function that breaks the assumption; it cannot prove one correct.
• False: off. Slower, and never changes the result for the built-in error.

With min_sup > 1, interval pruning is never used, whatever the setting: its argument does not hold when a leaf must keep a minimum number of rows. True then forces only the depth-2 solver’s skipping, which does not depend on min_sup.

References

• C. E. Briţa, J. G. M. van der Linden and E. Demirović. Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound. AAAI 2025. (The exact search.)
• H. Kiossou, P. Schaus and S. Nijssen. Anytime Optimal Decision Tree Learning with Continuous Features. ECML PKDD 2026. (The anytime search.)