Isolation Forest

Anomalies are few and different, so random splits isolate them in fewer steps; a short average path length means anomaly.

17 min read1988 wordscore0 viewsupdated 2026-10-08

Definition

An isolation forest (Liu, Ting & Zhou, 2008) detects anomalies without modelling what normal data looks like. It builds many isolation trees. Each one splits a small random subsample using a random feature and a random threshold, and keeps going until every point sits alone in a leaf. A point that ends up alone after only a few cuts is suspicious. The anomaly score is the average depth at which a point gets isolated, rescaled to lie between 0 and 1.

At a glance

Task
Unsupervised anomaly (outlier) detection; also used for novelty detection on new data
Input → output
points x1,…,xnx_1,\dots,x_n (no labels) → a score s(x)∈(0,1)s(x)\in(0,1) per point; higher means more anomalous
Learns
tt random binary trees, each grown on a subsample of ψ\psi points. Nothing is fitted: every split is random
Training
O(t ψlog⁡ψ)O(t\,\psi\log\psi), which does not depend on nn once the subsamples are drawn
Scoring
O(tlog⁡ψ)O(t\log\psi) per point: one root-to-leaf walk per tree
Hyperparameters
number of trees tt (100), subsample size ψ\psi (256), height limit ⌈log⁡2ψ⌉\lceil\log_2\psi\rceil, and the threshold or contamination
Assumes
anomalies are few and different: they sit in sparse regions, away from the bulk of the data along at least some features

The problem

Most outlier detectors first describe what normal data looks like and then flag whatever does not fit. A Gaussian fits a mean and covariance, LOF and k-NN methods compare distances to neighbours, and a one-class SVM fits a boundary around the bulk. All of them spend their effort on the normal points, which are the vast majority. Distance-based methods also cost O(n2)O(n^2), and their distances become less informative as dimensions are added.

Isolation Forest turns the question around. Instead of asking how normal is this point?, it asks how easy is it to separate this point from all the others? Imagine cutting a scatter plot with random straight lines parallel to the axes. A lone point far from the crowd gets fenced off by the first lucky cut. A point deep in a dense cluster has neighbours on every side, so it takes many cuts before it is alone. Counting the cuts gives a score, with no distances and no density estimate.

Isolation trees

iTree(S, d): grow one isolation tree

  1. 1Stop? If ∣S∣≤1|S|\le1, or the depth dd has reached the height limit ℓ\ell, or all points in SS are identical, return a leaf that remembers its size ∣S∣|S|.
  2. 2Pick a feature qq uniformly at random among the features that vary within SS.
  3. 3Pick a threshold pp uniformly at random between min⁡x∈Sxq\min_{x\in S}x_q and max⁡x∈Sxq\max_{x\in S}x_q.
  4. 4Split into L={x∈S:xq≤p}L=\{x\in S: x_q\le p\} and R=S∖LR=S\setminus L, and recurse: iTree(L,d+1)\text{iTree}(L,d+1), iTree(R,d+1)\text{iTree}(R,d+1).

No split is optimised. Unlike a decision tree, which searches every threshold for the purest split, an isolation tree draws both the feature and the threshold blindly. That makes it extremely cheap, and it is the reason the depth of a leaf carries information: only the shape of the data decides where random cuts tend to separate points.

The maths

Path length. Drop a point xx down a tree, following the same rule at every node. The number of edges it crosses before reaching a leaf is its path length.

h(x)=e(x)+c(m(x))h(x)=e(x)+c\big(m(x)\big)
h(x)h(x)
path length of x in one tree
e(x)e(x)
number of edges from the root to the leaf that x lands in, i.e. the leaf's depth
m(x)m(x)
number of training points in that leaf (1 if xx was isolated)
c(m)c(m)
expected extra depth needed to isolate mm points, defined below; c(1)=0c(1)=0

The correction c(m)c(m) is needed because of the height limit. A leaf that stopped at depth ℓ\ell with m>1m>1 points still unseparated would have needed more cuts. Instead of growing that subtree, we add the number of cuts it would need on average.

How deep is a typical point? To decide whether h(x)h(x) is short, we need a reference value: the average leaf depth of a fully grown tree on nn points. An isolation tree on nn distinct points has nn leaves and n−1n-1 internal nodes, which is the same structure as a binary search tree with n−1n-1 keys whose nn empty slots are the leaves. So the reference is the average depth of an unsuccessful search in a random BST. We derive it by assuming the root split sends kk points left and n−kn-k right, with kk equally likely to be any of 1,…,n−11,\dots,n-1.

Deriving c(n)

  1. 1Let E(n)E(n) be the expected sum of leaf depths of a tree that isolates nn points, so the average is c(n)=E(n)/nc(n)=E(n)/n. Clearly E(1)=0E(1)=0.
  2. 2The root split adds 1 to the depth of all nn leaves, and then the two sides are independent trees on kk and n−kn-k points: E(n)=n+1n−1∑k=1n−1[E(k)+E(n−k)]E(n)=n+\frac{1}{n-1}\sum_{k=1}^{n-1}\big[E(k)+E(n-k)\big].
  3. 3Check small cases. E(2)=2+11[0+0]=2E(2)=2+\tfrac11[0+0]=2, so c(2)=1c(2)=1 (one cut separates two points). E(3)=3+12[(0+2)+(2+0)]=5E(3)=3+\tfrac12[(0+2)+(2+0)]=5, so c(3)=53≈1.667c(3)=\tfrac53\approx1.667. E(4)=4+13⋅2(0+2+5)=8.667E(4)=4+\tfrac13\cdot2(0+2+5)=8.667, so c(4)≈2.167c(4)\approx2.167.
  4. 4Solving the recurrence (the textbook result for random BSTs) gives the closed form below. Plug in n=3n=3: 2(1+12)−43=1.6672(1+\tfrac12)-\tfrac43=1.667, which matches.
c(n)=2H(n−1)−2(n−1)n,H(i)≈ln⁡i+γc(n)=2H(n-1)-\frac{2(n-1)}{n},\qquad H(i)\approx\ln i+\gamma
c(n)c(n)
average path length of an unsuccessful search in a BST built from nn points; used as the "typical depth" for a tree grown on nn points. c(1)=0c(1)=0, c(2)=1c(2)=1
H(i)H(i)
the ii-th harmonic number 1+12+⋯+1i1+\tfrac12+\dots+\tfrac1i
γ\gamma
Euler's constant, 0.5772…

c(n)c(n) grows like 2ln⁡n2\ln n, so typical paths are logarithmic in the sample size. The paper and scikit-learn replace H(i)H(i) by ln⁡i+γ\ln i+\gamma for n>2n>2. That approximation is excellent for large nn, with c(256)=10.245c(256)=10.245 against the exact 10.24910.249, but rough for tiny leaves: it gives c(3)=1.207c(3)=1.207 instead of 1.6671.667. The worked example below uses the approximation so that its numbers match scikit-learn.

The score. Average the path lengths over all trees, then compare the average with c(ψ)c(\psi), the typical depth for the subsample size each tree was grown on:

s(x,ψ)=2− E[h(x)] / c(ψ)s(x,\psi)=2^{-\,\mathbb{E}[h(x)]\,/\,c(\psi)}
s(x,ψ)s(x,\psi)
anomaly score of x, between 0 and 1
E[h(x)]\mathbb{E}[h(x)]
mean path length of xx over the tt trees, i.e. 1t∑i=1thi(x)\tfrac1t\sum_{i=1}^{t}h_i(x)
ψ\psi
subsample size used to grow each tree
c(ψ)c(\psi)
normaliser: the average path length expected for a tree on ψ points

Reading the score

$\mathbb{E}[h]\to0$
s→1s\to1: the point is isolated almost immediately. Clear anomaly.
$\mathbb{E}[h]=c(\psi)$
s=2−1=0.5s=2^{-1}=0.5: the point is exactly as hard to isolate as an average point. If every point scores about 0.5, the data has no distinct anomalies.
$\mathbb{E}[h]\to\psi-1$
s→0s\to0: the point needs the maximum number of cuts. Clearly normal, deep inside a dense region.

