How does an isolation forest use a point's average path length to score it as an anomaly?
answer
- isolate, do not model normality
- few and different means easy to separate
- random feature, random threshold
- count the cuts to isolation
- short average path means anomalous
basics
~20 sAn isolation forest splits data at random until each point sits alone. Anomalies stand apart, so random cuts isolate them in very few splits. The score is the average number of splits across many trees, normalised: short paths mean anomalous.
solid answer
~50 sAn isolation forest builds many trees on random subsamples. At each node it picks a feature at random and a split value drawn uniformly between that feature's minimum and maximum in the node, and it recurses until a point is alone or a height limit is hit. The number of splits needed to isolate a point is its path length in that tree. Points that sit in sparse regions get carved off almost immediately, while points buried in a dense mass need many cuts, so the average path length across trees is short for anomalies and long for normal points. The average is normalised by the expected path length for that subsample size, giving a score in `(0, 1)` where values near 1 are strongly anomalous and values around 0.5 are unremarkable. Nothing here models what normal looks like and no labels are used.
code
python · 20 linesimport random
def path_length(x, points, depth=0):
lo, hi = min(points), max(points)
if len(points) <= 1 or lo == hi or depth >= 30:
return depth
split = random.uniform(lo, hi)
side = [p for p in points if p < split] if x < split else [p for p in points if p >= split]
return path_length(x, side, depth + 1)
random.seed(7)
data = [random.gauss(50, 5) for _ in range(255)] # normal bearing temperatures
normal = data[0]
data.append(140.0) # one overheating unit
for x in (normal, 140.0):
avg = sum(path_length(x, data) for _ in range(500)) / 500
print(round(x, 1), "-> average path length", round(avg, 2))
# 48.7 -> average path length 12.06
# 140.0 -> average path length 1.3go deeper
Recall the one-line intuition: anomalies are few and different, so random splits isolate them quickly, and a short average path length means a high anomaly score. Know that it needs no labels.
Be ready to walk the tree construction step by step - random feature, random threshold inside the node's range, recurse to isolation - and to explain why the raw path length is normalised by the expected path length for the subsample size.
Expect to be asked when the scores are untrustworthy: irrelevant padding features, local anomalies inside the global range, and correlated combinations that axis-parallel cuts cannot see. Say what you would inspect before trusting a top-ranked alert.
Own the tradeoff of a model-free ranker: it is cheap, assumption-light and scales, but it gives no calibrated probability and no natural cut point, so the operating point and the review process become your design problem rather than the model's.
## The inversion at the heart of the method Most anomaly detectors first build a profile of normal data - a density, a boundary, a distance to neighbours - and then call whatever fits the profile badly an anomaly. An isolation forest does the opposite: it never models normality at all. It exploits one property that anomalies have by definition - they are **few and different** - and therefore easy to separate from everything else with a handful of arbitrary cuts. ## Building one isolation tree One tree is grown like this: 1. Draw a small random subsample of the rows (a few hundred is typical; the original paper uses 256). 2. At a node, pick one feature uniformly at random. 3. Pick a split value uniformly at random between the minimum and maximum of that feature **among the rows currently in the node**. 4. Send rows below the value left and the rest right, and recurse. 5. Stop when a node holds a single row (or duplicates), or when a height limit is reached. No impurity criterion, no information gain, no target. The splits are pure randomness - that is what makes the forest cheap to build and what makes each tree an independent weak signal that averaging turns into a stable score. ## Path length A point's **path length** `h(x)` in a tree is the number of edges from the root to the leaf where it ends up - equivalently the number of random cuts that were needed before it stood alone. Consider a fleet of turbines described by vibration amplitude and bearing temperature. A unit running at 140 C when every other unit is between 40 and 60 C occupies an empty stretch of the temperature axis: the very first random threshold drawn on that feature has a good chance of falling below it and slicing it off by itself. A unit at 49 C sits inside a dense pile of neighbours, and it takes cut after cut to whittle that pile down to one row. One tree is noisy - a lucky draw can isolate a perfectly normal point early. The forest averages `h(x)` over hundreds of trees, and the expectation `E[h(x)]` is what carries signal. ## From path length to a bounded score Raw path lengths depend on the subsample size `n`, so they are normalised by `c(n)`, the average path length of an unsuccessful search in a random binary tree over `n` points: ``` c(n) = 2 * (ln(n - 1) + 0.5772) - 2 * (n - 1) / n score(x) = 2 ^ ( -E[h(x)] / c(n) ) ``` Read the score like this: **near 1** means the point is isolated in far fewer cuts than a typical point, so it is strongly anomalous; **around 0.5** means it behaves like an average point; **well below 0.5** means it is deep inside the mass. The transformation is monotone decreasing in path length, so it reorders nothing - it just puts every dataset on a comparable 0-to-1 scale. ## Why the subsample is small Subsampling is not only a speed trick, it fixes two well known failure modes: - **Masking** - a tight clump of anomalies is large enough to look like its own little cluster, so its members need many cuts. Small subsamples usually contain at most one or two members of the clump, restoring their isolation. - **Swamping** - normal points that happen to lie near an anomalous region get short paths and are wrongly flagged. Thinning the data pushes the normal mass and the anomalies further apart. Small subsamples also make the method near-linear in the number of rows and constant in memory per tree, which is why it scales to millions of rows. ## What it is good at, and where it breaks Strengths: no labels, no distance metric, no assumption about the shape of the normal distribution, few knobs, and it tolerates many features and large row counts. Limits worth naming in an interview: - **Axis-parallel cuts.** Splits are always perpendicular to a feature axis, so a point whose individual readings are all ordinary but whose *combination* is impossible - high vibration together with a low bearing temperature, when the two normally rise together - can keep a long path length and never surface. Variants that split on random oblique combinations of features exist for exactly this reason. - **Feature scale is irrelevant, feature relevance is not.** Padding the input with dozens of noisy features dilutes the chance of ever splitting on the informative ones, and scores drift toward the middle. - **Local anomalies.** A point that is only sparse relative to its own neighbourhood, while lying inside the global range of the data, is not carved off early; density-ratio methods handle that case better. - **The score is a ranking, not a probability.** A score of 0.62 is not a 62% chance of being an anomaly. Treat the output as an ordering and decide separately where to cut it.
- Why does each tree use a small random subsample instead of all the rows?Two reasons. It keeps building near-linear in the number of rows. More importantly it breaks masking and swamping: a dense clump of anomalies looks like a legitimate cluster in the full data and needs many cuts, but a 256-row subsample rarely holds more than one clump member, so it is isolated fast again. Thinning also stops normal points near an anomalous region from inheriting short paths.
- How is an average path length turned into a score between 0 and 1?Divide the average path length by `c(n)`, the expected path length of an unsuccessful search in a random binary tree over the subsample size `n`, and take `2 ^ (-ratio)`. Scores near 1 mean the point is isolated far faster than typical, around 0.5 means typical, well below 0.5 means deeply buried. The mapping is monotone, so it changes the scale but never the ranking.
- What kind of anomaly does an isolation forest tend to miss?One that is only anomalous in a correlated combination. Because every split is perpendicular to a single feature axis, a row whose individual values all sit comfortably inside their normal ranges - but whose joint pattern never occurs, such as high vibration with a cool bearing when the two usually move together - stays deep in the tree. Oblique-split variants, or engineered ratio features, are the usual answers.
Twenty questions with random questions. If someone is thinking of an unusual thing, even careless questions narrow it down almost immediately; a very ordinary thing takes the full twenty.
saying these in an interview costs you the question
- Says the forest learns a boundary around normal data
- Thinks a longer path length means more anomalous
- Claims it needs labelled anomalies to train
- Says splits are chosen to maximise purity or information gain
- Reads the 0-to-1 score as a probability of being an anomaly
- Assumes bigger subsamples always give better detection