Random Projection-based Anomaly Detection (RPAD) Algorithm

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 [Formula: see text] and [Formula: see text] for average precision and precision@K metrics, respectively.