The exponential form makes scores comparable across subsample sizes, because dividing by c(ψ)c(\psi) removes the log⁡ψ\log\psi growth of path lengths. Using base 2 puts the "average point" at exactly 0.5. Only the ranking of scores is fundamental. The 0.5 cut-off is a convention, and in practice the threshold is set from an expected anomaly rate.

Subsampling. Each tree sees only ψ\psi points, drawn without replacement (default ψ=256\psi=256, a value the paper found to work across many datasets). This is not just a speed trick. With the full data, a dense group of anomalies can protect its members from being isolated (masking), and normal points close to many anomalies get isolated early (swamping). A small subsample thins out both effects. It also makes training cost independent of nn.

Height limit. Trees stop growing at depth ℓ=⌈log⁡2ψ⌉\ell=\lceil\log_2\psi\rceil, about the average height of a random tree on ψ\psi points (8 for ψ=256\psi=256). We only care whether a point's path is short, and anything deeper than average is "normal enough". Leaves cut off at the limit get the c(m)c(m) correction, so their path lengths are still estimated rather than truncated. This keeps every tree at no more than 2ℓ2^\ell leaves.

Worked example: ten points and a newcomer

Eight points form a loose cluster, I sits a little away from it, and J is far out. After training we also score a new point Q=(8,3)Q=(8,3). We grow trees on all ten points, so ψ=10\psi=10, the height limit is ℓ=⌈log⁡210⌉=4\ell=\lceil\log_2 10\rceil=4, and the normaliser is c(10)=2(ln⁡9+0.5772)−2⋅910=2(2.1972+0.5772)−1.8=3.749c(10)=2(\ln9+0.5772)-\tfrac{2\cdot9}{10}=2(2.1972+0.5772)-1.8=3.749.

Pointx₁x₂Role
A23cluster
B32cluster
C34cluster
D43cluster
E45cluster
F54cluster
G25cluster
H52cluster
I6.56.5mild outlier
J98strong outlier
The training data. Highlighted: the two points that sit away from the cluster.

Step 1: how likely is a point to be isolated by the very first cut? At the root a feature is chosen with probability 12\tfrac12 each. On x1x_1 (range 2 to 9), J is alone exactly when p∈(6.5,9)p\in(6.5,9), with probability 2.57\tfrac{2.5}{7}. On x2x_2 (range 2 to 8) it needs p∈(6.5,8)p\in(6.5,8), with probability 1.56\tfrac{1.5}{6}. So P(J isolated at depth 1)=12⋅2.57+12⋅1.56=0.179+0.125=0.304P(\text{J isolated at depth 1})=\tfrac12\cdot\tfrac{2.5}{7}+\tfrac12\cdot\tfrac{1.5}{6}=0.179+0.125=0.304. For C =(3,4)=(3,4) the probability is 0: on both features it has points on both sides. Even I cannot be isolated at depth 1, because J is always on its far side. I has to wait until J has been cut away, which is masking on a small scale.

Step 2: grow one tree by hand. Each node draws a feature, then a uniform number u∈[0,1)u\in[0,1), and sets p=min⁡+u (max⁡−min⁡)p=\min+u\,(\max-\min) over the points that reached that node. These are the draws behind the first tab of the figure below:

Node pointsDepthFeature (range)uThreshold pLeft | right
ABCDEFGHIJ0x₂ (2 – 8)0.84832 + 0.8483·6 = 7.09ABCDEFGHI | J
ABCDEFGHI1x₁ (2 – 6.5)0.79862 + 0.7986·4.5 = 5.59ABCDEFGH | I
ABCDEFGH2x₂ (2 – 5)0.34112 + 0.3411·3 = 3.02ABDH | CEFG
ABDH3x₁ (2 – 5)0.16692 + 0.1669·3 = 2.50A | BDH
CEFG3x₂ (4 – 5)0.32734 + 0.3273·1 = 4.33CF | EG
One isolation tree, node by node (pre-order). Depth 4 = ℓ forces a leaf.

