2.4. Decision Trees

A decision tree splits the feature space into axis-aligned boxes with a chain of if/else tests. Each box gets one constant prediction: a class label (or class distribution) for classification, or the mean target for regression. RustyML packs this into one DecisionTree type. You choose the algorithm with the Algorithm parameter: ID3, C45, or CART.

In scikit-learn, you pick DecisionTreeClassifier or DecisionTreeRegressor, then pick a criterion with a criterion= string. RustyML makes the algorithm the top-level choice instead. Each Algorithm variant bundles the impurity measure, the split-selection rule, and the categorical-split policy together.

A numeric feature always splits on a binary threshold. A sample with feature <= t goes left. The algorithm changes only how RustyML scores thresholds and whether categorical columns get multi-way branches.

DecisionTree lives under rustyml::machine_learning. It follows the new -> fit -> predict contract from Classical Machine Learning.

2.4.1. Choosing an algorithm: ID3, C4.5, CART

The Algorithm enum has exactly 3 variants. The differences are not cosmetic. Each variant changes what the tree can do and how it scores a split.

This table gives 2 consequences. First, only CART supports regression. DecisionTree::new(Algorithm::ID3, false) and DecisionTree::new(Algorithm::C45, false) fail right away with Error::InvalidInput, not at fit time. The constructor is the fast-fail gate for this check.

Second, the C4.5 gain ratio fixes a bias in ID3 toward high-cardinality features. Information gain favors a feature with many distinct values. In the extreme, a unique-per-row ID column scores a perfect gain but does not generalize at all. C4.5 divides the gain by the split’s intrinsic information to penalize a split that fans out into many thin branches. When the intrinsic information falls to zero (a single-branch partition), C4.5 rejects the split. Gain ratio is the safer default when a dataset mixes categorical columns of very different cardinality.

For plain numeric data with no categorical columns, all 3 algorithms reduce to the same greedy binary-threshold search. They tend to agree on the result. Use CART unless you need entropy-based scoring or multi-way categorical branches.

2.4.2. Classification: construct, fit, predict

The classifier path is new(algorithm, true). Labels must be non-negative integers encoded as f64. They must be dense from 0. RustyML infers the number of classes as max(label) + 1. A label set like {0, 5} allocates 6 classes, with 4 of them empty and unused. Encode your labels to 0..k-1 before you fit (see Label Encoding).

use rustyml::machine_learning::{Algorithm, DecisionTree};
use ndarray::array;

fn main() {
    // 2 features, 3 classes, split cleanly along feature 0
    let x = array![
        [0.0, 0.0],
        [0.1, 0.0],
        [0.2, 0.1],
        [10.0, 1.0],
        [10.1, 1.0],
        [20.0, 2.0],
        [20.1, 2.0],
    ];
    let y = array![0.0, 0.0, 0.0, 1.0, 1.0, 2.0, 2.0];

    let mut tree = DecisionTree::new(Algorithm::CART, true)
        .unwrap()
        .with_max_depth(5)
        .with_random_state(42);
    tree.fit(&x, &y).unwrap();

    let x_test = array![[0.05, 0.0], [10.2, 1.0], [20.2, 2.0]];
    let labels = tree.predict(&x_test).unwrap(); // Array1<f64>, 1 label per row
    let proba = tree.predict_proba(&x_test).unwrap(); // Array2<f64>

    println!("labels: {:?}", labels);
    println!("proba shape: {:?}", proba.shape()); // [3, 3] = (n_samples, n_classes)
    println!("n_classes: {:?}", tree.get_n_classes()); // Some(3)
}

predict returns an Array1<f64> of labels. predict_proba returns an Array2<f64>. Each row is the leaf’s empirical class distribution, so it sums to 1.0. The argmax of each row agrees with the matching predict label.

On a pure leaf, the distribution is one-hot. On an impure leaf, it holds the exact class frequencies of the training samples that reached it. An impure leaf appears only when you stop growth early (see the next section).

DecisionTree also has 2 single-sample methods: predict_one(&[f64]) -> f64 and predict_proba_one(&[f64]) -> Vec<f64>. fit_predict fits the tree, then predicts on the same training matrix in 1 call.

Calling predict_proba on a regression tree is a runtime error. It returns Error::Tree(TreeError::NotClassificationTree).

2.4.3. Regression with CART

Set is_classifier = false to switch the tree to MSE impurity. MSE impurity is the population variance of a node’s targets. Each leaf predicts the mean of its training targets.

This rule explains the staircase output of a regression tree. Predictions are piecewise-constant, with 1 plateau per leaf. A regression tree never extrapolates beyond the training range.

use rustyml::machine_learning::{Algorithm, DecisionTree};
use ndarray::array;

fn main() {
    // Step function: the target jumps from 1 to 10 somewhere between x = 2 and x = 10
    let x = array![[0.0], [1.0], [2.0], [10.0], [11.0], [12.0]];
    let y = array![1.0, 1.0, 1.0, 10.0, 10.0, 10.0];

    // Only CART supports regression
    let mut tree = DecisionTree::new(Algorithm::CART, false).unwrap();
    tree.fit(&x, &y).unwrap();

    // Each query lands in a leaf and gets that leaf's mean target
    let preds = tree.predict(&array![[1.5], [11.5]]).unwrap();
    println!("{:?}", preds); // [1.0, 10.0], the 2 leaf means
}

A non-CART regressor request fails at construction time. This check is the only place RustyML validates the algorithm and task combination eagerly:

// ID3 and C4.5 are classification-only, so this fails fast:
let err = DecisionTree::new(Algorithm::ID3, false).unwrap_err();
// -> Error::InvalidInput("Only CART algorithm is supported for regression tasks")

2.4.4. Hyperparameters and overfitting control

A tree grown with no limits keeps splitting until every leaf is pure (classification) or holds a single sample (regression). That tree memorizes the training set, noise included. This is the classic decision-tree failure mode.

The 5 growth parameters below are the full toolbox for trading training fit against generalization. Four of them are pre-pruning stopping rules that apply during growth. RustyML does no post-pruning. It has no ccp_alpha-style cost-complexity pruning, so all overfitting control happens before training starts.

The bounded setters return Result. Use .unwrap() or ? after them in a chain. with_max_depth and with_random_state return Self directly, with no Result.

One rule spans both min_samples_leaf and min_samples_split. Since you set them independently, no single builder can enforce it. min_samples_leaf must not exceed min_samples_split. RustyML checks this constraint at fit time and returns Error::InvalidParameter on a bad pairing. A bad pairing fails when you train, not when you build the tree.

Each parameter rejects a candidate split for a different reason:

• max_depth caps the number of edges on any root-to-leaf path. Some(0) forces the root to be a leaf. That leaf predicts the global majority class (or global mean), a useful sanity baseline.
• min_samples_split stops a node from splitting when it holds fewer samples than this value. It ends recursion early and yields a shallower tree.
• min_samples_leaf constrains the split search, not just the final pick. RustyML never considers a threshold that would leave a child below this minimum. Instead of collapsing the node into a leaf, the tree falls back to the best split whose children both satisfy the floor. This matches scikit-learn semantics. It is the parameter people misread most often: a rare category or a lone outlier does not throw away an otherwise good split.
• min_impurity_decrease rejects a split whose impurity decrease, scaled by N_t / N_total, falls below the threshold. N_t / N_total is the fraction of all training samples that reach the node. This node-weight scaling follows the scikit-learn convention. A large impurity drop deep in the tree, where few samples remain, counts for less than the same drop near the root.

The next example contrasts an overfit tree with a constrained one, on data with 2 deliberately mislabeled points. The unconstrained tree grows extra depth to isolate the noise and reaches 100% training accuracy. The constrained tree stays shallow and keeps every leaf populated, so it does not fit the noise:

use rustyml::machine_learning::{Algorithm, DecisionTree, Node, NodeType};
use ndarray::{array, Array1, Array2};

