Implementation:Online ml River Tree MondrianTreeClassifier

Knowledge Sources	Online_ml_River
Domains	Online_Learning, Decision_Trees, Classification, Mondrian_Process
Last Updated	2026-02-08 16:00 GMT

Overview

Mondrian Tree Classifier is an online decision tree that uses a Mondrian process to determine split times and locations. It provides fast incremental learning with optional aggregation weighting for improved predictions.

Description

Unlike traditional Hoeffding Trees that use statistical tests, Mondrian Trees use a stochastic process (the Mondrian process) to decide when and where to split. The algorithm samples split times from an exponential distribution based on how much the current sample extends the node's known feature ranges. This creates a hierarchical partition of the feature space that adapts to the data distribution.

Key features:

Mondrian process-based splitting (no Hoeffding bounds)
Aggregation weighting for combining predictions across tree levels
Jeffreys prior with Dirichlet parameter for smoothing
Bootstrap-like sampling capabilities
Theoretically grounded in Bayesian online learning

The algorithm maintains range information for each feature at every node and uses exponential sampling to determine if splits should occur. Splits happen more frequently in regions where data extends the known ranges.

Usage

from river import datasets
from river import evaluate
from river import metrics
from river import tree

dataset = datasets.Bananas().take(500)

model = tree.mondrian.MondrianTreeClassifier(
    step=0.1,
    use_aggregation=True,
    dirichlet=0.2,
    seed=1
)

metric = metrics.Accuracy()

evaluate.progressive_val_score(dataset, model, metric)
# Accuracy: 58.52%

Code Reference

Source Location: /tmp/kapso_repo_178qi9vb/river/tree/mondrian/mondrian_tree_classifier.py

Signature:

class MondrianTreeClassifier(MondrianTree, base.Classifier):
    def __init__(
        self,
        step: float = 0.1,
        use_aggregation: bool = True,
        dirichlet: float = 0.5,
        split_pure: bool = False,
        iteration: int = 0,
        seed: int | None = None,
    )

Import:

from river.tree.mondrian import MondrianTreeClassifier

I/O Contract

Input:

x (dict): Feature dictionary with attribute names as keys
y (int/str): Class label

Output:

predict_proba_one(x): Dictionary mapping class labels to probabilities
predict_one(x): Predicted class label

Key Parameters

step (float): Step parameter controlling weight updates (learning rate)
use_aggregation (bool): Enable aggregation weighting across tree levels
dirichlet (float): Dirichlet parameter for Jeffreys prior smoothing
split_pure (bool): Whether to split nodes with pure class distributions
iteration (int): Current iteration count (typically start at 0)
seed (int): Random seed for reproducibility

Implementation Details

Key Methods:

learn_one(x, y): Incrementally train on one instance
predict_proba_one(x): Predict class probabilities
_go_downwards(x, y): Update tree from root to leaf
_go_upwards(leaf): Update weights from leaf to root
_compute_split_time(y, node, extensions_sum): Calculate split time via Mondrian process
_split(node, split_time, threshold, feature, is_right_extension): Execute split
_score(node): Compute node score for class y
_loss(node): Compute node loss for class y
_predict(node): Get class probability predictions from node

Node Types:

MondrianLeafClassifier: Leaf node with class counts
MondrianBranchClassifier: Branch node with split information

Mondrian Process

Range Extension:

For each feature j and sample x: 1. Compute current range: [min_j, max_j] at node 2. Calculate extension:

  * If x_j < min_j: extension = min_j - x_j
  * If x_j > max_j: extension = x_j - max_j
  * Otherwise: extension = 0

3. Sum extensions: E = Σⱼ extension_j

Split Time Sampling:

If E > 0: 1. Sample T ~ Exponential(1/E) 2. Split time = node.time + T 3. Compare with child times (for branches) 4. Split if split_time is before child creation time

Split Feature Selection:

Sample feature j with probability proportional to its range extension: P(j) = extension_j / E

Threshold Sampling:

If right extension: threshold ~ Uniform(range_max, x_j)
If left extension: threshold ~ Uniform(x_j, range_min)

Learning Algorithm

Downward Phase:

1. Start at root node 2. For each node on path to leaf:

  * Compute range extensions for current sample
  * Sample split time from Mondrian process
  * If split time triggers:
    * Sample feature proportionally to extensions
    * Sample threshold uniformly in extension region
    * Create new branch with two children
    * Route sample to appropriate child
  * If no split:
    * Update node statistics and range
    * Move to next child

3. Reach leaf and update its statistics

Upward Phase (if aggregation enabled):

1. Start at the reached leaf 2. Update weight_tree at each node from leaf to root 3. weight_tree combines node weight with children's weight_tree

Prediction with Aggregation

Without aggregation:

Use leaf node prediction only

With aggregation: 1. Start at reached leaf 2. Move upward to root 3. At each node:

  * Compute weight: w = exp(weight - log_weight_tree)
  * Combine: P_new = 0.5 * w * P_node + (1 - 0.5 * w) * P_prev

4. Final prediction uses contributions from all ancestors

Score Computation:

Using Jeffreys prior: P(c | node) = (count(c) + α) / (n_samples + α * n_classes)

where α = dirichlet parameter

Split Decision Logic

Don't Split If:

split_pure=False AND node is pure (all samples have same class)
No range extension (E = 0)

Split Conditions:

For leaf nodes:

Always split if extension exists and split time sampled

For branch nodes:

Split if sampled split_time < child_time
This inserts a new split above existing subtree

Properties

The tree tracks:

iteration: Number of samples processed
_classes: Set of observed class labels
_root: Root node (initially a leaf)

Nodes track:

time: Creation time in Mondrian process
depth: Level in tree
n_samples: Sample count
counts: Class distribution
memory_range_min/max: Feature ranges
weight: Node weight (for aggregation)
log_weight_tree: Combined weight with subtree

Advantages

1. No Hyperparameters for Splitting: No grace period or delta needed 2. Theoretical Foundation: Bayesian interpretation via Mondrian process 3. Flexible: Can split at any time based on data 4. Aggregation: Uses entire path for prediction 5. Fast Updates: Single pass through path

Limitations

1. Performance: May not always match Hoeffding Trees on stationary data 2. Pure Nodes: May create unnecessary splits unless split_pure=False 3. Memory: Maintains range information at all nodes 4. Complexity: More complex than standard Hoeffding Trees

Related Pages

References

Balaji Lakshminarayanan, Daniel M. Roy, Yee Whye Teh. "Mondrian Forests: Efficient Online Random Forests." arXiv:1406.2673, pages 2-4.

Page Connections

Double-click a node to navigate. Hold to expand connections.

Principle

Implementation

Heuristic

Environment