Core ML2008beginner10 min read

Isolation Forest

غابة العَزْل

Liu, F. T. · Ting, K. M. · Zhou, Z.-H. — ICDM

The problem

Traditional methods build a detailed profile of "normal" data, then flag anything that deviates. This profiling approach has two critical weaknesses: it optimizes for normality rather than for anomalies, causing false alarms or missed detections; and it scales poorly — and density calculations explode in time and memory on large or high-dimensional datasets, making real-time fraud detection or network intrusion monitoring impractical.

The contribution

A fundamentally different approach: instead of profiling what is normal, explicitly isolate what is anomalous. The (iForest) builds an of random binary trees (iTrees) that recursively partition a small subsample by picking a random and a random split. Anomalies — being "few and different" — are separated in far fewer splits, producing shorter path lengths from root to leaf. The anomaly score normalizes this average against a baseline. The result is a linear-time (O(tψ log ψ) , O(nt log ψ) evaluation) with low memory that outperforms distance-based and density-based detectors, especially on large datasets.

The impact

Isolation Forest became the default unsupervised anomaly detector in scikit-learn and industry pipelines. Its insight — that anomalies are easy to isolate rather than hard to profile — inspired Extended Isolation Forest, SCiForest, and random-cut forests for streaming data. It is used at scale in fraud detection, cybersecurity, manufacturing quality control, and medical diagnostics, and remains one of the most cited anomaly detection papers with over 5,000 citations.

Imagine a crowded school playground. You're asked to find the kid who doesn't belong — say, an adult who wandered in. The traditional approach is to study every child carefully, build a profile of "typical playground kid," then find whoever doesn't match. That takes ages.

Isolation Forest flips the question: just try to point someone out. Draw random fences across the yard. The adult — taller, in different clothes, standing alone — gets fenced off in one or two cuts. But isolating any particular child from the crowd takes many fences, because they all look alike and cluster together.

The fewer fences it takes to isolate something, the more anomalous it is.

The problem: profiling normality is expensive and indirect

By 2008, the dominant approach to anomaly detection was: learn what normal data looks like, then flag deviations. Methods like DBSCAN, LOF (Local Outlier Factor), and distance-based detectors all worked this way. They had two systemic problems:

Optimized for the wrong thing. The detector learns normality, not anomalousness. If the boundary between normal and anomalous is fuzzy, the detector either floods you with false alarms (swamping) or misses real anomalies hidden among many similar outliers (masking).
Computational cost. Distance and density calculations require $O(n^2)$ pairwise comparisons. On a dataset of 500,000 network packets, the distance-based detector ORCA took over 9,000 seconds. Real-time detection was out of reach.

How isolation works: random cuts on random features

An Isolation Tree (iTree) works like this: take a small random subsample of your data (typically 256 points). Pick a feature at random. Pick a random split value between that feature's min and max. Points below the split go left; points above go right. Repeat recursively until every point is alone in its own leaf — or until you hit a height limit.

This produces a binary tree where each point's path length — the number of edges from root to its leaf — tells you how hard it was to isolate. An anomaly, sitting far from the crowd with unusual feature values, gets split away early: short path. A normal point, buried in a dense cluster of similar points, needs many splits to be singled out: long path.

One tree is noisy — the random splits might be unlucky. So we build a forest of 100 trees (each from a different subsample) and average the path lengths. The average converges quickly, and the ranking of anomaly vs. normal stabilizes.

Open in Lab

Click "Build Tree" to watch random splits isolate the anomaly (red) in few cuts while normal points (blue) need many more.

The demo wakes as you arrive…

The algorithm: training and evaluation

The iForest algorithm has just two parameters: the number of trees $t$ (default 100) and the sub-sampling size $\psi$ (default 256). The algorithm runs in two stages:

Training stage: For each of the $t$ trees, randomly draw $\psi$ points without replacement. Set the height limit $l = \lceil \log_2 \psi \rceil$ (approximately the average tree height). Build an iTree by recursively choosing a random feature $q$ and a random split point $p$ between the min and max of $q$ in the current subset. Points where $q < p$ go left; the rest go right. Stop when a has one point, all points are identical, or the height limit is reached.

