Skip to content

README.md

Latest commit

 

History

History
494 lines (404 loc) · 20.6 KB

README.md

File metadata and controls

494 lines (404 loc) · 20.6 KB
Raw

Algorithm::Classifier::IsolationForest

Isolation Forest (Liu, Fei Tony & Ting, Kai & Zhou, Zhi-Hua, 2008) detects anomalies by random partitioning rather than by modelling normal points. Each tree repeatedly splits the data. Points that get isolated after only a few splits are likely anomalies. The score is the average isolation depth across many trees, normalised so values approach 1 for anomalies and stay below 0.5 for normal points.

In extended mode the module implements the Extended Isolation Forest variant. Each split is a random hyperplane instead of an axis-aligned cut, which removes the rectangular, axis-aligned bias in the score field and tends to help on elongated or multi-modal data.

With voting => 'majority' the module implements the Majority Voting Isolation Forest (MVIForest, Chabchoub, Togbe, Boly & Chiky 2022): each tree votes a sample anomalous or normal against the decision threshold on its own score, predict labels the sample by the majority of the votes and stops walking trees as soon as the outcome is decided, and score_samples returns the anomaly vote fraction. Trees are built identically either way, so majority voting composes with both axis and extended mode, and an existing model can be flipped between the two modes without refitting — with the set_voting method in Perl or the iforest set_voting command on a saved model. A contamination-learned threshold does not carry across modes (it is a quantile of a different per-point quantity in each), so switching relearns it for the target mode and therefore needs the original training data.

use Algorithm::Classifier::IsolationForest;

my @data = ([0.1, -0.2], [0.0, 0.1], [5.0, 6.0], ...);

# Classic, axis-parallel Isolation Forest
my $iforest = Algorithm::Classifier::IsolationForest->new(
    n_trees     => 100,
    sample_size => 256,
    seed        => 42,
);
$iforest->fit(\@data);

my $scores = $iforest->score_samples(\@data);  # arrayref, each in (0,1]
my $flags  = $iforest->predict(\@data, 0.6);    # arrayref of 0/1

# Save and reload
$iforest->save('model.json');
my $reloaded = Algorithm::Classifier::IsolationForest->load('model.json');

# Extended Isolation Forest (oblique hyperplane splits)
my $eif = IsolationForest->new(mode => 'extended', seed => 42);
$eif->fit(\@data);

# Majority Voting Isolation Forest (per-tree votes, majority label)
my $mv = IsolationForest->new(voting => 'majority', seed => 42);
$mv->fit(\@data);
my $labels = $mv->predict(\@data, 0.6);   # threshold is the per-tree cutoff here

# Switch an existing model's aggregation without refitting. No data needed
# unless it was fit with contamination, in which case pass the training set
# so the decision threshold is recalibrated for the target mode.
$iforest->set_voting('majority', \@data);  # ->set_voting('mean') if no contamination

Explaining a score

score_samples says how anomalous a sample is; explain_samples says which features made it so. It returns one hashref per sample — the score, the method used, and every feature ordered most responsible first.

my $explanations = $iforest->explain_samples(\@data);

for my $e (@$explanations) {
    my $top = $e->{features}[0];
    printf "score %.3f, mostly because of %s (weight %.2f)\n",
        $e->{score}, $top->{name} // $top->{index}, $top->{weight};
}

Two methods, differing in what they can answer:

  • ablation :: the default. Each feature in turn is replaced by its baseline — the per-feature training-data median fit learns and saves — and the sample is re-scored; the drop is that feature's delta. It answers "would this still be an outlier with feature j at a normal value?", which has an answer for any scored sample.
  • path :: apportions credit over the splits each tree walk actually crossed (local DIFFI). Needs nothing beyond the trees, so it also serves models saved before baseline support, but it only attributes well for samples that were in the training data.

explain_sample_tagged is the hashref-in, hashref-out counterpart. ::Online implements both, using the medians of its retained window as baselines so they track drift for free.

On the command line, iforest explain prints one line per (row, feature) pair, most responsible feature first:

iforest explain -i data.csv -m model.json                # ablation, all rows
iforest explain -i data.csv -m model.json --method path
iforest explain -i data.csv -m model.json -t 0.6 -n 3    # top 3, flagged rows only

Ablation scores n_features + 1 variants of every explained row, so on a large input pass -t to spend that only on the rows that cleared the cutoff.

Training from a CSV too large to fit in RAM

fit_from_csv trains straight from a file. An Isolation Forest never looks at more than n_trees * sample_size rows, so the working set is bounded by the model's parameters rather than the file size.

my $iforest = Algorithm::Classifier::IsolationForest->new(
    n_trees       => 100,
    sample_size   => 256,
    contamination => 0.01,
    seed          => 42,
);
$iforest->fit_from_csv('huge.csv', header => 1);

The file is read in two passes — a census that counts the rows and pins the feature width, then a gather that keeps only the rows the trees sampled (chosen in bounded memory via Floyd's algorithm) — plus a third scoring pass when contamination is set, whose min-heap yields the exact threshold the in-RAM learner would have. By default the census also records each row's byte offset, so gather seeks to the sampled rows instead of rescanning; that table is dropped automatically when it would exceed index_max.

Only the cells that actually train or get scored are parsed, so $path must be a stable, re-readable file rather than a pipe. Headers are auto-detected. Mungers and tagged columns are not supported on this path — load that data through fit_tagged.

Online (streaming) Isolation Forest

For data that arrives as a stream and may drift over time, the companion class Algorithm::Classifier::IsolationForest::Online implements Online Isolation Forest (Leveni, Weigert Cassales, Pfahringer, Bifet & Boracchi 2024). There is no fit: the model learns points as they arrive and, once more than window_size points have been seen, forgets the oldest point for every new one, so the model always reflects the most recent part of the stream. Trees never store data points — nodes keep only counts and bounding boxes; leaves split by simulating points inside their box, and forgetting collapses under-populated subtrees back into leaves.

Learning and scoring both run through the same Inline::C/OpenMP backend the batch class uses. Learning executes the per-tree insert/forget walks in C against the live trees, consuming the RNG in the same order as the pure-Perl path — same seed, same trees, bit-identical, whether use_c is on or off (measured ~9-10x: a default 100-tree model goes from ~290 to ~2,600 learned points/second, and the prequential score_learn loop from ~270 to ~2,800 pts/s). Batch scoring lazily packs the mutable trees into the batch scorer's node layout, and any learn invalidates the snapshot (measured ~60x single-threaded and 250x+ with OpenMP on 100 trees x 1000+ query points). Results are identical with the accelerator on or off; only speed differs.

use Algorithm::Classifier::IsolationForest::Online;

my $oif = Algorithm::Classifier::IsolationForest::Online->new(
    n_trees          => 100,
    window_size      => 2048,   # points the model reflects; 0 = never forget
    max_leaf_samples => 32,     # points a leaf accumulates before splitting
    contamination    => 0.05,   # optional: learn the label cutoff from the window
    seed             => 42,
);

$oif->learn(\@warmup_rows);                 # warm-up / plain learning
my $scores = $oif->score_learn(\@rows);     # prequential: score, then learn, per row
my $flags  = $oif->predict(\@query_rows);   # score without learning

# After the stream drifts, refresh the contamination cutoff:
$oif->relearn_threshold;

# Persistence keeps the sliding window, so a reloaded model resumes the
# stream where it left off. load() on the parent class dispatches on the
# stored format tag, so either model type loads through either class.
$oif->save('oiforest_model.json');
my $resumed = Algorithm::Classifier::IsolationForest->load('oiforest_model.json');

On the command line the iforest stream subcommand runs the same loop over a CSV: it creates or resumes the model at -m, scores + learns each row (prequentially), prints score,label lines, and saves the updated state back — so repeated invocations continue the stream.

iforest stream -i batch1.csv -m om.json -n 100 --window 2048 --eta 32 -c 0.05
iforest stream -i batch2.csv -m om.json               # resumes om.json
iforest stream -i suspect.csv -m om.json --score-only # score without learning
iforest info -m om.json                               # online-aware model info

iforest streamd — a scoring daemon

For continuous operation, iforest streamd wraps the same prequential loop in a daemon: it listens on a Unix domain socket (default /var/run/iforest_streamd/streamd.sock, pid file alongside it), serves many concurrent connections from one shared model, and exchanges one JSON document per line (via JSON::MaybeXS) — so raw values headed for mungers may safely contain commas, newlines, or any unicode, and object rows run the full munger plan (expanding and combining mungers included, which positional CSV cannot express).

iforest streamd --prototype proto.json -c 0.05      # /var defaults
iforest streamd -f --socket /tmp/s.sock --model-dir ./models \
                --save-interval 60 --keep 48        # foreground, local paths

# Named instances: several daemons side by side, each with its own
# socket (<rundir>/<set>.sock), pid, model subdirectory, and resume state.
iforest streamd --set web
iforest streamd --set dns --prototype dns-proto.json -c 0.02
→ {"row": {"method":"GET","path":"/a,b/☃.html","host":"h"}, "tag": "req-1"}
← {"score": 0.41, "label": 0, "tag": "req-1"}
→ {"rows": [[0.2,0.7],[0.3,0.5]], "mode": "learn"}
← {"ok": {"learned": 2}}
→ {"cmd": "stats"}
← {"ok": {"seen": 48210, "window": 2048, "threshold": 0.61, "connections": 3, ...}}

The optional "tag" (any JSON value) is echoed back verbatim — on errors too, which are always per-message: a bad row gets an {"error": ...} reply and the connection lives on. Models save to --model-dir (default /var/db/iforest_streamd) as timestamped files every --save-interval seconds when learning happened (plus on the save command, SIGUSR1, and shutdown), with the symlink latest.json atomically repointed at each save and resumed from at the next startup — a crash or restart loses at most one interval of learning.

iforest streamc is the matching client — no hand-rolled JSON needed:

iforest streamc --set web -i warmup.csv --mode learn   # silent warm-up
iforest streamc --set web -i batch1.csv                # prequential: score,label lines
tail -F log | to-jsonl | iforest streamc --set web --jsonl -i - --batch 1
iforest streamc --set web --stats                      # ops: --ping/--save/--relearn-threshold
iforest streamc --set web --ping && echo healthy       # exit code driven

CSV input matches stream's (positional rows; raw strings pass through for munged columns — the daemon owns validation); --jsonl takes one JSON row per line, unlocking tagged rows and the full munger plan from the shell. Errors from either side die naming the input line.

Munging raw values (Algorithm::ToNumberMunger)

With the optional Algorithm::ToNumberMunger module installed, a model can carry a declarative munger spec that turns raw tagged values — HTTP methods, hostnames, timestamps, status codes — into the numbers the forest needs, so callers hand the model the data they actually have. The spec is pure data and is saved with the model, so a loaded model munges scoring input exactly as it did training input. Works identically on the batch and online classes.

my $forest = Algorithm::Classifier::IsolationForest->new(
    feature_names => [ 'method', 'path_len', 'host_entropy', 'bytes' ],
    mungers       => {
        method       => { munger => 'http_method_enum', default => -1 },
        path_len     => { munger => 'length',  from => 'path' },
        host_entropy => { munger => 'entropy', from => 'host' },
        # 'bytes' has no munger: raw numeric passthrough
    },
);
$forest->fit_tagged(\@raw_rows);   # hashrefs of raw values
my $score = $forest->score_sample_tagged({
    method => 'BREW', path => '/aaaa...aaa.php',
    host   => 'kq3xv9z2.biz', bytes => 60000,
});

Expanding mungers (one timestamp into a sin/cos pair) and combining mungers (a ratio of two fields) work through the tagged methods; munge_rows applies scalar mungers to positional rows. On the command line, fit/stream take --mungers spec.json (with -t tags) and accept raw values in munged CSV columns; predict and resumed stream runs munge automatically because the model carries its spec, and info shows a per-tag munger summary. Loading a munger-bearing model does not require the module — only actually using tagged data does. See the MUNGERS section in the module POD for details and caveats.

Prototypes (schema-first model creation)

A prototype is a small JSON document describing what a model should be before any data exists: the variable schema (feature names in column order, plus their munger specs, per-feature descriptions, and missing policy), a required user-owned schema_version string and free-text schema_description, and optionally the tuning knobs. Creating a model from one stamps the schema metadata into the model JSON, so iforest info, resumed streams, and your own tooling can tell which revision of the input schema a model was built against — bump schema_version when the schema changes.

{
  "format": "Algorithm::Classifier::IsolationForest::Prototype",
  "version": 1,
  "class": "online",
  "schema_version": "2026.07.08-1",
  "schema_description": "HTTP request stream: method enum, path length, host entropy, raw bytes",
  "schema": {
    "feature_names": ["method", "path_len", "host_entropy", "bytes"],
    "feature_descriptions": {
      "host_entropy": "Shannon entropy of the Host header, catches DGA-ish hostnames"
    },
    "mungers": {
      "method":       { "munger": "http_method_enum", "default": -1 },
      "path_len":     { "munger": "length",  "from": "path" },
      "host_entropy": { "munger": "entropy", "from": "host" }
    }
  },
  "params": { "n_trees": 150, "window_size": 4096, "contamination": 0.02 }
}
# One entry point for both classes; dispatches on the prototype's "class".
# Overrides merge over params (the schema itself may not be overridden).
my $oif = Algorithm::Classifier::IsolationForest->load_prototype(
    'proto.json', seed => 42 );

# And back out again -- extract a prototype from a good model to
# periodically create fresh models with an identical schema:
my $proto_json = $oif->to_prototype;
iforest fit    --prototype proto.json -i train.csv -o model.json  # batch protos
iforest stream --prototype proto.json -i batch1.csv -m om.json    # online protos
iforest proto  --from-model model.json -o proto.json              # extract
iforest proto  --check proto.json                                 # validate + summarise

Explicit tuning switches override the prototype's params; the schema comes only from the prototype (combining --prototype with -t/--mungers is refused), and unknown or machine-local param keys croak rather than silently falling back to defaults. info shows schema_version / schema_description and prints each feature's description beside its tag. See the PROTOTYPES section in the module POD for the full format.

Performance options

A handful of constructor / method-level knobs unlock measurable speedups for specific workloads. All of them are no-ops when the optional Inline::C backend is absent.

parallel_fit => N — fork-based parallel training

Builds the n_trees across N forked workers (Unix-like platforms; no-op elsewhere). Each worker gets a derived RNG seed, so parallel fits are reproducible across runs at fixed worker count — though the trees differ from a serial fit with the same seed, because the RNG draws happen in a different order. Inference results are unaffected.

my $f = Algorithm::Classifier::IsolationForest->new(
    n_trees      => 200,
    sample_size  => 256,
    seed         => 42,
    parallel_fit => 4,       # 4 forked workers
)->fit(\@training_data);

pack_data — score the same dataset many times faster

pack_data returns an opaque wrapper that the scoring methods accept directly, skipping the per-call walk over the arrayref-of-arrayrefs. Use it when the same dataset is scored repeatedly (interactive threshold tuning, dashboards, plotting that updates as parameters change).

my $packed = $f->pack_data(\@data);
my $scores = $f->score_samples($packed);
my $flags  = $f->predict($packed, 0.6);
my ($s, $l) = $f->score_predict_split($packed);  # two flat arrayrefs

score_predict_split — get scores + labels without the AV-of-AVs

When you want both anomaly scores and 0/1 labels but don't need them paired together row-by-row, score_predict_split returns the two as flat arrayrefs and skips the ~2 * n_pts SV allocations that the classic score_predict_samples shape requires.

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

Native acceleration (Inline::C, OpenMP, SIMD)

The scoring hot path (score_samples, predict, path_lengths, score_predict_samples, score_predict_split) is automatically accelerated through Inline::C when it is installed and a working C compiler is present. On top of that:

  • if the toolchain accepts -fopenmp and can link against libgomp, the per-point tree walk runs in parallel across all available CPU cores using OpenMP;
  • on OpenMP 4.0+ compilers the extended-mode oblique dot product is vectorised via #pragma omp simd — substantially faster for high-feature-count extended models.

When Inline::C is available while the distribution is being built, the C backend is compiled once during make and installed with the module — at run time it loads like any XS module, with no compiler, Inline, or _Inline/ cache directory needed. Otherwise detection happens once at module load and the build is cached under _Inline/. None of these dependencies are required: without them the module falls back to a pure-Perl implementation that produces identical results, just slower.

Check which backend is active on your machine:

iforest accel

Sample output on a host with everything wired up:

Algorithm::Classifier::IsolationForest acceleration status
  Inline::C : available
  OpenMP    : available
  SIMD      : available
  C object  : prebuilt at install time
  Build flags: -O3 -march=x86-64-v3

Active backend: Inline::C with OpenMP + SIMD -- prebuilt at install time

User code that wants to introspect the active backend can read these package variables:

$Algorithm::Classifier::IsolationForest::HAS_C       # 0/1
$Algorithm::Classifier::IsolationForest::HAS_OPENMP  # 0/1
$Algorithm::Classifier::IsolationForest::HAS_SIMD    # 0/1
$Algorithm::Classifier::IsolationForest::C_SOURCE    # 'prebuilt' / 'runtime' / ''

Install

Source

perl Makefile.PL
make
make test
make install

On x86-64 machines from roughly the last decade, configuring with

IF_ARCH=x86-64-v3 perl Makefile.PL

bakes -march=x86-64-v3 (AVX2 + FMA, no AVX-512) into the installed C backend, which can speed up extended-mode scoring — how much is hardware-dependent, so benchmark before assuming. Results stay bit-identical to the pure-Perl backend either way. See "Tuning the C build" in the module documentation for the other IF_* knobs and why -march=native is not always the better choice.

FreeBSD

pkg install p5-App-Cmd p5-File-Slurp p5-App-cpanminus \
            p5-Inline p5-Inline-C gcc
cpanm Algorithm::Classifier::IsolationForest

gcc ships with libgomp and provides the OpenMP runtime; the system clang does not by default. p5-Inline-C is what makes the C backend build (at install time, or at first module load from a plain checkout).

Debian

apt-get install libapp-cmd-perl libfile-slurp-perl cpanminus \
                libinline-c-perl gcc
cpanm Algorithm::Classifier::IsolationForest

libinline-c-perl brings in libinline-perl. gcc pulls in libgomp1 (the OpenMP runtime), which is what enables the parallel tree-walk. Both dependencies are optional — leave them out and the module installs and runs in pure-Perl mode.