Isolation Forest

Unlike profile-based methods that construct a model of normality, Isolation Forest explicitly isolates anomalies. Anomalies are data points that are few and different, making them more susceptible to isolation through random partitioning. The algorithm recursively generates random splits on randomly selected features, creating a binary tree structure. Because anomalies have distinct attribute values, they require fewer random splits to be isolated in a leaf node. The path length—the number of edges traversed from the root to the leaf—serves as the anomaly score, with shorter paths indicating higher anomaly likelihood.

The algorithm constructs an ensemble of multiple isolation trees (iTrees) to ensure stable and reliable anomaly scoring. Each iTree is built from a random subsample of the training data, typically 256 or 512 instances, without replacement. This subsampling provides two critical benefits:

• Swamping and masking reduction: By limiting the sample size, the algorithm prevents normal instances from obscuring anomalies.
• Computational efficiency: Training each tree on a small subsample dramatically reduces time complexity to O(n log n) and memory footprint. The final anomaly score is the average path length across all trees, normalized by the expected path length of an unsuccessful search in a Binary Search Tree.

Isolation Forest fundamentally differs from distance-based methods like Local Outlier Factor (LOF) or density-based methods like DBSCAN. It does not require:

• Pairwise distance calculations between data points
• Density estimation or kernel functions
• Assumptions about the underlying data distribution This makes it exceptionally well-suited for high-dimensional datasets where distance metrics suffer from the curse of dimensionality. The algorithm's performance remains robust as dimensionality increases, unlike k-Nearest Neighbor-based detectors whose discriminative power degrades in sparse high-dimensional spaces.

A density-based anomaly detection algorithm that identifies outliers by measuring the local density deviation of a data point relative to its k-nearest neighbors. Unlike Isolation Forest's global partitioning approach, LOF computes a local reachability density ratio, making it effective at detecting anomalies in datasets with varying regional densities. A point is flagged as anomalous if its local density is significantly lower than that of its neighbors. This method is computationally more expensive than Isolation Forest due to pairwise distance calculations, scaling as O(n²) in naive implementations.

A support vector algorithm that learns a decision boundary surrounding normal training data in a high-dimensional kernel space. The model maximizes the margin between the origin and the normal samples, treating the origin as the sole representative of the anomaly class. Key characteristics:

• Uses the nu parameter to control the upper bound on outlier fraction
• Effective for high-dimensional datasets where density estimation fails
• Requires careful kernel selection (typically RBF) and parameter tuning
• Unlike Isolation Forest, does not naturally produce anomaly scores without distance-to-boundary calculation