Random forest on sparse vectors

A from-scratch Random Forest that trains CART decision trees directly on sparse k-mer vectors, bags 100 of them, and reports out-of-bag accuracy plus split-count feature importance.

pathotypr implements a custom Random Forest classifier that operates directly on sparse feature vectors — no dense matrix conversion required.

Why sparse

This eliminates the O(N × 1M) memory overhead that a library like smartcore would require for N samples with 1M feature buckets.

Decision tree (CART)

Each tree is a binary classifier built with the CART algorithm (Classification and Regression Trees):

Node types

enum TreeNode {
    Split { feature: u32, threshold: f32, left: u32, right: u32 },
    Leaf { class: u32 },
}

Nodes are stored in a flat arena (Vec<TreeNode>) with index-based child pointers. This gives cache-friendly traversal and compact serialization.

Tree construction

Input: Sparse feature vectors [(bucket_idx, count)], class labels, bootstrap sample indices.

Algorithm (iterative DFS via explicit stack):

1. Start with all bootstrap samples at the root
2. For each node:
3. Count class frequencies in the current sample set
4. Stopping conditions: pure node (single class), depth >= max_depth, or n_samples <= 2 × min_samples_leaf
5. If not stopped, find the best split (see below)
6. Partition samples by the split and push children onto the stack

Finding the best split

1. Feature subsampling: Collect all features present in the current node's data. If more than sqrt(n_features) features are present, randomly sample sqrt(n_features) via partial Fisher-Yates shuffle.

2. For each candidate feature:

3. Extract (value, label) pairs via binary search on each sample's sparse row
4. Sort by value
5. Scan sorted values to find the threshold that maximizes Gini impurity reduction

6. Only consider splits where both sides have ≥ min_samples_leaf samples

7. Gini impurity: 1 - Σ(p_i²) where p_i is the proportion of class i.

8. Threshold: Midpoint between consecutive distinct values at the best split point.

Prediction

Traversal from root to leaf in O(tree_depth):

fn predict_one(row: &[(usize, f32)]) -> usize {
    loop {
        match node {
            Leaf { class } => return class,
            Split { feature, threshold, left, right } => {
                let val = binary_search(row, feature);  // O(log nnz)
                node = if val <= threshold { left } else { right };
            }
        }
    }
}

The sparse_lookup() function uses binary search on the sorted sparse row, returning 0.0 for absent features.

Ensemble (bagging)

Training

• 100 trees trained in parallel with rayon
• Each tree gets a bootstrap sample: N samples drawn with replacement from N total (each sample appears in ~63% of trees)

Reproducibility

A master RNG (seed = 42) generates one seed per tree, so each tree's bootstrap — and the whole ensemble — is reproducible from that single seed.

Majority voting

For prediction, all 100 trees vote. The class with the most votes wins:

confidence = winner_votes / total_trees
margin = (winner_votes - runner_up_votes) / total_trees

Both metrics are reported alongside the predicted class.

Out-of-bag (OOB) accuracy

Each tree's bootstrap sample excludes ~37% of training data. These "out-of-bag" samples provide a free accuracy estimate:

1. For each tree, regenerate its bootstrap using the stored seed
2. Identify OOB samples (not in the bootstrap)
3. Predict OOB samples using only that tree
4. Aggregate: for each training sample, collect votes from all trees where it was OOB
5. Compare majority vote to true label

Why this matters

OOB accuracy is nearly unbiased and requires no held-out test set. It's always computed, even when using CV for accuracy estimation.

Feature importance

Split-count importance: for each feature (bucket), count how many times it was used as a split across all 100 trees. Features that appear in many splits are more discriminative.

importance(feature_j) = Σ_{trees} count_of_splits_on_feature_j

The top 500 features are exported with:

• Their k-mer sequences (reverse-mapped from the hashing trick)
• Genomic coordinates (sequence index + position) in the training data

Hyperparameters

Parameter	Default	Effect
n_trees	100	More trees → smoother predictions, diminishing returns past ~100
max_depth	20	Limits tree complexity; prevents memorization of training noise
min_samples_leaf	5	Regularization — prevents splits that isolate individual samples
max_features	√(n_features)	Standard RF: decorrelates trees by forcing different feature subsets
bootstrap_seed	42 (master)	Ensures reproducibility; each tree derives its seed from this

Complexity

Operation	Time	Space
Train one tree	O(n_bootstrap × sqrt(F) × depth)	O(nodes) ≈ O(2^depth)
Train ensemble	Above / num_threads (rayon)	O(100 × nodes)
Predict one sample	O(100 × depth × log(nnz))	O(1)
OOB accuracy	O(N × 100 × depth)	O(N × n_classes)

See also

• train
• predict
• Training pipeline