Linear discriminant trees

GuideClassifier can split on linear combinations of features instead of one feature at a time. With node_model="lda" each node selects its own features by one-way ANOVA F tests, splits on its first linear discriminant coordinate, and classifies its rows with linear discriminant analysis (LDA). With node_model="lda_splits" the nodes split the same way, but each cut minimizes the Gini impurity of its children and the leaves predict class proportions, as in an ordinary classification tree. Both reproduce GUIDE’s options of the same names.

This notebook compares them with a constant-leaf GUIDE tree, scikit-learn’s DecisionTreeClassifier (CART) and its LinearDiscriminantAnalysis on two scikit-learn datasets and on a synthetic problem whose class boundary is oblique.

import numpy as np
import pandas as pd
from sklearn.datasets import load_breast_cancer, load_wine
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.model_selection import StratifiedKFold, cross_validate
from sklearn.tree import DecisionTreeClassifier

from guide import GuideClassifier

rng = np.random.default_rng(0)
n = 600
X_obl = pd.DataFrame(rng.normal(size=(n, 4)), columns=["x1", "x2", "x3", "x4"])
score = X_obl["x1"] + X_obl["x2"] - 0.5 * X_obl["x3"]
y_obl = pd.Series(np.select([score < -0.8, score < 0.8], ["low", "mid"], "high"))

datasets = {
    "wine": load_wine(return_X_y=True, as_frame=True),
    "breast cancer": load_breast_cancer(return_X_y=True, as_frame=True),
    "oblique (synthetic)": (X_obl, y_obl),
}

Cross-validated comparison

Ten-fold cross-validated accuracy and log loss (lower is better), with the mean number of leaves. The GUIDE trees are pruned by their own internal cross-validation. LDA nodes default to min_samples_leaf=10, GUIDE’s default for this model.

models = {
    "GUIDE constant": GuideClassifier(),
    "GUIDE lda": GuideClassifier(node_model="lda", min_samples_leaf=10),
    "GUIDE lda_splits": GuideClassifier(node_model="lda_splits"),
    "CART": DecisionTreeClassifier(min_samples_leaf=5, random_state=0),
    "LDA": LinearDiscriminantAnalysis(),
}


def leaves(model):
    if hasattr(model, "get_n_leaves"):
        return model.get_n_leaves()
    return np.nan


rows = []
cv = StratifiedKFold(10, shuffle=True, random_state=0)
for data_name, (X, y) in datasets.items():
    for name, model in models.items():
        result = cross_validate(model, X, y, cv=cv, scoring=["accuracy", "neg_log_loss"],
                                return_estimator=True)
        rows.append({
            "dataset": data_name,
            "model": name,
            "accuracy": result["test_accuracy"].mean(),
            "log loss": -result["test_neg_log_loss"].mean(),
            "leaves": np.mean([leaves(m) for m in result["estimator"]]),
        })
pd.DataFrame(rows).set_index(["dataset", "model"]).round(3)
accuracy log loss leaves
dataset model
wine GUIDE constant 0.905 0.487 6.4
GUIDE lda 0.989 0.020 1.0
GUIDE lda_splits 0.950 0.232 3.5
CART 0.854 3.580 7.4
LDA 0.989 0.019 NaN
breast cancer GUIDE constant 0.942 0.249 7.1
GUIDE lda 0.958 0.149 1.7
GUIDE lda_splits 0.967 0.158 2.1
CART 0.933 1.211 14.3
LDA 0.956 0.130 NaN
oblique (synthetic) GUIDE constant 0.840 0.693 33.6
GUIDE lda 0.987 0.103 5.7
GUIDE lda_splits 0.982 0.110 3.0
CART 0.842 2.768 41.3
LDA 0.945 0.172 NaN

On wine the LDA tree never splits: one LDA leaf already separates the three cultivars, so it matches scikit-learn’s LDA (0.989 accuracy, log loss about 0.02), well ahead of both single-variable trees.

On breast cancer the two discriminant trees are the most accurate models (0.958 and 0.967), with one or two leaves on average against 7 for the constant GUIDE tree and 14 for CART. A single LDA still has the lowest log loss.

On the synthetic problem the three classes are bands along one oblique direction. Trees that split on one feature at a time need more than 30 leaves to approximate the boundary and reach only 0.84 accuracy; lda_splits finds it with three leaves and 0.982 accuracy, and the LDA tree does slightly better still. A single LDA (0.945) is limited by its shared covariance and Gaussian class densities, which the bands violate.

Reading a discriminant tree

Each split is a linear inequality in the node’s selected features; missing values take the node’s means.

X, y = datasets["oblique (synthetic)"]
tree = GuideClassifier(node_model="lda_splits", max_depth=2).fit(X, y)
print(tree.to_text())

guide-rs-0.1-experimental-reference28
1 tree(s), 3 fitted leaves
Tree 1
node 0 (n=600): 2.932656e-2 * x1 + 2.752057e-2 * x2 + -1.291214e-2 * x3 <= -2.422617e-2; missing values take node means
  node 1 (n=175): class "low"; p=[0.00046866333887964507, 0.9988297282307265, 0.0007016084303937881]
  node 2 (n=425): 5.050062e-2 * x1 + 4.730610e-2 * x2 + -2.412141e-2 * x3 <= 4.089382e-2; missing values take node means
    node 3 (n=259): class "mid"; p=[0.015444015444015444, 0.011583011583011584, 0.972972972972973]
    node 4 (n=166): class "high"; p=[0.9927906968974066, 0.0004936217415418746, 0.006715681361051527]