Skip to content
Last Dictionary
Plane
Machine LearningSecurity & Misuse

isolation forest

nounAlso: iForest, isolation-based anomaly detection, extended isolation forest

In plain wordsA method for spotting unusual data points by repeatedly slicing the data at random: odd points get cut off from the rest after only a few slices, while ordinary points take many.

  1. An unsupervised anomaly detectionanomaly detection, n.: Automatically spotting the rare data points that don't fit the usual pattern, such as a fraudulent card payment, a machine about to fail or an intruder on a network. algorithm that isolates points rather than modeling normal data. It builds an ensemble of random binary trees (isolation trees), each grown on a small random subsample (256 points in the original paper) by repeatedly choosing a random feature and a random split value between that feature's minimum and maximum, until points are isolated or a depth limit is reached. Because anomalies are few and different, they tend to be separated close to the root, so their average path length across the trees is short. The anomaly score normalizes the mean path length by c(n), the average path length of an unsuccessful search in a binary search tree built on n points: scores near 1 indicate anomalies, while scores well below 0.5 indicate normal points. The method runs in linear time with little memory, needs no distance computations and copes with many features, but its axis-parallel cuts create scoring artifacts that the extended isolation forest, which cuts along random slopes, reduces.

    The isolation forest scored the gift-card purchase burst at 0.78, far above anything else that day.

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

Origin

Introduced by Fei Tony Liu, Kai Ming Ting and Zhi-Hua Zhou at the 2008 IEEE International Conference on Data Mining (ICDM), with an extended version, 'Isolation-Based Anomaly Detection', in ACM Transactions on Knowledge Discovery from Data. Sahand Hariri, Matias Carrasco Kind and Robert Brunner proposed the extended isolation forest in 2018.

Usage note

Despite the name, it is not a random forestrandom forest, n.: A prediction method that builds hundreds of decision trees, each from a random sample of the data and features, and lets them vote. The crowd is far more reliable than any single tree.: its trees are unsupervised, splits are random rather than optimized, and only path lengths are used.

Related

See also
  • anomaly detectionanomaly detection, n.: Automatically spotting the rare data points that don't fit the usual pattern, such as a fraudulent card payment, a machine about to fail or an intruder on a network.
  • random forestrandom forest, n.: A prediction method that builds hundreds of decision trees, each from a random sample of the data and features, and lets them vote. The crowd is far more reliable than any single tree.
  • decision treedecision tree, n.: A model that makes a prediction by asking a series of yes-or-no questions about the input, like a flowchart, with each answer leading to the next question until it reaches a final answer.
  • ensemble learningensemble learning, n.: Combining the predictions of several models — by voting or averaging — so their individual mistakes partly cancel out, giving more accurate and stable results than any one model.
  • density estimationdensity estimation, n.: Working out from a sample of data how likely different values are, by drawing a smooth curve or surface showing where data points bunch up and where they are rare.
  • DBSCANDBSCAN, n.: A clustering method that finds groups as crowded regions of data separated by sparse ones, so it can discover oddly shaped groups and set stray points aside as noise.

Sources

  1. Liu, F. T., Ting, K. M. & Zhou, Z.-H. (2008). Isolation Forest. Proc. 8th IEEE International Conference on Data Mining (ICDM).
  2. Liu, F. T., Ting, K. M. & Zhou, Z.-H. (2012). Isolation-Based Anomaly Detection. ACM Transactions on Knowledge Discovery from Data 6(1).
  3. Hariri, S., Carrasco Kind, M. & Brunner, R. J. (2021). Extended Isolation Forest. IEEE Transactions on Knowledge and Data Engineering 33(4).

Mentioned in

anomaly detectionanomaly detection, n.: Automatically spotting the rare data points that don't fit the usual pattern, such as a fraudulent card payment, a machine about to fail or an intruder on a network., random forestrandom forest, n.: A prediction method that builds hundreds of decision trees, each from a random sample of the data and features, and lets them vote. The crowd is far more reliable than any single tree.