Random Projection-based Anomaly Detection (RPAD) Algorithm
- 5 August 2025
- journal article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Information Technology & Decision Making
- Vol. 25 (03) , 997-1022
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.Keywords
This publication has 33 references indexed in Scilit:
- Machine Learning and Artificial Intelligence with Industrial Applications2022
- On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical studyData Mining and Knowledge Discovery, 2016
- Fast and Scalable Outlier Detection with Approximate Nearest Neighbor Ensembles2015
- A survey on unsupervised outlier detection in high‐dimensional numerical dataStatistical Analysis and Data Mining: An ASA Data Science Journal, 2012
- Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data2009
- Fast Outlier Detection in High Dimensional Spaces2002
- Enhancing Effectiveness of Outlier Detections for Low Density Patterns2002
- When Is “Nearest Neighbor” Meaningful?1999
- Ueber die stetige Abbildung einer Line auf ein Fl chenst ckMathematische Annalen, 1891
- Sur une courbe, qui remplit toute une aire planeMathematische Annalen, 1890