// Longest root-to-leaf path in edges (a bare leaf is depth 0)
fn depth(node: &Node) -> usize {
    match &node.node_type {
        NodeType::Leaf { .. } => 0,
        NodeType::Internal { .. } => {
            let mut d = 0;
            if let Some(l) = &node.left {
                d = d.max(depth(l));
            }
            if let Some(r) = &node.right {
                d = d.max(depth(r));
            }
            if let Some(children) = &node.children {
                for c in children.values() {
                    d = d.max(depth(c));
                }
            }
            1 + d
        }
    }
}

fn train_accuracy(tree: &DecisionTree, x: &Array2<f64>, y: &Array1<f64>) -> f64 {
    let preds = tree.predict(x).unwrap();
    let correct = preds
        .iter()
        .zip(y.iter())
        .filter(|(p, t)| (*p - *t).abs() < 0.5)
        .count();
    correct as f64 / y.len() as f64
}

fn main() {
    // Underlying rule: x <= 4 -> class 0, x >= 5 -> class 1.
    // 2 labels violate it: x = 1 and x = 8 are flipped noise.
    let x = array![[0.0], [1.0], [2.0], [3.0], [4.0], [5.0], [6.0], [7.0], [8.0], [9.0]];
    let y = array![0.0, 1.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 1.0];

    // Unconstrained: grows until pure, memorizing the noise
    let mut overfit = DecisionTree::new(Algorithm::CART, true).unwrap();
    overfit.fit(&x, &y).unwrap();

    // Constrained: 1 split deep, every leaf must retain >= 2 samples
    let mut constrained = DecisionTree::new(Algorithm::CART, true)
        .unwrap()
        .with_max_depth(1)
        .with_min_samples_leaf(2)
        .unwrap();
    constrained.fit(&x, &y).unwrap();

    println!(
        "unconstrained: depth {}, train acc {:.3}",
        depth(overfit.get_root().unwrap()),
        train_accuracy(&overfit, &x, &y)
    );
    println!(
        "constrained:   depth {}, train acc {:.3}",
        depth(constrained.get_root().unwrap()),
        train_accuracy(&constrained, &x, &y)
    );
}

The unconstrained tree reports a deeper structure and perfect training accuracy. The constrained tree has a single split, with 2 errors it deliberately keeps. On unseen data, the shallow tree is the one you want.

Real tuning sweeps these parameters against a validation split (see Train-Test Split). Score the result with the classification metrics.

2.4.5. Categorical features, missing values, and constant columns

RustyML has no separate categorical dtype. Every feature is an f64 column. You declare which columns hold discrete category codes with set_categorical_features(vec![...]). This is a &mut self setter. Call it between new and fit.

Under ID3 or C45, a declared column splits multi-way, with 1 child branch per distinct value. A multi-way split solves a pattern that a single numeric threshold cannot, such as “class 1 only when the code equals 1”. CART is binary by construction and ignores the declaration completely. On a CART tree, marking a column categorical does nothing. RustyML gives no warning.

use rustyml::machine_learning::{Algorithm, DecisionTree};
use ndarray::array;

fn main() {
    // 1 categorical feature (codes 0/1/2). Class depends on the code, not on any
    // single numeric cut: 0 -> class 0, 1 -> class 1, 2 -> class 0.
    let x = array![[0.0], [0.0], [1.0], [1.0], [2.0], [2.0]];
    let y = array![0.0, 0.0, 1.0, 1.0, 0.0, 0.0];

    let mut tree = DecisionTree::new(Algorithm::C45, true).unwrap();
    tree.set_categorical_features(vec![0]); // treat column 0 as categorical
    tree.fit(&x, &y).unwrap();

    // Each distinct code becomes its own branch, so the pattern is learned exactly
    println!("train preds: {:?}", tree.predict(&x).unwrap());

    // A category never seen in training routes to the node's fallback leaf: no error
    println!("unseen code 99 -> {:?}", tree.predict(&array![[99.0]]).unwrap());
}

