# Isolation Forest

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

Source: https://www.mlfoundry.in/learn/isolation-forest  
Section: ML Algorithms › Unsupervised · Anomaly Detection  
Level: core · 17 min read · updated 2026-10-08

**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.

- **Task:** Unsupervised anomaly (outlier) detection; also used for novelty detection on new data
- **Input → output:** points $x_1,\dots,x_n$ (no labels) → a score $s(x)\in(0,1)$ per point; higher means more anomalous
- **Learns:** $t$ random binary trees, each grown on a subsample of $\psi$ points. Nothing is fitted: every split is random
- **Training:** $O(t\,\psi\log\psi)$, which does not depend on $n$ once the subsamples are drawn
- **Scoring:** $O(t\log\psi)$ per point: one root-to-leaf walk per tree
- **Hyperparameters:** number of trees $t$ (100), subsample size $\psi$ (256), height limit $\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(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.

> **Few and different:** The method relies on two properties of anomalies. **Different**: their feature values lie away from the bulk, so a random threshold has a good chance of falling in the empty gap between them and everything else. **Few**: there are not many of them, so they do not form a dense group that would protect them. A random cut lands in a gap with probability proportional to the gap's width, and anomalies are exactly the points next to wide gaps.

## Isolation trees

**iTree(S, d): grow one isolation tree**

1. **Stop?** If $|S|\le1$, or the depth $d$ has reached the height limit $\ell$, or all points in $S$ are identical, return a leaf that remembers its size $|S|$.
2. **Pick a feature** $q$ uniformly at random among the features that vary within $S$.
3. **Pick a threshold** $p$ uniformly at random between $\min_{x\in S}x_q$ and $\max_{x\in S}x_q$.
4. **Split** into $L=\{x\in S: x_q\le p\}$ and $R=S\setminus L$, and recurse: $\text{iTree}(L,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 $x$ 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\big(m(x)\big)
$$

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

The correction $c(m)$ is needed because of the height limit. A leaf that stopped at depth $\ell$ with $m>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)$ is short, we need a reference value: the average leaf depth of a fully grown tree on $n$ points. An isolation tree on $n$ distinct points has $n$ leaves and $n-1$ internal nodes, which is the same structure as a binary search tree with $n-1$ keys whose $n$ 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 $k$ points left and $n-k$ right, with $k$ equally likely to be any of $1,\dots,n-1$.

**Deriving c(n)**

1. Let $E(n)$ be the expected **sum** of leaf depths of a tree that isolates $n$ points, so the average is $c(n)=E(n)/n$. Clearly $E(1)=0$.
2. The root split adds 1 to the depth of all $n$ leaves, and then the two sides are independent trees on $k$ and $n-k$ points: $E(n)=n+\frac{1}{n-1}\sum_{k=1}^{n-1}\big[E(k)+E(n-k)\big]$.
3. Check small cases. $E(2)=2+\tfrac11[0+0]=2$, so $c(2)=1$ (one cut separates two points). $E(3)=3+\tfrac12[(0+2)+(2+0)]=5$, so $c(3)=\tfrac53\approx1.667$. $E(4)=4+\tfrac13\cdot2(0+2+5)=8.667$, so $c(4)\approx2.167$.
4. Solving the recurrence (the textbook result for random BSTs) gives the closed form below. Plug in $n=3$: $2(1+\tfrac12)-\tfrac43=1.667$, which matches.

$$
c(n)=2H(n-1)-\frac{2(n-1)}{n},\qquad H(i)\approx\ln i+\gamma
$$

- $c(n)$: average path length of an unsuccessful search in a BST built from $n$ points; used as the "typical depth" for a tree grown on $n$ points. $c(1)=0$, $c(2)=1$
- $H(i)$: the $i$-th harmonic number $1+\tfrac12+\dots+\tfrac1i$
- $\gamma$: Euler's constant, 0.5772…

$c(n)$ grows like $2\ln n$, so typical paths are logarithmic in the sample size. The paper and scikit-learn replace $H(i)$ by $\ln i+\gamma$ for $n>2$. That approximation is excellent for large $n$, with $c(256)=10.245$ against the exact $10.249$, but rough for tiny leaves: it gives $c(3)=1.207$ instead of $1.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(\psi)$, the typical depth for the subsample size each tree was grown on:

$$
s(x,\psi)=2^{-\,\mathbb{E}[h(x)]\,/\,c(\psi)}
$$

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

**Reading the score**

- **$\mathbb{E}[h]\to0$:** $s\to1$: the point is isolated almost immediately. **Clear anomaly.**
- **$\mathbb{E}[h]=c(\psi)$:** $s=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\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(\psi)$ removes the $\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 $\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 $n$.

**Height limit.** Trees stop growing at depth $\ell=\lceil\log_2\psi\rceil$, about the average height of a random tree on $\psi$ points (8 for $\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)$ correction, so their path lengths are still estimated rather than truncated. This keeps every tree at no more than $2^\ell$ leaves.

> **Why short paths mean anomaly: an exact toy case:** Take three 1-D points $\{0,1,10\}$ (height limit $\lceil\log_2 3\rceil=2$). The root threshold is uniform on $(0,10)$. With probability $0.9$ it falls in $(1,10)$ and isolates **10** at depth 1. With probability $0.1$ it falls in $(0,1)$, isolates 0, and 10 needs one more cut. So $\mathbb{E}[h(10)]=0.9\cdot1+0.1\cdot2=1.1$, while $\mathbb{E}[h(0)]=0.1\cdot1+0.9\cdot2=1.9$ and $\mathbb{E}[h(1)]=2$. With $c(3)=1.207$ the scores are $0.532$, $0.336$ and $0.317$. The width of the gap next to a point is what drives its expected depth down.

## 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)$. We grow trees on all ten points, so $\psi=10$, the height limit is $\ell=\lceil\log_2 10\rceil=4$, and the normaliser is $c(10)=2(\ln9+0.5772)-\tfrac{2\cdot9}{10}=2(2.1972+0.5772)-1.8=3.749$.

The training data. Highlighted: the two points that sit away from the cluster.

| 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 $\tfrac12$ each. On $x_1$ (range 2 to 9), J is alone exactly when $p\in(6.5,9)$, with probability $\tfrac{2.5}{7}$. On $x_2$ (range 2 to 8) it needs $p\in(6.5,8)$, with probability $\tfrac{1.5}{6}$. So $P(\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)$ 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\in[0,1)$, and sets $p=\min+u\,(\max-\min)$ over the points that reached that node. These are the draws behind the first tab of the figure below:

One isolation tree, node by node (pre-order). Depth 4 = ℓ forces a leaf.

| 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: $h=4+c(3)=4+1.207=5.207$ for B, D, H and $h=4+c(2)=5$ for C, E, F, G. The new point Q has $x_2=3\le7.09$ (left) and then $x_1=8>5.59$ (right). It lands in I's leaf at depth 2, so $h(Q)=2+c(1)=2$.

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).

