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 (no labels) → a score per point; higher means more anomalous
- Learns
- random binary trees, each grown on a subsample of points. Nothing is fitted: every split is random
- Training
- , which does not depend on once the subsamples are drawn
- Scoring
- per point: one root-to-leaf walk per tree
- Hyperparameters
- number of trees (100), subsample size (256), height limit , 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 , 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
- 1Stop? If , or the depth has reached the height limit , or all points in are identical, return a leaf that remembers its size .
- 2Pick a feature uniformly at random among the features that vary within .
- 3Pick a threshold uniformly at random between and .
- 4Split into and , and recurse: , .
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 down a tree, following the same rule at every node. The number of edges it crosses before reaching a leaf is its path length.
- path length of x in one tree
- number of edges from the root to the leaf that x lands in, i.e. the leaf's depth
- number of training points in that leaf (1 if was isolated)
- expected extra depth needed to isolate points, defined below;
The correction is needed because of the height limit. A leaf that stopped at depth with 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 is short, we need a reference value: the average leaf depth of a fully grown tree on points. An isolation tree on distinct points has leaves and internal nodes, which is the same structure as a binary search tree with keys whose 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 points left and right, with equally likely to be any of .
Deriving c(n)
- 1Let be the expected sum of leaf depths of a tree that isolates points, so the average is . Clearly .
- 2The root split adds 1 to the depth of all leaves, and then the two sides are independent trees on and points: .
- 3Check small cases. , so (one cut separates two points). , so . , so .
- 4Solving the recurrence (the textbook result for random BSTs) gives the closed form below. Plug in : , which matches.
- average path length of an unsuccessful search in a BST built from points; used as the "typical depth" for a tree grown on points. ,
- the -th harmonic number
- Euler's constant, 0.5772…
grows like , so typical paths are logarithmic in the sample size. The paper and scikit-learn replace by for . That approximation is excellent for large , with against the exact , but rough for tiny leaves: it gives instead of . 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 , the typical depth for the subsample size each tree was grown on:
- anomaly score of x, between 0 and 1
- mean path length of over the trees, i.e.
- subsample size used to grow each tree
- normaliser: the average path length expected for a tree on ψ points
Reading the score
- $\mathbb{E}[h]\to0$
- : the point is isolated almost immediately. Clear anomaly.
- $\mathbb{E}[h]=c(\psi)$
- : 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$
- : 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 removes the 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 points, drawn without replacement (default , 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 .
Height limit. Trees stop growing at depth , about the average height of a random tree on points (8 for ). 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 correction, so their path lengths are still estimated rather than truncated. This keeps every tree at no more than 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 . We grow trees on all ten points, so , the height limit is , and the normaliser is .
| Point | x₁ | x₂ | Role |
|---|---|---|---|
| A | 2 | 3 | cluster |
| B | 3 | 2 | cluster |
| C | 3 | 4 | cluster |
| D | 4 | 3 | cluster |
| E | 4 | 5 | cluster |
| F | 5 | 4 | cluster |
| G | 2 | 5 | cluster |
| H | 5 | 2 | cluster |
| I | 6.5 | 6.5 | mild outlier |
| J | 9 | 8 | strong outlier |
Step 1: how likely is a point to be isolated by the very first cut? At the root a feature is chosen with probability each. On (range 2 to 9), J is alone exactly when , with probability . On (range 2 to 8) it needs , with probability . So . For C 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 , and sets over the points that reached that node. These are the draws behind the first tab of the figure below:
| Node points | Depth | Feature (range) | u | Threshold p | Left | right |
|---|---|---|---|---|---|
| ABCDEFGHIJ | 0 | x₂ (2 – 8) | 0.8483 | 2 + 0.8483·6 = 7.09 | ABCDEFGHI | J |
| ABCDEFGHI | 1 | x₁ (2 – 6.5) | 0.7986 | 2 + 0.7986·4.5 = 5.59 | ABCDEFGH | I |
| ABCDEFGH | 2 | x₂ (2 – 5) | 0.3411 | 2 + 0.3411·3 = 3.02 | ABDH | CEFG |
| ABDH | 3 | x₁ (2 – 5) | 0.1669 | 2 + 0.1669·3 = 2.50 | A | BDH |
| CEFG | 3 | x₂ (4 – 5) | 0.3273 | 4 + 0.3273·1 = 4.33 | CF | EG |
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: for B, D, H and for C, E, F, G. The new point Q has (left) and then (right). It lands in I's leaf at depth 2, so .
| Point | Leaf | e(x) | c(m) | h(x) |
|---|---|---|---|---|
| J | {J} | 1 | 0 | 1 |
| I | {I} | 2 | 0 | 2 |
| Q (new) | {I} | 2 | 0 | 2 |
| A | {A} | 4 | 0 | 4 |
| C, F | {C, F} | 4 | c(2) = 1 | 5 |
| E, G | {E, G} | 4 | c(2) = 1 | 5 |
| B, D, H | {B, D, H} | 4 | c(3) = 1.207 | 5.207 |
Step 3: average over the forest and score. One tree is a single random draw. The forest averages over many trees, and as the average converges to the exact expectation over the random splits. With 20 000 trees, scikit-learn agrees with the exact values below to three decimals. Each score is . For J: , and .
| Point | E[h(x)] | E[h] / c(10) | s(x, 10) | Flagged at s > 0.5? |
|---|---|---|---|---|
| J | 2.078 | 0.554 | 0.681 | yes |
| I | 3.072 | 0.820 | 0.567 | yes |
| Q (new) | 3.208 | 0.856 | 0.553 | yes |
| H | 3.753 | 1.001 | 0.500 | no (just) |
| G | 3.796 | 1.013 | 0.496 | no |
| B | 3.860 | 1.030 | 0.490 | no |
| A | 3.881 | 1.035 | 0.488 | no |
| F | 4.419 | 1.179 | 0.442 | no |
| E | 4.428 | 1.181 | 0.441 | no |
| D | 4.532 | 1.209 | 0.433 | no |
| C | 4.546 | 1.212 | 0.432 | no |
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 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.
- 1iTree(S, d):
- 2 if |S| ≤ 1 or d = ℓ: return Leaf(|S|)
- 3 q ← random feature that varies in S
- 4 p ← min Sq + u·(max Sq − min Sq)
- 5 L ← {x ∈ S : xq ≤ p}; R ← S − L
- 6 return Node(q, p, iTree(L,d+1), iTree(R,d+1))
- 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.
The full algorithm
Isolation Forest
- 1Train. For : draw points without replacement and grow on them with height limit .
- 2Path lengths. For a point (training or new), walk each tree to a leaf: depth .
- 3Score. with .
- 4Decide. Rank by . Flag the top fraction you expect to be anomalous (the
contaminationrate), or use 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 in scikit-learn; not exposed as a parameter.
- contamination
- only moves the decision threshold (
offset_)."auto"means ; 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
1import numpy as np23EULER = 0.577215664901532945def c(n):6 """Average path length of an unsuccessful BST search among n points."""7 if n <= 1: return 0.08 if n == 2: return 1.09 return 2 * (np.log(n - 1) + EULER) - 2 * (n - 1) / n1011def 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 duplicates17 return {"size": n}18 q = rng.choice(varying) # random feature19 p = rng.uniform(X[:, q].min(), X[:, q].max()) # random threshold20 left = X[:, q] <= p21 return {"q": q, "p": p,22 "L": itree(X[left], depth + 1, limit, rng),23 "R": itree(X[~left], depth + 1, limit, rng)}2425def 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 += 129 return depth + c(node["size"])3031class 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)3435 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 self4344 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_))4748X = 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]1import numpy as np2from sklearn.ensemble import IsolationForest34X = 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]])78iso = 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]1516# 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]Use when
- +You have lots of data and need speed: training is , independent of , 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 exactly. Its anomaly score is…
Check yourself
1-D data . 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 with 3 points still in a leaf. What path length do those points get (using )?
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.
- ✓ is the average path length of a random tree on points. It normalises path lengths and also corrects leaves stopped at the height limit.
- ✓Score : near 1 for anomalies, 0.5 for an average point, near 0 for points deep in dense regions.
- ✓Each tree sees points and stops at depth . That makes it fast, independent of , 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.