RustyML canonicalizes category values by rounding to 6 decimals. 1.0000001 and 1.0000002 collapse into the same branch, while 1.0 and 2.0 stay distinct. Encode your codes as clean integers stored in f64, to avoid surprises.

At predict time, an unseen category cannot match any branch. It falls through to a stored fallback leaf, the majority prediction of the parent node’s training samples. You always get a valid prediction, never an error.

Even under ID3 or C45, min_samples_leaf still guards categorical splits. RustyML keeps a split as long as at least 2 branches each meet the leaf floor. One rare category with too few samples does not discard the whole multi-way split.

Missing values. RustyML has no NaN routing. fit and predict both check every input for finiteness. Any NaN or infinity in the feature matrix returns Error::NonFinite. Impute or drop missing entries before training (see Data Preprocessing).

Constant columns. A constant column is harmless. A numeric split is valid only between 2 distinct feature values. A column that never varies gives no candidate threshold, so RustyML skips it. A declared categorical column with fewer than 2 distinct values likewise gives no split. A constant feature costs a little search time but never corrupts the tree.

2.4.6. Inspecting the fitted tree

A fitted tree is easy to inspect. generate_tree_structure() returns a ready-to-print ASCII rendering of the tree: splits, thresholds, leaf classes, and probability vectors. It returns Error::NotFitted when you call it before training.

use rustyml::machine_learning::{Algorithm, DecisionTree};
use ndarray::array;

fn main() {
    let x = array![[0.0], [1.0], [2.0], [3.0]];
    let y = array![0.0, 0.0, 1.0, 1.0];

    let mut tree = DecisionTree::new(Algorithm::CART, true).unwrap();
    tree.fit(&x, &y).unwrap();

    print!("{}", tree.generate_tree_structure().unwrap());
    println!("features seen: {}", tree.get_n_features());
}

For programmatic inspection, get_root() -> Option<&Node> returns the raw tree. Node is public, with fields node_type, left, right, and children (an AHashMap<String, Box<Node>> for multi-way categorical nodes). NodeType is either Internal { feature_index, threshold, categories } or Leaf { value, class, probabilities }.

The depth helper in 2.4.4 walks this structure. You can walk it too, to extract feature-importance statistics or export the tree to another format.

The remaining getters are plain accessors. They are get_algorithm(), get_is_classifier(), get_n_features(), get_n_classes() (None for regression), get_parameters() (a Copy DecisionTreeParams), and get_categorical_features().

2.4.7. Determinism and seeding

Growth is greedy and deterministic, with one exception. When 2 or more candidate splits tie at the exact same selection score, the tree must break the tie.

With random_state = None and no crate-wide seed set, tie-breaking is deterministic. The last tied candidate wins. Repeated fits on the same data give a bit-for-bit identical tree. You do not need a seed for reproducibility, even on data with ties.

Set with_random_state(seed) to pick a uniformly random tied candidate from a seeded stream instead. The same seed reproduces the same tree. Different seeds may pick different, equally-scoring features.

use rustyml::machine_learning::{Algorithm, DecisionTree};
use ndarray::array;

fn main() {
    // Features 0 and 1 are identical columns, so their best splits tie exactly
    let x = array![[0.0, 0.0], [0.0, 0.0], [1.0, 1.0], [1.0, 1.0]];
    let y = array![0.0, 0.0, 1.0, 1.0];

    let fit_seeded = |seed: u64| {
        let mut t = DecisionTree::new(Algorithm::CART, true)
            .unwrap()
            .with_random_state(seed);
        t.fit(&x, &y).unwrap();
        t.generate_tree_structure().unwrap()
    };

    // Same seed -> identical tree, even though ties are broken at random
    assert_eq!(fit_seeded(7), fit_seeded(7));
    println!("seed 7 is reproducible");
}

random_state = Some(seed) uses that seed on its own and ignores any global seed. A tree left at random_state = None instead draws its tie-breaking randomness from the thread-local global stream, when one is active. Call set_global_seed(s) (paired with clear_global_seed()) to make a whole pipeline of unseeded models reproducible together.

