# 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.0._Classical_Machine_Learning.md).
## 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.
| Algorithm | Tasks | Classification impurity | Split score | Categorical columns |
| --- | --- | --- | --- | --- |
| `ID3` | classification only | Shannon entropy | information gain (raw impurity decrease) | multi-way (one branch per value) |
| `C45` | classification only | Shannon entropy | gain **ratio** (gain / split information) | multi-way |
| `CART` | classification **and** regression | Gini for classification, MSE for regression | raw impurity decrease | binary only |
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](../Chapter-04/4.3._Label_Encoding.md)).
```rust
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.
```rust
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:
```rust,ignore
// 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.
| Builder | Field / type | Default | Constraint |
| --- | --- | --- | --- |
| `with_max_depth` | `max_depth: Option<usize>` | `None` (unlimited) | infallible, returns `Self` |
| `with_min_samples_split` | `min_samples_split: usize` | `2` | `>= 2`, else `InvalidParameter` |
| `with_min_samples_leaf` | `min_samples_leaf: usize` | `1` | `>= 1`, else `InvalidParameter` (also must be `<= min_samples_split`) |
| `with_min_impurity_decrease` | `min_impurity_decrease: f64` | `0.0` | non-negative and finite, else `InvalidParameter` |
| `with_random_state` | `random_state: Option<u64>` | `None` | infallible, returns `Self` |
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:
```rust
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](../Chapter-04/4.1._Train_Test_Split.md)). Score the result with the [classification metrics](../Chapter-05/5.2._Classification_Metrics.md).
## 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.
```rust
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](../Chapter-04/4.0._Data_Preprocessing.md)).
**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.
```rust
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](#244-hyperparameters-and-overfitting-control) 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.
```rust
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](../Chapter-07/7.1._Reproducibility_and_Random_Seeds.md) 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](../Chapter-01/1.6._Error_Handling.md):
- `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.
```rust
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](https://docs.rs/postcard) binary format through [serde](https://serde.rs). 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.
```rust
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](../Chapter-07/7.2._Model_Persistence_in_Depth.md) 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](../Chapter-07/7.3._Performance_Tuning_and_Parallelism.md) covers how to tune the thresholds.