Algorithm-Classifier-IsolationForest
view release on metacpan or search on metacpan
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
split. 0 behaves like a single-feature (axis) cut; the
maximum (n_features - 1) uses every varying feature. undef
=> maximum. Clamped to [0, n_features - 1] at fit time.
- contamination :: expected fraction of anomalies, in (0, 0.5]. When given,
fit() learns a score threshold that flags this fraction of
the training set, and predict() uses it by default. undef
=> no learned threshold (predict() falls back to 0.5).
default :: undef
- missing :: how fit() treats undef (missing) feature cells. Scoring always
tolerates undef regardless of this setting; it governs fit().
die :: croak from fit() if the training data contains any
undef cell. Scoring still maps undef to 0 (the
long-standing behaviour), so a model fitted on clean
data can still score rows with missing features.
zero :: treat a missing cell as the value 0, at fit and score.
impute :: replace a missing cell with the per-feature mean (or
median, see impute_with) learned from the present
values at fit time. The fill vector is stored on the
model and reused for scoring and persistence.
nan :: build feature ranges from present values only and route
a point missing the split feature to the right child,
consistently at fit and score time. Missingness is
preserved as signal rather than filled.
default :: die
- impute_with :: 'mean' or 'median'; the statistic used to compute the
per-feature fill under missing => 'impute'. Ignored otherwise.
default :: mean
- voting :: how the per-tree results are aggregated at scoring time.
Trees are built identically in both settings -- only aggregation
changes -- so the knob composes with either mode (axis or
extended) and an existing model may switch it after the fact with
set_voting() (which relearns a contamination threshold for the
new mode).
mean :: classic Isolation Forest: a sample's path lengths
across all trees are averaged and normalised into
one anomaly score; predict() thresholds that score.
majority :: Majority Voting Isolation Forest (MVIForest;
Chabchoub, Togbe, Boly & Chiky 2022 -- see
REFERENCES). Each tree scores the sample on its own
(s_i = 2**(-h_i / c(psi))) and votes it anomalous
when s_i >= the decision threshold; predict() flags
the sample when more than half of the trees
(int(n_trees/2) + 1) vote anomalous, and stops
walking trees per sample as soon as the outcome is
decided. The threshold argument/default of the
predict methods is therefore the PER-TREE cutoff
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
successfully. When true (or unset) the C backend is used if
available ($HAS_C). fit() with use_c on produces bit-identical
trees to use_c off for the same seed -- only build speed differs.
default :: $HAS_C
- use_openmp :: boolean, override whether OpenMP parallel scoring is
used inside score_all_xs(). When false the C tree walk runs
single-threaded even if OpenMP was linked in. Ignored when
use_c is false (pure Perl has no OpenMP path).
default :: $HAS_OPENMP
- use_openmp_fit :: boolean, build fit()'s trees across OpenMP threads
(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
- mungers :: optional hashref of declarative L<Algorithm::ToNumberMunger>
specs, keyed as that module's compile() expects (scalar mungers by
their output tag, expanding mungers by any label with an 'into'
list, combining mungers by their output tag with a 'from' list).
When set, every tagged row -- the *_tagged methods, fit_tagged,
and tagged_row_to_array -- is munged from raw values (strings,
timestamps, status codes, ...) into numbers through the compiled
plan, and munge_rows() applies the scalar mungers to positional
rows. Requires feature_names; the plan compiles against them, so
any spec error croaks here in new(). Algorithm::ToNumberMunger is
an optional dependency, required only when a spec is given (or a
loaded model carrying one is used with tagged data). The spec is
saved with the model, so a loaded model munges scoring input
exactly as it did training input. See L</MUNGERS> 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
or compared numerically; saved with the model and shown by
`iforest info`. Usually set from a prototype (see
L</PROTOTYPES>) rather than passed directly.
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 (a description for a feature
that does not exist croaks -- it is either a typo or a stale
leftover from a schema change). Partial coverage is fine.
Saved with the model and shown beside each tag by
`iforest info`.
default :: undef
Note: log2 under Perl is as below...
log($psi) / log(2)
=cut
sub new {
my ( $class, %args ) = @_;
my $mode = $args{mode} // 'axis';
croak "mode must be 'axis' or 'extended'"
unless $mode eq 'axis' || $mode eq 'extended';
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
$node = ( $x->[ $node->[1] ] // 0 ) < $node->[2] ? $node->[3] : $node->[4];
}
} else { # [2, \@idx, \@coef, b, left, right]
my ( $idx, $coef, $b ) = ( $node->[1], $node->[2], $node->[3] );
if ($nan) {
my $dot = 0.0;
my $missing = 0;
for ( 0 .. $#$idx ) {
my $v = $x->[ $idx->[$_] ];
if ( !defined $v ) { $missing = 1; last }
$dot += $coef->[$_] * $v;
}
$node = ( !$missing && $dot <= $b ) ? $node->[4] : $node->[5];
} else {
my $dot = 0.0;
$dot += $coef->[$_] * ( $x->[ $idx->[$_] ] // 0 ) for 0 .. $#$idx;
$node = $dot <= $b ? $node->[4] : $node->[5];
}
} ## end else [ if ( $node->[0] == _NODE_AXIS ) ]
$depth++;
} ## end while ( $node->[0] )
return $depth + _c( $node->[1] ); # leaf size at slot 1
} ## end sub _path_length
# Recursively convert a version-0 hash-based tree node to the version-1
# array format. Called by from_json when loading an old saved model.
sub _hash_node_to_array {
my ($node) = @_;
if ( $node->{leaf} ) {
return [ _NODE_LEAF, $node->{size} ];
} elsif ( exists $node->{attr} ) {
return [
_NODE_AXIS, $node->{attr},
$node->{split}, _hash_node_to_array( $node->{left} ),
_hash_node_to_array( $node->{right} ),
];
} else {
return [
_NODE_OBLIQUE, $node->{idx}, $node->{coef}, $node->{b},
_hash_node_to_array( $node->{left} ),
_hash_node_to_array( $node->{right} ),
];
}
} ## end sub _hash_node_to_array
# ---------------------------------------------------------------------------
# _pack_tree($root) -- flatten one tree into three packed buffers.
#
# Returns ($nodes_packed, $idx_packed, $val_packed) where:
# nodes_packed: 6 doubles per node (see score_all_xs comment above)
# 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
if ( $node->[0] == _NODE_LEAF ) {
# Slot 2 carries c(size) precomputed, so the C scoring loop
# adds it straight to the depth instead of paying a log()
# per point per tree at every leaf hit. _c is the same
# function the pure-Perl scorer uses, so both backends keep
# producing bit-identical path lengths.
$node_data[$my_idx] = [ 0.0, $node->[1] + 0.0, _c( $node->[1] ), 0.0, 0.0, 0.0 ];
} elsif ( $node->[0] == _NODE_AXIS ) {
my $li = $assign->( $node->[3] );
my $ri = $assign->( $node->[4] );
$node_data[$my_idx] = [
1.0,
$node->[1] + 0.0, # attr
$node->[2] + 0.0, # split
$li + 0.0,
$ri + 0.0,
0.0,
];
} else { # _NODE_OBLIQUE
my ( $idx_arr, $coef_arr, $b ) = ( $node->[1], $node->[2], $node->[3] );
my $coef_off = scalar @coef_idx;
my $num = scalar @$idx_arr;
# Dense-pack opportunity: when this oblique split uses
# every feature (extension_level == n_features - 1 and
# all features vary), pack the coefficients in feature
# order so val[k] is the coefficient for feature k. The
# C scoring path then detects `nf == n_feats` and switches
# to a no-gather inner loop (dot += val[k] * xi[k]) that
# auto-vectorizes cleanly with FMA.
if ( defined $n_features && $num == $n_features ) {
my %coef_for;
@coef_for{@$idx_arr} = @$coef_arr;
for my $k ( 0 .. $n_features - 1 ) {
push @coef_idx, $k;
push @coef_val, $coef_for{$k} + 0.0;
}
} else {
for my $i ( 0 .. $num - 1 ) {
push @coef_idx, int( $idx_arr->[$i] );
push @coef_val, $coef_arr->[$i] + 0.0;
}
}
my $li = $assign->( $node->[4] );
my $ri = $assign->( $node->[5] );
$node_data[$my_idx] = [ 2.0, $coef_off + 0.0, $num + 0.0, $li + 0.0, $ri + 0.0, $b + 0.0, ];
} ## end else [ if ( $node->[0] == _NODE_LEAF ) ]
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
unless ref $tags eq 'ARRAY' && @$tags;
my %known = map { $_ => 1 } @$tags;
for my $k ( sort keys %$fd ) {
croak "feature_descriptions describes '$k', which is not in feature_names"
unless $known{$k};
croak "feature_descriptions entry for '$k' must be a plain string"
if ref $fd->{$k};
}
return 1;
} ## end sub _validate_feature_descriptions
# Compile a munger spec against the model's feature names. Requires
# Algorithm::ToNumberMunger on demand -- it is an optional dependency --
# and lets its compile() croak on any spec problem.
sub _compile_mungers {
my ( $tags, $mungers ) = @_;
croak "this model has mungers but no feature_names to compile them against"
unless ref $tags eq 'ARRAY' && @$tags;
local $@;
eval { require Algorithm::ToNumberMunger; 1 }
or croak "this model has mungers configured but Algorithm::ToNumberMunger "
. "could not be loaded; install it to use tagged data with this model: $@";
return Algorithm::ToNumberMunger->compile(
tags => $tags,
mungers => $mungers,
);
} ## end sub _compile_mungers
# The compiled plan for this model, or undef when no mungers are
# configured. Compiled lazily (memoised in _munger_plan) so from_json
# does not need Algorithm::ToNumberMunger installed unless tagged data
# is actually used; new() populates the slot eagerly instead, surfacing
# spec errors at construction.
sub _plan {
my ($self) = @_;
return undef unless $self->{mungers};
$self->{_munger_plan} //= _compile_mungers( $self->{feature_names}, $self->{mungers} );
return $self->{_munger_plan};
}
# Memoised "does this perl have a real fork()?". False on Windows
# without Cygwin; true on every Unix-like platform.
{
my $cached;
sub _fork_supported {
return $cached if defined $cached;
require Config;
$cached
= ( ( $Config::Config{d_fork} || '' ) eq 'define' ) ? 1 : 0;
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;
my $n_trees = $self->{n_trees};
$workers = $n_trees if $workers > $n_trees;
# Divide n_trees as evenly as possible across workers.
my @shares;
{
my $base = int( $n_trees / $workers );
my $extras = $n_trees - $base * $workers;
for my $w ( 0 .. $workers - 1 ) {
push @shares, $base + ( $w < $extras ? 1 : 0 );
}
}
my @procs; # { pid, rh, share }
for my $w ( 0 .. $workers - 1 ) {
my $share = $shares[$w];
next unless $share > 0;
pipe( my $rh, my $wh ) or croak "pipe failed: $!";
my $pid = fork();
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
# why parallel_fit + use_openmp_fit isn't composed for real.
my $trees;
if ( $self->{_use_c} ) {
$trees = $self->_build_forest_c( $data, $psi, $limit, $share );
} 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, ...).
my @all_trees;
for my $p (@procs) {
my $buf;
{
local $/;
$buf = readline( $p->{rh} );
}
close $p->{rh};
waitpid( $p->{pid}, 0 );
my $exit = $? >> 8;
croak "parallel_fit worker $p->{pid} exited with status $exit"
if $exit != 0;
my $trees = eval { Storable::thaw($buf) };
croak "parallel_fit worker $p->{pid} returned unparseable trees: $@"
if $@ || ref $trees ne 'ARRAY';
push @all_trees, @$trees;
} ## end for my $p (@procs)
return \@all_trees;
} ## end sub _fit_trees_parallel
#-------------------------------------------------------------------------------
# C-accelerated fit(): builds $n_trees trees against $data (a subset or
# the full training set) via build_forest_xs, which does its own
# per-tree subsampling internally. Random draws inside the C builder
# go through Drand01() -- the same generator Perl's rand() uses -- in
# the same call order _subsample/_build_tree used, so the returned
# trees are bit-identical to what the pure-Perl path would build from
# the same RNG state. That's what lets fit() switch backends on the
# existing `use_c` knob instead of a new one.
#-------------------------------------------------------------------------------
sub _build_forest_c {
my ( $self, $data, $psi, $limit, $n_trees ) = @_;
my $n = scalar @$data;
my $nf = $self->{n_features};
my $x_packed = "\0" x ( $n * $nf * 8 );
my ( $mode, $fill ) = $self->_pack_args;
pack_input_xs( $data, $x_packed, $n, $nf, $mode, $fill );
my $mode_flag = $self->{mode} eq 'extended' ? 1 : 0;
my $ext_level = $self->{extension_level_used} // 0;
my $trees = [];
build_forest_xs( $x_packed, $n, $nf, $n_trees, $psi, $limit, $mode_flag, $ext_level, $trees );
return $trees;
} ## end sub _build_forest_c
#-------------------------------------------------------------------------------
# OpenMP-parallel fit(): builds $n_trees trees across OpenMP threads (one
# tree per thread) via build_forest_openmp_xs. Unlike _build_forest_c,
# 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.
#-------------------------------------------------------------------------------
sub _build_forest_openmp {
my ( $self, $data, $psi, $limit, $n_trees ) = @_;
my $n = scalar @$data;
my $nf = $self->{n_features};
my $x_packed = "\0" x ( $n * $nf * 8 );
my ( $mode, $fill ) = $self->_pack_args;
pack_input_xs( $data, $x_packed, $n, $nf, $mode, $fill );
my $mode_flag = $self->{mode} eq 'extended' ? 1 : 0;
my $ext_level = $self->{extension_level_used} // 0;
my ( @nodes, @idx, @val );
build_forest_openmp_xs( $x_packed, $n, $nf, $n_trees, $psi, $limit,
$mode_flag, $ext_level, \@nodes, \@idx, \@val, 1 );
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 )
= @{$nodes}[ $off + 1 .. $off + 4 ];
return [
_NODE_AXIS, int($attr), $split,
_unpack_node( $nodes, $idx, $val, int($li) ),
_unpack_node( $nodes, $idx, $val, int($ri) ),
];
} else {
my ( $coff, $num, $li, $ri, $b ) = @{$nodes}[ $off + 1 .. $off + 5 ];
$coff = int($coff);
$num = int($num);
return [
_NODE_OBLIQUE,
[ @{$idx}[ $coff .. $coff + $num - 1 ] ],
[ @{$val}[ $coff .. $coff + $num - 1 ] ],
$b,
_unpack_node( $nodes, $idx, $val, int($li) ),
_unpack_node( $nodes, $idx, $val, int($ri) ),
];
} ## end else [ if ( $type == 0 ) ]
} ## end sub _unpack_node
# Unpacks every tree in the three per-tree packed-buffer arrayrefs
# build_forest_openmp_xs returns into the ordinary nested tree shape.
# The C builder pushes nodes post-order (a node is recorded after both
# of its children), so each tree's root is the LAST node record, not
# index 0 as in _pack_tree's pre-order layout.
sub _unpack_forest {
my ( $nodes_list, $idx_list, $val_list ) = @_;
my @trees;
for my $i ( 0 .. $#$nodes_list ) {
my @nodes = unpack( 'd*', $nodes_list->[$i] );
my @idx = unpack( 'l*', $idx_list->[$i] );
my @val = unpack( 'd*', $val_list->[$i] );
my $root = @nodes / 6 - 1;
push @trees, _unpack_node( \@nodes, \@idx, \@val, $root );
}
return \@trees;
} ## end sub _unpack_forest
#-------------------------------------------------------------------------------
# Packed input wrapper. pack_data() returns one of these so callers can
# score the same dataset many times without re-walking the AV/AV refs on
# every call -- a meaningful win at high feature counts where
# pack_input_xs is a non-trivial slice of total scoring time.
#
# It's a minimal blessed hashref: { packed, n_pts, n_feats }. The C
# scoring functions only need the packed bytes + dimensions.
#-------------------------------------------------------------------------------
sub pack_data {
my ( $self, $data ) = @_;
( run in 0.530 second using v1.01-cache-2.11-cpan-995e09ba956 )