DL85Classifier

DL85Classifier finds the decision tree of at most max_depth levels with the fewest training errors, on binary features. It implements DL8.5, a dynamic programming search with branch-and-bound and a cache of subproblems: the rows that reach a node depend only on the tests on the path to it, so each set of tests is solved once and reused.

from pytrees import DL85Classifier

clf = DL85Classifier(max_depth=3, min_sup=5, max_time=60)
clf.fit(X, y)            # X holds only 0 and 1
clf.predict(X_test)
clf.status_              # "optimal" or "time_limit"

Parameters

Fitted attributes

Anytime search

With the default settings DL8.5 is a depth-first search: it may spend all its time in one part of the search space and return a poor tree when the time limit hits. The search rules fix that by restricting each pass of the search to the choices the heuristic prefers, then restarting with a wider budget until a pass completes. The last complete pass proves the tree optimal.

from pytrees import DL85Classifier
from pytrees.rules import DiscrepancyRule

clf = DL85Classifier(
    max_depth=5,
    heuristic="information_gain",
    discrepancy=DiscrepancyRule(),
    max_time=300,
)
clf.fit_anytime(X, y, callback=lambda error, seconds, status: print(seconds, error, status))

fit_anytime(X, y, callback) behaves like fit, and calls callback(error, seconds, status) whenever a pass improves the tree. While a rule still restricts the search, status is "budget_exhausted"; the last call has "optimal" or "time_limit".

Custom error functions

DL8.5 is not tied to the misclassification error. It finds the tree that minimises the sum of the errors of its leaves, for any error you define for a leaf. Pass it as error_function, a function that receives the content of a leaf and returns (error, prediction), where prediction is 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_. This covers any error that depends only on the class distribution, such as costs that differ per class.
• "indices": the indices of the rows in the leaf. The error can then depend on anything you know about those rows: sample weights, another target, distances between rows, and so on.

With class counts, for instance, missing class 1 can cost five times more than missing class 0:

import numpy as np
from pytrees import DL85Classifier

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

def cost_sensitive(class_counts):
    counts = np.asarray(class_counts, dtype=float)
    # Cost of predicting each class: every row of another class is an error.
    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 = DL85Classifier(max_depth=3, error_function=cost_sensitive).fit(X, y)

With row indices, each row can carry its own weight:

classes, y_index = np.unique(y, return_inverse=True)   # the encoding DL8.5 uses
weights = np.asarray(sample_weight, dtype=float)

def weighted_error(indices):
    rows = np.asarray(indices, dtype=int)
    # Weight of the rows each prediction would get wrong.
    per_prediction = [weights[rows][y_index[rows] != k].sum() for k in range(len(classes))]
    best = int(np.argmin(per_prediction))
    return per_prediction[best], best

clf = DL85Classifier(
    max_depth=3, error_function=weighted_error, error_function_input="indices"
).fit(X, y)

A few things change with a custom error:

• The similarity lower bound is turned off, because it assumes each row adds at most 1 to the error.
• With "indices", the depth-2 solver is not used, because it works from class counts. The search is slower as a result.
• 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.
• train_error_ is the error your function measured, not the number of misclassified rows.

DL85Cluster uses the same mechanism with row indices to learn clusterings.

Reference

G. Aglin, S. Nijssen and P. Schaus. Learning Optimal Decision Trees Using Caching Branch-and-Bound Search. AAAI 2020. The search rules are described in the papers listed on the search rules page.