Explain how Isolation Forest works and when it fails
In an interview you are asked: "Explain Isolation Forest to a colleague who has only used z-scores. Why does it need no distance computation? What does the contamination parameter do? Name two situations where you would not use it."
Include a short numerical illustration, for example eight one-dimensional points 10, 11, 12, 13, 14, 15, 16 and 40, and say what you would change if your colleague wants to flag the top 0.05 percent of 20,000 daily transactions.
The idea. Anomalies are few and different, so a random partition separates them from the rest in fewer splits than it needs for ordinary points. Build many trees on small random subsamples (size \psi, typically a few hundred). Each node picks a random feature and a random split value between the minimum and maximum of that feature in the node. The path length h(x) is the number of splits needed to isolate x; the average over trees is E[h(x)], and the score is
where c(\psi) is the average path length in a binary search tree of \psi points, used to normalise the score to between 0 and 1. Trees are cut at depth \lceil\log_2\psi\rceil and an unfinished leaf of size n adds c(n) (these details are from memory of the original paper; the formula reproduced sklearn's scores in my check). Scores near 1 are anomalous; near 0.5 for all points means no clear anomalies.
No distances. It only compares one feature at a time against a random threshold, so there is no metric to choose, no feature scaling requirement, and training and scoring cost scale with the subsample size and the number of trees, not with n^2.
Numerical illustration. For the eight points, \psi = 8, depth limit 3, c(8) = 3.296. The first split falls in the gap between 16 and 40 with probability 24/30 = 0.8 and then isolates 40 at depth 1. Enumerating every possible split exactly gives E[h(40)] = 1.219, so s = 2^{-1.219/3.296} = 0.774; for the middle point 13, E[h] = 4.284, s = 0.406. A 3,000-tree sklearn forest with max_samples=8 returned 0.773 and 0.406 (verified).
Contamination. It does not change the ranking. It sets the decision threshold at that quantile of the training scores (offset_), and 'auto' uses the fixed offset -0.5 (verified), meaning "score above 0.5". On 5,000 rows with 50 true anomalies, 'auto' flagged 479 (precision 0.104), contamination=0.01 flagged 50 (49 true) and 0.001 flagged 5 (recall 0.10), while AUROC stayed 1.000 (verified). If the colleague wants the top 0.05 percent of 20,000 transactions a day, that is 10 alerts; skip contamination, score a held-out week and use the 0.9995 quantile of the scores as the threshold. A threshold taken from the training scores gave 8.3 alerts a day instead of 10.0 on unseen days (verified).
When not to use it. (1) Correlation structure is the signal (anomalies lie off the main axis but inside each marginal range): axis-parallel splits see little, AUROC 0.957 against 1.000 for Mahalanobis at correlation 0.95 (verified). Use Mahalanobis, PCA residuals or an extended variant (from memory: random hyperplanes). (2) Many irrelevant features: AUROC fell from 0.998 to 0.790 with 100 noise dimensions (verified); select features first. Also, an anomaly that is extreme in only one of several features can score low: a synthetic injection of that kind had recall 0.00 at the budget threshold (verified).
Share this question