Extended isolation forest, read closely

Most outlier detectors ask a density question: how far is this point from its neighbours, how unlikely under the fitted distribution? Isolation Forest (Liu, Ting & Zhou, 2008) flips it into a question about separation. Grow a binary tree by repeatedly slicing the data with a random cut. A point buried in a dense cluster needs many cuts before it sits alone in its own cell; a point out on its own gets isolated almost immediately. So the depth at which a point becomes alone — its path length — is a ready-made anomaly signal, and it costs no distance computations and no density estimate at all.

Average that depth over a forest of random trees, normalise it, and you have a score. The normaliser c(n) is the expected path length of an unsuccessful search in a random binary tree — it is what a “typical” depth looks like for n points, so dividing by it makes the score scale-free. The final score lives in (0, 1): near 1 means “isolated far too fast — anomalous”, near 0.5 means “ordinary.”

import math
EULER = 0.5772156649

def c(n):                       # avg path length of an unsuccessful BST search
    if n <= 1: return 0.0
    if n == 2: return 1.0
    return 2 * (math.log(n - 1) + EULER) - 2 * (n - 1) / n

def anomaly_score(x, forest, psi):
    total = 0.0                               # expected depth to isolate x
    for tree in forest:
        total += path_length(x, tree)
    h = total / len(forest)
    return 2 ** (-h / c(psi))    # in (0,1): short path -> score near 1 -> anomalous

That is the whole scoring rule, and every number in the maps below comes out of it. The site runs the TypeScript; the Python and C++ are line-for-line translations. This is the same random-tree ensemble idea behind the random forest page — only here the trees are unsupervised and we read their depth, not their votes.

Everything rides on how you draw a single cut. Standard Isolation Forest does the simplest thing imaginable: pick one coordinate at random, pick a random threshold inside that coordinate's range, and split. The boundary is always axis-parallel — a horizontal or vertical line in 2D, an axis-aligned plane in higher dimensions. Exactly like a split on the decision tree page, except chosen at random rather than to reduce impurity.

The Extended Isolation Forest changes one thing. Instead of an axis and a threshold, draw a random direction — a normal vector with each component sampled from a Gaussian — and a random point for the plane to pass through. Now the boundary is a tilted hyperplane, free to face any way it likes.

import numpy as np

def standard_cut(pts):               # Isolation Forest: split on ONE axis
    d  = np.random.randint(pts.shape[1])           # pick a coordinate
    lo, hi = pts[:, d].min(), pts[:, d].max()
    p  = np.random.uniform(lo, hi)                 # threshold within its range
    return lambda x: x[d] <= p                     # boundary is axis-parallel

def extended_cut(pts):               # Extended Isolation Forest: split on a random SLOPE
    n = np.random.normal(size=pts.shape[1])        # a random direction, not an axis
    p = np.random.uniform(pts.min(0), pts.max(0))  # a random point to pass through
    return lambda x: np.dot(x - p, n) <= 0         # boundary is a tilted hyperplane

Here is the thing a skim misses. Take the friendliest possible data: a single round Gaussian blob, centred, symmetric in every direction. Whatever the anomaly score means, it ought to depend only on how far a point is from the centre — the map should be a set of clean concentric rings. We fit a standard forest and colour the whole plane by its score.

Why does it happen? An axis-parallel cut can only carve out rectangles. A point sitting far out along the x-axis shares its x-band with the whole spread of the blob, so a vertical cut rarely isolates it quickly; it takes extra depth to fence off, and extra depth reads as less anomalous. The forest cannot express “far in a diagonal direction” cleanly, so it leaks the coordinate frame into the score. Swap in tilted cuts and the leak stops:

“Looks rounder” is not evidence. So we make the bias a number. Walk a circle of fixed radius around the centre of the symmetric blob and read the score at each angle. For a truly isotropic detector this profile is a flat line — every direction is equally ordinary. The standard forest ripples; the extended one is nearly flat.

The single blob is the gentle case. The bias turns pathological with structure. Put two blobs side by side. The axis-parallel forest builds long rectangular bands spanning both clusters, and where those bands overlap it manufactures a ghost cluster: a pocket of low anomaly score in the empty space between and around the two blobs, where no data lives at all. An anomaly parked in that pocket would be scored as perfectly normal.

Here is where a careful read pays off. A prettier score map is not the same as better detection. Most benchmarks score a detector by AUROC — the probability it ranks a random true anomaly above a random normal point — and ranking only cares about theorder of scores, not their exact surface. If the real anomalies do not happen to sit in the phantom corridors, fixing the corridors changes the ranking very little.

We test it on a seeded scene: a dense central blob of inliers plus a scatter of uniform background anomalies, scored by both forests. On this data both are already strong, and the tilt helps only a little.

The paper's own benchmark numbers tell the same nuanced story. On real datasets the extension helps most where the data is elongated or multi-cluster (ForestCover jumps from 0.81 to 0.92), and barely moves where it is already compact (Mammography, 0.859 to 0.862):

There is a lovely irony here, and it connects two posts on this site. Our tabular-data walkthrough argued that a tree's obsession with the coordinate axes is a virtue: real tabular features are individually meaningful, and rotating them into a mush is what kills neural nets on tables. Here the very same axis-alignment is a vice: the geometry of an anomaly has no reason to respect your columns, so baking the axes into the score is a bug, and EIF's fix is precisely to make the model rotation-invariant again.

Both are true. The axis bias helps when the axes carry the signal and hurts when they don't — the same inductive bias, read as a feature or a bug depending on the task. That is the whole game of choosing a model.

• Where do the corridors actually catch anomalies? Inject outliers specifically into the phantom low-score corridors and re-measure AUROC. That isolates exactly how much of the paper's benchmark gain comes from repairing the bias versus from other effects.
• Intermediate extension levels. We ran only the two extremes. In higher dimensions the dial between them trades off some axis-alignment for some obliqueness — and the sweet spot may not be “fully tilted,” especially on genuinely tabular data where a few axes really do matter.
• Contamination and thresholds. AUROC ignores where you cut the score. The bias distorts the surface most, so its practical cost should be largest when you must pick an operating threshold — a fraud team's real constraint. Sweeping precision at fixed recall would show it.

Isolation Forest is a small marvel: no distances, no density, just the observation that weird things are easy to fence off. This paper's contribution is to notice that the fence was always drawn on graph paper, and to let it tilt. Go build the random ensembles on the forest page and picture reading their depth instead of their votes — then imagine every cut free to face any direction it likes.