Implementation:Online ml River Tree LASTClassifier

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

Overview

Local Adaptive Streaming Tree (LAST) Classifier is an incremental decision tree with adaptive splitting mechanisms. LAST maintains a change detector at each leaf and triggers splits when drift is detected in either prediction errors or data distribution at that leaf.

Description

Unlike traditional Hoeffding Trees that rely on grace periods and Hoeffding bounds, LAST uses change detection to determine when to split. Each leaf maintains a drift detector that monitors either prediction errors (when track_error=True) or split criterion values (when track_error=False). When the detector signals drift, the leaf immediately evaluates split candidates and executes the best split if one exists with positive merit.

This "just change on change" philosophy makes LAST more reactive to concept drift at the local level, potentially creating more adaptive trees. However, LAST is not yet suitable as a base classifier in ensembles due to the change detectors.

Key features:

Drift detector at each leaf node
No grace period or Hoeffding bound constraints
Splits triggered by detected changes
Choice between error-based or distribution-based tracking
Support for three leaf prediction strategies
Immediate response to local concept drift

Usage

from river.datasets import synth
from river import evaluate
from river import metrics
from river import tree

gen = synth.ConceptDriftStream(stream=synth.SEA(seed=42, variant=0),
                       drift_stream=synth.SEA(seed=42, variant=1),
                       seed=1, position=1500, width=50)
dataset = iter(gen.take(3000))

model = tree.LASTClassifier()

metric = metrics.Accuracy()

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

Code Reference

Source Location: /tmp/kapso_repo_178qi9vb/river/tree/last_classifier.py

Signature:

class LASTClassifier(HoeffdingTreeClassifier, base.Classifier):
    def __init__(
        self,
        max_depth: int | None = None,
        split_criterion: str = "info_gain",
        leaf_prediction: str = "nba",
        change_detector: base.DriftDetector | None = None,
        track_error: bool = True,
        nb_threshold: int = 0,
        nominal_attributes: list | None = None,
        splitter: Splitter | None = None,
        binary_split: bool = False,
        min_branch_fraction: float = 0.01,
        max_share_to_split: float = 0.99,
        max_size: float = 100.0,
        memory_estimate_period: int = 1000000,
        stop_mem_management: bool = False,
        remove_poor_attrs: bool = False,
        merit_preprune: bool = True,
    )

Import:

from river.tree import LASTClassifier

I/O Contract

Input:

x (dict): Feature dictionary with attribute names as keys
y (int/str): Class label
w (float, optional): Sample weight (default: 1.0)

Output:

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

Key Parameters

change_detector (DriftDetector): Change detector at leaves (default: ADWIN)
track_error (bool): If True, track prediction errors; if False, track split criterion
split_criterion (str): Split criterion ('gini', 'info_gain', 'hellinger')
leaf_prediction (str): Prediction mechanism ('mc', 'nb', 'nba')
max_depth (int): Maximum tree depth
binary_split (bool): Restrict to binary splits
min_branch_fraction (float): Minimum branch sample percentage
max_share_to_split (float): Maximum majority class proportion for splitting

Implementation Details

Key Methods:

learn_one(x, y, w=1.0): Train on one instance with drift detection
_new_leaf(initial_stats, parent): Create leaf with embedded change detector
_attempt_to_split(leaf, parent, parent_branch): Execute split on drift detection
_new_split_criterion(): Create appropriate split criterion instance

Node Types:

LeafMajorityClassWithDetector: Majority class leaf with change detector
LeafNaiveBayesWithDetector: Naive Bayes leaf with change detector
LeafNaiveBayesAdaptiveWithDetector: Adaptive NB leaf with change detector

Change Detection Modes:

1. track_error=True (default):

  * Detector input: 1 if misclassification, 0 if correct
  * Reacts to changes in prediction performance
  * Works with all split criteria including Hellinger

2. track_error=False:

  * Detector input: split criterion value (e.g., Gini, entropy)
  * Reacts to changes in data distribution purity
  * Cannot use Hellinger distance (requires two distributions)

Learning Algorithm

Learning Process:

1. Route instance to appropriate leaf 2. Update leaf statistics and prediction model 3. Update leaf's change detector:

  * If track_error=True: input prediction error (0 or 1)
  * If track_error=False: input split criterion value

4. Check if drift detected AND depth < max_depth 5. If drift detected:

  * Evaluate all split candidates
  * Select candidate with highest merit
  * Split if merit > 0

6. Handle missing features by following most common path

Split Execution:

Unlike standard Hoeffding Trees, LAST splits immediately upon drift detection without checking Hoeffding bounds. The split occurs if:

Drift detector signals change
At least one split candidate has positive merit
Maximum depth not reached

Comparison with Hoeffding Trees

Feature	LAST	Hoeffding Tree
Split trigger	Drift detection	Grace period + Hoeffding bound
Statistical guarantees	None	Probabilistic (via Hoeffding bound)
Reactivity	High (immediate)	Moderate (delayed)
Drift adaptation	Local (per leaf)	None (base version)
Ensemble usage	Not recommended	Yes

Related Pages

References

Daniel Nowak Assis, Jean Paul Barddal, and Fabrício Enembreck. "Just Change on Change: Adaptive Splitting Time for Decision Trees in Data Stream Classification." In Proceedings of ACM SAC Conference (SAC'24).

Page Connections

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

Principle

Implementation

Heuristic

Environment