Algorithm-Classifier-IsolationForest
view release on metacpan or search on metacpan
d) If a facility in the modified Library refers to a function or a
table of data to be supplied by an application program that uses
the facility, other than as an argument passed when the facility
is invoked, then you must make a good faith effort to ensure that,
in the event an application does not supply such function or
table, the facility still operates, and performs whatever part of
its purpose remains meaningful.
(For example, a function in a library to compute square roots has
a purpose that is entirely well-defined independent of the
application. Therefore, Subsection 2d requires that any
application-supplied function or table used by this function must
be optional: if the application does not supply it, the square
root function must still compute square roots.)
These requirements apply to the modified work as a whole. If
identifiable sections of that work are not derived from the Library,
and can be reasonably considered independent and separate works in
themselves, then this License, and its terms, do not apply to those
sections when you distribute them as separate works. But when you
distribute the same sections as part of a whole which is a work based
on the Library, the distribution of the whole must be on the terms of
this License, whose permissions for other licensees extend to the
entire whole, and thus to each and every part regardless of who wrote
it.
Thus, it is not the intent of this section to claim rights or contest
your rights to work written entirely by you; rather, the intent is to
exercise the right to control the distribution of derivative or
collective works based on the Library.
In addition, mere aggregation of another work not based on the Library
with the Library (or with a work based on the Library) on a volume of
a storage or distribution medium does not bring the other work under
the scope of this License.
3. You may opt to apply the terms of the ordinary GNU General Public
b) Use a suitable shared library mechanism for linking with the
Library. A suitable mechanism is one that (1) uses at run time a
copy of the library already present on the user's computer system,
rather than copying library functions into the executable, and (2)
will operate properly with a modified version of the library, if
the user installs one, as long as the modified version is
interface-compatible with the version that the work was made with.
c) Accompany the work with a written offer, valid for at
least three years, to give the same user the materials
specified in Subsection 6a, above, for a charge no more
than the cost of performing this distribution.
d) If distribution of the work is made by offering access to copy
from a designated place, offer equivalent access to copy the above
specified materials from the same place.
e) Verify that the user has already received a copy of these
materials or that you have already sent this user a copy.
For an executable, the required form of the "work that uses the
otherwise) that contradict the conditions of this License, they do not
excuse you from the conditions of this License. If you cannot
distribute so as to satisfy simultaneously your obligations under this
License and any other pertinent obligations, then as a consequence you
may not distribute the Library at all. For example, if a patent
license would not permit royalty-free redistribution of the Library by
all those who receive copies directly or indirectly through you, then
the only way you could satisfy both it and this License would be to
refrain entirely from distribution of the Library.
If any portion of this section is held invalid or unenforceable under any
particular circumstance, the balance of the section is intended to apply,
and the section as a whole is intended to apply in other circumstances.
It is not the purpose of this section to induce you to infringe any
patents or other property right claims or to contest validity of any
such claims; this section has the sole purpose of protecting the
integrity of the free software distribution system which is
implemented by public license practices. Many people have made
generous contributions to the wide range of software distributed
through that system in reliance on consistent application of that
system; it is up to the author/donor to decide if he or she is willing
to distribute software through any other system and a licensee cannot
impose that choice.
This section is intended to make thoroughly clear what is believed to
be a consequence of the rest of this License.
12. If the distribution and/or use of the Library is restricted in
certain countries either by patents or by copyrighted interfaces, the
original copyright holder who places the Library under this License may add
an explicit geographical distribution limitation excluding those countries,
so that distribution is permitted only in or among countries not thus
excluded. In such case, this License incorporates the limitation as if
written in the body of this License.
benchmarking/BenchAccel.pm view on Meta::CPAN
# (user + sys), and an OpenMP `parallel for` running on N cores
# consumes ~N x the CPU time of its serial counterpart even when
# wall-clock time drops. That makes the c_openmp variant look
# *slower* than c_serial in cmpthese output -- the opposite of what
# a user actually experiences.
#
# This module replaces it with three Time::HiRes-based helpers, used
# across every bench script in this directory so they share a single
# timing path:
#
# wall_cmpthese($target_secs, \%vars)
# cmpthese-style comparison table, sorted slowest -> fastest with
# a pairwise percent-difference matrix. Prints only; returns
# nothing. Used when comparing several alternatives at once.
#
# wall_rate($code, $secs)
# Warm up briefly, then time $code for $secs wall-clock seconds.
# Returns ops/second as a scalar. Used when the script formats
# its own table (e.g. bench-sklearn-scoring's side-by-side
# Perl-vs-sklearn rows).
#
# wall_time_median($code, $reps)
# Run $code once as a warm-up, then time exactly $reps invocations
# and return the median elapsed time in seconds. Used when each
# invocation is too expensive to run on a time budget (fit() at
# large sizes); the small fixed sample with median statistic
# resists outliers without burning a 2-second budget per row.
use strict;
use warnings;
use Time::HiRes qw(time);
use Exporter qw(import);
our @EXPORT_OK = qw(wall_cmpthese wall_rate wall_time_median);
sub wall_cmpthese {
my ( $target_secs, $vars ) = @_;
my $target = abs( $target_secs || 0 ) || 1;
my %res;
for my $name ( sort keys %$vars ) {
my $code = $vars->{$name};
# Warm-up: one call absorbs first-touch and cache-miss spikes
# so the calibration window measures steady-state cost.
$code->();
# Calibrate over 50 ms so the real run lands close to $target s
benchmarking/BenchAccel.pm view on Meta::CPAN
} ## end for my $a (@names)
} ## end sub wall_cmpthese
sub _fmt_rate {
my $r = shift;
return sprintf '%.2g/s', $r if $r < 1;
return sprintf '%.2f/s', $r if $r < 100;
return sprintf '%.0f/s', $r;
}
# wall_rate($code, $secs) -- scalar ops/second over $secs wall-clock
# seconds. Returns the rate as a plain number so callers can format
# their own tables.
#
# The measurement is split into 3 equal sub-windows and the median of
# their rates is returned. At small workloads (a few hundred
# microseconds per call) OpenMP thread scheduling is non-deterministic
# enough that a single 2-second window can land in a slow stretch and
# report ~30x lower throughput than steady state; median across
# windows smooths that without spending extra time.
sub wall_rate {
my ( $code, $secs ) = @_;
$secs ||= 1;
# Warm-up: at least 0.3 s (matches the original Perl bench() helper
# this replaced) so OpenMP thread pools are firmly hot before any
# measurement window starts. Scales up for long budgets -- a 30 s
# measurement gets a 3 s warmup.
my $warmup = $secs * 0.1;
$warmup = 0.3 if $warmup < 0.3;
my $wt0 = time;
$code->() while time - $wt0 < $warmup;
my $WINDOWS = 3;
my $win_secs = $secs / $WINDOWS;
my @rates;
for ( 1 .. $WINDOWS ) {
my $t0 = time;
my $n = 0;
while ( time - $t0 < $win_secs ) { $code->(); $n++ }
my $elapsed = ( time - $t0 ) || 1e-9;
push @rates, $n / $elapsed;
}
my @s = sort { $a <=> $b } @rates;
return $s[ int( @s / 2 ) ];
} ## end sub wall_rate
# wall_time_median($code, $reps) -- single warm-up + $reps timed
# invocations; returns the median elapsed time in seconds. Use this
# when each call is expensive enough that running it on a $secs budget
# would either be wasteful (3 calls in 2 s tells you little more than
# 3 calls in 30 s) or pull in confounders like GC pauses.
sub wall_time_median {
my ( $code, $reps ) = @_;
$reps = 5 unless $reps && $reps >= 1;
$code->(); # warm-up: covers Inline::C compile, first-touch cache
my @times;
for ( 1 .. $reps ) {
benchmarking/bench-axis-fit-accel.pl view on Meta::CPAN
my $HAS_C = $Algorithm::Classifier::IsolationForest::HAS_C;
my $HAS_OPENMP = $Algorithm::Classifier::IsolationForest::HAS_OPENMP;
print "=" x 70, "\n";
print " axis-mode fit() accel benchmarks\n";
print " Algorithm::Classifier::IsolationForest\n";
print "=" x 70, "\n";
printf "Backend availability: HAS_C=%d HAS_OPENMP=%d HAS_SIMD=%d\n",
$HAS_C, $HAS_OPENMP,
$Algorithm::Classifier::IsolationForest::HAS_SIMD;
print "(rates shown as fits/second wall-clock; higher is faster)\n";
# Build the set of accel configs to compare. Always include pure_perl;
# only include C variants when the backend actually compiled.
sub accel_variants {
my (%base) = @_;
my %v = (
'pure_perl' => sub {
Algorithm::Classifier::IsolationForest->new( %base, use_c => 0 )->fit( $base{_data} );
},
);
benchmarking/bench-axis-predict-accel.pl view on Meta::CPAN
return \%m;
} ## end sub build_models
print "=" x 70, "\n";
print " axis-mode scoring/predict accel benchmarks\n";
print " Algorithm::Classifier::IsolationForest\n";
print "=" x 70, "\n";
printf "Backend availability: HAS_C=%d HAS_OPENMP=%d HAS_SIMD=%d\n",
$HAS_C, $HAS_OPENMP,
$Algorithm::Classifier::IsolationForest::HAS_SIMD;
print "(rates shown as calls/second wall-clock; higher is faster)\n";
# -----------------------------------------------------------------------
# 1. Scoring method comparison (n_trees=100, 1000 query points)
# -----------------------------------------------------------------------
print "\n--- scoring methods (n_trees=100, 1000 query points, 2 features) ---\n";
srand(42);
my $train = make_data( 1000, 2 );
my $q1k = make_data( 1000, 2 );
my $models = build_models(
n_trees => 100,
benchmarking/bench-extended-fit-accel.pl view on Meta::CPAN
my $HAS_C = $Algorithm::Classifier::IsolationForest::HAS_C;
my $HAS_OPENMP = $Algorithm::Classifier::IsolationForest::HAS_OPENMP;
print "=" x 70, "\n";
print " extended-mode fit() accel benchmarks\n";
print " Algorithm::Classifier::IsolationForest\n";
print "=" x 70, "\n";
printf "Backend availability: HAS_C=%d HAS_OPENMP=%d HAS_SIMD=%d\n",
$HAS_C, $HAS_OPENMP,
$Algorithm::Classifier::IsolationForest::HAS_SIMD;
print "(rates shown as fits/second wall-clock; higher is faster)\n";
sub accel_variants {
my (%base) = @_;
my %v = (
'pure_perl' => sub {
Algorithm::Classifier::IsolationForest->new( %base, use_c => 0 )->fit( $base{_data} );
},
);
if ($HAS_C) {
$v{'c_serial'} = sub {
benchmarking/bench-extended-predict-accel.pl view on Meta::CPAN
return \%m;
} ## end sub build_models
print "=" x 70, "\n";
print " extended-mode scoring/predict accel benchmarks\n";
print " Algorithm::Classifier::IsolationForest\n";
print "=" x 70, "\n";
printf "Backend availability: HAS_C=%d HAS_OPENMP=%d HAS_SIMD=%d\n",
$HAS_C, $HAS_OPENMP,
$Algorithm::Classifier::IsolationForest::HAS_SIMD;
print "(rates shown as calls/second wall-clock; higher is faster)\n";
# -----------------------------------------------------------------------
# 1. Scoring method comparison (n_trees=100, 1000 query points)
# -----------------------------------------------------------------------
print "\n--- scoring methods (n_trees=100, 1000 query points, 2 features) ---\n";
srand(42);
my $train = make_data( 1000, 2 );
my $q1k = make_data( 1000, 2 );
my $models = build_models(
n_trees => 100,
benchmarking/bench-fit.pl view on Meta::CPAN
#!/usr/bin/perl
# benchmarking/bench-fit.pl
#
# Benchmarks the fit() method across five dimensions:
# 1. n_trees -- number of isolation trees
# 2. sample_size/psi -- sub-sample size used to build each tree
# 3. dataset size -- number of training samples
# 4. feature count -- dimensionality (wide range: 2, 5, 10, 20, 50)
# 5. feature count -- fine-grained 2–10 columns
#
# Each section uses BenchAccel::wall_cmpthese so results include both the raw
# rate (fits/sec) and relative %-difference between variants.
# Data generation is done before timing starts.
#
# Run with:
# perl -Ilib benchmarking/bench-fit.pl
use strict;
use warnings;
use lib '../lib';
use FindBin;
use lib "$FindBin::Bin";
benchmarking/bench-fit.pl view on Meta::CPAN
for ( 1 .. int( $n * 0.05 ) ) {
my $r = 5 + rand() * 3;
push @rows, [ map { $r * ( rand() > 0.5 ? 1 : -1 ) } 1 .. $nf ];
}
return \@rows;
} ## end sub make_data
print "=" x 62, "\n";
print " fit() benchmarks -- Algorithm::Classifier::IsolationForest\n";
print "=" x 62, "\n";
print "(rates shown as fits/second wall-clock; higher is faster)\n";
# -----------------------------------------------------------------------
# 1. n_trees
# -----------------------------------------------------------------------
print "\n--- n_trees (1000 samples, 2 features, sample_size=256) ---\n";
srand(42);
my $d1k = make_data( 1000, 2 );
wall_cmpthese(
-2,
{
benchmarking/bench-modes.pl view on Meta::CPAN
push @rows, [ map { $r * ( rand() > 0.5 ? 1 : -1 ) } 1 .. $nf ];
}
return \@rows;
} ## end sub make_data
print "=" x 62, "\n";
print " axis vs extended mode -- Algorithm::Classifier::IsolationForest\n";
print "=" x 62, "\n";
print "(1000 training samples, n_trees=100, sample_size=256)\n";
print "(1000 query points for score_samples)\n";
print "(rates shown as calls/second wall-clock; higher is faster)\n";
my @feature_counts = ( 2 .. 10, 20, 50, 100 );
# Pre-generate all datasets (training and query) before any timing.
srand(42);
my ( %train_data, %query_data );
for my $nf (@feature_counts) {
$train_data{$nf} = make_data( 1000, $nf );
$query_data{$nf} = make_data( 1000, $nf );
}
benchmarking/bench-online-score-accel.pl view on Meta::CPAN
# 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,
# 5 features): batch scoring of 20k query points -- pure Perl ~3.6 s/call,
# C serial ~58 ms, C+OpenMP ~9 ms; score_learn stream -- pure Perl ~270
# pts/s, C ~2,400 pts/s.
#
# Run with:
# perl -Ilib benchmarking/bench-online-score-accel.pl
benchmarking/bench-online-score-accel.pl view on Meta::CPAN
} 1 .. $n
];
}
my $HAS_C = $Algorithm::Classifier::IsolationForest::HAS_C;
my $HAS_OPENMP = $Algorithm::Classifier::IsolationForest::HAS_OPENMP;
# One model per accel config. Each learn is reseeded so every model
# sees the identical draw sequence; with the C/Perl learn parity
# guarantee that makes the trees identical across configs, so the
# scoring sections compare equal work.
sub build_models {
my ( $stream, %opts ) = @_;
my %m;
$m{pure_perl} = Algorithm::Classifier::IsolationForest::Online->new( %opts, use_c => 0 );
$m{c_serial} = Algorithm::Classifier::IsolationForest::Online->new( %opts, use_c => 1, use_openmp => 0 )
if $HAS_C;
$m{c_openmp} = Algorithm::Classifier::IsolationForest::Online->new( %opts, use_c => 1, use_openmp => 1 )
if $HAS_C && $HAS_OPENMP;
for my $name ( sort keys %m ) {
srand(1);
benchmarking/bench-online-score-accel.pl view on Meta::CPAN
return \%m;
} ## end sub build_models
print "=" x 70, "\n";
print " online (streaming) scoring accel benchmarks\n";
print " Algorithm::Classifier::IsolationForest::Online\n";
print "=" x 70, "\n";
printf "Backend availability: HAS_C=%d HAS_OPENMP=%d online_learn_xs=%d\n",
$HAS_C, $HAS_OPENMP,
Algorithm::Classifier::IsolationForest::Online::_HAS_ONLINE_XS;
print "(rates shown as calls/second wall-clock; higher is faster)\n";
print "(online_learn_xs=0 means the loaded C object predates the online\n"
. " learn accelerators -- rebuild or rerun with IF_RUNTIME_BUILD=1)\n"
unless Algorithm::Classifier::IsolationForest::Online::_HAS_ONLINE_XS;
srand(42);
my $stream = make_data( 3000, 5 );
my $models = build_models(
$stream,
n_trees => 100,
window_size => 2048,
benchmarking/bench-score.pl view on Meta::CPAN
for ( 1 .. int( $n * 0.05 ) ) {
my $r = 5 + rand() * 3;
push @rows, [ map { $r * ( rand() > 0.5 ? 1 : -1 ) } 1 .. $nf ];
}
return \@rows;
} ## end sub make_data
print "=" x 62, "\n";
print " scoring benchmarks -- Algorithm::Classifier::IsolationForest\n";
print "=" x 62, "\n";
print "(rates shown as calls/second wall-clock; higher is faster)\n";
# -----------------------------------------------------------------------
# Pre-train models with different n_trees on the same 1000-sample dataset
# -----------------------------------------------------------------------
srand(42);
my $train = make_data( 1000, 2 );
my %model;
for my $nt ( 10, 50, 100, 200, 500 ) {
$model{$nt} = Algorithm::Classifier::IsolationForest->new(
n_trees => $nt,
benchmarking/bench-sklearn-scoring.pl view on Meta::CPAN
# -----------------------------------------------------------------------
# Python benchmarking script (embedded, written to a temp file).
# -----------------------------------------------------------------------
my $py_script = <<'END_PY';
import sys, json
import time as pytime
import numpy as np
from sklearn.ensemble import IsolationForest
def bench(fn, seconds):
t0 = pytime.perf_counter()
while pytime.perf_counter() - t0 < 0.3:
fn()
t0 = pytime.perf_counter()
n = 0
while pytime.perf_counter() - t0 < seconds:
fn()
n += 1
return n / (pytime.perf_counter() - t0)
def load_csv(path):
with open(path) as f:
return np.array([[float(v) for v in ln.strip().split(',')]
for ln in f if ln.strip()])
bench_secs = float(sys.argv[1])
specs = sys.argv[2:]
models = {}
results = {}
for spec in specs:
train_csv, query_csv, label = spec.split('|', 2)
clf = models.get(train_csv)
if clf is None:
X_train = load_csv(train_csv)
psi = min(256, len(X_train))
clf = IsolationForest(n_estimators=100, max_samples=psi,
contamination='auto', random_state=1)
clf.fit(X_train)
models[train_csv] = clf
X_q = load_csv(query_csv)
results[label] = {
'score_samples': bench(lambda X=X_q: clf.score_samples(X), bench_secs),
'predict': bench(lambda X=X_q: clf.predict(X), bench_secs),
'decision_function': bench(lambda X=X_q: clf.decision_function(X), bench_secs),
}
print(json.dumps(results))
END_PY
# -----------------------------------------------------------------------
# Run Python (one subprocess for all experiments)
# -----------------------------------------------------------------------
my $sk;
if ( defined $python_bin ) {
benchmarking/bench-streamd.pl view on Meta::CPAN
#!/usr/bin/perl
# benchmarking/bench-streamd.pl
#
# Benchmarks `iforest streamd` end to end: the script spawns its own
# daemon on a temp Unix socket and pumps rows through the JSON-lines
# protocol, measuring points/second wall-clock at the client.
#
# Sections:
# 1. in-process baseline -- score_learn on an identical model in this
# process; the ceiling everything else is measured against. The
# gap between it and the socket numbers is protocol + JSON + IPC
# overhead, not model work.
# 2. batch-size sweep -- prequential rows per {"rows": [...]}
# message; directly informs streamc's --batch choice.
# 3. modes -- prequential vs score vs learn at a fixed
# batch size.
benchmarking/bench-streamd.pl view on Meta::CPAN
my $got = sysread( $s, my $chunk, 262144 );
die "daemon closed the connection\n" unless $got;
$$buf .= $chunk;
}
$$buf =~ s/\A([^\n]*)\n//;
my $reply = $JSON->decode($1);
die "daemon error: $reply->{error}\n" if defined $reply->{error};
return $reply;
} ## end sub rt
# Pump rows through in lockstep batches; returns elapsed seconds.
sub pump {
my ( $s, $rows, $batch, $mode ) = @_;
my $n = scalar @$rows;
my $t0 = time;
my $i = 0;
while ( $i < $n ) {
my $end = $i + $batch - 1;
$end = $n - 1 if $end > $n - 1;
rt( $s, { rows => [ @{$rows}[ $i .. $end ] ], mode => $mode } );
$i = $end + 1;
benchmarking/bench-streamd.pl view on Meta::CPAN
my ( $label, $n, $elapsed ) = @_;
printf " %-34s %10.0f pts/s (%d rows in %.2fs)\n", $label, $n / $elapsed, $n, $elapsed;
return;
}
print "=" x 70, "\n";
print " streamd end-to-end benchmarks (JSON lines over a Unix socket)\n";
print "=" x 70, "\n";
printf " %d trees, window %d, eta %d, %d features; JSON backend: %s\n",
$N_TREES, $WINDOW, $ETA, $NF, JSON::MaybeXS::JSON();
print " (points/second wall-clock at the client; higher is faster)\n";
# Warm both the daemon and the baseline model past the window size so
# every section measures steady-state, full-window work.
srand(42);
my $warm = make_data( 3000, $NF );
srand(43);
my $feed = make_data( 60000, $NF );
my $c = connect_daemon();
pump( $c, $warm, 500, 'learn' );
# -----------------------------------------------------------------------
# 1. In-process baseline: the same stream loop without the wire
benchmarking/bench-voting.pl view on Meta::CPAN
use constant PI => 3.14159265358979;
sub gaussian {
my ( $mu, $sigma ) = @_;
return $mu + $sigma * sqrt( -2 * log( rand() || 1e-12 ) ) * cos( 2 * PI * rand() );
}
# Returns ($rows, $n_inliers): the first $n_inliers rows are the gaussian
# cluster, the remaining rows are the planted outliers (a 5% block pushed
# 5-8 sigma out). Keeping the split point lets the detection section
# score recall (true outliers caught) against false alarms (inliers
# flagged).
sub make_data {
my ( $n, $nf ) = @_;
my @rows = map {
[ map { gaussian( 0, 1 ) } 1 .. $nf ]
} 1 .. $n;
my $n_inliers = scalar @rows;
for ( 1 .. int( $n * 0.05 ) ) {
my $r = 5 + rand() * 3;
benchmarking/bench-voting.pl view on Meta::CPAN
};
} ## end sub build_pair
print "=" x 70, "\n";
print " mean vs majority-vote aggregation\n";
print " Algorithm::Classifier::IsolationForest\n";
print "=" x 70, "\n";
printf "Backend availability: HAS_C=%d HAS_OPENMP=%d HAS_SIMD=%d\n",
$HAS_C, $HAS_OPENMP,
$Algorithm::Classifier::IsolationForest::HAS_SIMD;
print "(rates shown as calls/second wall-clock; higher is faster)\n";
# =======================================================================
# PART 1 -- SPEED
# =======================================================================
print "\n", "=" x 70, "\n";
print " PART 1: speed (predict is where majority voting can win)\n";
print " (serial C backend -- isolates the fewer-tree-walks effect)\n";
print "=" x 70, "\n";
# -----------------------------------------------------------------------
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
if (p == k) return a[p];
if (p < k) lo = p + 1; else hi = p - 1;
}
return a[lo];
}
/* Median of a[0..n-1] (reorders a[]). Odd n: the single middle order
* statistic. Even n: quickselect finds the lower-median at k = n/2-1,
* which leaves every a[i > k] >= a[k] (the standard quickselect
* post-condition) -- so the upper-median is just the min of that
* remaining slice, one more linear scan instead of a second full
* selection pass. */
static double _median_select(double *a, int n) {
if (n % 2 == 1) {
return _kth_smallest(a, n, n / 2);
} else {
int k = n / 2 - 1;
double lower = _kth_smallest(a, n, k);
double upper = a[k + 1];
int i;
for (i = k + 2; i < n; i++) {
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
SV* child = AvARRAY(node)[ci];
SV* nc = _ol_node_learn(aTHX_ child, x, nf, depth + 1, limit, eta,
adaptive);
if (nc != child) av_store(node, ci, nc);
return node_rv;
}
}
/* Union of two nodes' boxes into caller-provided arrays, matching
* _box_union(): nodes without a box are skipped, the first boxed node
* is copied and the second folded in. Returns 0 when neither node has
* a box. */
static int _ol_box_union(pTHX_ SV* a_rv, SV* b_rv, int nf,
double* lo, double* hi) {
SV* boxed[2];
int nb = 0, bi, f;
if (SvOK(AvARRAY((AV*)SvRV(a_rv))[OL_LO])) boxed[nb++] = a_rv;
if (SvOK(AvARRAY((AV*)SvRV(b_rv))[OL_LO])) boxed[nb++] = b_rv;
if (nb == 0) return 0;
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
By default this C builder is single-threaded per call, because Perl's
RNG state isn't safe to share across OpenMP threads. Two ways to scale
fit() across cores are available (see below for why they don't compose):
=over 4
=item * C<parallel_fit> forks N worker processes, each building its
share of the trees with the (still single-threaded) C builder. Fixed
IPC/serialisation overhead per worker means this can cost more than it
saves once a fit already completes in milliseconds; it's most useful
once a single-process fit is large enough that the fork/Storable
overhead is small relative to the work being split.
=item * C<use_openmp_fit> builds trees across OpenMP threads within a
single process (one tree per thread), using a separate, thread-safe
PRNG seeded per tree index instead of Perl's C<rand()>. This means
trees built with C<use_openmp_fit> are I<not> bit-identical to the
default C<use_c> path for the same seed -- but a fixed seed and
C<n_trees> still reproduce the same trees regardless of
C<OMP_NUM_THREADS> or how OpenMP schedules the work. It's off by
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
$iforest->set_voting('majority');
$iforest->set_voting('mean', \@training_data);
The one thing that does not carry over is a C<contamination>-learned
L</decision_threshold>. That cutoff is a quantile of whichever per-point
quantity the mode thresholds against -- the averaged anomaly score under
C<'mean'>, the per-tree majority pivot under C<'majority'> -- and those live in
different spaces, so a threshold learned in one mode flags the wrong fraction
in the other. When the model was fitted with C<contamination>, C<set_voting>
therefore relearns the threshold for the target mode, which requires the
original training data to be passed as the second argument (the model does not
retain it). Switching a model that had no C<contamination> needs no data:
C<predict> falls back to C<0.5>, which is meaningful in both modes.
Passing the current mode is a no-op (returns immediately, no data needed).
Calling this before L</fit> just records the mode for the eventual fit.
=cut
sub set_voting {
my ( $self, $voting, $data ) = @_;
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
# A learned threshold only exists once a contamination-fitted model has
# been fit(); that value is mode-specific and must be relearned against
# the same training set (see _learn_contamination_threshold). Everything
# else -- pre-fit models, and fitted models without contamination -- just
# flips the knob; predict()'s 0.5 fallback is valid in either mode.
my $fitted = ref $self->{trees} eq 'ARRAY' && @{ $self->{trees} };
my $recalibrate = $fitted && defined $self->{contamination};
if ($recalibrate) {
croak "set_voting: switching a contamination-fitted model requires "
. "the original training data as the second argument to "
. "recalibrate the decision threshold"
unless ref $data eq 'ARRAY' && @$data;
}
$self->{voting} = $voting;
$self->_learn_contamination_threshold($data) if $recalibrate;
return $self;
} ## end sub set_voting
lib/Algorithm/Classifier/IsolationForest.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 score_predict_samples
Returns an array ref of arrays. First value of each sub array is the score with the second being
0/1 for if it is a anomaly or not.
C<$threshold> defaults the same way as in C<predict>.
Under C<< voting => 'majority' >> the score is the anomaly vote fraction at
C<$threshold> (used as the per-tree cutoff) and the label is the majority
vote, matching C<score_samples>/C<predict> semantics in that mode.
my $results = $forest->score_predict_samples(\@data, $threshold);
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
} ## end sub _rebuild_c_trees
sub _check_fitted {
my ($self) = @_;
croak "model is not fitted yet; call fit() first"
unless ref $self->{trees} eq 'ARRAY' && @{ $self->{trees} };
}
# ---------------------------------------------------------------------------
# Optional Algorithm::ToNumberMunger integration -- see the MUNGERS POD
# section. Both helpers are plain functions (not methods) so the Online
# class's delegating methods can hand them their own $self: the plan and
# spec live in the same hash slots on either class.
# ---------------------------------------------------------------------------
# Validate a feature_descriptions hash against the feature names: every
# described feature must exist (a description for one that does not is
# either a typo or a stale leftover from a schema change) and every
# description must be a plain string. Partial coverage is fine. A plain
# function, like the munger helpers, so both classes and the prototype
# validator can call it.
lib/Algorithm/Classifier/IsolationForest.pm view on Meta::CPAN
}
return $data;
} ## end if ( $m eq 'die' )
# nan: leave undef in place -- _build_tree / the split routers handle it.
return $data if $m eq 'nan';
# zero / impute: undef has to become a real number somewhere before a
# split can look at it. The fill vector is computed either way (it's
# needed for persistence and for scoring later), but densifying $data
# into a second, fully separate Perl array here is only necessary for
# the pure-Perl tree builder (_build_tree assumes every cell is
# defined once missing != 'nan' -- see its lo/hi scan). The C
# tree-building path -- _build_forest_c/_build_forest_openmp, and
# every parallel_fit worker, all of which go through pack_input_xs --
# already fills undef cells itself from this same fill vector, so
# skip the redundant whole-dataset copy when that's the path fit()
# will actually take. Scoring the training set for a learned
# contamination threshold (below, in fit()) is unaffected: it always
# runs through the pure-Perl scorer regardless of use_c (fit() drops
# any previous fit's packed buffers before that scoring, and
lib/Algorithm/Classifier/IsolationForest/App/Command/bench.pm view on Meta::CPAN
use Time::HiRes qw(time);
sub opt_spec {
return (
[
'm=s',
'Input model JSON file path/name.',
{ 'default' => 'iforest_model.json', 'completion' => 'files' }
],
[ 'i=s', 'Input CSV (rows of features to score).', { 'completion' => 'files' } ],
[ 'secs|s=f', 'Seconds per measurement (after a 0.3s warm-up).', { 'default' => 2 } ],
[ 't=f', 'Threshold to use for predict / score_predict_*.', { 'default' => 0.5 } ],
);
} ## end sub opt_spec
sub abstract { 'Measure scoring throughput of a saved model on a CSV dataset' }
sub description {
'Loads a model and a CSV dataset, then times each of the
public scoring methods over the configured wall-clock budget. Reports
ops-per-second for each.
When the Inline::C backend is active the bench also runs pack_data once
up front and times the *_packed variants so users can see how much
pre-packing saves on their workload.
Use this to answer:
* is my Inline::C / OpenMP / SIMD build actually faster than the
pure-Perl fallback?
* how much does pack_data help on my data shape?
lib/Algorithm/Classifier/IsolationForest/App/Command/bench.pm view on Meta::CPAN
} elsif ( !-r $opt->{'i'} ) {
$self->usage_error( '-i, "' . $opt->{'i'} . '", is not readable' );
}
if ( !-f $opt->{'m'} ) {
$self->usage_error( '-m, "' . $opt->{'m'} . '", is not a file or does not exist' );
} elsif ( !-r $opt->{'m'} ) {
$self->usage_error( '-m, "' . $opt->{'m'} . '", is not readable' );
}
if ( $opt->{'secs'} <= 0 ) {
$self->usage_error('--secs must be > 0');
}
if ( $opt->{'t'} <= 0 || $opt->{'t'} >= 1 ) {
$self->usage_error('-t must satisfy 0 < t < 1');
}
return 1;
} ## end sub validate
# Standard bench helper: warm up briefly, then time exactly $secs of
# back-to-back calls. Returns ops/second.
sub _bench {
my ( $code, $secs ) = @_;
my $t0 = time();
$code->() while time() - $t0 < 0.3;
$t0 = time();
my $n = 0;
$code->(), $n++ while time() - $t0 < $secs;
return $n / ( time() - $t0 );
}
sub _read_csv {
my ($path) = @_;
my @data;
my $expected;
my $line = 0;
for my $row ( read_file($path) ) {
$line++;
lib/Algorithm/Classifier/IsolationForest/App/Command/bench.pm view on Meta::CPAN
sub execute {
my ( $self, $opt, $args ) = @_;
my $model = Algorithm::Classifier::IsolationForest->load( $opt->{'m'} );
my ( $data, $cols ) = _read_csv( $opt->{'i'} );
die "input CSV has $cols feature columns but model expects " . $model->{n_features} . "\n"
if $cols != $model->{n_features};
my $n_pts = scalar @$data;
my $secs = $opt->{'secs'};
my $thresh = $opt->{'t'};
my $has_c = $Algorithm::Classifier::IsolationForest::HAS_C ? 1 : 0;
printf "Model: %s (n_trees=%d, mode=%s, n_features=%d)\n",
$opt->{'m'}, scalar @{ $model->{trees} },
$model->{mode}, $model->{n_features};
printf "Input: %s (%d rows)\n", $opt->{'i'}, $n_pts;
printf "Budget: %.1fs per measurement (0.3s warm-up)\n", $secs;
printf "Backend: HAS_C=%d HAS_OPENMP=%d HAS_SIMD=%d\n\n",
$has_c,
$Algorithm::Classifier::IsolationForest::HAS_OPENMP ? 1 : 0,
$Algorithm::Classifier::IsolationForest::HAS_SIMD ? 1 : 0;
# Pre-pack once (when C is available) so the *_packed rows measure
# scoring in isolation, without the per-call pack_input_xs cost.
my $packed = $has_c ? $model->pack_data($data) : undef;
my @bench = (
lib/Algorithm/Classifier/IsolationForest/App/Command/bench.pm view on Meta::CPAN
[ 'score_samples (packed)' => sub { $model->score_samples($packed) } ],
[ 'predict (packed)' => sub { $model->predict( $packed, $thresh ) } ],
[ 'score_predict_split (packed)' => sub { my @r = $model->score_predict_split( $packed, $thresh ); } ],
);
}
printf " %-30s %14s %14s\n", 'method', 'ops/s', 'ms/call';
printf " %-30s %14s %14s\n", '-' x 30, '-' x 14, '-' x 14;
for my $row (@bench) {
my ( $label, $code ) = @$row;
my $rate = _bench( $code, $secs );
printf " %-30s %14.1f %14.2f\n", $label, $rate, $rate > 0 ? 1000 / $rate : 0;
}
return 1;
} ## end sub execute
return 1;
lib/Algorithm/Classifier/IsolationForest/App/Command/csv2plot.pm view on Meta::CPAN
sub abstract { 'Plot the CSV data used with iforest via gnuplot.' }
sub description {
'Plot the CSV data used with iforest via gnuplot.
Plot types are as below.
auto: If there are two columns, 2heat. If there are 4 or more columns, 3range.
2heat: Use column 1 and 2 to generate a splatter plot over a heat map.
3range: Use columns 1 and 2 for x/y, and the second-to-last column for the
score gradient. Suitable for predict -d output (any number of features).
3binary: Use columns 1 and 2 for x/y, and the last column for normal/abnormal.
Suitable for predict -d output or gblob output.
3range and 3binary require data outputted from predict with the -d flag.
For N-dimensional data, columns 1 and 2 are always used for the x/y axes.
';
} ## end sub description
sub validate {
lib/Algorithm/Classifier/IsolationForest/App/Command/csv2plot.pm view on Meta::CPAN
} elsif ( $opt->{'p'} eq 'auto' ) {
die('-p is set to auto and the specified CSV does not have enough columns');
} elsif ( $opt->{'p'} eq '2heat' && $ncols < 2 ) {
die('2heat specified but there is no column for y');
} elsif ( $opt->{'p'} eq '3range' && $ncols < 3 ) {
die('3range specified but there is no column for score');
} elsif ( $opt->{'p'} eq '3binary' && $ncols < 3 ) {
die('3binary specified but there is no column for truth');
}
# For predict -d output: score is the second-to-last column, prediction is last.
my $score_col = $ncols - 1;
my $pred_col = $ncols;
$opt->{'i'} = File::Spec->rel2abs( $opt->{'i'} );
$opt->{'o'} = File::Spec->rel2abs( $opt->{'o'} );
my ( $tempfh, $tempfile ) = tempfile( 'UNLINK' => 1 );
my $ps = $opt->{'small_points'} ? '0.8' : '1.5';
lib/Algorithm/Classifier/IsolationForest/App/Command/streamd.pm view on Meta::CPAN
sub description {
'Runs a prequential scoring daemon around an Online Isolation Forest
model (Algorithm::Classifier::IsolationForest::Online): clients connect
to the Unix domain socket and exchange one JSON document per line.
At startup the daemon resumes from <model-dir>/latest.json when it
exists; otherwise it creates a new model from the creation knobs (-n,
--window, --eta, --growth, --subsample, -s, -c, -t, --mungers,
--prototype -- the same set `iforest stream` takes). The model is saved
to a timestamped file in --model-dir every --save-interval seconds
(only when something was learned), on SIGUSR1, on the save command, and
at shutdown; the symlink latest.json is atomically repointed at every
save, so a restart resumes the stream losing at most one interval.
Requests are JSON objects carrying exactly one of "row", "rows", or
"cmd", an optional "mode", and an optional "tag" (any JSON value,
echoed back verbatim in the reply -- a correlation tag, not to be
confused with feature tags):
{"row": [0.1, 0.7]} -> {"score": 0.41, "label": 0}
lib/Algorithm/Classifier/IsolationForest/App/Command/streamd.pm view on Meta::CPAN
# Anchored with \A/\z rather than ^/$ ($ tolerates a trailing newline).
# The class has no '.' or '/', so a set name can only ever create one
# new path segment -- no traversal is expressible.
if ( defined( $opt->{'set'} ) && $opt->{'set'} !~ /\A[A-Za-z0-9+\-@_]+\z/ ) {
$self->usage_error( '--set, "'
. $opt->{'set'}
. '", must match /\A[A-Za-z0-9+\-@_]+\z/ (letters, digits, and + - @ _ only)' );
}
if ( $opt->{'save_interval'} < 1 ) {
$self->usage_error( '--save-interval, "' . $opt->{'save_interval'} . '", must be >= 1 second' );
}
if ( defined( $opt->{'keep'} ) && $opt->{'keep'} < 1 ) {
$self->usage_error( '--keep, "' . $opt->{'keep'} . '", must be >= 1' );
}
if ( defined( $opt->{'threshold'} ) && ( $opt->{'threshold'} <= 0 || $opt->{'threshold'} >= 1 ) ) {
$self->usage_error( '--threshold, "' . $opt->{'threshold'} . '", needs to be greater than 0 and less than 1' );
}
lib/Algorithm/Classifier/IsolationForest/App/Command/streamd.pm view on Meta::CPAN
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;
} ## end sub _daemonize
sub _open_log {
if ( defined $OPT{'log'} ) {
open( my $fh, '>>', $OPT{'log'} ) or die( 'failed to open log "' . $OPT{'log'} . '": ' . $! . "\n" );
$fh->autoflush(1);
t/03-fit-determinism.t view on Meta::CPAN
sub fit_trees {
my (%opts) = @_;
my $data = delete $opts{data} // \@data;
return trees_json( $CLASS->new(%opts)->fit($data) );
}
# Bounds a block with alarm() so a regression of the fork()+libgomp
# hazard documented below fails this one assertion instead of hanging
# the whole test run (and anything waiting on it, e.g. CI) forever.
sub with_timeout {
my ( $secs, $code ) = @_;
my $result;
eval {
local $SIG{ALRM} = sub { die "timeout\n" };
alarm($secs);
$result = $code->();
alarm(0);
};
alarm(0);
return ( $result, $@ );
} ## end sub with_timeout
# ------------------------------------------------------------------------
# 1. Same seed, same backend, twice => identical trees.
# ------------------------------------------------------------------------
t/03-fit-determinism.t view on Meta::CPAN
parallel_fit => 3,
);
# A regression of the fork()+libgomp hazard would hang fit() itself,
# not just fail an assertion -- with_timeout() bounds that so it
# fails this test instead of stalling the whole run.
my ( $r1, $err1 ) = with_timeout( 20, sub { fit_trees(%opts) } );
my ( $r2, $err2 ) = with_timeout( 20, sub { fit_trees(%opts) } );
is( $err1, '', 'first parallel_fit + use_openmp_fit run does not hang' )
or diag("error: $err1");
is( $err2, '', 'second parallel_fit + use_openmp_fit run does not hang' )
or diag("error: $err2");
is( $r1, $r2, 'two parallel_fit + use_openmp_fit runs with the same seed and ' . 'worker count match' );
}; ## end 'use_openmp_fit + parallel_fit does not hang and is reproducible' => sub
done_testing;
t/34-missing-values.t view on Meta::CPAN
# learn, and must croak -- on the first such column in feature order,
# matching the pure-Perl fallback's message exactly. This exercises
# the multi-column case (one good column, one entirely-undef column)
# specifically: an earlier regression in the C fast path freed a
# good column's scratch buffer once when computing its fill and then
# again while cleaning up after discovering the later, entirely-undef
# column -- a double free that only shows up with more than one
# feature column, so a single-column case wouldn't have caught it.
# -----------------------------------------------------------------------
subtest "[$be_name] impute mode croaks on a feature with no present values" => sub {
my @all_missing_second = map { [ $_->[0], undef ] } @holey;
my $f = $CLASS->new(
n_trees => 20,
seed => $SEED,
missing => 'impute',
use_c => $USE_C
);
ok( !eval { $f->fit( \@all_missing_second ); 1 }, 'fit croaks when a feature column is entirely undef' );
like( $@, qr/impute: feature column 1 has no present values/, 'names the offending column' );
my @all_missing_first = map { [ undef, $_->[1] ] } @holey;
my $g = $CLASS->new(
n_trees => 20,
seed => $SEED,
missing => 'impute',
use_c => $USE_C
);
ok( !eval { $g->fit( \@all_missing_first ); 1 },
t/90-cli-commands.t view on Meta::CPAN
my $obj = eval { JSON::PP->new->decode($j) };
ok( !$@, 'tagged --json parses' ) or diag("error: $@");
if ($obj) {
is( $obj->{tagged}, 1, 'JSON tagged=1' );
is_deeply( $obj->{feature_names}, [qw(cpu mem disk)], 'JSON feature_names matches tags' );
}
}; ## end 'info displays tag info' => sub
# --- 4. bench -----------------------------------------------------------
subtest 'bench reports per-method ops/s' => sub {
# Short --secs so the bench finishes quickly in CI.
my $out = `$^X -Ilib $bin bench -m $model -i $query_csv --secs 0.3 2>&1`;
is( $?, 0, 'bench exits 0' );
like( $out, qr/score_samples\b/, 'mentions score_samples' );
like( $out, qr/predict\b/, 'mentions predict' );
like( $out, qr/score_predict_split\b/, 'mentions score_predict_split' );
like( $out, qr/path_lengths\b/, 'mentions path_lengths' );
like( $out, qr/ops\/s/, 'has ops/s column header' );
}; ## end 'bench reports per-method ops/s' => sub
# --- 5. pack + packed predict ------------------------------------------
SKIP: {
t/91-streamd.t view on Meta::CPAN
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' );
close $c3;
is( stop_daemon($daemon), 0, 'second daemon exits 0' );
undef $daemon;
}; ## end 'clean shutdown and resume' => sub
subtest 'raw munged values that CSV could never carry' => sub {
plan skip_all => 'Algorithm::ToNumberMunger is not installed'
unless eval { require Algorithm::ToNumberMunger; 1 };
# A munged online model via a prototype, in its own model dir.
my $mdir2 = "$tmp/models2";
my $proto = "$tmp/proto.json";
( run in 1.572 second using v1.01-cache-2.11-cpan-995e09ba956 )