Anomaly Detection in High-Dimensional Data

Finding Needles in High-Dimensional Haystacks: Techniques and Hurdles

Authored by: Loveleen Narang

Date: November 2, 2024

Introduction: The Quest for the Unusual

Anomaly Detection, also known as outlier detection, is the task of identifying data points, events, or observations that deviate significantly from the majority of the data, raising suspicions by differing from normal behavior. These anomalies can represent critical incidents such as fraudulent transactions, network intrusions, manufacturing defects, system failures, or novel medical conditions.

While anomaly detection is challenging in itself, it becomes significantly harder when dealing with High-Dimensional Data – datasets where each data point \( x \) is described by a large number of features or dimensions \( d \) (Formula 1: \( x \in \mathbb{R}^d, d \gg 1 \)). Modern datasets from domains like cybersecurity, finance, bioinformatics, and sensor networks often possess hundreds or thousands of dimensions. This high dimensionality introduces unique challenges collectively known as the "Curse of Dimensionality", rendering many traditional anomaly detection techniques ineffective. This article explores the specific challenges and prominent techniques for tackling anomaly detection in high-dimensional spaces.

The Curse of Dimensionality: Why High Dimensions are Hard

As the number of dimensions \( d \) increases, several phenomena emerge that complicate anomaly detection:

• Distance Concentration: In high dimensions, the distances between pairs of points tend to become statistically indistinguishable. Standard distance metrics like Euclidean distance (Formula 2: \( ||x - y||_2 = \sqrt{\sum (x_i - y_i)^2} \)) lose their discriminative power, making it hard to separate outliers based solely on distance. Manhattan distance (Formula 3: \( ||x - y||_1 = \sum |x_i - y_i| \)) can sometimes be less affected.
• Data Sparsity: The volume of the space grows exponentially with dimensionality. A fixed number of data points becomes increasingly sparse, making density estimation extremely difficult and unreliable.
• Irrelevant Features: High-dimensional data often contains many irrelevant or noisy features that can mask the anomalous nature of a data point in the relevant dimensions. Anomalies might only be apparent in specific low-dimensional subspaces.
• Subspace Anomalies: Anomalies might not be outliers in the full feature space but only within specific combinations (subspaces) of features.
• Computational Cost: Many algorithms scale poorly with the number of dimensions, increasing computational time and memory requirements significantly.

Techniques for High-Dimensional Anomaly Detection

Various strategies have been developed to specifically address the challenges of high dimensionality.

Projection-Based Methods

These methods project the high-dimensional data onto a lower-dimensional space where anomalies might be easier to detect, assuming anomalies behave differently under projection.

• Principal Component Analysis (PCA): Finds principal components (directions of maximum variance). Normal data is expected to project well onto the principal subspace spanned by the first \( k \) components, while anomalies might deviate significantly.
  • Process: Compute covariance matrix \( \Sigma \), find eigenvectors (principal components \( W \)), project data \( z = W_k^T (x - \mu) \). Formulas (7, 8, 9): Mean \( \mu \), Covariance \( \Sigma \), Eigenvectors \( W \).
  • Anomaly Score: Can be based on the reconstruction error (distance between original point \( x \) and its projection back from the subspace \( \hat{x} = W_k z + \mu \)) or the distance in the residual subspace. Formula (10): Reconstruction Error \( ||x - \hat{x}||^2 \).
• Random Projections: Projects data onto random lower-dimensional subspaces. Faster than PCA, relies on the Johnson-Lindenstrauss lemma which states that distances are approximately preserved under random projection. Anomalies might stand out consistently across multiple random projections.

Subspace and Feature Selection Methods

These methods assume anomalies are only visible in certain subsets of features (subspaces) and try to identify these relevant subspaces.

• Subspace Search: Algorithms like HiCS (High Contrast Subspaces) search for subspaces where the data distribution significantly differs from the full space, potentially highlighting anomalies.
• Feature Bagging: Trains multiple anomaly detectors on random subsets of features and combines their outlier scores (e.g., by averaging). This makes the detection more robust to irrelevant features.

Distance and Density-Based Methods (with High-D Caveats)

While standard distance/density methods suffer in high dimensions, adaptations exist.

• k-NN Based: Measure distance to k-th nearest neighbor (\( D_k(x) \)) (Formula 11) or average distance to k neighbors. Anomalies are expected to be far from their neighbors. Less reliable in high-D due to distance concentration. Using robust distance metrics like Mahalanobis distance (Formula 4: \( D_M(x) = \sqrt{(x - \mu)^T \Sigma^{-1} (x - \mu)} \)) which accounts for correlations can sometimes help, but estimating \( \Sigma \) (Formula 6) is difficult in high-D.
• Local Outlier Factor (LOF): Compares the local density around a point to the local densities of its neighbors. A point with significantly lower density than its neighbors is considered an outlier. Calculates reachability distance (Formula 12), local reachability density (Formula 13: \( lrd_k(p) \)), and finally LOF (Formula 14: \( LOF_k(p) \)). Suffers from distance concentration and computational cost (\(O(N^2)\) naively) in high dimensions.
• Kernel Density Estimation (KDE): Estimates the probability density function \( \hat{p}(x) \) (Formula 15: \( \hat{p}(x) = \frac{1}{N h^d} \sum K(\frac{x - x_i}{h}) \)) (Formula 16: Kernel \(K\), Formula 17: Bandwidth \(h\)). Points in low-density regions are outliers. Very difficult to apply effectively in high dimensions due to sparsity.

Isolation-Based Methods

These methods explicitly try to isolate anomalies, leveraging the idea that anomalies are "few and different" and thus easier to separate from the bulk of the data.

