Algorithm-Classifier-IsolationForest
view release on metacpan or search on metacpan
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
# 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
default :: 100
- window_size :: how many of the most recent points the model reflects.
Once the stream exceeds this, learning a point forgets the
oldest retained point. 0 or undef disables forgetting: the
model then learns from the whole stream and retains no window
(so nothing is ever unlearned and threshold relearning needs
caller-supplied data).
default :: 2048
- max_leaf_samples :: how many points a leaf must accumulate before it
splits (eta in the paper). Also the unit of the depth budget:
trees stop splitting past log(n/eta)/log(4).
default :: 32
- growth :: how the split requirement scales with depth (the reference
implementation's `type` parameter).
adaptive :: a leaf at depth k needs max_leaf_samples * 2**k
points to split -- deeper splits need
exponentially more evidence
fixed :: max_leaf_samples points regardless of depth
default :: adaptive
- subsample :: probability in (0, 1] that a given tree learns (or
forgets) a given point, drawn independently per tree per point.
Values below 1 increase diversity among trees on very dense
streams. Note that, as in the reference implementation, learn
and forget draws are independent, so per-tree counts are only
approximate under subsampling.
default :: 1.0
- seed :: optional integer to seed srand with, for reproducible trees
given the same stream in the same order. Processed via
abs(int()). Seeding happens here in new(), since there is no
fit() to do it in.
default :: undef
- contamination :: expected fraction of anomalies, in (0, 0.5]. When
set, the first predict()-family call learns a score threshold
that flags this fraction of the current window, and uses it as
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
my $growth = $args{growth} // 'adaptive';
croak "growth must be 'adaptive' or 'fixed'"
unless $growth =~ /\A(?:adaptive|fixed)\z/;
my $missing = $args{missing} // 'die';
croak "missing must be one of: die, zero"
unless $missing =~ /\A(?:die|zero)\z/;
if ( defined( $args{seed} ) ) {
$args{seed} = abs( int( $args{seed} ) );
}
# window_size => 0 and window_size => undef both mean "no forgetting";
# normalise to 0 so the rest of the code has one falsy spelling.
my $window_size = exists $args{window_size} ? ( $args{window_size} // 0 ) : 2048;
# Clamp the accel knobs against what the parent's build actually has,
# exactly as the parent's new() does: use_c => 1 without a compiled
# backend would otherwise call undefined XS subs at first scoring, and
# OpenMP is meaningless without the C tree walk.
my $use_c
= defined $args{use_c}
? ( $args{use_c} && $Algorithm::Classifier::IsolationForest::HAS_C ? 1 : 0 )
: $Algorithm::Classifier::IsolationForest::HAS_C;
my $use_openmp
= defined $args{use_openmp}
? ( $args{use_openmp} && $Algorithm::Classifier::IsolationForest::HAS_OPENMP ? 1 : 0 )
: $Algorithm::Classifier::IsolationForest::HAS_OPENMP;
$use_openmp = 0 unless $use_c;
my $self = {
n_trees => $args{n_trees} // 100,
window_size => $window_size,
max_leaf_samples => $args{max_leaf_samples} // 32,
growth => $growth,
subsample => $args{subsample} // 1.0,
seed => $args{seed},
contamination => $args{contamination},
missing => $missing,
feature_names => $args{feature_names},
threshold => undef, # learned lazily if contamination set
n_features => undef, # learned from the first row
seen => 0, # total points learned over the model's lifetime
window => [], # the retained rows, oldest first
trees => [],
mungers => undef, # optional Algorithm::ToNumberMunger spec hash
# Opaque schema metadata, usually set via the parent class's
# new_from_prototype and persisted with the model.
schema_version => $args{schema_version},
schema_description => $args{schema_description},
feature_descriptions => $args{feature_descriptions},
_use_c => $use_c,
_use_openmp => $use_openmp,
};
for my $doc (qw(schema_version schema_description)) {
croak "$doc must be a plain string"
if defined $self->{$doc} && ref $self->{$doc};
}
Algorithm::Classifier::IsolationForest::_validate_feature_descriptions( $self->{feature_names},
$self->{feature_descriptions} )
if defined $self->{feature_descriptions};
# Optional Algorithm::ToNumberMunger integration, identical to the
# parent's: compiled eagerly so spec errors surface here; the module
# is only required when a spec is actually given.
if ( defined $args{mungers} ) {
croak "mungers must be a hashref of 'tag => munger spec'"
unless ref $args{mungers} eq 'HASH';
croak "mungers requires feature_names (the munger plan compiles against them)"
unless ref $self->{feature_names} eq 'ARRAY' && @{ $self->{feature_names} };
$self->{mungers} = $args{mungers};
$self->{_munger_plan}
= Algorithm::Classifier::IsolationForest::_compile_mungers( $self->{feature_names}, $self->{mungers} );
$self->{munger_module_version} = $Algorithm::ToNumberMunger::VERSION;
} ## end if ( defined $args{mungers} )
croak "n_trees must be >= 1" unless $self->{n_trees} >= 1;
croak "max_leaf_samples must be >= 1" unless $self->{max_leaf_samples} >= 1;
croak "window_size must be 0 (unbounded) or >= max_leaf_samples"
if $self->{window_size} && $self->{window_size} < $self->{max_leaf_samples};
croak "subsample must be in (0, 1]"
unless $self->{subsample} > 0 && $self->{subsample} <= 1;
croak "contamination must be a number in (0, 0.5]"
if defined $self->{contamination}
&& !( $self->{contamination} > 0 && $self->{contamination} <= 0.5 );
$self->{trees} = [ map { { root => undef, count => 0, depth_limit => 0 } } 1 .. $self->{n_trees} ];
srand( $self->{seed} ) if defined $self->{seed};
return bless $self, $class;
} ## end sub new
=head2 learn(\@data)
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;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
} elsif ( scalar @$row != $self->{n_features} ) {
croak "$caller: sample has " . scalar(@$row) . " features but model expects " . $self->{n_features};
}
if ( $self->{missing} eq 'die' ) {
for my $f ( 0 .. $#$row ) {
next if defined $row->[$f];
croak "$caller: undef feature value at column $f; "
. "construct with missing => 'zero' to learn from data with missing values";
}
return [@$row];
}
# zero: a missing cell counts as the value 0.
return [ map { $_ // 0 } @$row ];
} ## end sub _prep_row
# The depth budget for n points: how deep a tree fed n points is allowed
# (learn) or expected (scoring normalisation, per-leaf adjustment) to
# go. log base 4 = log(2 * branching_factor) with binary trees. Under
# max_leaf_samples points there is nothing to isolate: 0.
sub _rpl {
my ( $self, $n ) = @_;
my $eta = $self->{max_leaf_samples};
return 0 if $n < $eta;
return log( $n / $eta ) / _LOG4;
}
# How many points a node at $depth needs before it may split (or below
# which, on forgetting, it collapses back into a leaf).
sub _split_threshold {
my ( $self, $depth ) = @_;
return $self->{max_leaf_samples} * ( $self->{growth} eq 'adaptive' ? 2**$depth : 1 );
}
# Number of points the model currently reflects: the window fill, or the
# whole stream when forgetting is disabled.
sub _data_size {
my ($self) = @_;
return $self->{window_size} ? scalar @{ $self->{window} } : $self->{seen};
}
# exp() multiplier turning a per-sample depth SUM into the normalised
# anomaly score: 2**(-(sum/t)/norm) == exp(-sum * log(2)/(t*norm)).
# _EPS keeps a zero normaliser (fewer than max_leaf_samples points seen)
# well-defined; every depth is 0 then, so everything scores 1.0.
sub _score_inv {
my ($self) = @_;
my $norm = $self->_rpl( $self->_data_size * $self->{subsample} );
return _LOG2 / ( $self->{n_trees} * ( $norm + _EPS ) );
}
#-------------------------------------------------------------------------------
# Learning.
#-------------------------------------------------------------------------------
# Advance the stream by one (already prepped) row: every tree learns it
# (subject to subsampling), it enters the window, and the oldest point
# beyond the window is forgotten. This is the single choke point through
# which every tree mutation flows, so it is also where the packed C
# scoring snapshot gets invalidated.
#
# With use_c the per-tree learn and eviction loops run inside the
# parent's C backend (online_learn_row_xs / online_unlearn_row_xs),
# mutating the same live trees this file's Perl recursion would. Random
# draws go through the same generator in the same order, so the trees
# built are bit-identical either way (on nvsize == 8 perls) -- use_c
# only changes speed, matching fit()'s guarantee.
sub _learn_row {
my ( $self, $r ) = @_;
my $sub = $self->{subsample};
$self->_invalidate_c_trees;
if ( _HAS_ONLINE_XS && $self->{_use_c} ) {
Algorithm::Classifier::IsolationForest::online_learn_row_xs(
$self->{trees}, $r, $self->{n_features},
$self->{max_leaf_samples},
( $self->{growth} eq 'adaptive' ? 1 : 0 ), $sub
);
} else {
for my $tree ( @{ $self->{trees} } ) {
next if $sub < 1 && rand() >= $sub;
$self->_tree_learn( $tree, $r );
}
}
$self->{seen}++;
if ( $self->{window_size} ) {
push @{ $self->{window} }, $r;
if ( @{ $self->{window} } > $self->{window_size} ) {
my $old = shift @{ $self->{window} };
if ( _HAS_ONLINE_XS && $self->{_use_c} ) {
Algorithm::Classifier::IsolationForest::online_unlearn_row_xs(
$self->{trees}, $old, $self->{n_features},
$self->{max_leaf_samples},
( $self->{growth} eq 'adaptive' ? 1 : 0 ), $sub
);
} else {
for my $tree ( @{ $self->{trees} } ) {
next if $sub < 1 && rand() >= $sub;
$self->_tree_unlearn( $tree, $old );
}
}
} ## end if ( @{ $self->{window} } > $self->{window_size...})
} ## end if ( $self->{window_size} )
return;
} ## end sub _learn_row
sub _tree_learn {
my ( $self, $tree, $x ) = @_;
$tree->{count}++;
$tree->{depth_limit} = $self->_rpl( $tree->{count} );
if ( !defined $tree->{root} ) {
$tree->{root} = [ _NT_LEAF, 1, [@$x], [@$x] ];
} else {
$tree->{root} = $self->_node_learn( $tree->{root}, $x, 0, $tree->{depth_limit} );
}
return;
} ## end sub _tree_learn
# Route $x down to its leaf, growing counts and bounding boxes along the
# path. A leaf that has accumulated its split requirement (and still has
# depth budget) is replaced by a subtree built from synthetic points
# sampled inside its box -- the return value replaces the node in the
# parent, which is how leaves turn into subtrees in place.
sub _node_learn {
my ( $self, $node, $x, $depth, $limit ) = @_;
$node->[_N_COUNT]++;
if ( !defined $node->[_N_LO] ) {
# Leaf born from an empty synthetic partition: first real point
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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:
#
# leaf: [0, count, _rpl(count), 0, 0, 0]
# axis: [1, attr, split, li, ri, 0]
#
# The parent packs c(leaf size) into slot 2 and its C walker returns
# depth + slot2 at a leaf; packing the online depth-budget adjustment
# _rpl(count) there instead makes score_all_xs compute exactly the
# pure-Perl _depth_of value, so every downstream C helper (finalize_*,
# predict_sums_xs, score_predict_*) applies unchanged. The per-tree
# coefficient buffers are empty -- there are no oblique nodes -- and only
# exist because score_all_xs expects them.
#
# score_learn deliberately never uses this path: it mutates the trees
# after every single point, so the snapshot could never be reused and
# repacking per point would cost more than the walks it replaces.
#-------------------------------------------------------------------------------
# Drop the packed snapshot; called on every mutation.
sub _invalidate_c_trees {
delete @{ $_[0] }{qw(_c_nodes _c_coef_idx _c_coef_val)};
return;
}
# Build (or reuse) the packed snapshot. Returns true when the C scoring
# path may be taken, false when the caller must use the pure-Perl walk.
sub _ensure_c_trees {
my ($self) = @_;
return 0 unless $self->{_use_c};
return 1 if $self->{_c_nodes};
my ( @c_nodes, @c_coef_idx, @c_coef_val );
my $empty_idx = pack('l*');
my $empty_val = pack('d*');
for my $tree ( @{ $self->{trees} } ) {
push @c_nodes, $self->_pack_online_tree( $tree->{root} );
push @c_coef_idx, $empty_idx;
push @c_coef_val, $empty_val;
}
$self->{_c_nodes} = \@c_nodes;
$self->{_c_coef_idx} = \@c_coef_idx;
$self->{_c_coef_val} = \@c_coef_val;
return 1;
} ## end sub _ensure_c_trees
# Flatten one live tree into the parent's packed node buffer (DFS
# pre-order, root at index 0 -- the origin score_all_xs walks from).
sub _pack_online_tree {
my ( $self, $root ) = @_;
# A tree that has not learned anything walks as depth 0 with a zero
# adjustment: one empty leaf record.
return pack( 'd*', 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 ) unless defined $root;
my @node_data;
my $assign;
$assign = sub {
my ($node) = @_;
my $my_idx = scalar @node_data;
push @node_data, undef; # reserve slot; filled in after children
if ( $node->[_N_TYPE] == _NT_LEAF ) {
$node_data[$my_idx]
= [ 0.0, $node->[_N_COUNT] + 0.0, $self->_rpl( $node->[_N_COUNT] ) + 0.0, 0.0, 0.0, 0.0 ];
} else {
my $li = $assign->( $node->[_N_LEFT] );
my $ri = $assign->( $node->[_N_RIGHT] );
$node_data[$my_idx]
= [ 1.0, $node->[_N_ATTR] + 0.0, $node->[_N_SPLIT] + 0.0, $li + 0.0, $ri + 0.0, 0.0 ];
}
return $my_idx;
}; ## end $assign = sub
$assign->($root);
return pack( 'd*', map { @$_ } @node_data );
} ## end sub _pack_online_tree
# Pack the query rows into the row-major double buffer score_all_xs
# reads, via the parent's C row walker. miss_mode 0 maps an undef cell
# to 0.0, matching the pure-Perl walk's "// 0".
sub _pack_input {
my ( $self, $data ) = @_;
( run in 0.944 second using v1.01-cache-2.11-cpan-f4a522933cf )