view release on metacpan or  search on metacpan

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

    );

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

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

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
	# 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        = [];
		Algorithm::Classifier::IsolationForest::predict_sums_xs( $sums_packed, $n_pts, $sum_threshold, $result );
		return $result;
	} ## end if ( $threshold > 0 && $threshold < 1 && $self...)

	my $scores = $self->score_samples($data);
	return [ map { $_ >= $threshold ? 1 : 0 } @$scores ];
} ## end sub predict

=head2 predict_tagged(\%row, $threshold)

Predicts whether a single sample, supplied as a hashref of named feature
values, is an anomaly.  Returns a scalar 1 (anomaly) or 0 (normal).
C<$threshold> defaults the same way as in L</predict>.

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

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