Isolation Forest Anomaly Score

Background

Isolation Forest is a tree-based anomaly detector: random partitions isolate anomalies in shorter path lengths than normal points. The anomaly score is the average path length, normalised by the expected path length under a binary search tree on $n$ leaves. Standard tabular fraud / outlier baseline.

Problem statement

Implement isolation_score(x, X, n_trees=50, sample_size=64, seed=0):

1. Build n_trees isolation trees on i.i.d. subsamples of size sample_size from X.
2. Each tree: random feature, random split in $[\min, \max]$, recurse; track path length to isolate x.
3. Average path length $\bar h$ across trees. Normalise:

$$c(n) = 2\bigl(\ln(n - 1) + 0.5772156649\bigr) - \tfrac{2(n-1)}{n},\qquad \text{score} = 2^{-\bar h / c(n)}$$

Score near $1$ = anomaly; score near $0.5$ = normal.

Input

• x — 1-D np.ndarray of length $d$.
• X — 2-D np.ndarray shape $(N, d)$, the training data.
• n_trees — int, number of trees (default 50).
• sample_size — int, subsample size per tree (default 64).
• seed — int, RNG seed.

Output

Returns a Python float in $[0, 1]$.

Examples

Example 1 — outlier has higher score than inlier

Input:  X ~ N(0, 1) (200 rows, 2 dim); compare x=0 vs x=10
Output: score(x=10) > score(x=0)

Example 2 — bounded in [0, 1]

Input:  any valid query against any data
Output: 0.0 <= score <= 1.0

Example 3 — reproducible

Input:  same seed
Output: identical score across calls

Constraints

• sample_size is capped at len(X).
• Recursion depth capped at $\lceil \log_2(\max(n, 2)) \rceil$ to avoid infinite splits on constant features.
• Returns Python float.

Notes

• Subsample size matters. The published default is $256$; smaller subsamples isolate anomalies faster but are noisier. $64$ is a reasonable interview-grade default.
• Multivariate vs univariate. This is the classic axis-aligned version. Extended IsoForest uses random hyperplane splits — better for high-dim correlated features.