• Isolation Forest: Builds an ensemble of random trees (Isolation Trees). In each tree, data is recursively partitioned by randomly selecting a feature and a random split value within the feature's range until instances are isolated. Anomalies, being different, tend to be isolated in paths closer to the root (shorter path length \( h(x) \)).
  • Anomaly Score: Based on the average path length \( E[h(x)] \) across all trees, normalized by the average path length for a sample size \( n \). Formula 18: \( s(x, n) = 2^{-\frac{E[h(x)]}{c(n)}} \). Score near 1 indicates anomaly, near 0.5 indicates normal. Formulas (19, 20, 21): \( h(x), E[h(x)], c(n) \).
  • Advantages: Computationally efficient (\( O(N \log N) \)), requires less memory, works well in high dimensions as it doesn't rely on distance metrics, robust to irrelevant features due to random feature selection.

Reconstruction-Based Methods (Deep Learning)

These methods, often using neural networks, learn a compressed representation of normal data and assume anomalies cannot be accurately reconstructed from this compressed form.

• Autoencoders (AE): Neural networks trained to reconstruct their input. Consist of an Encoder \( f_{enc} \) mapping input \( x \) to a lower-dimensional latent representation \( z \), and a Decoder \( f_{dec} \) mapping \( z \) back to a reconstruction \( \hat{x} \). Formulas (22, 23): \( z = f_{enc}(x) \), \( \hat{x} = f_{dec}(z) \). Trained on normal data to minimize reconstruction error (e.g., MSE). Formula (24): \( L(x, \hat{x}) = ||x - \hat{x}||^2 \). Anomalies, unseen during training, are expected to yield high reconstruction errors.
• Variational Autoencoders (VAE): Probabilistic version of AEs, modeling the latent space as a distribution. Anomaly score can be based on reconstruction probability or deviation in the latent space. Loss includes reconstruction term and KL divergence regularizer. Formula (25): \( L_{ELBO} = E_{q(z|x)}[\log p(x|z)] - D_{KL}(q(z|x) || p(z)) \).
• GAN-based Anomaly Detection (e.g., AnoGAN): Train a GAN on normal data. Anomalies can be detected because: 1) The discriminator might assign low probability to them. 2) The generator cannot produce similar images from the latent space. Anomalies can be detected by mapping a test image to the latent space (finding \( z \) that minimizes reconstruction error \( ||x - G(z)||^2 \)) and using the reconstruction error or discriminator score as the anomaly score.

One-Class Classification Methods

These methods learn a boundary around the normal data points. Instances falling outside this boundary are classified as anomalies.

• One-Class SVM (OC-SVM): An adaptation of Support Vector Machines for unsupervised anomaly detection. It finds a hyperplane (in a high-dimensional feature space defined by a kernel \( \phi \)) that separates the majority of the data points from the origin with maximum margin.
  • Objective (simplified): Minimize \( \frac{1}{2} ||w||^2 + \frac{1}{\nu N} \sum \xi_i - \rho \) subject to constraints. Formula (26, 27, 28): parameters \( w, \rho, \xi_i \), kernel \( \phi \), hyperparameter \( \nu \).
  • Decision Function: \( f(x) = \text{sgn}(w \cdot \phi(x) - \rho) \). Points with \( f(x) < 0 \) are anomalies.

Evaluation Metrics for Anomaly Detection

Since anomaly detection is often a highly imbalanced problem (few anomalies vs. many normal points), standard accuracy is not suitable. Common metrics include:

• Precision: Proportion of detected anomalies that are actually anomalies. Formula (29): \( P = \frac{TP}{TP + FP} \).
• Recall (Sensitivity, True Positive Rate): Proportion of actual anomalies that were correctly detected. Formula (30): \( R = \frac{TP}{TP + FN} \).
• F1-Score: Harmonic mean of Precision and Recall. Formula (31): \( F1 = 2 \cdot \frac{P \times R}{P + R} \).
• ROC Curve & AUC-ROC: Plots True Positive Rate vs. False Positive Rate at various thresholds. Area Under the Curve (AUC) summarizes performance.
• Precision-Recall Curve & AUC-PRC: Plots Precision vs. Recall. Often more informative than ROC for imbalanced datasets. Area Under the PR Curve (AUC-PRC) is a key metric.

Formulas (32-35): TP, FP, TN, FN (True/False Positives/Negatives).

Conclusion

Anomaly detection in high-dimensional data is a critical yet challenging task due to the curse of dimensionality. Standard distance and density-based methods often falter as dimensions increase. Successful techniques typically involve dimensionality reduction (PCA), identifying relevant subspaces, using robust isolation mechanisms (Isolation Forest), or learning representations of normality via reconstruction (Autoencoders, GANs) or boundary description (One-Class SVM). Deep learning methods, particularly autoencoders, have shown great promise in automatically learning relevant features and representations from complex, high-dimensional data. The choice of method depends heavily on the specific characteristics of the data, the nature of expected anomalies, and computational constraints. As datasets continue to grow in size and dimensionality, research into scalable, robust, and interpretable anomaly detection methods will remain a vital area within machine learning.

(Formula count check: Includes High-D def, Euclidean Dist, Manhattan Dist, Mahalanobis Dist, Mean, Covariance, PCA Max Var, PCA Projection, PCA Reconstruction, PCA Recon Error, kNN Dist D_k, LOF reach_dist, LOF lrd, LOF N_k(p), LOF formula, KDE formula, Kernel K, Bandwidth h, iForest h(x), iForest E[h(x)], iForest score s, iForest c(n), AE Encoder, AE Decoder, AE Loss, VAE ELBO, OC-SVM Objective (concept), OC-SVM kernel phi, Precision, Recall, F1 Score, TP, FP, TN, FN. Total > 35).