Reproducibility and Random Seeds covers the mechanics and the reasoning behind routing all randomness through one seed.

2.4.8. Errors

Tree-specific failures live in the TreeError enum, re-exported as rustyml::machine_learning::TreeError. You reach it through the crate-wide Error::Tree variant. It is #[non_exhaustive] and has 2 members.

NotClassificationTree returns when you call predict_proba or predict_proba_one on a regression tree. CorruptStructure(&'static str) guards an invariant violation. A normally fitted and used model never triggers it. It protects tree traversal against a hand-built or otherwise broken node graph.

Every other error comes from the shared error surface in Error Handling:

• InvalidInput: bad labels, too few samples, or zero features.
• InvalidParameter: an out-of-range builder value, or the min_samples_leaf > min_samples_split cross-check.
• NonFinite: NaN or infinity in features.
• NotFitted: returned before training.
• EmptyInput: empty training or prediction data.
• DimensionMismatch { expected, found }: a prediction matrix with the wrong feature count.

use rustyml::machine_learning::{Algorithm, DecisionTree, TreeError};
use rustyml::error::Error;
use ndarray::array;

fn main() {
    let x = array![[0.0], [1.0], [2.0], [10.0], [11.0], [12.0]];
    let y = array![1.0, 1.0, 1.0, 10.0, 10.0, 10.0];

    let mut reg = DecisionTree::new(Algorithm::CART, false).unwrap();
    reg.fit(&x, &y).unwrap();

    // A regression tree has no class probabilities to report
    match reg.predict_proba(&x) {
        Err(Error::Tree(TreeError::NotClassificationTree)) => {
            println!("predict_proba is classification-only");
        }
        other => panic!("unexpected: {:?}", other),
    }
}

2.4.9. Persistence

A fitted DecisionTree serializes with save_to_path and load_from_path. These methods write and read the compact postcard binary format through serde. The whole structure round-trips, including the AHashMap children of multi-way categorical nodes. A loaded model reproduces predictions exactly.

You can name the file anything you want. The content is binary regardless of the file extension.

use rustyml::machine_learning::{Algorithm, DecisionTree};
use ndarray::array;

fn main() {
    let x = array![[0.0], [1.0], [2.0], [10.0], [11.0], [12.0]];
    let y = array![0.0, 0.0, 0.0, 1.0, 1.0, 1.0];

    let mut tree = DecisionTree::new(Algorithm::CART, true).unwrap();
    tree.fit(&x, &y).unwrap();

    tree.save_to_path("dt_model.bin").unwrap();
    let loaded = DecisionTree::load_from_path("dt_model.bin").unwrap();

    // Predictions survive the round trip bit-for-bit
    assert_eq!(tree.predict(&x).unwrap(), loaded.predict(&x).unwrap());
    println!("round trip OK");

    std::fs::remove_file("dt_model.bin").unwrap();
}

A failed read, a failed write, or a corrupt payload returns Error::Io. See Model Persistence in Depth for the format’s guarantees and version considerations.

2.4.10. Complexity and parallelism

Growing a node sorts each feature’s values once, then sweeps them with running impurity statistics. A node over n samples costs O(n_features * n log n). For a reasonably balanced tree, this compounds to roughly O(n_features * n log^2 n) overall. This is the standard cost of a CART-style learner. It is why a wide dataset (many features) dominates the training budget.

Prediction is a root-to-leaf walk, at O(depth) per sample. The trained tree does not store its own depth. The parallel gate instead assumes a walk of about 16 nodes as a stand-in value.

RustyML runs 2 independent rayon parallelizations, once the work clears a calibrated gate. During fit, the per-feature split search runs in parallel when n_samples * n_features clears the sort-scan gate. During predict or predict_proba, per-sample traversal runs in parallel when the sample count clears the tree-traversal gate.

A small problem stays single-threaded, to avoid parallel overhead. You do nothing to opt in. These gates pick a strategy only. They never change the result. Performance Tuning and Parallelism covers how to tune the thresholds.