Preprint
Abstract
Real-time detection of anomalies in streaming data is receiving increasing attention as it allows us to raise alerts, predict faults, and detect intrusions or threats across industries. Yet, little attention has been given to compare the effectiveness and efficiency of anomaly detectors for streaming data (i.e., of online algorithms). In this paper, we present a qualitative, synthetic overview of major online detectors from different algorithmic families (i.e., distance, density, tree or projection-based) and highlight their main ideas for constructing, updating and testing detection models. Then, we provide a thorough analysis of the results of a quantitative experimental evaluation of online detection algorithms along with their offline counterparts. The behavior of the detectors is correlated with the characteristics of different datasets (i.e., meta-features), thereby providing a meta-level analysis of their performance. Our study addresses several missing insights from the literature such as (a) how reliable are detectors against a random classifier and what dataset characteristics make them perform randomly; (b) to what extent online detectors approximate the performance of offline counterparts; (c) which sketch strategy and update primitives of detectors are best to detect anomalies visible only within a feature subspace of a dataset; (d) what are the tradeoffs between the effectiveness and the efficiency of detectors belonging to different algorithmic families; (e) which specific characteristics of datasets yield an online algorithm to outperform all others.Keywords
All Related Versions
This publication has 35 references indexed in Scilit:
- There and back again: Outlier detection between statistical reasoning and data mining algorithmsWIREs Data Mining and Knowledge Discovery, 2018
- Defying the gravity of learning curve: a characteristic of nearest neighbour anomaly detectorsMachine Learning, 2016
- On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical studyData Mining and Knowledge Discovery, 2016
- Effectiveness of the Euclidean distance in high dimensional spacesOptik, 2015
- Loda: Lightweight on-line detector of anomaliesMachine Learning, 2015
- Randomized Algorithms in Automatic Control and Data Mining2015
- On Stopping Rules in Dependency-Aware Feature RankingLecture Notes in Computer Science, 2013
- A survey on unsupervised outlier detection in high‐dimensional numerical dataStatistical Analysis and Data Mining: An ASA Data Science Journal, 2012
- Identifying Feature Relevance Using a Random Forest2006
- On the Surprising Behavior of Distance Metrics in High Dimensional Space2001