Isolation Forest › Formula

The mathematical foundation of Isolation Forest centers around the concept of path length and anomaly score calculation. Let's walk through the key formulas step by step, starting with the most intuitive concepts and building up to the complete mathematical framework.

The core concept in Isolation Forest is to assess how easily a data point can be separated, or "isolated," from the rest of the dataset. This is achieved by constructing a tree structure, known as an isolation tree, where each internal node represents a split on a randomly selected feature at a randomly chosen split value. The process of isolating a data point involves traversing the tree from the root node down to a leaf node that contains the point in question.

For a given data point, denoted as $x$, the "path length" $h(x)$ is defined as the number of edges (or splits) encountered along the path from the root node of the tree to the external node (leaf node) that contains $x$. In other words, the path length quantifies the number of random partitions required to isolate $x$ from all other points in the dataset.

Mathematically, if we consider a specific isolation tree $T$ and a data point $x$, the path length is given by:

$$h(x) = \text{number of edges from the root node to the leaf node that contains } x$$

The underlying intuition is as follows: data points that are "normal" (i.e., typical or common) tend to be located in dense regions of the data space, often clustering together with many other points. As a result, it takes more random splits to isolate such points, leading to longer path lengths. In contrast, "anomalies" (i.e., rare or unusual data points) are more likely to be located in sparse regions or far from clusters of normal data. These points can often be isolated with fewer splits, resulting in shorter path lengths.

In summary, the path length is a measure of how isolated a data point is within the dataset: shorter path lengths indicate that a point is easier to isolate and is therefore more likely to be an anomaly, while longer path lengths suggest that a point is more deeply embedded within a cluster of normal data.

Since Isolation Forest is based on an ensemble of randomly constructed isolation trees, the path length for a single data point can vary from tree to tree due to the inherent randomness in feature selection and split values. To obtain a stable measure of how easily a point can be isolated, we compute the average path length across all trees in the ensemble.

For a given data point $x$ and an ensemble consisting of $t$ isolation trees, the average path length is calculated as:

$$\bar{h}(x) = \frac{1}{t} \sum_{i=1}^{t} h_i(x)$$

where $h_i(x)$ denotes the path length of point $x$ in the $i$-th tree. By averaging over all trees, we mitigate the effects of randomness and outliers that may occur in individual trees, resulting in a more stable and representative estimate of the isolation difficulty for each data point. This ensemble averaging is a key step in the algorithm, as it ensures that the anomaly score is not overly influenced by any single tree's random partitioning, but instead reflects the general tendency of the data point to be isolated across many different random partitions.

To fairly compare the path lengths of different data points and interpret their anomaly scores, we need to normalize the observed path lengths. This normalization is based on the expected path length for a data point in a randomly generated dataset, which is a reference for what is "typical" behavior in the absence of anomalies.

In the context of Isolation Forest, this expected path length is closely related to the average number of comparisons required to find a data point in a randomly constructed binary search tree. For a dataset with $n$ points, the expected path length, denoted as $c(n)$, is given by:

$$c(n) = 2H(n-1) - \frac{2(n-1)}{n}$$

where $H(n-1)$ is the $(n-1)$-th harmonic number and $n$ is the number of points in the dataset. Let's expand and analyze this formula in detail.

A harmonic number is a mathematical quantity that arises frequently in probabilistic and statistical analysis, including the analysis of computer algorithms. The $n$-th harmonic number, denoted as $H(n)$, is defined as the sum of the reciprocals of the first $n$ positive integers:

$$H(n) = \sum_{k=1}^{n} \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$$

Harmonic numbers grow slowly as $n$ increases, and for large $n$, they can be approximated by the natural logarithm of $n$ plus a constant (the Euler-Mascheroni constant, $\gamma$). In the context of Isolation Forest, the harmonic number is used to calculate the expected path length in a random binary tree, which is a normalization factor for the anomaly score.

$$H(n-1) = \sum_{k=1}^{n-1} \frac{1}{k}$$

The natural interpretation of the harmonic number $H(n)$ is that it represents the expected number of steps required to select a specific item from a set of $n$ items if, at each step, you randomly pick and remove one of the remaining items until your target is chosen. In other words, it is the average number of times you need to sample without replacement from a set of $n$ items to eventually select a particular item.

In algorithmic and probabilistic contexts, the harmonic number often arises as the expected value of certain random processes. For example, in the context of binary search trees, $H(n)$ gives the expected depth of a randomly chosen node, or the average number of comparisons needed to find an item. More generally, the harmonic number quantifies the cumulative effect of repeatedly dividing or sampling from a set, and its slow (logarithmic) growth reflects the diminishing returns of each additional division or sample as the set size increases.

Thus, the harmonic number naturally measures the "average effort" or "expected number of steps" in processes that involve sequentially reducing a set by random selection or partitioning.

For large $n$, we can use an asymptotic expansion, a mathematical technique that approximates a function by a series whose terms become increasingly accurate as $n$ grows, to estimate the harmonic number. The following formula is derived from the Euler-Maclaurin formula, which connects sums and integrals and provides a way to approximate sums like the harmonic series with logarithmic and correction terms:

$$H(n-1) \approx \ln(n-1) + \gamma + \frac{1}{2(n-1)} - \frac{1}{12(n-1)^2} + \frac{1}{120(n-1)^4} - \cdots$$

where $\gamma \approx 0.5772$ is the Euler-Mascheroni constant. The first few terms provide a very accurate approximation for moderate to large $n$.

The expected path length $c(n)$ is derived from the average depth of a node in a random binary search tree. The intuition is that, in a random binary tree, the expected number of comparisons to isolate a point is related to the sum of the harmonic numbers, since each split divides the data and the process recurses on the resulting partitions.