Evaluation stage: Pass each test point through every iTree. Count the edges from root to termination leaf — that is $h(x)$ . If the point reaches an external node that still contains multiple points (because we hit the height limit), add an adjustment $c(\text{Size})$ that estimates the subtree depth that would have been needed. Average $h(x)$ over all trees to get $E[h(x)]$ , then compute the anomaly score.

Open in Lab

Step through the two stages of iForest: build trees from subsamples, then evaluate path lengths and compute anomaly scores.

The demo wakes as you arrive…

The anomaly score: from path length to a number between 0 and 1

Raw path lengths are hard to compare across different dataset sizes. A path of 8 in a 256-point sample means something different than 8 in a 1024-point sample. We need a baseline.

The key observation: an iTree has the same structure as a Binary Search Tree (BST). External-node termination in an iTree corresponds to an unsuccessful search in a BST. So we can borrow the well-known formula for the average path length of an unsuccessful BST search as our normalizer.

c(n) = 2H(n-1) - \frac{2(n-1)}{n}

Average path length of unsuccessful BST search — our normalization baseline — H(i) is the harmonic number ≈ ln(i) + 0.5772 (Euler's constant). c(n) grows as O(log n), giving us a scale-independent reference path length.

With this normalizer, the anomaly score $s$ for a point $x$ is defined as:

s(x, n) = 2^{-\frac{E[h(x)]}{c(n)}}

The iForest anomaly score — E[h(x)] is the average path length across all trees. When E[h(x)] → 0, score → 1 (definite anomaly). When E[h(x)] → c(n), score → 0.5 (no clear signal). When E[h(x)] → n−1, score → 0 (definitely normal).

Think of the score as a thermometer for strangeness: the closer to 1, the hotter (more anomalous). At 0.5, the thermometer reads "room temperature" — nothing unusual. Below 0.5, you're looking at a thoroughly normal point.

Open in Lab

Drag the slider to change the average path length and watch the anomaly score respond. Notice how score = 0.5 is the "no information" midpoint.

The demo wakes as you arrive…

Why subsampling helps: less data, better detection

This is perhaps the most counterintuitive property of Isolation Forest. In most methods, more data is better. Here, actually improves detection. Why?

When you use the full dataset, normal points crowd around anomalies, making it harder to isolate them (swamping). Dense anomaly clusters blend in with normal clusters (masking). But with a small subsample of 256 points, the crowd thins out: the normal points surrounding anomalies are cleared away, and anomaly clusters shrink to a handful of points that stand out clearly.

Liu et al. demonstrated this dramatically: on the Mulcross dataset with 4096 points, using the full sample gave = 0.67. Using a subsample of just 128 points? AUC jumped to 0.91. The less-data version was far better at detecting anomalies.

Open in Lab

Toggle between the full sample and a small subsample. Notice how anomalies become clearly separable when the crowd thins out.

The demo wakes as you arrive…

The algorithm in code

Isolation Forest — complete implementationpython

Simplified to show the idea — not the real implementation.

import numpy as np

def c(n):
    """Average path length of unsuccessful BST search (normalizer)."""
    if n <= 1: return 0
    if n == 2: return 1
    H = np.log(n - 1) + 0.5772156649   # harmonic number approx.
    return 2 * H - 2 * (n - 1) / n

class ITree:
    """One isolation tree: recursively split until isolated."""
    def __init__(self, X, height=0, limit=8):
        self.n = len(X)
        if height >= limit or self.n <= 1:
            self.is_leaf = True
        else:
            self.is_leaf = False
            q = np.random.randint(X.shape[1])       # random feature
            lo, hi = X[:, q].min(), X[:, q].max()
            self.split_val = np.random.uniform(lo, hi)
            self.split_att = q
            left_mask = X[:, q] < self.split_val
            self.left  = ITree(X[left_mask],  height + 1, limit)
            self.right = ITree(X[~left_mask], height + 1, limit)

    def path_length(self, x, e=0):
        if self.is_leaf:
            return e + c(self.n)            # adjustment for unbuilt subtree
        if x[self.split_att] < self.split_val:
            return self.left.path_length(x, e + 1)
        return self.right.path_length(x, e + 1)

def iforest_scores(X, t=100, psi=256):
    """Build t trees on subsamples of size psi, return anomaly scores."""
    trees = []
    limit = int(np.ceil(np.log2(psi)))
    for _ in range(t):
        idx = np.random.choice(len(X), size=min(psi, len(X)), replace=False)
        trees.append(ITree(X[idx], limit=limit))

    scores = np.zeros(len(X))
    for i, x in enumerate(X):
        avg_h = np.mean([tree.path_length(x) for tree in trees])
        scores[i] = 2 ** (-avg_h / c(psi))   # anomaly score
    return scores

# Usage: scores close to 1 → anomaly, close to 0.5 → normal

Performance and efficiency

iForest has a training complexity of $O(t\psi \log \psi)$ and an evaluation complexity of $O(nt \log \psi)$ , where $n$ is the test set size. Since $\psi$ and $t$ are small constants (256 and 100), both stages are effectively linear in $n$ .

On the Http dataset (567,497 instances), iForest finished in 15.6 seconds total — while ORCA took 9,487 seconds. That's a 600× speedup. On the same dataset, iForest achieved AUC = 1.00 versus ORCA's 0.36.

Memory is equally frugal. With $\psi = 256$ , each tree has at most 511 nodes. With 100 trees, the entire fits in a few hundred kilobytes — small enough for embedded systems or real-time monitoring agents.

Open in Lab

Compare iForest's AUC and runtime against ORCA and LOF across benchmark datasets. Notice the dramatic gap on large datasets.

The demo wakes as you arrive…

Fast convergence: a few trees are enough

One of the practical strengths of iForest is that AUC stabilizes with very few trees. The paper showed that detection performance converges well before $t = 100$ on all tested datasets. Similarly, performance is near-optimal at $\psi = 256$ , which is a tiny fraction of the original data (less than 0.05% of a 500K dataset). Increasing $\psi$ beyond 256 adds processing time without improving AUC.

This means you can confidently use the defaults: 100 trees, subsample size 256. The algorithm is remarkably insensitive to tuning — a rare luxury in machine learning.

Isolation vs. profiling: a paradigm shift

The table below captures the conceptual difference between the two paradigms:

Traditional detectors (LOF, ORCA, DBSCAN) build a model of what is normal, then measure how much each point deviates. This requires computing distances or densities between all pairs — $O(n^2)$ work. Isolation Forest never computes a distance. It uses random partitions — $O(\log n)$ per point per tree — and asks a simpler question: "how quickly can I separate this point?"

This also means iForest is naturally robust to irrelevant features. In high-dimensional spaces where distance-based methods suffer from the curse of dimensionality (all points become equidistant), iForest's random feature selection automatically focuses on the informative dimensions. Adding a Kurtosis-based feature selector further improves performance, letting iForest handle datasets with 500+ irrelevant dimensions.

Open in Lab

Left: iForest isolates the anomaly with a few random splits. Right: a distance method must compute distances to all other points.

The demo wakes as you arrive…

Why it mattered

2008
Isolation Forest (iForest)
The original paper introduced isolation-based anomaly detection with linear time complexity and sub-sampling. Published at ICDM.
2010
SCiForest
Extended iForest to handle clustered anomalies by using hyperplane splits instead of axis-aligned ones.
2012
Isolation-Based Anomaly Detection (TKDD)
The extended journal version with deeper theoretical analysis and additional experiments. Published in ACM TKDD.
2018
Extended Isolation Forest (EIF)
Replaced axis-aligned splits with random hyperplane splits, eliminating ghost clusters and bias artifacts in the anomaly score contours.
2020
Random Cut Forest (streaming)
Amazon adapted the isolation idea for streaming data, enabling real-time anomaly detection in AWS services like Kinesis Analytics.

CitationLiu, Ting, Zhou. Isolation Forest. ICDM, 2008.

Terms in this paper

Anomaly Detectionكشف الشذوذ
Isolation Forestغابة العَزْل
Outlier Detectionرصد القيم الشاذة
Decision Treeشجرة القرار الإحصائية
Random Forestالغابة العشوائية خوارزمية
Binary Search Treeشجرة البحث الثنائية
Path Lengthطول المسار
subsamplingالتقليص المكاني
Ensembleالنماذج التجميعية الهجينة
Unsupervised Learningالتعلّم غير الخاضع للإشراف