J is isolated by the first cut and I by the second. The cluster is only split apart at depth 3, and at depth 4 the limit stops the tree with BDH, CF and EG still together. Their path lengths get the correction: h=4+c(3)=4+1.207=5.207h=4+c(3)=4+1.207=5.207 for B, D, H and h=4+c(2)=5h=4+c(2)=5 for C, E, F, G. The new point Q has x2=3≤7.09x_2=3\le7.09 (left) and then x1=8>5.59x_1=8>5.59 (right). It lands in I's leaf at depth 2, so h(Q)=2+c(1)=2h(Q)=2+c(1)=2.

PointLeafe(x)c(m)h(x)
J{J}101
I{I}202
Q (new){I}202
A{A}404
C, F{C, F}4c(2) = 15
E, G{E, G}4c(2) = 15
B, D, H{B, D, H}4c(3) = 1.2075.207
Path lengths in this one tree. One tree already ranks J and I first, but the cluster values are noisy (A got lucky at depth 4).

Step 3: average over the forest and score. One tree is a single random draw. The forest averages hh over many trees, and as t→∞t\to\infty the average converges to the exact expectation E[h(x)]\mathbb{E}[h(x)] over the random splits. With 20 000 trees, scikit-learn agrees with the exact values below to three decimals. Each score is s=2−E[h]/3.749s=2^{-\mathbb{E}[h]/3.749}. For J: 2.078/3.749=0.5542.078/3.749=0.554, and 2−0.554=0.6812^{-0.554}=0.681.

PointE[h(x)]E[h] / c(10)s(x, 10)Flagged at s > 0.5?
J2.0780.5540.681yes
I3.0720.8200.567yes
Q (new)3.2080.8560.553yes
H3.7531.0010.500no (just)
G3.7961.0130.496no
B3.8601.0300.490no
A3.8811.0350.488no
F4.4191.1790.442no
E4.4281.1810.441no
D4.5321.2090.433no
C4.5461.2120.432no
Exact expected path lengths (the infinite-forest limit, ψ = 10, ℓ = 4) and scores. Highlighted: scores above 0.5.

The ranking is right: J, then I, then the newcomer Q, then the cluster. Within the cluster, the corner points (H, G, B, A) score higher than the inner ones (C, D, E, F), because a cut near the edge of the cluster can peel a corner off. Note how compressed the scores are: with only ψ=10\psi=10 points every path is short, so the whole range runs from 0.43 to 0.68 and H sits right on the 0.5 line. This is typical, and it is why practitioners threshold by rank or contamination rate rather than at exactly 0.5.

▸ isolation tree · random splitsstep 1/14
12345678910123456789x₁ →x₂ABCDEFGHIJthe tree · depth ↓01234
nodes 0/11c(ψ=10) = 3.749
  1. 1iTree(S, d):
  2. 2 if |S| ≤ 1 or d = ℓ: return Leaf(|S|)
  3. 3 q ← random feature that varies in S
  4. 4 p ← min Sq + u·(max Sq − min Sq)
  5. 5 L ← {x ∈ S : xq ≤ p}; R ← S − L
  6. 6 return Node(q, p, iTree(L,d+1), iTree(R,d+1))
  7. 7h(x) = depth(leaf of x) + c(|leaf|)

Grow one isolation tree on all 10 points (ψ = 10, height limit ℓ = ⌈log₂ 10⌉ = 4). There are no labels: every split is random.

fig.Tab ① grows the tree from the table above, one node at a time: each random cut is drawn in the plane and in the tree. J and I are fenced off at depths 1 and 2, the cluster only at the height limit ℓ = 4 (amber leaves get +c(m)). Q then drops down the same splits to depth 2. Tab ② is the forest: the background is the score at every location, the bars are each point's score from t trees with a tick at the exact value from the table, and the lower plot shows the running mean of h for the selected point converging to its exact E[h]. Drag J into the cluster and watch its score fall below 0.5. Switch off the height limit and the scores barely change.

The full algorithm

