Isolation forest

Overview

The task is to flag unusual points in unlabelled data. The method does not need labels; the paper defines the problem for vectors, time series and graphs alike 2206.06602 §3. Every variant shares one idea: grow random partitions of the data, and treat a point that is cut off after few steps as anomalous. Classic isolation forest counts the path length to isolate a point 2206.06602 §4. The variants differ in what they cut and how they turn the path into a score.

The original isolation forest paper has no card in this wiki. Its method is described here as the Deep Isolation Forest paper describes it 2206.06602 §4; the original paper is cited there as Liu et al. (2008).

Variants

Classic isolation forest (iForest)

Each tree cuts on one feature at a time, at random. A point's score comes from how few cuts isolate it, so an outlier along single axes is cut off quickly 2206.06602 §4. The paper names two failures 2206.06602 §1:

• Hard anomalies. Points that differ from normal data only in a combination of features are isolated no faster than normal points. The paper illustrates this with a ring of normal points around a few anomalies 2206.06602 §1 fig. 1.
• Ghost regions. Empty space next to normal data can get low scores. The paper shows this on three 2-D synthetic sets 2206.06602 §1 fig. 2.

The paper's comparison uses 300 iForest trees, each on a subsample of 256 points 2206.06602 §6.1.3.

Extended isolation forest (EIF)

EIF, by Hariri et al. (2019), replaces the single-feature cut with a random hyperplane 2206.06602 §5.4.2. The paper groups EIF with other extensions that still use linear partitions or heuristic axis choices, and argues that these keep both failures above 2206.06602 §1 2206.06602 §2.2. The paper reports EIF as the strongest isolation baseline on its tabular sets, with AUC-ROC 0.888 and AUC-PR 0.219 on average 2206.06602 tab. 3. EIF has no card here; these numbers are the Deep Isolation Forest paper's own measurements.

Deep Isolation Forest (DIF)

DIF keeps the random cuts but applies them to several random, untrained neural representations of the data 2206.06602 §5.1. The paper uses 50 representations and 6 trees on each, so 300 trees in total [arxiv:2206.06602 §5.1] 2206.06602 §6.1.3. Each tree cuts a random dimension at a uniform random value between that dimension's minimum and maximum [arxiv:2206.06602 alg. 1]. The score combines the path depth with a deviation term: how far the point sits from the cuts on its path 2206.06602 §5.2.2 [arxiv:2206.06602 eq. 8]. The representations are never trained, so DIF has no gradient steps 2206.06602 §5.1.

The paper's ensemble trick, CERE, shares one base weight matrix across members and gives each a pair of random vectors 2206.06602 §5.2.1. On the ten tabular sets, the paper reports total time of 128.7 s with CERE against 950.6 s for a sequential ensemble 2206.06602 tab. 6. Card: Deep Isolation Forest for Anomaly Detection.

When to use which

DIF's gain over classic iForest rests on the paper's own experiments on ten tabular sets 2206.06602 tab. 3. Its ablation shows the deviation term adds to the depth-only score: AUC-ROC 0.925 against 0.920 without it, and AUC-PR 0.351 against 0.318 2206.06602 tab. 6. The authors report p-values of 0.07 for AUC-ROC and 0.03 for AUC-PR for that comparison 2206.06602 §6.6.

Implementation sketch

The common core is one tree per random subsample and a score from path depth. Variants differ in the cut (DIF: applied to a random representation; EIF: a hyperplane) and in the deviation term.

# Build one isolation tree on a subsample  [arxiv:2206.06602 alg. 1] [§5.1]
# Input:  points (m, d); depth limit J
# Output: tree whose internal nodes hold a dimension and a threshold

def build_tree(points, depth_limit):
    # a node is a leaf at one point or when the depth limit is reached [alg. 1]
    if len(points) <= 1 or depth_limit == 0:
        return leaf(size=len(points))
    # pick one dimension uniformly at random  [§5.1]
    dim = random_index(points.shape[1])
    # pick a threshold uniformly between that dimension's min and max  [alg. 1]
    threshold = uniform(min(points[:, dim]), max(points[:, dim]))
    # values at or below the threshold go left  [§5.1]
    left = points[points[:, dim] <= threshold]
    right = points[points[:, dim] > threshold]
    return node(dim, threshold,
                build_tree(left, depth_limit - 1),
                build_tree(right, depth_limit - 1))

# Score one point: a shorter average path means more anomalous
# [arxiv:2206.06602 §5.2.2] [eq. 8]
# Input:  point x, forest of trees, normaliser C
# Output: score (higher = more anomalous)

def path_score(x, forest, normaliser):
    # count the splits each tree passes before reaching a leaf  [eq. 7-8]
    depths = [len(walk(tree, x)) for tree in forest]
    # 2 to the minus mean depth over the normaliser  [eq. 8]
    return 2 ** (-mean(depths) / normaliser)

The paper leaves the normaliser C(T) undefined 2206.06602 eq. 8. Deep Isolation Forest also multiplies in a deviation term and builds each tree on a random representation 2206.06602 §5.2.2. The released code differs from eq. 8 in how it aggregates scores and in its normaliser; see the card's "Paper vs code" section before you reimplement.

Contradictions

None known between papers: one card cites this slug. Within the Deep Isolation Forest paper, eq. 8 and its released code aggregate the scores differently 2206.06602 §5.2.2 2206.06602 eq. 8. See the card for the full list of differences.

Papers

• Deep Isolation Forest for Anomaly Detection: replaces raw-feature cuts with cuts on random untrained representations, and adds a deviation term to the path score. Author-reported gains on tabular, graph and time-series sets.