Algorithm-Classifier-IsolationForest
view release on metacpan or search on metacpan
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
# parent never loads this module at compile time (its from_json requires
# it on demand), so there is no cycle.
use Algorithm::Classifier::IsolationForest ();
our $VERSION = '0.6.0';
# Node layout. Unlike the batch forest's nodes, online nodes are mutable
# and carry a running point count plus the bounding box (per-feature
# lo/hi) of every point that has passed through them -- that box is what
# split simulation samples from, since points themselves are never stored
# in the tree. Both node types share the first four slots so the
# learn/unlearn bookkeeping never has to branch on type:
#
# leaf: [0, count, \@lo, \@hi]
# internal: [1, count, \@lo, \@hi, attr, split, left, right]
#
# The type tag mirrors the parent's convention (0 is falsy, so
# while ($node->[0]) walks to a leaf). A leaf built from an empty
# synthetic partition has count 0 and an undef box (slots 2/3); the box
# is initialised from the first real point that reaches it.
use constant _N_TYPE => 0;
use constant _N_COUNT => 1;
use constant _N_LO => 2;
use constant _N_HI => 3;
use constant _N_ATTR => 4;
use constant _N_SPLIT => 5;
use constant _N_LEFT => 6;
use constant _N_RIGHT => 7;
use constant _NT_LEAF => 0;
use constant _NT_AXIS => 1;
# Trees are binary (the reference implementation's branching_factor == 2),
# which fixes the depth-budget log base at log(2 * 2). Spelled as the
# exact-double literal rather than log(4) so it is bit-identical to the
# OL_LOG4 literal the C learn path uses regardless of the platform's
# libm rounding -- a one-ulp disagreement would flip `depth < limit`
# split decisions exactly when a tree's count is eta * 4**k (the same
# TWO_PI trick the parent uses for _randn parity).
use constant _LOG4 => unpack( 'd', pack 'd', 1.3862943611198906 );
use constant _LOG2 => log(2);
# DBL_EPSILON, added to the normalisation factor before dividing so a
# just-started model (normaliser 0) yields well-defined scores instead of
# a division by zero -- the same guard the reference implementation uses.
use constant _EPS => 2.220446049250313e-16;
# The online learn/unlearn/score-row XS functions were added to the C
# backend after the batch-scoring ones, so a prebuilt object installed
# from an older release can back $HAS_C while lacking them (the parent
# trusts a flag-matched prebuilt object without inspecting its symbol
# set). Probe once at load: without them, use_c still accelerates the
# packed-snapshot batch scoring -- those functions have been in the
# object all along -- and learning quietly stays pure Perl instead of
# crashing on an undefined XS sub. Rebuilding/reinstalling (or
# IF_RUNTIME_BUILD=1) restores the full set.
use constant _HAS_ONLINE_XS => defined &Algorithm::Classifier::IsolationForest::online_learn_row_xs ? 1 : 0;
=head1 NAME
Algorithm::Classifier::IsolationForest::Online - Online (streaming) Isolation Forest anomaly detection
=head1 SYNOPSIS
use Algorithm::Classifier::IsolationForest::Online;
my $oif = Algorithm::Classifier::IsolationForest::Online->new(
n_trees => 100,
window_size => 2048,
max_leaf_samples => 32,
seed => 42,
);
# stream data through the model; each point is learned and old
# points beyond the window are forgotten automatically
$oif->learn(\@warmup_rows);
# prequential operation: score each point against the model as it
# stood BEFORE that point was learned, then learn it
my $scores = $oif->score_learn(\@new_rows);
# or score without learning
my $scores2 = $oif->score_samples(\@query_rows);
my $labels = $oif->predict(\@query_rows);
# persistence keeps the window, so a reloaded model keeps forgetting
# correctly as the stream continues
$oif->save('oiforest_model.json');
my $resumed = Algorithm::Classifier::IsolationForest::Online->load('oiforest_model.json');
=head1 DESCRIPTION
Implements Online Isolation Forest (Online-iForest; Leveni, Weigert
Cassales, Pfahringer, Bifet & Boracchi 2024 -- see REFERENCES), a
streaming variant of Isolation Forest for data that arrives continuously
and whose distribution may drift. There is no C<fit()>: the model
C<learn>s points as they arrive and, once more than C<window_size> points
have been seen, forgets the oldest point for every new one so the model
always reflects the most recent C<window_size> points of the stream.
Trees never store data points. Each node keeps only a running count of
the points that passed through it and the bounding box of their feature
values. A leaf splits once enough points have accumulated (see
C<max_leaf_samples> and C<growth>); because the actual points are gone,
the split simulates them by sampling uniformly inside the leaf's bounding
box. Forgetting reverses the process: counts are decremented along the
forgotten point's path and a subtree whose count falls below its split
requirement is collapsed back into a leaf.
Scoring follows the classic Isolation Forest intuition -- anomalies
isolate at shallow depth -- but normalises by the depth budget
C<log(n/max_leaf_samples) / log(4)> of the current window rather than the
batch model's C<c(psi)>. Scores are in (0, 1] with high values
anomalous, directly comparable in spirit (though not numerically) to the
parent class's scores.
Both learning and scoring are accelerated through the parent class's
Inline::C backend when it is available; C<use_c> covers them together.
Learning (and the per-row walks inside C<score_learn>) runs in C
directly against the live trees, drawing randomness through the same
generator in the same order as the pure-Perl path -- so, like the
parent's C<fit()>, a C<learn()> with a given seed produces bit-identical
trees whether C<use_c> is on or off (on C<nvsize == 8> perls; wide-NV
perls keep extra low bits in the pure-Perl path). The knob changes
speed, never results.
Batch scoring lazily flattens the mutable trees into the same packed
node layout the batch scorer walks -- online trees are axis-only, and
the online per-leaf depth adjustment rides in the slot the batch packer
uses for its own leaf adjustment -- so C<score_samples>, C<predict>,
C<path_lengths>, C<score_predict_samples>, and C<score_predict_split>
all run through the same C (and OpenMP, when linked) tree walk the
parent uses, with identical results to the pure-Perl fallback. Any
C<learn> invalidates the packed snapshot; the next batch-scoring call
repacks once. C<score_learn> never touches the snapshot: it mutates
the trees after every single point, so its rows are scored by walking
the live trees in C instead.
A model needs to have seen at least C<max_leaf_samples> points before
tree structure exists at all; until then every point scores 1.0. Give
the model a warm-up C<learn()> pass before trusting scores or labels.
Models saved by this class carry their own C<format> tag.
C<< Algorithm::Classifier::IsolationForest->load >> recognises it and
dispatches here, so callers can load either model type through the
parent class.
=head1 GENERAL METHODS
=head2 new(%args)
Inits the object.
- n_trees :: number of isolation trees in the ensemble
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
Learns the passed samples, in order, as the next points of the stream.
Once the model has seen more than C<window_size> points, each learned
point also forgets the oldest retained point, so the model tracks the
most recent C<window_size> points.
The data format matches the parent class's C<fit>: an arrayref of
arrayrefs, each inner arrayref one sample of numeric features. All
samples must have the same feature count; the count is locked in by the
first sample ever learned.
Returns C<$self>, so it chains.
$oif->learn(\@rows);
=cut
sub learn {
my ( $self, $data ) = @_;
croak "learn() expects a non-empty arrayref of samples"
unless ref $data eq 'ARRAY' && @$data;
for my $row (@$data) {
$self->_learn_row( $self->_prep_row( $row, 'learn' ) );
}
return $self;
}
=head2 learn_tagged(\%row)
=head2 learn_tagged(\@rows)
Learns one sample supplied as a hashref of named feature values, or a
whole batch supplied as an arrayref of such hashrefs, in stream order.
The model must have C<feature_names> set. Rows go through
L</tagged_row_to_array> (and therefore through the munger plan when
C<mungers> is configured). Returns C<$self>.
$oif->learn_tagged({ cpu => 0.9, mem => 0.4, disk => 0.1 });
$oif->learn_tagged(\@hashref_rows);
Croaks under the same conditions as L</tagged_row_to_array>, naming the
offending row by index in the batch form.
=cut
sub learn_tagged {
my ( $self, $row ) = @_;
if ( ref $row eq 'ARRAY' ) {
my @rows;
for my $i ( 0 .. $#$row ) {
push @rows, $self->tagged_row_to_array( $row->[$i], "learn_tagged (row $i)" );
}
return $self->learn( \@rows );
}
my $vec = $self->tagged_row_to_array( $row, 'learn_tagged' );
return $self->learn( [$vec] );
} ## end sub learn_tagged
=head2 score_learn(\@data)
Prequential (test-then-train) operation, the usual way to run a streaming
detector: each sample is scored against the model as it stood I<before>
that sample was learned, then learned. Returns an arrayref of anomaly
scores, one per sample, in input order.
Unlike the pure scoring methods this works on a brand-new model too (the
first points of a stream simply score 1.0, as nothing is known yet).
my $scores = $oif->score_learn(\@rows);
=cut
sub score_learn {
my ( $self, $data ) = @_;
croak "score_learn() expects a non-empty arrayref of samples"
unless ref $data eq 'ARRAY' && @$data;
my @scores;
for my $row (@$data) {
my $r = $self->_prep_row( $row, 'score_learn' );
push @scores, $self->_score_row($r);
$self->_learn_row($r);
}
return \@scores;
} ## end sub score_learn
=head2 score_learn_tagged(\%row)
Prequential score-then-learn for a single sample supplied as a hashref of
named feature values. Returns the scalar anomaly score the sample had
before it was learned.
my $score = $oif->score_learn_tagged({ cpu => 0.9, mem => 0.4 });
Croaks under the same conditions as L</tagged_row_to_array>.
=cut
sub score_learn_tagged {
my ( $self, $row ) = @_;
my $vec = $self->tagged_row_to_array( $row, 'score_learn_tagged' );
my $result = $self->score_learn( [$vec] );
return $result->[0];
}
=head2 score_samples(\@data)
Returns an arrayref of anomaly scores in (0, 1] without learning
anything. Scores near 1 are strong anomalies (isolated at shallow
depth); scores well below 0.5 are normal.
my $scores = $oif->score_samples(\@data);
=cut
sub score_samples {
my ( $self, $data ) = @_;
$self->_check_learned;
croak "score_samples() expects an arrayref of samples"
unless ref $data eq 'ARRAY';
if ( $self->_ensure_c_trees ) {
my ( $n_pts, $x_packed ) = $self->_pack_input($data);
my $sums_packed = "\0" x ( $n_pts * 8 );
Algorithm::Classifier::IsolationForest::score_all_xs(
$self->{_c_nodes}, $self->{_c_coef_idx}, $self->{_c_coef_val},
$x_packed, $sums_packed, $n_pts,
$self->{n_features}, scalar @{ $self->{trees} }, $self->{_use_openmp}
);
my $result = [];
Algorithm::Classifier::IsolationForest::finalize_scores_xs( $sums_packed, $n_pts, $self->_score_inv, $result );
return $result;
} ## end if ( $self->_ensure_c_trees )
my $sums = $self->_depth_sums($data);
my $inv = $self->_score_inv;
return [ map { exp( -$_ * $inv ) } @$sums ];
} ## end sub score_samples
=head2 score_sample_tagged(\%row)
Scores a single sample supplied as a hashref of named feature values,
without learning it. Returns a scalar anomaly score in (0, 1].
my $score = $oif->score_sample_tagged({ cpu => 0.9, mem => 0.4 });
Croaks under the same conditions as L</tagged_row_to_array>.
=cut
sub score_sample_tagged {
my ( $self, $row ) = @_;
my $vec = $self->tagged_row_to_array( $row, 'score_sample_tagged' );
my $result = $self->score_samples( [$vec] );
return $result->[0];
}
=head2 path_lengths(\@data)
Returns an arrayref of the mean isolation depth per sample across the
trees, for inspection -- the streaming counterpart of the parent class's
method of the same name. Depths include the per-leaf count adjustment.
my $depths = $oif->path_lengths(\@data);
=cut
sub path_lengths {
my ( $self, $data ) = @_;
$self->_check_learned;
croak "path_lengths() expects an arrayref of samples"
unless ref $data eq 'ARRAY';
my $t = scalar @{ $self->{trees} };
if ( $self->_ensure_c_trees ) {
my ( $n_pts, $x_packed ) = $self->_pack_input($data);
my $sums_packed = "\0" x ( $n_pts * 8 );
Algorithm::Classifier::IsolationForest::score_all_xs(
$self->{_c_nodes}, $self->{_c_coef_idx}, $self->{_c_coef_val},
$x_packed, $sums_packed, $n_pts,
$self->{n_features}, $t, $self->{_use_openmp}
);
my $result = [];
Algorithm::Classifier::IsolationForest::finalize_path_lengths_xs( $sums_packed, $n_pts, $t + 0.0, $result );
return $result;
} ## end if ( $self->_ensure_c_trees )
my $sums = $self->_depth_sums($data);
return [ map { $_ / $t } @$sums ];
} ## end sub path_lengths
=head2 predict(\@data, $threshold)
Returns an arrayref of 0/1 labels for the specified data, without
learning it.
If C<$threshold> is not given, the contamination-learned cutoff is used
when available (learned from the current window on first use -- see
C<contamination> in L</new>), otherwise 0.5.
Note that absolute score levels depend on C<window_size> and
C<max_leaf_samples> (shallower depth budgets compress scores downward),
so the 0.5 fallback is a blunt default here -- anomalies reliably rank
above normal points, but may sit below 0.5. Setting C<contamination>,
or passing a threshold calibrated from observed scores, is recommended.
my $labels = $oif->predict(\@data);
=cut
sub predict {
my ( $self, $data, $threshold ) = @_;
$self->_check_learned;
$self->_ensure_threshold;
$threshold
= defined $threshold ? $threshold
: defined $self->{threshold} ? $self->{threshold}
: 0.5;
# Fast path: threshold the raw depth sums directly, skipping the
# per-point exp() -- score >= T iff sum <= -log(T)/inv. Only valid
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
}
return $node;
} ## end sub _node_unlearn
# Aggregate a subtree back into a single leaf holding the subtree's
# (already decremented) count and the union of its descendants' boxes.
sub _collapse {
my ($node) = @_;
return $node if $node->[_N_TYPE] == _NT_LEAF;
my $l = _collapse( $node->[_N_LEFT] );
my $r = _collapse( $node->[_N_RIGHT] );
my ( $lo, $hi ) = _box_union( $l, $r );
if ( !defined $lo ) {
# Both children empty: keep the node's own box.
( $lo, $hi ) = ( $node->[_N_LO], $node->[_N_HI] );
}
return [ _NT_LEAF, $node->[_N_COUNT], $lo, $hi ];
} ## end sub _collapse
# (lo, hi) of the union of two nodes' boxes, as fresh arrays (parent
# boxes grow in place, so they must never alias a child's). Nodes with
# no box yet (empty leaves) are skipped; (undef, undef) if neither has
# one.
sub _box_union {
my ( $a, $b ) = @_;
my @boxed = grep { defined $_->[_N_LO] } ( $a, $b );
return ( undef, undef ) unless @boxed;
my $lo = [ @{ $boxed[0][_N_LO] } ];
my $hi = [ @{ $boxed[0][_N_HI] } ];
if ( @boxed == 2 ) {
my ( $blo, $bhi ) = ( $boxed[1][_N_LO], $boxed[1][_N_HI] );
for my $f ( 0 .. $#$lo ) {
$lo->[$f] = $blo->[$f] if $blo->[$f] < $lo->[$f];
$hi->[$f] = $bhi->[$f] if $bhi->[$f] > $hi->[$f];
}
}
return ( $lo, $hi );
} ## end sub _box_union
# (lo, hi) bounding box of a point set; (undef, undef) when empty.
sub _box_of {
my ($pts) = @_;
return ( undef, undef ) unless @$pts;
my $lo = [ @{ $pts->[0] } ];
my $hi = [ @{ $pts->[0] } ];
for my $p (@$pts) {
for my $f ( 0 .. $#$p ) {
$lo->[$f] = $p->[$f] if $p->[$f] < $lo->[$f];
$hi->[$f] = $p->[$f] if $p->[$f] > $hi->[$f];
}
}
return ( $lo, $hi );
} ## end sub _box_of
#-------------------------------------------------------------------------------
# Scoring.
#-------------------------------------------------------------------------------
# Depth of the leaf $x lands in, plus the leaf's own depth budget -- the
# streaming analogue of the batch scorer's c(leaf size) adjustment.
# Scoring tolerates undef cells (mapped to 0), matching the parent class.
sub _depth_of {
my ( $self, $x, $node ) = @_;
my $depth = 0;
while ( $node->[_N_TYPE] ) {
$node = ( $x->[ $node->[_N_ATTR] ] // 0 ) < $node->[_N_SPLIT] ? $node->[_N_LEFT] : $node->[_N_RIGHT];
$depth++;
}
return $depth + $self->_rpl( $node->[_N_COUNT] );
}
# Per-sample depth sums across all trees (tree-outer, sample-inner for
# cache locality, mirroring the parent's pure-Perl loops).
sub _depth_sums {
my ( $self, $data ) = @_;
my @sums = (0) x @$data;
for my $tree ( @{ $self->{trees} } ) {
my $root = $tree->{root};
next unless defined $root;
for my $i ( 0 .. $#$data ) {
$sums[$i] += $self->_depth_of( $data->[$i], $root );
}
}
return \@sums;
} ## end sub _depth_sums
# Single-row score against the current model state; used by the
# prequential score_learn loop, where the normaliser moves as points are
# learned and so must be recomputed per row.
sub _score_row {
my ( $self, $r ) = @_;
if ( _HAS_ONLINE_XS && $self->{_use_c} ) {
# Walks the live trees in C -- no packed snapshot involved, so
# this stays fast even though score_learn mutates the trees
# between rows.
my $sum = Algorithm::Classifier::IsolationForest::online_score_row_xs( $self->{trees}, $r,
$self->{n_features}, $self->{max_leaf_samples} );
return exp( -$sum * $self->_score_inv );
}
my $sum = 0;
for my $tree ( @{ $self->{trees} } ) {
$sum += $self->_depth_of( $r, $tree->{root} ) if defined $tree->{root};
}
return exp( -$sum * $self->_score_inv );
} ## end sub _score_row
#-------------------------------------------------------------------------------
# C-accelerated scoring.
#
# The parent class's Inline::C scorer walks immutable packed node buffers;
# online trees mutate on every learned point. The bridge is a lazily
# built snapshot: the first scoring call after any mutation flattens the
# live trees into the parent's packed node layout (below) and every
# scoring call until the next mutation reuses it. _learn_row -- the one
# choke point all mutations flow through -- drops the snapshot.
#
# Online trees are axis-only, so they map onto the parent's 6-double node
# records directly:
#
( run in 0.484 second using v1.01-cache-2.11-cpan-7fcb06a456a )