Isolation Forest

  1. 1Train. For i=1…ti=1\dots t: draw ψ\psi points without replacement and grow iTree\text{iTree} on them with height limit ℓ=⌈log⁡2ψ⌉\ell=\lceil\log_2\psi\rceil.
  2. 2Path lengths. For a point xx (training or new), walk each tree to a leaf: hi(x)=h_i(x)= depth + c(leaf size)+\,c(\text{leaf size}).
  3. 3Score. s(x)=2−hˉ(x)/c(ψ)s(x)=2^{-\bar h(x)/c(\psi)} with hˉ=1t∑ihi(x)\bar h=\tfrac1t\sum_i h_i(x).
  4. 4Decide. Rank by ss. Flag the top fraction you expect to be anomalous (the contamination rate), or use s>0.5s>0.5 when no rate is known.

Hyperparameters in practice

n_estimators (t)
100 is the paper's default. Path lengths converge quickly, and more trees only reduce the variance of the score.
max_samples (ψ)
256 by default. Larger ψ rarely helps and can bring back masking; smaller ψ is faster but noisier.
Height limit
fixed at ⌈log⁡2ψ⌉\lceil\log_2\psi\rceil in scikit-learn; not exposed as a parameter.
contamination
only moves the decision threshold (offset_). "auto" means s>0.5s>0.5; a number such as 0.01 flags the top 1% of training scores.
max_features
fraction of features each tree may split on. Below 1.0 it gives each tree a random feature subset, which helps when many features are irrelevant.

In code

python
1import numpy as np
2
3EULER = 0.5772156649015329
4
5def c(n):
6 """Average path length of an unsuccessful BST search among n points."""
7 if n <= 1: return 0.0
8 if n == 2: return 1.0
9 return 2 * (np.log(n - 1) + EULER) - 2 * (n - 1) / n
10
11def itree(X, depth, limit, rng):
12 n = len(X)
13 if n <= 1 or depth >= limit:
14 return {"size": n}
15 varying = np.flatnonzero(X.max(0) > X.min(0))
16 if len(varying) == 0: # all duplicates
17 return {"size": n}
18 q = rng.choice(varying) # random feature
19 p = rng.uniform(X[:, q].min(), X[:, q].max()) # random threshold
20 left = X[:, q] <= p
21 return {"q": q, "p": p,
22 "L": itree(X[left], depth + 1, limit, rng),
23 "R": itree(X[~left], depth + 1, limit, rng)}
24
25def path_length(x, node, depth=0):
26 while "size" not in node:
27 node = node["L"] if x[node["q"]] <= node["p"] else node["R"]
28 depth += 1
29 return depth + c(node["size"])
30
31class IForest:
32 def __init__(self, n_trees=100, psi=256, seed=0):
33 self.n_trees, self.psi, self.rng = n_trees, psi, np.random.default_rng(seed)
34
35 def fit(self, X):
36 self.psi_ = min(self.psi, len(X))
37 limit = int(np.ceil(np.log2(self.psi_)))
38 self.trees = []
39 for _ in range(self.n_trees):
40 sub = X[self.rng.choice(len(X), self.psi_, replace=False)]
41 self.trees.append(itree(sub, 0, limit, self.rng))
42 return self
43
44 def score(self, X):
45 h = np.array([[path_length(x, t) for t in self.trees] for x in X]).mean(1)
46 return 2 ** (-h / c(self.psi_))
47
48X = np.array([[2, 3], [3, 2], [3, 4], [4, 3], [4, 5], [5, 4],
49 [2, 5], [5, 2], [6.5, 6.5], [9, 8]])
50Q = np.array([[8, 3]])
51forest = IForest(n_trees=5000, psi=10, seed=0).fit(X)
52print(np.round(forest.score(np.vstack([X, Q])), 3))
53# [0.489 0.492 0.433 0.432 0.441 0.444 0.497 0.502 0.566 0.678 0.554]
From scratch: iTrees with a height limit, the c(n) correction and the score. With many trees it reproduces the exact table.
python
1import numpy as np
2from sklearn.ensemble import IsolationForest
3
4X = np.array([[2, 3], [3, 2], [3, 4], [4, 3], [4, 5], [5, 4],
5 [2, 5], [5, 2], [6.5, 6.5], [9, 8]])
6Q = np.array([[8, 3]])
7
8iso = IsolationForest(n_estimators=1000, max_samples=10, random_state=0).fit(X)
9s = -iso.score_samples(np.vstack([X, Q])) # the paper's s(x, psi)
10print(np.round(s, 3))
11# [0.49 0.489 0.431 0.434 0.44 0.441 0.497 0.496 0.563 0.679 0.55 ]
12print(iso.offset_) # -0.5 with contamination="auto"
13print(iso.predict(np.vstack([X, Q]))) # -1 = anomaly (s > 0.5)
14# [ 1 1 1 1 1 1 1 1 -1 -1 -1]
15
16# With a known anomaly rate, contamination sets the threshold at that quantile:
17iso20 = IsolationForest(n_estimators=1000, max_samples=10,
18 contamination=0.2, random_state=0).fit(X)
19print(iso20.predict(X)) # [ 1 1 1 1 1 1 1 1 -1 -1]
scikit-learn. score_samples returns −s, so negate it to get the paper's score.

