Stochastic Voronoi Ensembles for Anomaly Detection
This addresses the challenge of detecting local anomalies in applications like fraud detection and network security, offering a more efficient and effective solution compared to existing methods.
The paper tackles the problem of anomaly detection in datasets with varying local densities by proposing SVEAD, which uses stochastic Voronoi ensembles to decompose the data space and score anomalies based on cell-relative distances, achieving linear time and constant space complexity while outperforming 12 state-of-the-art methods on 45 datasets.
Anomaly detection aims to identify data instances that deviate significantly from majority of data, which has been widely used in fraud detection, network security, and industrial quality control. Existing methods struggle with datasets exhibiting varying local densities: distance-based methods miss local anomalies, while density-based approaches require careful parameter selection and incur quadratic time complexity. We observe that local anomalies, though indistinguishable under global analysis, become conspicuous when the data space is decomposed into restricted regions and each region is examined independently. Leveraging this geometric insight, we propose SVEAD (Stochastic Voronoi Ensembles Anomaly Detector), which constructs ensemble random Voronoi diagrams and scores points by normalized cell-relative distances weighted by local scale. The proposed method achieves linear time complexity and constant space complexity. Experiments on 45 datasets demonstrate that SVEAD outperforms 12 state-of-the-art approaches.