Abstract
Extreme regions in the feature space are of particular concern for anomaly detection: anomalies are likely to be located in the tails, whereas data scarcity in such regions makes it difficult to distinguish them from "normal" extreme observations. This paper introduces an unsupervised algorithm that detects anomalies in the tails of multivariate data by focusing on their angular distribution. By projecting extreme observations onto a unit sphere and using Minimum Volume (MV) sets, the method identifies extreme events with unusual directions, providing a robust framework for high-stakes monitoring.
Introduction: The "Weird" vs. the "Extreme"
In anomaly detection, the "tails" of a distribution—where values are exceptionally large—are often the primary area of interest. A common assumption is that extreme values are inherently anomalous. However, in complex systems like aviation safety or network monitoring, a spike in a single variable might be normal, while a specific combination of spikes signals a catastrophe. The challenge lies in separating "normal extremes" from true anomalies based on the geometry of rare events.
Methodology
The proposed approach combines Multivariate Extreme Value Theory (EVT) with Empirical Minimum Volume sets (MV-sets) through a three-step pipeline.
1. Rank-Based Standardization
To handle data with different units and marginal distributions, the authors employ a rank transformation. This maps the data to a common scale (Frechet margins), making the method distribution-free regarding the margins. This step ensures that the dependence structure—the "shape" of how variables interact at extremes—is preserved regardless of individual feature scaling.
2. Spherical Projection and Angular Measure
The core innovation involves focusing on the "directions" of extreme events. By projecting observations where at least one component is large onto a unit sphere ($S_{d-1}$), the algorithm isolates the angular measure. In EVT, this measure describes the asymptotic dependence structure of the variables.
3. Empirical MV-set Estimation
The algorithm "paves" the sphere with a grid of hypercubes to estimate the density of the angular measure. By counting extreme points within these cubes, the method identifies the densest regions on the sphere.
Anomalies are then defined as points falling into low-density or "empty" regions of this spherical map. A scoring function $\hat{s}$ is constructed by combining the radial component (magnitude) and the angular component (direction).
Experimental Evaluation
The method was evaluated against standard baselines, including Isolation Forest and One-Class SVM (OCSVM), across synthetic and real-world datasets such as flight data (Shuttle) and network intrusion (KDD Cup '99).
Key results include:
- Superior Performance in Tails: The method achieved the highest ROC-AUC on 3 out of 5 real-world datasets when focusing specifically on the top $k$ extreme points.
- Robustness to Scaling: By using rank-transformation, the algorithm avoids the sensitivity to feature scaling that often plagues K-Means or SVM-based approaches.
- Theoretical Convergence: The authors provide a statistical rate bound, proving that the empirical MV-set converges to the true theoretical "normal" region as more data is collected.
Conclusion
By shifting the focus from magnitude to direction in extreme regions, this work provides a specialized tool for detecting anomalies where data is most scarce. While the current grid-based "paving" faces challenges in very high dimensions, the use of angular measures on the sphere offers a theoretically grounded and practically effective approach to reducing false alarms in critical monitoring systems.
Reference: Thomas, A., Clémençon, S., Gramfort, A., & Sabourin, A. (2017). Anomaly Detection in Extreme Regions via Empirical MV-sets on the Sphere. Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS).
Summary updated