Abstract
Anomaly detection is an active research topic with applications in many fields. Various methods have been proposed for anomaly detection in multivariate numerical datasets, each based on different techniques: nearest neighbors, decision trees, self-encoding neural networks, statistical methods, ensemble methods and others. However, the availability of large, high-dimensional datasets presents new challenges to anomaly detection algorithms. In particular, distance-based anomaly detection methods in high-dimensional spaces may become less efficient due to difficulties commonly referred to as the “curse of dimensionality”. In this paper, we present a new unsupervised anomaly detection algorithm for multivariate numerical data, which we call Random Projection Anomaly Detection (RPAD), that can scale to high-dimensional datasets while exhibiting sub-quadratic time complexity. RPAD takes advantage of Euclidean Locality Sensitive Hashing to estimate anomaly scores. Tests performed on 33 datasets using 14 unsupervised algorithms representing state-of-the-art and recent anomaly detection methods show that RPAD outperforms all tested algorithms in terms of execution time, with a more than 10 times improvement over competing algorithms. Additionally, RPAD achieves good performance with an average absolute deviation from the best result equal to [ ] and [ ] for average precision and precision@K metrics, respectively.

This publication has 33 references indexed in Scilit: