Anomaly Detection: Isolation Forests & LOF

Anomaly detection identifies observations that deviate so substantially from the remainder of the data as to arouse suspicion that they were generated by a different underlying mechanism.

Rather than attempting to model the complex multi-modal density profile of normal inliers, modern algorithms like Isolation Forests exploit two quantitative quantitative properties of anomalies: they are few in number and possess attribute values divergent from normal points.

Anomaly ScoreTree Ensembles

2^(-E[h(x)] / c(n))

Measures isolation depth relative to the expected path length of a random binary search tree.

1. Isolation Forest: Deriving Expected Path Length $c(n)$ #

An Isolation Tree (iTree) recursively bisects data points by selecting a feature at random and choosing a uniform random split threshold between the feature's minimum and maximum values.

Architecture Diagram

Rendering diagram...

Because anomalies reside in low-density peripheral regions, they require remarkably few random cuts to isolate into singleton leaves compared to normal points clustered densely together.

Derivation of BST Average Path Length $c(n)$ #

An iTree has an identical structure to an unsuccessful search in a Random Binary Search Tree (BST). We derive the average path length $c(n)$ for a dataset of size $n$ .

Step 1: Formulate the Recurrence Relation

Let $c(n)$ denote the average depth of an unsuccessful search in a BST constructed from $n$ elements. When inserting a new node, it can fall into any of the $n$ intervals between sorted keys with equal probability $\frac{1}{n}$ .

The recurrence relation is:

c(n) = 1 + \frac{1}{n} \sum_{i=1}^{n} \Big( c(i - 1) + c(n - i) \Big)

By symmetry, $\sum_{i=1}^n c(i - 1) = \sum_{i=1}^n c(n - i)$ :

c(n) = 1 + \frac{2}{n} \sum_{i=0}^{n-1} c(i)

Step 2: Eliminate the Summation via Difference Equations

Multiply by $n$ :

n c(n) = n + 2 \sum_{i=0}^{n-1} c(i)

Write the identical relation for $n - 1$ :

(n - 1) c(n - 1) = (n - 1) + 2 \sum_{i=0}^{n-2} c(i)

Subtract the second equation from the first:

n c(n) - (n - 1) c(n - 1) = 1 + 2 c(n - 1) = 1 + (n + 1) c(n - 1)

Rearranging terms:

n c(n) = 1 + (n + 1) c(n - 1) \implies \frac{c(n)}{n + 1} = \frac{c(n - 1)}{n} + \frac{1}{n(n + 1)}

Step 3: Expand the Telescoping Sum

Using partial fraction decomposition $\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}$ :

\frac{c(n)}{n + 1} = \frac{c(1)}{2} + \sum_{k=2}^n \left( \frac{1}{k} - \frac{1}{k+1} \right)

Evaluating the summation via Harmonic numbers $H_n = \sum_{k=1}^n \frac{1}{k}$ :

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

Step 4: Apply the Euler-Mascheroni Constant

Approximating the Harmonic series $H_{n-1} \approx \ln(n - 1) + \gamma$ , where $\gamma \approx 0.5772156649$ is the Euler-Mascheroni constant:

c(n) = 2 \Big( \ln(n - 1) + 0.5772156649 \Big) - \frac{2(n - 1)}{n}

This value $c(n)$ serves as the universal normalization constant.

2. The Anomaly Score Function#

For an ensemble of $T$ isolation trees, let $h(x)$ denote the path length (number of edges traversed from root to leaf) for point $x$ . The mean path length is $\mathbb{E}[h(x)] = \frac{1}{T} \sum_{t=1}^T h_t(x)$ .

The Anomaly Score $s(x, n)$ is defined as:

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

Architecture Diagram

Rendering diagram...

When $\mathbb{E}[h(x)] \to 0$ : $s \to 2^0 = 1.0$ (point isolated immediately; definite anomaly).
When $\mathbb{E}[h(x)] \to c(n)$ : $s \to 2^{-1} = 0.5$ (point exhibits average depth; ordinary instance).
When $\mathbb{E}[h(x)] \to n - 1$ : $s \to 2^{-(n-1)/c(n)} \approx 0$ (deep leaf; structural inlier).

3. Local Outlier Factor (LOF)#

For datasets with variable cluster densities, distance-to-centroid metrics fail because an outlier near a dense cluster may have a smaller absolute distance than an inlier in a sparse cluster.

Local Outlier Factor (LOF) (Breunig et al., 2000) measures anomalousness relative to local neighborhood density.

Architecture Diagram

Rendering diagram...

Step 1: Reachability Distance

The reachability distance of point $p$ from neighbor $o$ is:

\text{reach-dist}_k(p, o) = \max\Big( d_k(o), \text{dist}(p, o) \Big)

Where $d_k(o)$ is the distance from $o$ to its $k$ -th nearest neighbor.

Step 2: Local Reachability Density (lrd)

The local reachability density of $p$ is the inverse of the average reachability distance of its $k$ -nearest neighbors $N_k(p)$ :

\text{lrd}_k(p) = \frac{|N_k(p)|}{\sum_{o \in N_k(p)} \text{reach-dist}_k(p, o)}

Step 3: Local Outlier Factor

The LOF score is the average ratio of the $\text{lrd}$ of its neighbors to the $\text{lrd}$ of $p$ :

\text{LOF}_k(p) = \frac{1}{|N_k(p)|} \sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}

If $\text{LOF} \approx 1$ : Point has density comparable to its neighbors (inlier).
If $\text{LOF} \gg 1$ : Point has substantially lower density than its neighbors (outlier).

4. From-Scratch Implementation: Zero Dependencies#

The following implementations construct an Isolation Forest from scratch in Python and Rust without third-party dependencies.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import math
import random
from typing import List, Optional

class IsolationTreeNode:
    def __init__(self, size: int):
        self.size = size
        self.split_feature: Optional[int] = None
        self.split_value: Optional[float] = None
        self.left: Optional['IsolationTreeNode'] = None
        self.right: Optional['IsolationTreeNode'] = None

    @property
    def is_leaf(self) -> bool:
        return self.left is None and self.right is None

class IsolationTree:
    def __init__(self, max_depth: int):
        self.max_depth = max_depth
        self.root: Optional[IsolationTreeNode] = None

    def fit(self, X: List[List[float]], current_depth: int = 0) -> IsolationTreeNode:
        num_samples = len(X)
        if current_depth >= self.max_depth or num_samples <= 1:
            return IsolationTreeNode(size=num_samples)

        num_features = len(X[0])
        # Randomly choose split feature
        feat = random.randint(0, num_features - 1)
        vals = [row[feat] for row in X]
        min_v, max_v = min(vals), max(vals)

        if min_v == max_v:
            return IsolationTreeNode(size=num_samples)

        # Uniform random split threshold
        split_val = random.uniform(min_v, max_v)
        left_X = [row for row in X if row[feat] < split_val]
        right_X = [row for row in X if row[feat] >= split_val]

        node = IsolationTreeNode(size=num_samples)
        node.split_feature = feat
        node.split_value = split_val
        node.left = self.fit(left_X, current_depth + 1)
        node.right = self.fit(right_X, current_depth + 1)
        return node

    def path_length(self, sample: List[float], node: IsolationTreeNode, current_depth: int = 0) -> float:
        if node.is_leaf:
            # Add average path adjustment for unbuilt subtrees
            if node.size > 1:
                return current_depth + IsolationForestFromScratch.c_factor(node.size)
            return float(current_depth)

        feat = node.split_feature
        if sample[feat] < node.split_value:
            return self.path_length(sample, node.left, current_depth + 1)
        return self.path_length(sample, node.right, current_depth + 1)

class IsolationForestFromScratch:
    def __init__(self, n_estimators: int = 50, max_samples: int = 256):
        self.n_estimators = n_estimators
        self.max_samples = max_samples
        self.trees: List[IsolationTree] = []

    @staticmethod
    def c_factor(n: int) -> float:
        if n <= 1: return 0.0
        if n == 2: return 1.0
        # 2 * (ln(n - 1) + 0.5772156649) - (2 * (n - 1) / n)
        return 2.0 * (math.log(n - 1) + 0.5772156649) - (2.0 * (n - 1) / n)

    def fit(self, X: List[List[float]]) -> None:
        random.seed(42)
        num_samples = len(X)
        subsample_size = min(self.max_samples, num_samples)
        max_depth = math.ceil(math.log2(max(subsample_size, 2)))

        self.trees = []
        for _ in range(self.n_estimators):
            sample_sub = random.sample(X, subsample_size)
            itree = IsolationTree(max_depth=max_depth)
            itree.root = itree.fit(sample_sub)
            self.trees.append(itree)

    def anomaly_score(self, X: List[List[float]]) -> List[float]:
        num_samples = len(X)
        c = self.c_factor(min(self.max_samples, num_samples))
        scores = []

        for sample in X:
            avg_h = sum(tree.path_length(sample, tree.root) for tree in self.trees) / self.n_estimators
            score = 2.0 ** (-avg_h / c) if c > 0 else 0.5
            scores.append(score)

        return scores

if __name__ == "__main__":
    X_train = [
        [1.0, 1.0], [1.1, 1.2], [0.9, 0.8], [1.2, 1.1], [1.0, 0.9],
        [2.0, 2.1], [2.1, 1.9], [1.9, 2.0], [2.2, 2.2],
        [15.0, 14.0] # Severe Anomaly
    ]

    forest = IsolationForestFromScratch(n_estimators=30)
    forest.fit(X_train)
    scores = forest.anomaly_score(X_train)
    print("Anomaly Scores (Higher => More Anomalous):")
    for sample, s in zip(X_train, scores):
        print(f"  Sample {sample} -> Score: {s:.4f}")

5. Active Knowledge Checks#

Concept check

Why do anomalies in an Isolation Forest yield an anomaly score s(x, n) approaching 1.0?

Concept check

What unique problem in clustering and anomaly detection does the Local Outlier Factor (LOF) address that global distance metrics fail to capture?

1. Isolation Forest: Deriving Expected Path Length c(n)c(n)c(n)#

Derivation of BST Average Path Length c(n)c(n)c(n)#

Step 1: Formulate the Recurrence Relation

Step 2: Eliminate the Summation via Difference Equations

Step 3: Expand the Telescoping Sum

Step 4: Apply the Euler-Mascheroni Constant

2. The Anomaly Score Function#

3. Local Outlier Factor (LOF)#

Step 1: Reachability Distance

Step 2: Local Reachability Density (lrd)

Step 3: Local Outlier Factor

4. From-Scratch Implementation: Zero Dependencies#

5. Active Knowledge Checks#

1. Isolation Forest: Deriving Expected Path Length $c(n)$ #

Derivation of BST Average Path Length $c(n)$ #