| 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 $h$ over many trees, and as $t\to\infty$ the average converges to the exact expectation $\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^{-\mathbb{E}[h]/3.749}$. For J: $2.078/3.749=0.554$, and $2^{-0.554}=0.681$.

Exact expected path lengths (the infinite-forest limit, ψ = 10, ℓ = 4) and scores. Highlighted: scores above 0.5.

| 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 $\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.

> Figure: 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.

> **Computing E[h] exactly:** Every threshold inside the same gap between two consecutive values gives the same split. So $\mathbb{E}[h]$ is a finite sum: for each feature and each gap, (probability of that feature) × (gap width ÷ range) × (expected path in the child that contains $x$), recursing down to the height limit. Step 1 is the first level of this recursion. The figure computes the full recursion to draw its "exact" ticks.

## The full algorithm

**Isolation Forest**

1. **Train.** For $i=1\dots t$: draw $\psi$ points without replacement and grow $\text{iTree}$ on them with height limit $\ell=\lceil\log_2\psi\rceil$.
2. **Path lengths.** For a point $x$ (training or new), walk each tree to a leaf: $h_i(x)=$ depth $+\,c(\text{leaf size})$.
3. **Score.** $s(x)=2^{-\bar h(x)/c(\psi)}$ with $\bar h=\tfrac1t\sum_i h_i(x)$.
4. **Decide.** Rank by $s$. Flag the top fraction you expect to be anomalous (the `contamination` rate), or use $s>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 $\lceil\log_2\psi\rceil$ in scikit-learn; not exposed as a parameter.
- **contamination:** only moves the decision threshold (`offset_`). `"auto"` means $s>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
import numpy as np

EULER = 0.5772156649015329

def c(n):
  """Average path length of an unsuccessful BST search among n points."""
  if n <= 1: return 0.0
  if n == 2: return 1.0
  return 2 * (np.log(n - 1) + EULER) - 2 * (n - 1) / n

def itree(X, depth, limit, rng):
  n = len(X)
  if n <= 1 or depth >= limit:
      return {"size": n}
  varying = np.flatnonzero(X.max(0) > X.min(0))
  if len(varying) == 0:                       # all duplicates
      return {"size": n}
  q = rng.choice(varying)                     # random feature
  p = rng.uniform(X[:, q].min(), X[:, q].max())   # random threshold
  left = X[:, q] <= p
  return {"q": q, "p": p,
          "L": itree(X[left], depth + 1, limit, rng),
          "R": itree(X[~left], depth + 1, limit, rng)}

def path_length(x, node, depth=0):
  while "size" not in node:
      node = node["L"] if x[node["q"]] <= node["p"] else node["R"]
      depth += 1
  return depth + c(node["size"])

class IForest:
  def __init__(self, n_trees=100, psi=256, seed=0):
      self.n_trees, self.psi, self.rng = n_trees, psi, np.random.default_rng(seed)

  def fit(self, X):
      self.psi_ = min(self.psi, len(X))
      limit = int(np.ceil(np.log2(self.psi_)))
      self.trees = []
      for _ in range(self.n_trees):
          sub = X[self.rng.choice(len(X), self.psi_, replace=False)]
          self.trees.append(itree(sub, 0, limit, self.rng))
      return self

  def score(self, X):
      h = np.array([[path_length(x, t) for t in self.trees] for x in X]).mean(1)
      return 2 ** (-h / c(self.psi_))