The formula:

$$c(n) = 2H(n-1) - \frac{2(n-1)}{n}$$

where:

• $H(n-1)$ is the $(n-1)$-th harmonic number
• $n$ is the number of points in the dataset

can be understood as follows:

• The term $2H(n-1)$ accounts for the expected number of comparisons (or splits) needed to isolate a point, considering both the left and right branches at each split.
• The correction term $-\frac{2(n-1)}{n}$ adjusts for the fact that, in a finite sample, the last partition may not be perfectly balanced, and ensures the expectation is exact for all $n$.

Let's see how this works for small $n$:

• For $n=2$:
  • $H(1) = 1$
  • $c(2) = 2 \times 1 - \frac{2 \times 1}{2} = 2 - 1 = 1$
• For $n=3$:
  • $H(2) = 1 + \frac{1}{2} = 1.5$
  • $c(3) = 2 \times 1.5 - \frac{2 \times 2}{3} = 3 - \frac{4}{3} = \frac{5}{3} \approx 1.666...$

As $n$ increases, $c(n)$ grows slowly.

• $H(n-1)$ is the $(n-1)$-th harmonic number, which can be written as a sum or approximated by a logarithm plus correction terms.
• $c(n)$ gives the expected path length for a random point in a random binary tree of $n$ points, and is used to normalize the observed average path length in Isolation Forest.
• This normalization allows us to compare path lengths across datasets of different sizes and interpret anomaly scores in a consistent way.

The harmonic number $H(n-1)$ captures the average depth of a node in a random binary tree, which is analogous to the number of splits required to isolate a point when the splits are made randomly. The formula for $c(n)$ refines this expectation to account for the specific way isolation trees are built: each split randomly partitions the data, and the process continues recursively until each point is isolated.

By using $c(n)$ as a normalization factor, we can compare the observed average path length $\bar{h}(x)$ for a data point $x$ to what would be expected if the data were distributed randomly. If a point is isolated much faster than $c(n)$ would predict (i.e., with a much shorter path length), it is likely to be an anomaly. Conversely, if its path length is close to or longer than $c(n)$, it behaves like a typical, non-anomalous point. This normalization makes the anomaly scores interpretable and comparable across datasets of different sizes.

The anomaly score combines the average path length with the expected path length to produce a normalized measure between 0 and 1. The formula is:

$$s(x,n) = 2^{-\frac{\bar{h}(x)}{c(n)}}$$

where:

-$s(x,n)$: the anomaly score for data point $x$ in a dataset of size $n$ (bounded between 0 and 1)

• $\bar{h}(x)$: the average path length of point $x$ across all isolation trees in the ensemble
• $c(n)$: the expected path length for a point in a randomly generated dataset of size $n$ (normalization constant)
• $n$: the number of points in the dataset

Let's break down this formula step by step:

1. The ratio $\frac{\bar{h}(x)}{c(n)}$: This compares the actual average path length to the expected path length for random data. If a point has a path length close to the expected value, this ratio will be close to 1. If it has a much shorter path length (indicating it's easier to isolate), this ratio will be much less than 1.

2. The negative exponent: We use $-\frac{\bar{h}(x)}{c(n)}$ as the exponent. This means that shorter path lengths (easier to isolate) result in larger negative exponents, which in turn produce larger anomaly scores.

3. The base 2: The anomaly score formula uses 2 as the base of the exponent, which affects how the score is interpreted:

• Interpretation at ratio 1: When the average path length $\bar{h}(x)$ equals the expected path length $c(n)$ (i.e., $\frac{\bar{h}(x)}{c(n)} = 1$), the anomaly score becomes $2^{-1} = 0.5$. This value is a natural threshold: points with scores below 0.5 are more "normal" (harder to isolate than expected), while those above 0.5 are more "anomalous" (easier to isolate).

  • Interpretation at ratio 0: When the ratio is 0 (i.e., the path length is extremely short, so $\bar{h}(x) = 0$), the score is $2^0 = 1$. This represents the most anomalous possible case, where a point is isolated immediately, indicating it is highly distinct from the rest of the data.

  • Intermediate values: As the ratio increases from 0 to 1, the score decreases smoothly from 1 to 0.5. For example, if $\frac{\bar{h}(x)}{c(n)} = 0.5$, the score is $2^{-0.5} \approx 0.707$, indicating a point that is somewhat easier to isolate than average.

• Ratios greater than 1: If the path length is longer than expected (i.e., $\frac{\bar{h}(x)}{c(n)} > 1$), the score drops below 0.5.suggesting it is very "normal" or deeply embedded in the data distribution.

  • Why base 2?: The choice of base 2 is not strictly required, but it provides a convenient and interpretable scale. Using base 2 means that each unit increase in the ratio halves the anomaly score, creating a clear and intuitive relationship between path length and anomaly score. This exponential decay ensures that small differences in path length near the lower end (shorter paths) have a larger impact on the score, which helps to highlight truly anomalous points.

The anomaly score has a clear interpretation:

• Score close to 1: Indicates an anomaly (easy to isolate)
• Score close to 0: Indicates normal data (hard to isolate)
• Score around 0.5: Indicates data that behaves like random data

The anomaly score function has several important mathematical properties. First, it's bounded between 0 and 1, with 0 representing the most normal behavior and 1 representing the most anomalous behavior. Second, the function is monotonically decreasing with respect to path length, meaning that as path length increases (harder to isolate), the anomaly score decreases.

The choice of base 2 in the exponential function is somewhat arbitrary but provides a nice interpretation where a score of 0.5 represents the threshold between normal and anomalous behavior. The function is also continuous and differentiable, which can be useful for optimization and analysis purposes.