Algorithm-Classifier-IsolationForest
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
my $explanations = $oif->explain_samples(\@data);
my $top = $explanations->[0]{features}[0];
Differences from the batch class:
The default C<ablation> method substitutes per-feature medians of the
currently retained window (there is no fit() to store baselines at;
the window IS the model's view of normal, and it tracks drift for
free). It therefore requires C<< window_size > 0 >> with learned
points and croaks otherwise -- use C<path> on a windowless model.
The C<path> method carries an extra caveat on top of the batch class's
(see the parent POD): online trees are shallow by construction (the
depth budget is C<log(n/max_leaf_samples)/log(4)>) and most of a
sample's anomalousness lives in the per-leaf count adjustment rather
than in which splits it crossed, so path attributions here are coarse.
Treat them as a rough second opinion; prefer C<ablation> whenever a
window exists.
A model that has not yet accumulated tree structure (fewer than
C<max_leaf_samples> points seen) scores everything 1.0 and has no
splits to attribute; every weight comes back 0.
=cut
sub explain_samples {
my ( $self, $data, %opts ) = @_;
$self->_check_learned;
croak "explain_samples() expects a non-empty arrayref of samples"
unless ref $data eq 'ARRAY' && @$data;
my $method = delete $opts{method} // 'ablation';
croak "explain_samples: method must be 'path' or 'ablation'"
unless $method =~ /\A(?:path|ablation)\z/;
croak "explain_samples: unknown option(s): " . join( ', ', sort keys %opts )
if %opts;
return $method eq 'ablation'
? $self->_explain_ablation($data)
: $self->_explain_path($data);
} ## end sub explain_samples
=head2 explain_sample_tagged(\%row, %opts)
Explains a single sample supplied as a hashref of named feature values,
without learning it. Takes the same C<method> option as
L<explain_samples|/explain_samples(\@data, %opts)> and returns the single explanation hashref.
my $e = $oif->explain_sample_tagged({ cpu => 0.9, mem => 0.4 });
Croaks under the same conditions as L<tagged_row_to_array|/tagged_row_to_array(\%row, $caller)>.
=cut
sub explain_sample_tagged {
my ( $self, $row, %opts ) = @_;
my $vec = $self->tagged_row_to_array( $row, 'explain_sample_tagged' );
return $self->explain_samples( [$vec], %opts )->[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|/new(%args)>), 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|/predict(\@data, $threshold)>.
my $label = $oif->predict_tagged({ cpu => 0.9, mem => 0.4 });
Croaks under the same conditions as L<tagged_row_to_array|/tagged_row_to_array(\%row, $caller)>.
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
#
# Returns: nothing on success. Croaks when the model has seen no points --
# a fresh model that has not been fed anything yet.
#
# Example:
# $self->_check_learned; # croaks with "model has not learned any data yet"
sub _check_learned {
my ($self) = @_;
croak "model has not learned any data yet; call learn() first"
unless $self->{seen} > 0;
}
# Validate one incoming sample, apply the missing-value strategy, and
# return a fresh dense copy (the window owns its rows; the caller may
# reuse or mutate the original). Locks in n_features on first contact.
#
# Args:
# $row :: one sample, a non-empty arrayref of feature values. undef
# cells are allowed only under missing => 'zero'.
# $caller :: the public method's name, used to prefix croak messages so
# the error names what the user actually called.
#
# Returns: a fresh dense arrayref, safe for the window to keep. Croaks
# when $row is not a non-empty arrayref, when its width disagrees with the
# width the first row established, or when it holds an undef cell under
# missing => 'die'.
#
# Example:
# my $r = $self->_prep_row( [ 0.9, undef ], 'learn' ); # [ 0.9, 0 ]
sub _prep_row {
my ( $self, $row, $caller ) = @_;
croak "$caller: each sample must be an arrayref of features"
unless ref $row eq 'ARRAY' && @$row;
if ( !defined $self->{n_features} ) {
$self->{n_features} = scalar @$row;
} 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.
#
# Args:
# $n :: a point count, non-negative. A tree's count when budgeting its
# depth, a leaf's count when adjusting a path length.
#
# Returns: the depth budget as a float, 0 for n below max_leaf_samples and
# growing logarithmically past it.
#
# Example:
# $self->_rpl(32); # 0 at the default max_leaf_samples of 32
# $self->_rpl(2048); # ~3.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). Learning and
# forgetting both go through it, which is what keeps a tree's shape a
# function of its current contents rather than of the order it saw them.
#
# Args:
# $depth :: the node's depth, 0 at the root.
#
# Returns: the required point count. A flat max_leaf_samples under
# growth => 'fixed'; doubling per level under 'adaptive', so deep nodes
# need proportionally more evidence before splitting.
#
# Example:
# $self->_split_threshold(0); # 32 at the default max_leaf_samples
# $self->_split_threshold(3); # 256 under growth => 'adaptive'
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. This is the population the
# score normaliser is computed against, so it moves as the stream does.
#
# Args: none beyond the model itself.
#
# Returns: the point count as an integer -- the retained window's length,
# or the lifetime seen count under window_size 0.
#
# Example:
# $self->_data_size; # 2048 once a default window has filled
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.
#
# Args: none beyond the model itself. The value tracks the current window
# fill, so it has to be recomputed whenever the stream has moved.
#
# Returns: the multiplier as a float. Feed it a depth sum and exp() turns
# the product into the anomaly score.
#
# Example:
# my $inv = $self->_score_inv;
# my $score = exp( -$depth_sum * $inv ); # in (0, 1]
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.
#
# Args:
# $r :: one sample, already through _prep_row -- dense, width-checked,
# and owned by the model, since the window keeps this very
# reference rather than a copy.
#
# Returns: nothing. Advances seen, mutates the trees, appends to the
# window and evicts the oldest point once the window is over size.
#
# Example:
# $self->_learn_row( $self->_prep_row( [ 0.9, 0.4 ], 'learn' ) );
# $self->seen; # one higher than before
sub _learn_row {
my ( $self, $r ) = @_;
my $sub = $self->{subsample};
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
# nodes, or (undef, undef) when neither has a box yet.
#
# Example:
# my ( $lo, $hi ) = _box_union( $node->[_N_LEFT], $node->[_N_RIGHT] );
# if ( defined $lo ) { $node->[_N_LO] = $lo; $node->[_N_HI] = $hi }
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.
#
# Args:
# $pts :: the points to bound, an arrayref of arrayrefs. May be empty.
#
# Returns: the two-element list ($lo, $hi) of fresh arrayrefs holding the
# per-feature minimum and maximum, or (undef, undef) for an empty set.
#
# Example:
# my ( $lo, $hi ) = _box_of( [ [ 0.9, 0.4 ], [ 0.2, 0.7 ] ] );
# # ( [ 0.2, 0.4 ], [ 0.9, 0.7 ] )
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.
#
# Args:
# $x :: one sample, an arrayref of feature values. undef cells are
# allowed and count as 0.
# $node :: the node to start walking from, normally a tree's root. Must
# be defined -- callers skip trees that have not grown one.
#
# Returns: the path length as a float: edges walked plus the leaf's
# _rpl(count), so it is rarely a whole number.
#
# Example:
# $self->_depth_of( [ 0.9, 0.4 ], $self->{trees}[0]{root} ); # e.g. 2.8
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).
#
# Args:
# $data :: the samples to walk, an arrayref of feature-value arrayrefs
# already through _prep_row or otherwise known dense-ish (undef
# cells count as 0).
#
# Returns: arrayref of per-sample depth sums, positionally matching $data.
# Trees with no root contribute nothing, so a brand-new model yields all
# zeroes.
#
# Example:
# my $sums = $self->_depth_sums( \@rows );
# my $inv = $self->_score_inv;
# my @scores = map { exp( -$_ * $inv ) } @$sums;
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.
#
# Args:
# $r :: one sample, already through _prep_row.
#
# Returns: the anomaly score as a float in (0, 1] -- near 1 for an
# anomaly, well under 0.5 for a normal point.
#
# Example:
# my $r = $self->_prep_row( $row, 'score_learn' );
# my $score = $self->_score_row($r);
# $self->_learn_row($r); # prequential: score, then learn
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
#-------------------------------------------------------------------------------
# Explanation (explain_samples) internals. The output shaping is shared
# with the parent class (_credit_to_features / _deltas_to_features) so
# both classes return the identical structure; only the walks and the
# baseline source differ.
#-------------------------------------------------------------------------------
# Path-credit explanation: _depth_of's exact routing recorded as
# (path length, crossed features) walks, turned into local-DIFFI
# credit by the parent's _walks_to_credit (see _path_length_explain
# there for the weighting and its rationale). Path lengths carry the
# per-leaf _rpl(count) adjustment, exactly as scoring's do -- with the
# shallow trees online models build, most of the between-tree contrast
# lives in that adjustment, not the raw depth. Online trees are
# axis-only, so each node credits exactly one feature (share 1).
#
# Args:
# $data :: the samples to explain, an arrayref of feature-value
# arrayrefs, already prepped by the caller.
#
# Returns: arrayref of one hashref per row, in input order, each holding
# score, method (always 'path') and features -- the same sorted structure
# the parent class returns, so callers cannot tell the two apart.
#
# Example:
# my $out = $self->_explain_path( [ [ 8.1, 0.2 ] ] );
# $out->[0]{features}[0]{name}; # the feature most responsible
sub _explain_path {
my ( $self, $data ) = @_;
my $scores = $self->score_samples($data);
my $nf = $self->{n_features};
my $names = $self->{feature_names};
my @out;
for my $i ( 0 .. $#$data ) {
my $x = $data->[$i];
my @walks;
for my $tree ( @{ $self->{trees} } ) {
my $node = $tree->{root};
next unless defined $node;
my @pairs;
while ( $node->[_N_TYPE] ) {
push @pairs, [ $node->[_N_ATTR], 1 ];
$node = ( $x->[ $node->[_N_ATTR] ] // 0 ) < $node->[_N_SPLIT] ? $node->[_N_LEFT] : $node->[_N_RIGHT];
}
push @walks, [ scalar(@pairs) + $self->_rpl( $node->[_N_COUNT] ), \@pairs ];
} ## end for my $tree ( @{ $self->{trees} } )
my $credit = Algorithm::Classifier::IsolationForest::_walks_to_credit( \@walks, $nf );
push @out,
{
score => $scores->[$i],
method => 'path',
features => Algorithm::Classifier::IsolationForest::_credit_to_features( $names, $credit, $x ),
};
} ## end for my $i ( 0 .. $#$data )
return \@out;
} ## end sub _explain_path
# Counterfactual explanation: every row followed by its n_features
# single-feature baseline substitutions, scored as one batch (which
# rides the packed-snapshot C scorer when available). Mirrors the
# parent's _explain_ablation with the window medians as baselines.
#
# Args:
# $data :: the samples to explain, an arrayref of feature-value
# arrayrefs, already prepped by the caller.
#
# Returns: arrayref of one hashref per row, in input order, each holding
# score, method (always 'ablation') and features. Croaks by way of
# _window_baselines when the model has no retained window to take medians
# from.
lib/Algorithm/Classifier/IsolationForest/Online.pm view on Meta::CPAN
# is enough to keep the snapshot from ever going stale.
#
# Args: none beyond the model itself.
#
# Returns: nothing. Removes _c_nodes, _c_coef_idx and _c_coef_val, which
# is what makes the next _ensure_c_trees rebuild rather than reuse.
#
# Example:
# $self->_invalidate_c_trees; # next scoring call repacks
sub _invalidate_c_trees {
delete @{ $_[0] }{qw(_c_nodes _c_coef_idx _c_coef_val)};
return;
}
# Build (or reuse) the packed snapshot of the live trees.
#
# Args: none beyond the model itself.
#
# Returns: 1 when the C scoring path may be taken -- the snapshot is
# present and current afterwards -- and 0 when the caller must fall back to
# the pure-Perl walk because use_c is off. Repacking only happens on the
# first call after a mutation; later calls just confirm the snapshot.
#
# Example:
# if ( $self->_ensure_c_trees ) {
# my ( $n_pts, $x ) = $self->_pack_input($data);
# # ... score through the parent's score_all_xs
# }
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).
#
# Args:
# $root :: the tree's root node, or undef for a tree that has not learned
# anything yet.
#
# Returns: a packed 'd*' string of 6 doubles per node, in the parent's node
# layout. An undef root yields the single zeroed leaf record described
# above, which walks as depth 0 with no adjustment.
#
# Example:
# my $buf = $self->_pack_online_tree( $tree->{root} );
# length($buf) / ( 6 * 8 ); # node count
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".
#
# Args:
# $data :: the samples to pack, an arrayref of feature-value arrayrefs.
# Each must be n_features wide.
#
# Returns: the two-element list ($n_pts, $x_packed) -- the row count and
# the row-major 'd*' buffer. There is no online counterpart to the
# parent's PackedData: the snapshot goes stale on every learn, so buffers
# are built per call.
#
# Example:
# my ( $n_pts, $x ) = $self->_pack_input( \@rows );
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 );
}
# Lazily learn the contamination threshold from the current window the
# first time a predict-family method needs it. A model with no retained
# window (window_size 0) stays on the 0.5 fallback until the caller runs
# relearn_threshold with data.
#
# Args: none beyond the model itself.
#
# Returns: nothing. Sets $self->{threshold} on the first call that finds a
( run in 1.879 second using v1.01-cache-2.11-cpan-54e63673c56 )