Use when

  • +You have lots of data and need speed: training is O(tψlog⁡ψ)O(t\psi\log\psi), independent of nn, and scoring is a few hundred tree walks.
  • +There are no labels, or very few anomalies to learn from: it needs neither.
  • +Features are on different scales or units: thresholds are drawn per feature within its own range, so linear rescaling changes nothing.
  • +Anomalies are global, meaning far from the bulk along some features, and the data has moderately many dimensions.

Avoid when

  • −Anomalies are local: a point in the gap between a dense and a sparse cluster can look normal globally. LOF is built for that case.
  • −The structure is diagonal or curved: axis-parallel cuts create artefacts (score bands along the axes and "ghost" low-score regions). Extended Isolation Forest uses random hyperplanes instead.
  • −Most features are irrelevant noise: random feature choice wastes most cuts on them, and the scores blur.
  • −You need calibrated probabilities: the score ranks points but is not a probability of being an anomaly.

Where it's used

Fraud and payments

Flag unusual transactions in real time; the model is cheap to retrain daily on fresh subsamples.

Infrastructure monitoring

Spot abnormal combinations of CPU, latency and error-rate metrics without hand-written alert rules.

Data cleaning

Find corrupt rows, sensor glitches and unit errors before training a supervised model.

Security

Network intrusion and unusual login behaviour, where attacks are rare and labels scarce.

Check yourself

A point's mean path length over the forest equals c(ψ)c(\psi) exactly. Its anomaly score is…

Check yourself

1-D data {0,1,2,10}\{0, 1, 2, 10\}. At the root, what is the probability that the random threshold isolates the point 10 immediately?

Check yourself

Why does Isolation Forest grow each tree on a small subsample (ψ = 256) instead of the full dataset?

Check yourself

A tree stops at the height limit ℓ=4\ell=4 with 3 points still in a leaf. What path length do those points get (using c(3)=1.207c(3)=1.207)?

Remember

  • ✓Anomalies are few and different, so random axis-parallel cuts isolate them after only a few splits. The path length h(x) measures how easy a point is to isolate.
  • ✓c(n)=2H(n−1)−2(n−1)/nc(n)=2H(n-1)-2(n-1)/n is the average path length of a random tree on nn points. It normalises path lengths and also corrects leaves stopped at the height limit.
  • ✓Score s=2−E[h]/c(ψ)s=2^{-\mathbb{E}[h]/c(\psi)}: near 1 for anomalies, 0.5 for an average point, near 0 for points deep in dense regions.
  • ✓Each tree sees ψ=256\psi=256 points and stops at depth ⌈log⁡2ψ⌉\lceil\log_2\psi\rceil. That makes it fast, independent of nn, and less prone to masking and swamping.
  • ✓Rank by score and set the threshold from an expected anomaly rate. The 0.5 cut-off is a convention, and scores crowd around it when ψ is small.
← back to ML Algorithms roadmap