X = np.array([[2, 3], [3, 2], [3, 4], [4, 3], [4, 5], [5, 4],
            [2, 5], [5, 2], [6.5, 6.5], [9, 8]])
Q = np.array([[8, 3]])
forest = IForest(n_trees=5000, psi=10, seed=0).fit(X)
print(np.round(forest.score(np.vstack([X, Q])), 3))
# [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
import numpy as np
from sklearn.ensemble import IsolationForest

X = np.array([[2, 3], [3, 2], [3, 4], [4, 3], [4, 5], [5, 4],
            [2, 5], [5, 2], [6.5, 6.5], [9, 8]])
Q = np.array([[8, 3]])

iso = IsolationForest(n_estimators=1000, max_samples=10, random_state=0).fit(X)
s = -iso.score_samples(np.vstack([X, Q]))      # the paper's s(x, psi)
print(np.round(s, 3))
# [0.49  0.489 0.431 0.434 0.44  0.441 0.497 0.496 0.563 0.679 0.55 ]
print(iso.offset_)                              # -0.5 with contamination="auto"
print(iso.predict(np.vstack([X, Q])))           # -1 = anomaly (s > 0.5)
# [ 1  1  1  1  1  1  1  1 -1 -1 -1]

# With a known anomaly rate, contamination sets the threshold at that quantile:
iso20 = IsolationForest(n_estimators=1000, max_samples=10,
                      contamination=0.2, random_state=0).fit(X)
print(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.

> **Three different numbers in scikit-learn:** `score_samples(x)` is $-s(x)$ (lower means more abnormal). `decision_function(x)` is `score_samples(x) - offset_`, so it is negative for anomalies. `predict` returns −1 where `decision_function < 0`. Only `offset_` depends on `contamination`; the trees and scores do not.

**Strengths**

- You have lots of data and need speed: training is $O(t\psi\log\psi)$, independent of $n$, 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.

**Limitations**

- 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.

- **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.

> **Treating 0.5 as a magic threshold:** With small $\psi$ or data without clear outliers, all scores crowd around 0.5. In the worked example, H scores 0.4997 with exact averaging, and G scores 0.496 exactly but 0.509 in a 100-tree scikit-learn forest (random_state = 0). Cluster corners flip between "normal" and "anomaly" from seed to seed. Choose the threshold from an expected anomaly rate or a labelled validation sample, and check the score histogram before trusting any cut-off.

> **Duplicates and categorical codes:** Many identical rows form a leaf that can never be split, and integer-encoded categories give thresholds an arbitrary order to work with. Heavy duplication makes those points look extremely normal, and a rare category code at the end of the range looks anomalous just because of its encoding. De-duplicate or weight the data, and one-hot or target-encode categories deliberately.

> **Scaling is irrelevant, transformations are not:** Multiplying a feature by 1000 changes nothing, because thresholds are uniform on that feature's own range. A **nonlinear** transform such as a log does change the result: it moves where the wide gaps are. A long right tail makes every large value look isolated, and a log transform hides that. Decide which representation reflects "different" for your problem.

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

- A. 0
- B. 0.5
- C. 1
- D. $1/c(\psi)$

**Answer:** B. 0.5 — $s=2^{-c(\psi)/c(\psi)}=2^{-1}=0.5$. The point is exactly as hard to isolate as an average point in a random tree on $\psi$ points.

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

- A. 0.25
- B. 0.5
- C. 0.8
- D. 0.9

**Answer:** C. 0.8 — The threshold is uniform on $(0,10)$, and 10 is alone exactly when $p\in(2,10)$: probability $8/10=0.8$. A wide gap next to a point means a high chance of early isolation and a short path.

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

- A. To make the trees deeper
- B. It reduces masking and swamping, and makes training cost independent of n
- C. Because c(n) is only defined up to 256
- D. To make the score a calibrated probability

**Answer:** B. It reduces masking and swamping, and makes training cost independent of n — In a small subsample, clustered anomalies are less likely to shield each other (masking) and normal points near anomalies are less likely to be cut off early (swamping). Each tree also costs O(ψ log ψ) regardless of the dataset size.

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

- A. 3
- B. 4
- C. 5.207
- D. Undefined: the tree must be grown further

**Answer:** C. 5.207 — $h=e+c(m)=4+c(3)=5.207$. The correction adds the expected number of extra cuts that a full subtree on 3 points would have needed. This is exactly what happens to B, D and H in the worked example.

**Key points**

- 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)/n$ is the average path length of a random tree on $n$ points. It normalises path lengths and also corrects leaves stopped at the height limit.
- Score $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 $\psi=256$ points and stops at depth $\lceil\log_2\psi\rceil$. That makes it fast, independent of $n$, 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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
