Introduction
Anomaly detection—the process of identifying data points that deviate significantly from a "normal" baseline—is a notoriously difficult challenge in high-dimensional feature spaces. Traditional methods typically face two major hurdles. First is the curse of dimensionality: standard density estimation techniques, which attempt to map out the "shape" of the data, become highly unreliable as the number of dimensions increases. Second is the reliance on parametric assumptions: many classical statistical tests assume the data follows a specific distribution, such as a Gaussian. If the real-world data is complex, non-linear, or if the baseline shifts over time, these rigid models fail.
To overcome these limitations, we introduce Geometric Entropy Minimization (GEM), a novel adaptive, non-parametric anomaly detection framework. GEM identifies outliers by finding the most "concentrated" (lowest entropy) regions of a dataset using graph theory, providing a mathematically optimal way to detect anomalies without needing to assume a specific underlying probability distribution.
The Geometric Entropy Minimization (GEM) Framework
The core intuition behind GEM is that "normal" data points naturally cluster in regions of high density and low entropy, while anomalies fall into the "tails" or low-density regions of the feature space.
Instead of attempting to calculate a complex probability density function directly, GEM uses geometry as a proxy for entropy. The method leverages the properties of $K$-point entropic graphs, such as Minimal Spanning Trees (MST) or k-Nearest Neighbor Graphs (kNNG). The total length of these graphs is mathematically related to the Rényi entropy of the underlying distribution.
GEM identifies the subset of $K$ points that minimizes the total graph length. As the number of samples grows, this subset converges to the "minimum volume set," which is the statistically optimal region for defining normal behavior.
The L1O-kNNG Algorithm
Finding the absolute best $K$-point subset is an NP-hard problem, making exact solutions computationally prohibitive for large datasets. To resolve this, GEM introduces the Leave-One-Out k-Nearest Neighbor Graph (L1O-kNNG) algorithm.
Instead of exhaustively searching for the optimal subset, the L1O-kNNG calculates the "influence" of each point by measuring how much the total graph length changes when that specific point is removed. Points that cause the largest reduction in graph length when removed are deemed the most "outlying." Unlike standard kNN anomaly detection, which typically only measures the distance to the $k$-th neighbor, the L1O-kNNG evaluates how the entire topology of the graph changes, making it significantly more robust to local variations in data density.
Key Insights and Experimental Validation
GEM offers several strong theoretical guarantees and practical advantages:
- Uniformly Most Powerful (UMP): The framework proves that for anomalies following a uniform distribution, GEM acts as the "best possible" test (UMP) at a given significance level.
- No Tuning Required: Unlike many machine learning models that require complex hyperparameter tuning or function approximation classes, GEM is largely parameter-free once the significance level is set.
- Statistical Significance: The method allows for the calculation of empirical p-values, letting users set a specific level of significance (e.g., $\alpha = 0.1$) for declaring an anomaly.
In simulations using Bivariate Gaussian Mixtures and Uniform Mixtures, the GEM detector's Receiver Operating Characteristic (ROC) curves almost perfectly matched the "clairvoyant" detector—a theoretical ideal that operates with perfect knowledge of the true underlying distribution.
Furthermore, the L1O-kNNG approach is highly efficient. The computational complexity scales linearly with the dimension of the data, making it highly suitable for the unprecedented dimensionality of modern feature spaces. Early benchmarks demonstrated the algorithm processing 10 outliers among 1,000 test samples in just a few seconds on standard hardware.
Limitations and Future Directions
While the L1O approximation successfully bypasses the exponential complexity of exact $K$-point MST/kNNG calculations, there are still areas for future expansion. Although the method is adaptive, handling truly "shifting" baselines over long periods may require extending the methodology with a sliding window approach. Additionally, while the current version computes empirical p-values, future work could extend this framework to account for false discovery rate (FDR) constraints, which is particularly relevant for large-scale sensor networks.
Summary updated