Algorithm-Classifier-IsolationForest

 view release on metacpan or  search on metacpan

lib/Algorithm/Classifier/IsolationForest/Online.pm  view on Meta::CPAN

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;
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

lib/Algorithm/Classifier/IsolationForest/Online.pm  view on Meta::CPAN

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
          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).
      default :: undef

  - 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.
      default :: $Algorithm::Classifier::IsolationForest::HAS_OPENMP

=cut

lib/Algorithm/Classifier/IsolationForest/Online.pm  view on Meta::CPAN

feature values.  Returns a two-element arrayref C<[$score, $label]>.
C<$threshold> defaults the same way as in L</predict>.

    my $pair = $oif->score_predict_sample_tagged({ cpu => 0.9, mem => 0.4 });

Croaks under the same conditions as L</tagged_row_to_array>.

=cut

sub score_predict_sample_tagged {
	my ( $self, $row, $threshold ) = @_;
	my $vec    = $self->tagged_row_to_array( $row, 'score_predict_sample_tagged' );
	my $result = $self->score_predict_samples( [$vec], $threshold );
	return $result->[0];
}

=head2 score_predict_split(\@data, $threshold)

Same values as L</score_predict_samples> but returned as two flat
arrayrefs.  In list context returns C<($scores_aref, $labels_aref)>.

    my ($scores, $labels) = $oif->score_predict_split(\@data);

=cut

sub score_predict_split {
	my ( $self, $data, $threshold ) = @_;
	$self->_check_learned;
	$self->_ensure_threshold;
	$threshold
		= defined $threshold         ? $threshold
		: defined $self->{threshold} ? $self->{threshold}
		:                              0.5;

	# Fast path: two flat arrayrefs straight from the sum buffer; gated
	# identically to predict().
	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 $inv           = $self->_score_inv;
		my $sum_threshold = -log($threshold) / $inv;
		my $scores        = [];
		my $labels        = [];
		Algorithm::Classifier::IsolationForest::score_predict_split_xs( $sums_packed, $n_pts, $inv,
			$sum_threshold, $scores, $labels );
		return ( $scores, $labels );
	} ## end if ( $threshold > 0 && $threshold < 1 && $self...)

	my $scores = $self->score_samples($data);
	my @labels = map { $_ >= $threshold ? 1 : 0 } @$scores;
	return ( $scores, \@labels );
} ## end sub score_predict_split

=head2 relearn_threshold(\@data)

Re-derives the contamination decision threshold so it flags the requested
fraction of the current window (or of C<\@data>, when passed).  Call this
after the stream has drifted, or on whatever cadence threshold freshness
matters; learning alone never moves the threshold.

Requires C<contamination> to have been set.  With C<< window_size => 0 >>
no window is retained, so C<\@data> must be supplied.

Returns C<$self>, so it chains.

    $oif->relearn_threshold;

=cut

sub relearn_threshold {
	my ( $self, $data ) = @_;
	croak "relearn_threshold requires contamination to have been set in new()"
		unless defined $self->{contamination};
	my $rows = defined $data ? $data : $self->{window};
	croak "relearn_threshold: no retained window to learn a threshold from "
		. "(window_size is 0); pass an arrayref of recent data"
		unless ref $rows eq 'ARRAY' && @$rows;

	my $scores = $self->score_samples($rows);
	my @desc   = sort { $b <=> $a } @$scores;
	my $n_pts  = scalar @desc;
	my $k      = int( $self->{contamination} * $n_pts + 0.5 );
	$k                 = 1      if $k < 1;
	$k                 = $n_pts if $k > $n_pts;
	$self->{threshold} = Algorithm::Classifier::IsolationForest::_threshold_from_ranked( \@desc, $k );
	return $self;
} ## end sub relearn_threshold

=head2 decision_threshold

The score cutoff the predict methods use by default; undef unless
C<contamination> was set and a predict-family method or
L</relearn_threshold> has run.

=cut

sub decision_threshold { return $_[0]->{threshold} }

=head2 feature_names

Returns the arrayref of feature name strings stored with the model, or
undef if none were provided.

=cut

sub feature_names { return $_[0]->{feature_names} }

=head2 schema_version

Returns the user-owned schema version string stored with the model
(usually via a prototype -- see PROTOTYPES in
L<Algorithm::Classifier::IsolationForest>), or undef if none was
recorded.

=cut