Algorithm-Classifier-IsolationForest
view release on metacpan or search on metacpan
benchmarking/bench-fit-parallel.pl view on Meta::CPAN
#!/usr/bin/perl
# benchmarking/bench-fit-parallel.pl
#
# Measures fit() throughput across a sweep of parallel_fit worker
# counts. The training data is the same for every run; only the
# `parallel_fit` constructor option changes.
#
# parallel_fit forks workers and divvies up n_trees across them, with
# each worker fitting its share in a child process (via the C tree
# builder when Inline::C is available, same as a non-parallel fit) and
# returning the trees to the parent via Storable on a pipe. Speedup is
# bounded by:
# * core count
# * Storable freeze/thaw + pipe IPC overhead per worker
# * fork() cost (small but non-zero)
#
# With the C builder, a single-process fit is often fast enough that
# this fixed per-worker overhead costs more than splitting the work
# saves -- watch for parallel_fit making things *slower* on small/
# medium datasets in the sweep below.
#
benchmarking/bench-online-score-accel.pl view on Meta::CPAN
#!/usr/bin/perl
# benchmarking/bench-online-score-accel.pl
#
# Benchmarks Online Isolation Forest batch scoring under each acceleration
# backend:
# pure_perl -- use_c => 0 (pure Perl tree walk)
# c_serial -- use_c => 1, use_openmp => 0 (C tree walk, single thread)
# c_openmp -- use_c => 1, use_openmp => 1 (C tree walk, OpenMP parallel)
#
# The online class scores through the parent's C backend by lazily packing
# its mutable trees into the parent's node layout; learning invalidates the
# packed snapshot and the next scoring call repacks once. Learning itself
# (and the per-row walks inside score_learn) runs in C directly against the
# live trees. Sections 1 and 2 measure steady-state batch scoring (snapshot
# reused across calls); section 3 interleaves a learned point before every
# scoring call, so each call pays the repack -- the worst case for the C
# path; sections 4 and 5 measure the prequential score_learn /
# score_learn_tagged stream loop, where the mutable-tree C walks are what
# matters.
#
# Reference numbers (2026-07-08, 8-core dev box, 100 trees, window 2048,
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
here, not a forest-level score cutoff.
score_samples() returns the fraction of trees
voting anomalous -- still in [0, 1], but discrete
in steps of 1/n_trees. contamination composes: fit()
learns the per-tree cutoff that flags the requested
fraction of the training set.
default :: mean
- parallel_fit :: positive integer N => build the trees across N forked
worker processes during fit(). Each worker gets a derived seed
(parent seed + worker_id * 1009) so the parallel fit is
reproducible across runs at fixed worker count -- but the trees
produced are NOT bit-identical to a serial fit with the same
seed, because the RNG draws happen in a different order.
Inference is unaffected. Falls back silently to serial on
platforms without a real fork() (e.g. Windows without Cygwin).
default :: undef (serial)
- use_c :: boolean, override whether the Inline::C backend is used for
both scoring and fit()'s tree builder. When false the instance
falls back to pure Perl for both even if the C backend compiled
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
(one tree per thread) instead of the single-threaded C builder.
Opt-in and off by default: unlike use_c/use_openmp, this changes
which trees get built. Perl's RNG isn't safe to call from
multiple OS threads sharing one interpreter, so this path seeds
an independent PRNG per tree from the tree index rather than
Drand01() -- trees differ from the use_c (single-threaded)
and pure-Perl paths even with the same seed, though a fixed
seed and n_trees still reproduce the same trees regardless of
OMP_NUM_THREADS or scheduling. Does NOT compose with
parallel_fit: a forked child starting its own OpenMP region
after the parent process has used OpenMP for anything can
hang (a general fork()+libgomp limitation), so parallel_fit's
workers always use the single-threaded C builder regardless
of this setting -- setting both just means parallel_fit wins.
Ignored (clamped to 0) when use_c is false or OpenMP isn't
linked in.
default :: 0
- feature_names :: optional arrayref of per-feature labels enabling the
*_tagged methods (and required by mungers below).
default :: undef
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
# idx_packed: int32 feature indices for every oblique-node coefficient
# val_packed: double values matching idx_packed one-for-one
#
# Storing idx and val in separate buffers (SoA) instead of interleaved
# doubles lets the oblique dot product's SIMD inner loop run over a
# contiguous val[] stream without a per-iteration (int) cast, and
# halves the index bandwidth (int32 vs double). The same `coff`
# offset addresses paired entries in both buffers.
#
# Nodes are numbered in DFS pre-order: the root is always index 0 and
# children always get indices larger than their parent's.
# ---------------------------------------------------------------------------
sub _pack_tree {
my ( $root, $n_features ) = @_;
my ( @node_data, @coef_idx, @coef_val );
my $assign;
$assign = sub {
my ($node) = @_;
my $my_idx = scalar @node_data;
push @node_data, undef; # reserve slot; filled in after children
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
return $cached;
}
}
#-------------------------------------------------------------------------------
# Fork-based parallel tree builder. Used by fit() when parallel_fit > 1
# and the platform has a real fork(). Divides n_trees evenly among
# workers; each child seeds its own RNG ($seed + worker_id * 1009 so
# fixed-worker-count runs are reproducible), builds its share (via the
# C builder when _use_c is on, same as the non-parallel path), and
# returns the trees to the parent via Storable on a one-shot pipe.
#
# The trees that come back differ from a serial fit with the same seed
# because the RNG draws happen in a different order -- this is documented
# as part of the parallel_fit contract.
#-------------------------------------------------------------------------------
sub _fit_trees_parallel {
my ( $self, $data, $psi, $limit, $workers ) = @_;
require Storable;
require POSIX;
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
croak "fork failed: $!" unless defined $pid;
if ( $pid == 0 ) {
# child
close $rh;
binmode $wh;
if ( defined $self->{seed} ) {
srand( $self->{seed} + $w * 1009 );
}
# Deliberately never _build_forest_openmp here, even when
# use_openmp_fit is on: if this process (or the parent that
# fork()ed us) already ran any OpenMP region before this
# fork -- including plain score_samples()/predict() with
# the default use_openmp -- libgomp's thread pool exists
# but its worker threads didn't survive the fork. A child
# starting its own #pragma omp parallel region then tries
# to reuse that now-invalid pool and hangs. This is a
# general fork()+libgomp limitation, not fixable from here,
# so forked workers always use the single-threaded C
# builder (or pure Perl) instead. See t/03-fit-determinism.t
# and the NATIVE ACCELERATION docs for the observed hang and
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
} else {
my @t;
for ( 1 .. $share ) {
my $sample = _subsample( $data, $psi );
push @t, $self->_build_tree( $sample, 0, $limit );
}
$trees = \@t;
}
print $wh Storable::freeze($trees);
close $wh;
# _exit so we don't run parent END/DESTROY in the child.
POSIX::_exit(0);
} ## end if ( $pid == 0 )
close $wh;
binmode $rh;
push @procs, { pid => $pid, rh => $rh, share => $share };
} ## end for my $w ( 0 .. $workers - 1 )
# Collect from each pipe in worker order so the canonical tree
# ordering is deterministic (worker 0's trees first, then 1's, ...).
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
# random draws come from a thread-private PRNG seeded per tree index
# rather than Drand01() -- Perl's RNG state can't be shared safely
# across OpenMP threads -- so the resulting trees are NOT bit-identical
# to the use_c (serial) or pure-Perl paths for the same seed, though a
# fixed seed + n_trees still reproduce the same trees regardless of
# OMP_NUM_THREADS. This is why it's gated by the separate, opt-in
# use_openmp_fit knob rather than reusing use_c/use_openmp.
#
# Only called from fit()'s non-forked branch. _fit_trees_parallel's
# workers never call this, even when use_openmp_fit is on: a forked
# child starting its own OpenMP region after the parent process has
# used OpenMP for anything (this includes plain score_samples()) can
# hang -- see the comment above that branch for the fork()+libgomp
# hazard this avoids.
#
# build_forest_openmp_xs hands back three arrayrefs of per-tree packed
# buffers (the same SoA layout _pack_tree produces) instead of Perl tree
# structures -- that's how it avoids any Perl API call inside its
# parallel region. _unpack_forest converts them back into the ordinary
# nested-arrayref tree shape so to_json/from_json/_rebuild_c_trees don't
# need to know this path exists.
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
return _unpack_forest( \@nodes, \@idx, \@val );
} ## end sub _build_forest_openmp
# Inverse of _pack_tree's SoA layout: given one tree's packed node
# buffer plus the shared idx/val coefficient buffers, reconstructs the
# ordinary nested-arrayref tree structure _build_tree/_build_node_c
# produce. li/ri fields hold the child's absolute node index, so this
# just follows them recursively from whatever index the caller says the
# root lives at. NOTE: _pack_tree numbers nodes DFS pre-order (root at
# 0), but build_forest_openmp_xs appends nodes post-order (children
# before parent), putting the root LAST -- the caller must pass the
# right root index for the buffer's origin.
sub _unpack_node {
my ( $nodes, $idx, $val, $node_i ) = @_;
my $off = $node_i * 6;
my $type = $nodes->[$off];
if ( $type == 0 ) {
return [ _NODE_LEAF, int( $nodes->[ $off + 1 ] ) ];
} elsif ( $type == 1 ) {
my ( $attr, $split, $li, $ri )
lib/Algorithm/Classifier/IsolationForest/App/Command/streamd.pm view on Meta::CPAN
. $flag
. ' somewhere writable'
. "\n" )
if !-d $dir;
} ## end if ( !-d $dir )
die( '"' . $dir . '" (needed for ' . $flag . ') is not writable; fix permissions or override ' . $flag . "\n" )
unless -w $dir;
return 1;
} ## end sub _ensure_dir
# Classic double-fork daemonization. The parents leave via POSIX::_exit
# so no END blocks (Inline's, App::Cmd's) run twice.
sub _daemonize {
defined( my $pid = fork() ) or die( 'fork failed: ' . $! . "\n" );
POSIX::_exit(0) if $pid;
setsid() or die( 'setsid failed: ' . $! . "\n" );
defined( $pid = fork() ) or die( 'second fork failed: ' . $! . "\n" );
POSIX::_exit(0) if $pid;
chdir '/' or die( 'chdir / failed: ' . $! . "\n" );
open( STDIN, '<', '/dev/null' ) or die( 'reopen STDIN failed: ' . $! . "\n" );
return 1;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
package Algorithm::Classifier::IsolationForest::Online;
use strict;
use warnings;
use Carp qw(croak);
use JSON::PP ();
use File::Slurp qw(read_file write_file);
# Runtime-only dependency: tagged_row_to_array is delegated to the parent
# class (identical semantics, no point duplicating it) and the
# contamination threshold selection reuses _threshold_from_ranked. The
# 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;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
- 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
the default cutoff. The threshold does NOT track the stream
automatically afterwards; call relearn_threshold() to refresh
it. undef => no learned threshold (predict() falls back to
0.5).
default :: undef
- missing :: how learn() treats undef (missing) feature cells. Scoring
always tolerates undef (mapped to 0), matching the parent
class's long-standing behaviour.
die :: croak if a learned point contains an undef cell
zero :: treat a missing cell as the value 0
default :: die
- feature_names :: optional arrayref of per-feature labels enabling the
*_tagged methods (and required by mungers below).
default :: undef
- mungers :: optional hashref of declarative L<Algorithm::ToNumberMunger>
specs; every tagged row (learn_tagged, score_learn_tagged, the
scoring *_tagged methods, tagged_row_to_array) is munged from
raw values into numbers through the compiled plan, and
munge_rows() applies the scalar mungers to positional rows.
Requires feature_names; spec errors croak here. The spec is
saved with the model. Identical semantics to the parent
class's knob -- see MUNGERS in
L<Algorithm::Classifier::IsolationForest> for details and
caveats.
default :: undef
- schema_version :: optional opaque string identifying the revision of
the variable schema this model was built against. Never
parsed; saved with the model. Usually set via a prototype --
see PROTOTYPES in L<Algorithm::Classifier::IsolationForest>
(whose new_from_prototype creates online models too).
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
- schema_description :: optional opaque free-text description of what
the variable schema is. Same handling as schema_version.
default :: undef
- feature_descriptions :: optional hashref of 'feature name => free
text' describing individual features. Requires feature_names;
every key must name an entry there or new() croaks. Partial
coverage is fine. Saved with the model.
default :: undef
- use_c :: boolean, override whether the parent class's Inline::C
backend is used, for learning and scoring both (see
DESCRIPTION). When false the instance runs pure Perl even if
the C backend compiled. Results are identical either way --
learn() builds bit-identical trees for the same seed (on
nvsize == 8 perls) and scoring matches exactly -- so only
speed differs.
default :: $Algorithm::Classifier::IsolationForest::HAS_C
- use_openmp :: boolean, override whether OpenMP parallel scoring is
used inside the C tree walk. Ignored when use_c is false.
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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"
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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
# for a normal threshold in (0, 1), like the parent's gate.
if ( $threshold > 0 && $threshold < 1 && $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 $sum_threshold = -log($threshold) / $self->_score_inv;
my $result = [];
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
including points that have since been forgotten.
=cut
sub seen { return $_[0]->{seen} }
=head2 tagged_row_to_array(\%row, $caller)
Validates a hashref of named feature values against the model's stored
C<feature_names> and returns a positional arrayref. Identical semantics
to the parent class's method of the same name (to which it delegates);
see there for the croak conditions.
=cut
sub tagged_row_to_array {
my $self = shift;
return Algorithm::Classifier::IsolationForest::tagged_row_to_array( $self, @_ );
}
=head2 munge_rows(\@rows)
Applies the model's scalar mungers to positional rows, exactly as the
parent class's method of the same name (to which it delegates); a model
without C<mungers> returns the input unchanged.
=cut
sub munge_rows {
my $self = shift;
return Algorithm::Classifier::IsolationForest::munge_rows( $self, @_ );
}
=head1 MODEL SAVE/LOAD METHODS
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
window_size => $p->{window_size} // 0,
max_leaf_samples => $p->{max_leaf_samples},
growth => $p->{growth} // 'adaptive',
subsample => $p->{subsample} // 1.0,
seed => undef,
contamination => $p->{contamination},
threshold => $p->{threshold},
n_features => $p->{n_features},
missing => $p->{missing} // 'die',
feature_names => $p->{feature_names},
# Recompiled lazily on first tagged use, like the parent.
mungers => $p->{mungers},
munger_module_version => $p->{munger_module_version},
# Opaque schema metadata; absent in models saved before prototype
# support, which just means "none recorded".
schema_version => $p->{schema_version},
schema_description => $p->{schema_description},
feature_descriptions => $p->{feature_descriptions},
seen => $p->{seen} // 0,
window => $payload->{window} // [],
trees => [],
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
my ( $class, $path ) = @_;
my $raw_model = read_file($path);
return $class->from_json($raw_model);
}
=head2 to_prototype
Returns a prototype JSON string extracted from this model: its variable
schema (feature_names, feature_descriptions, mungers, missing policy)
plus its current tuning knobs, with C<"class": "online">. Identical
semantics to the parent class's method -- see PROTOTYPES in
L<Algorithm::Classifier::IsolationForest> for the file format and the
croak/placeholder rules. C<seed> is not emitted; pass it as an override
when creating from the prototype.
my $proto_json = $oif->to_prototype;
=cut
sub to_prototype {
my ($self) = @_;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
# 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;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
} 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
# initialises the box.
$node->[_N_LO] = [@$x];
$node->[_N_HI] = [@$x];
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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 ) {
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
}
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 );
}
}
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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.
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
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;
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
$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 ) = @_;
my $n_pts = scalar @$data;
my $nf = $self->{n_features};
my $x_packed = "\0" x ( $n_pts * $nf * 8 );
Algorithm::Classifier::IsolationForest::pack_input_xs( $data, $x_packed, $n_pts, $nf, 0, '' );
return ( $n_pts, $x_packed );
}
t/03-fit-determinism.t view on Meta::CPAN
# 3. use_openmp_fit is reproducible for a fixed seed + n_trees
# regardless of OMP_NUM_THREADS (checked across separate
# subprocesses, since that's the only way to force a different
# thread count) -- it deliberately does NOT match the Drand01-based
# backends (documented behaviour: it uses its own thread-safe PRNG),
# so that's checked as a "differs, but each is internally consistent"
# property rather than cross-backend equality.
# 4. use_openmp_fit + parallel_fit together is still safe and
# reproducible -- but does NOT actually run forked workers in
# OpenMP. A forked child starting its own OpenMP region after
# the parent process has used OpenMP for anything (including
# plain score_samples()) can hang -- a general fork()+libgomp
# limitation -- so parallel_fit's workers always use the
# single-threaded C builder regardless of use_openmp_fit. This
# was caught by an earlier version of this test hanging.
use strict;
use warnings;
use Test::More;
use File::Temp qw(tempfile);
use Config;
t/35-online-accel.t view on Meta::CPAN
#!perl
# 35-online-accel.t
#
# C-accelerated scoring and learning for the Online Isolation Forest.
# Scoring reuses the parent's Inline::C scorer by lazily packing the
# mutable trees into the parent's node layout; learning runs the
# per-tree insert/forget walks in C against the live trees with the
# same RNG draw order as pure Perl. The contract to test is the same
# one the parent keeps: use_c changes speed, never results.
#
# * every scoring method returns bit-identical values with use_c on
# and off (including undef cells and learned contamination cutoffs)
# * mutating the model (learn, and window eviction/unlearn) drops the
# packed snapshot -- the next C-path call must reflect the new trees
# * OpenMP on/off does not change results
# * a reloaded model (which defaults to use_c) scores identically
# * learning under the same seed and stream builds byte-identical
# models whether use_c is on or off, across every learn code path
# (eviction/collapse, growth modes, subsampling, missing => zero)
#
# Skipped entirely when the parent's C backend did not compile. The
# learn-parity subtests additionally skip when the loaded C object
# predates the online learn accelerators (older prebuilt) or on
# wide-NV perls.
use strict;
use warnings;
use Test::More;
use File::Temp qw(tempdir);
use Config ();
t/35-online-accel.t view on Meta::CPAN
# (scoring maps undef to 0 on both backends).
my @eval = ( [ 0, 0 ], [ 8, 8 ], [ 0.5, -0.3 ], [ undef, 2 ], [ -7, 7 ] );
sub with_knobs {
my ( $m, $use_c, $use_openmp, $code ) = @_;
local $m->{_use_c} = $use_c;
local $m->{_use_openmp} = ( $use_openmp && $Algorithm::Classifier::IsolationForest::HAS_OPENMP ) ? 1 : 0;
return $code->();
}
subtest 'constructor knobs clamp like the parent' => sub {
my $on = $class->new( use_c => 1 );
is( $on->{_use_c}, 1, 'use_c => 1 sticks when the backend compiled' );
my $off = $class->new( use_c => 0 );
is( $off->{_use_c}, 0, 'use_c => 0 forces pure Perl' );
is( $off->{_use_openmp}, 0, 'use_openmp is clamped off without use_c' );
my $omp_only = $class->new( use_c => 0, use_openmp => 1 );
is( $omp_only->{_use_openmp}, 0, 'use_openmp => 1 is still clamped off without use_c' );
}; ## end 'constructor knobs clamp like the parent' => sub
subtest 'scoring parity: C vs pure Perl' => sub {
my $m = make_model();
# Prime the learned contamination threshold on the Perl path so both
# backends label against the identical cutoff.
with_knobs( $m, 0, 0, sub { $m->predict( \@eval ) } );
my %perl = with_knobs(
$m, 0, 0,
t/39-online-stream.t view on Meta::CPAN
#!perl
# 39-online-stream.t
#
# Streaming behaviour of Algorithm::Classifier::IsolationForest::Online:
# drift adaptation through the sliding window (learning AND forgetting),
# subtree collapse bookkeeping, contamination thresholds, unbounded
# (window_size 0) operation, and persistence -- including resuming the
# stream after a save/load round trip and loading through the parent
# class's format dispatch.
use strict;
use warnings;
use Test::More;
use Algorithm::Classifier::IsolationForest ();
use Algorithm::Classifier::IsolationForest::Online ();
use File::Temp qw(tempdir);
t/39-online-stream.t view on Meta::CPAN
# The stream can resume: learning after a reload keeps the window
# bookkeeping intact.
$re->learn( cluster( 100, 0 ) );
is( $re->window_count, 256, 'window still capped after resuming' );
is( $re->seen, 500, 'seen kept counting after resuming' );
for my $tree ( @{ $re->{trees} } ) {
is( $tree->{count}, 256, 'per-tree counts consistent after resuming' );
}
# Parent-class load dispatches on the format tag.
my $via_parent = Algorithm::Classifier::IsolationForest->load($path);
isa_ok( $via_parent, $class, 'parent load() returns an online model' );
# And the online class refuses a batch model.
srand(12);
my $batch = Algorithm::Classifier::IsolationForest->new( n_trees => 5, seed => 1 );
$batch->fit( cluster( 64, 0 ) );
ok( !eval { $class->from_json( $batch->to_json ); 1 }, 'online from_json rejects a batch model' );
ok( !eval { $class->from_json('{"format":"bogus"}'); 1 }, 'online from_json rejects unknown formats' );
}; ## end 'persistence round trip' => sub
done_testing;
t/41-mungers.t view on Meta::CPAN
my $normal = $m->score_sample_tagged( {%NORMAL} );
my $weird = $m->score_learn_tagged( {%WEIRD} );
cmp_ok( $weird, '>', $normal, 'raw anomalous row scores above a normal one prequentially' );
my $path = "$dir/oiforest_munged.json";
$m->save($path);
# Parent-class load dispatches AND keeps the munger spec.
my $re = Algorithm::Classifier::IsolationForest->load($path);
isa_ok( $re, $online_class, 'parent load() returns the online model' );
is_deeply( $re->{mungers}, mungers(), 'munger spec survived the online round trip' );
my $s1 = $m->score_sample_tagged( {%WEIRD} );
my $s2 = $re->score_sample_tagged( {%WEIRD} );
cmp_ok( abs( $s2 - $s1 ), '<', 1e-12, 'reloaded online model munges and scores identically' );
}; ## end 'Online: learn_tagged batches, prequential scoring, persistence' => sub
done_testing;
t/42-prototype.t view on Meta::CPAN
is( $b->{n_trees}, 25, 'params applied' );
is( $b->{sample_size}, 64, 'sample_size applied' );
is( $b->{voting}, 'majority', 'voting applied' );
is( $b->{seed}, 42, 'override applied' );
is( $b->schema_version, 'b1', 'schema_version stamped' );
is( $b->schema_description, 'batch variant', 'schema_description stamped' );
is_deeply( $b->feature_names, [ 'cpu', 'mem' ], 'feature_names from the schema' );
my $o = $online_class->new( n_trees => 1 ); # just to prove dispatch is by prototype, not caller
$o = $batch_class->new_from_prototype( proto_online() );
isa_ok( $o, $online_class, 'online prototype creates the online class through the parent' );
is( $o->{window_size}, 128, 'online params applied' );
is( $o->{max_leaf_samples}, 8, 'eta applied' );
is( $o->{missing}, 'zero', 'schema missing policy applied' );
is_deeply( $o->feature_descriptions, { cpu => 'cpu utilisation fraction' }, 'feature_descriptions applied' );
my $tuned = $batch_class->new_from_prototype( proto_online(), n_trees => 99 );
is( $tuned->{n_trees}, 99, 'override beats the prototype param' );
ok( !eval { $batch_class->new_from_prototype( proto_online(), mungers => {} ); 1 },
'overriding a schema key croaks' );
t/42-prototype.t view on Meta::CPAN
$f->save("$dir/model.json");
my $re = $batch_class->load("$dir/model.json");
is( $re->schema_version, 'b1', 'batch: schema_version survives save/load' );
is( $re->schema_description, 'batch variant', 'batch: schema_description survives save/load' );
srand(12);
my $o = $batch_class->new_from_prototype( proto_online(), seed => 7 );
$o->learn( rows(100) );
$o->save("$dir/omodel.json");
my $ore = Algorithm::Classifier::IsolationForest->load("$dir/omodel.json");
isa_ok( $ore, $online_class, 'parent load() dispatches the online model' );
is( $ore->schema_version, '2026.07.08-1', 'online: schema_version survives save/load' );
is_deeply(
$ore->feature_descriptions,
{ cpu => 'cpu utilisation fraction' },
'online: feature_descriptions survive save/load'
);
}; ## end 'load_prototype and persistence of the schema metadata' => sub
subtest 'to_prototype extraction round trip' => sub {
my $data = do { srand(13); rows(150) };
t/91-streamd.t view on Meta::CPAN
}; ## end 'saves: command, interval, symlink' => sub
my $seen_at_shutdown = rt( $c, { cmd => 'stats' } )->{ok}{seen};
subtest 'clean shutdown and resume' => sub {
is( stop_daemon($daemon), 0, 'SIGTERM exits 0' );
undef $daemon;
ok( !-e $sock, 'socket removed' );
ok( !-e $pidf, 'pid file removed' );
# latest.json is a complete model; the parent class loads it and it
# carries everything learned (the shutdown save flushed the tail).
require Algorithm::Classifier::IsolationForest;
my $m = Algorithm::Classifier::IsolationForest->load($latest);
isa_ok( $m, 'Algorithm::Classifier::IsolationForest::Online', 'latest.json' );
is( $m->seen, $seen_at_shutdown, 'shutdown save captured everything learned' );
# Restart with no creation knobs: resumes from latest.json.
$daemon = start_daemon( '--save-interval' => 60 );
my $c3 = connect_client();
is( rt( $c3, { cmd => 'stats' } )->{ok}{seen}, $seen_at_shutdown, 'restart resumed from latest.json' );
( run in 0.910 second using v1.01-cache-2.11-cpan-995e09ba956 )