Anomaly Detection in High-Dimensional Data

The HDoutliers algorithm is a powerful unsupervised algorithm for detecting anomalies in high-dimensional data, with a strong theoretical foundation. However, it suffers from some limitations that significantly hinder its performance level, under certain circumstances. In this article, we propose an algorithm that addresses these limitations. We define an anomaly as an observation where itsk-nearest neighbor distance with the maximum gap is significantly different from what we would expect if the distribution ofk-nearest neighbors with the maximum gap is in the maximum domain of attraction of the Gumbel distribution. An approach based on extreme value theory is used for the anomalous threshold calculation. Using various synthetic and real datasets, we demonstrate the wide applicability and usefulness of our algorithm, which we call the stray algorithm. We also demonstrate how this algorithm can assist in detecting anomalies present in other data structures using feature engineering. We show the situations where the stray algorithm outperforms the HDoutliers algorithm both in accuracy and computational time. This framework is implemented in the open source R package stray.for this article are available online.

Automated summary

The article introduces an algorithm for detecting anomalies in high-dimensional data, addressing limitations of the HDoutliers algorithm to improve performance, and demonstrates its wide applicability on various datasets.