Isolation forest

Isolation Forest is an algorithm for data anomaly detection initially developed by Fei Tony Liu and Zhi-Hua Zhou in 2008. It detects anomalies using isolation (how far a data point is from the rest of the data). This method deviates from the mainstream philosophy that underpinned most existing anomaly detectors at the time. Instead of profiling all normal instances before anomalies are identified, Isolation Forest detects anomalies using binary trees. The algorithm has a linear time complexity with a low constant and a low memory requirement, which works well with high volume data.

The normalized anomaly scores of the Isolation Forest algorithm fit on the Old Faithful dataset

Isolation Forest splits the data space using lines that are orthogonal to the origin and assigns higher anomaly scores to data points that need fewer splits to be isolated. The figure on the right shows an application of the Isolation Forest algorithm to the waiting time between eruptions and the duration of the eruption of the Old Faithful geyser in Yellowstone National Park. Darker shades of red indicate higher estimated anomaly scores.

Anomalies in a large dataset may follow very complicated patterns, which are difficult to detect visually in the majority of cases. This makes the field of anomaly detection well suited for the application of machine learning techniques.

History

The Isolation Forest (iForest) algorithm was initially proposed by Fei Tony Liu, Kai Ming Ting and Zhi-Hua Zhou in 2008. It takes advantage of two quantitative properties of anomalous data points in a sample:

1. Few - anomalous data points are the minority, consisting of fewer instances
2. Different - anomalous data points have attribute-values that are very different from those of normal instances

Since anomalies are "few and different", they are easier to “isolate” compared to normal points. Isolation Forest builds an ensemble of “Isolation Trees” (iTrees) for the data set, and anomalies are the points that have shorter average path lengths.

In 2010, an extension of the algorithm - SCiforest was published to address the issues of clustered anomalies and utilize random hyperplanes to enhance the algorithm's ability to detect axis-paralleled anomalies. These abilities are lacking in the original implementation.

In a later paper, published in 2012 the same authors described a set of experiments to prove that iForest:

• has a low linear time complexity and a small memory requirement
• is able to deal with high dimensional data with irrelevant attributes
• can be trained with or without anomalies in the training set
• can provide detection results with different levels of granularity without re-training

In 2013 Zhiguo Ding and Minrui Fei proposed a framework based on iForest to resolve the problem of detecting anomalies in streaming data. More applications of iForest to streaming data are described in papers by Tan et al., Susto et al. and Weng et al.

One of the main problems encountered when applying iForest to anomaly detection is the way the “anomaly score” is computed. This problem was highlighted in a 2018 paper, wherein an improved iForest model named Extended Isolation Forest (EIF) was proposed. The paper describes the improvements made to the original model that enhance the consistency and reliability of the anomaly score produced for a given data point. It is not sure if the random slope enhancement proposed in EIF is novel, as a similar construct "random hyperplane" was proposed in SCiForest in 2010, which mitigates the same axis-parallel bias in iForest.

Algorithm

Fig. 2 - an example of isolating a non-anomalous point in a 2D Gaussian distribution.

At the basis of the Isolation Forest algorithm, there is the tendency of anomalous instances in a dataset to be easier to separate from the rest of the sample (isolate), compared to normal points. In order to isolate a data point, the algorithm recursively generates partitions on the sample by randomly selecting an attribute and then randomly selecting a split value between the minimum and maximum values allowed for that attribute.

Fig. 3 - an example of isolating an anomalous point in a 2D Gaussian distribution.

An example of random partitioning in a 2D dataset of normally distributed points is given in Fig. 2 for a non-anomalous point and Fig. 3 for a point that's more likely to be an anomaly. It is apparent from the pictures how anomalies require fewer random partitions to be isolated, compared to normal points.

Mathematically, recursive partitioning can be represented by a tree structure named Isolation Tree, while the number of partitions required to isolate a point can be interpreted as the length of the path, within the tree, to reach a terminating node starting from the root. For example, the path length of point $x_{i}$ in Fig. 2 is greater than the path length of $x_{j}$ in Fig. 3.

More formally, let $X=\{x_{1},\dots ,x_{n}\}$ be a set of d-dimensional points and $X'\subset X$. An Isolation Tree (iTree) is defined as a data structure with the following properties:

1. for each node $T$ in the Tree, $T$ is either an external-node with no child, or an internal-node with one “test” and exactly two daughter nodes ($T_{l}$ and $T_{r}$)
2. a test at node $T$ consists of an attribute $q$ and a split value $p$ such that the test $q<p$ determines the traversal of a data point to either $T_{l}$ oder $T_{r}$.

In order to build an iTree, the algorithm recursively divides $X'$ by randomly selecting an attribute $q$ and a split value $p$, until either

1. the node has only one instance, or
2. all data at the node have the same values.

When the iTree is fully grown, each point in $X$ is isolated at one of the external nodes. Intuitively, the anomalous points are those (easier to isolate, hence) with the smaller path length in the tree, where the path length $h(x_{i})$ of point $x_{i}\in X$ is defined as the number of edges $x_{i}$ traverses from the root node to get to an external node.

