iforest.nu

iforest — Isolation Forest anomaly detection for NURL.

An Isolation Forest (Liu, Ting & Zhou, 2008) detects anomalies by isolating points rather than profiling normal data. It builds an ensemble of random binary trees (iTrees); each tree repeatedly splits a random feature at a random threshold until every point is isolated. Anomalies — being few and different — sit in sparse regions and get isolated near the root, so their average path length over the forest is short. The score maps that path length to (0, 1]:

s(x) = 2 ^ ( -E[h(x)] / c(psi) )

≈ 1.0 almost certainly an anomaly (isolated very quickly) ≈ 0.5 no clear signal (path length ≈ the average) < 0.5 deep in the tree — a normal, "crowded" point

where E[h(x)] is the mean path length of x across the trees and c(psi) is the expected path length of an unsuccessful BST search over a subsample of size psi (the normalising constant).

This package lives in the NURL registry (it is NOT part of the core stdlib). It is pure NURL: a seedable PRNG (std/rng) drives the random splits, so a fixed seed gives a byte-identical forest on every platform.

Surface: ( iforest_train data n_rows n_cols n_trees sample_size seed ) → IForest data is a row-major ( Vec f ) of n_rows*n_cols values. Returns a trained forest (caller owns it → iforest_free). ( iforest_score forest point ) → f anomaly score in (0, 1] for a ( Vec f ) of length n_cols. ( iforest_score_row forest data row ) → f score row row of a row-major ( Vec f ) matrix. ( iforest_avg_path n ) → f c(n), exported for thresholding. ( iforest_n_trees f ) / ( iforest_sample_size f ) → i accessors. ( iforest_free forest ) → v

The trees are stored as a flat struct-of-arrays shared across the whole forest (one node arena, a root index per tree): no recursive ADTs, no Vec-of-Vec, and scoring walks raw pointers for speed.

API

: f GAMMA 0.5772156649015329

Euler–Mascheroni constant, for the harmonic-number approximation in c(n).

: IForest

: IForest {
    i n_trees
    i sample_size       // psi — points subsampled per tree (clamped to n_rows)
    f c_psi             // c(psi): path-length normaliser, precomputed
    i n_cols            // dimensionality of a point
    ( Vec i ) roots     // roots[t] = node index of tree t's root
    ( Vec i ) feature   // split feature, or -1 at a leaf
    ( Vec f ) split     // split threshold (internal nodes only)
    ( Vec i ) left      // left child index, or -1
    ( Vec i ) right     // right child index, or -1
    ( Vec i ) size      // subsample size that reached this node
}

@ iforest_avg_path i n → f

── Path-length normaliser c(n) ───────────────────────────────────────

c(n) = 2H(n-1) - 2(n-1)/n, the average path length of an unsuccessful search in a binary search tree of n nodes, with H(i) ≈ ln(i) + γ. This is both the per-leaf adjustment for the unbuilt subtree below a depth cap and the forest-wide normaliser c(psi).

@ iforest_train ( Vec f ) data i n_rows i n_cols i n_trees i sample_size i seed → IForest

@ iforest_score IForest fo ( Vec f ) point → f

Anomaly score in (0, 1] for a single point given as a ( Vec f ) of length n_cols. Higher = more anomalous.

@ iforest_score_row IForest fo ( Vec f ) data i row → f

Score row row of a row-major ( Vec f ) matrix without copying it out.

@ iforest_n_trees IForest fo → i

@ iforest_sample_size IForest fo → i

@ iforest_free IForest fo → v

---

main.nu

iforest — score the rows of a numeric CSV for anomalousness.

Reads a numeric CSV (rows = samples, columns = features) from stdin or a file, trains an Isolation Forest, and prints an anomaly score in (0, 1] for each row — higher means more anomalous. By default one score per line, in input order (paste it back as a new column); with --top K it prints the K most anomalous rows as index<TAB>score, highest first.

iforest < data.csv # one score per row iforest -f data.csv --top 10 # 10 most anomalous rows iforest -f data.csv -H -t 200 -S 7 # skip header, 200 trees, seed 7

Built on the argz registry package (flags) and this package's own iforest library.

API

: Dataset

: Dataset {
    ( Vec f ) data
    i rows
    i cols
}

A parsed numeric matrix: data is row-major (rows*cols), owned by caller.

: ScoreRow

: ScoreRow {
    i row
    f score
}

One row's score, for the --top ranking. NB: the index field is row, not idx — a field named idx would collide with the generic vec.nu helpers' own idx parameter, so . data idx inside vec_get[ScoreRow] would resolve as a field access instead of an array index.

@ main → i