A probabilistic explanation of iTree is provided in the iForest original paper.

Properties of isolation forest

• Sub-sampling: since iForest does not need to isolate all normal instances, it can frequently ignore the big majority of the training sample. As a consequence, iForest works very well when the sampling size is kept small, a property that is in contrast with the great majority of existing methods, where a large sampling size is usually desirable.
• Swamping: when normal instances are too close to anomalies, the number of partitions required to separate anomalies increases, a phenomenon known as swamping, which makes it more difficult for iForest to discriminate between anomalies and normal points. One of the main reasons for swamping is the presence of too much data for the purpose of anomaly detection, which implies one possible solution to the problem is sub-sampling. Since iForest responds very well to sub-sampling in terms of performance, the reduction of the number of points in the sample is also a good way to reduce the effect of swamping.
• Masking: when the number of anomalies is high it is possible that some of those aggregate in a dense and large cluster, making it more difficult to separate the single anomalies and, in turn, to detect such points as anomalous. Similarly to swamping, this phenomenon (known as “masking”) is also more likely when the number of points in the sample is big and can be alleviated through sub-sampling.
• High Dimensional Data: one of the main limitations of standard, distance-based methods is their inefficiency in dealing with high dimensional datasets. The main reason for that is, in a high dimensional space every point is equally sparse, so using a distance-based measure of separation is pretty ineffective. Unfortunately, high-dimensional data also affects the detection performance of iForest, but the performance can be vastly improved by adding a features selection test like Kurtosis to reduce the dimensionality of the sample space.
• Normal Instances Only: iForest performs well even if the training set does not contain any anomalous point, the reason being that iForest describes data distributions in such a way that high values of the path length $h(x_{i})$ correspond to the presence of data points. As a consequence, the presence of anomalies is pretty irrelevant to iForest's detection performance.

Anomaly detection with isolation forest

Anomaly detection with Isolation Forest is a process composed of two main stages:

1. in the first stage, a training dataset is used to build iTrees.
2. in the second stage, each instance in the test set is passed through these iTrees, and a proper “anomaly score” is assigned to the instance.

Once all the instances in the test set have been assigned an anomaly score, it is possible to mark as “anomaly” any point whose score is greater than a predefined threshold, which depends on the domain the analysis is being applied to.

Anomaly score

The algorithm for computing the anomaly score of a data point is based on the observation that the structure of iTrees is equivalent to that of Binary Search Trees (BST): a termination to an external node of the iTree corresponds to an unsuccessful search in the BST. As a consequence, the estimation of average $h(x)$ for external node terminations is the same as that of the unsuccessful searches in BST, that is

where $n$ is the testing data size, $m$ is the size of the sample set and $H$ is the harmonic number, which can be estimated by $H(i)=ln(i)+\gamma$, where $\gamma =0.5772156649$ is the Euler-Mascheroni constant.

The value of c(m) above represents the average of $h(x)$ given $m$, so we can use it to normalise $h(x)$ and get an estimation of the anomaly score for a given instance x:

$s(x,m)=2^{\frac {-E(h(x))}{c(m)}}$$c(m)={\begin{cases}2H(m-1)-{\frac {2(m-1)}{n}}&{\text{for }}m>2\\1&{\text{for }}m=2\\0&{\text{otherwise}}\end{cases}}$

where $E(h(x))$ is the average value of $h(x)$ from a collection of iTrees. It is interesting to note that for any given instance $x$:

• if $s$ is close to $1$ then $x$ is very likely to be an anomaly
• if $s$ is smaller than $0.5$ then $x$ is likely to be a normal value
• if for a given sample all instances are assigned an anomaly score of around $0.5$, then it is safe to assume that the sample doesn't have any anomaly

Open source implementations

Original implementation:

• Isolation Forest, an algorithm that detects data-anomalies using binary trees written in R. Released by the paper's first author Liu, Fei Tony in 2009.

Other implementations (in alphabetical order):

• Isolation Forest - A Spark/Scala implementation, created by James Verbus from the LinkedIn Anti-Abuse AI team.
• Isolation Forest by H2O-3 - An implementation of Isolation Forest for Anomaly Detection by H2O-3.
• Package solitude implementation in R by Srikanth Komala Sheshachala.
• Python implementation with examples in scikit-learn.
• Spark iForest - A distributed implementation in Scala and Python, which runs on Apache Spark. Written by Yang, Fangzhou.
• PyOD IForest - Another Python implementation in the popular Python Outlier Detection (PyOD) library.

Other variations of Isolation Forest algorithm implementations:

• Extended Isolation Forest – An implementation of Extended Isolation Forest for Anomaly Detection by Sahand Hariri.

• Extended Isolation Forest by H2O-3 - An implementation of Extended Isolation Forest for Anomaly Detection by H2O-3.

• (Python, R, C/C++) Isolation Forest and variations by David Cortes - An implementation of Isolation Forest and its variations by David Cortes.

See also

• Anomaly detection
• Random forest