Real-Time Nonparametric Anomaly Detection in High-Dimensional Settings
Preprint
Abstract
Timely detection of abrupt anomalies is crucial for real-time monitoring and security of modern systems producing high-dimensional data. With this goal, we propose effective and scalable algorithms. Proposed algorithms are nonparametric as both the nominal and anomalous multivariate data distributions are assumed unknown. We extract useful univariate summary statistics and perform anomaly detection in a single-dimensional space. We model anomalies as persistent outliers and propose to detect them via a cumulative sum-like algorithm. In case the observed data have a low intrinsic dimensionality, we learn a submanifold in which the nominal data are embedded and evaluate whether the sequentially acquired data persistently deviate from the nominal submanifold. Further, in the general case, we learn an acceptance region for nominal data via Geometric Entropy Minimization and evaluate whether the sequentially observed data persistently fall outside the acceptance region. We provide an asymptotic lower bound and an asymptotic approximation for the average false alarm period of the proposed algorithm. Moreover, we provide a sufficient condition to asymptotically guarantee that the decision statistic of the proposed algorithm does not diverge in the absence of anomalies. Experiments illustrate the effectiveness of the proposed schemes in quick and accurate anomaly detection in high-dimensional settings.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- DDoS in the IoT: Mirai and Other BotnetsComputer, 2017
- Transition-Aware Human Activity Recognition Using SmartphonesNeurocomputing, 2016
- A review of novelty detectionSignal Processing, 2014
- On false data injection attacks against Kalman filtering in power system dynamic state estimationSecurity and Communication Networks, 2013
- Change-Point Detection for High-Dimensional Time Series With Missing DataIEEE Journal of Selected Topics in Signal Processing, 2012
- Fast mining of distance-based outliers in high-dimensional datasetsData Mining and Knowledge Discovery, 2008
- Robust detection of selfish misbehavior in wireless networksIEEE Journal on Selected Areas in Communications, 2007
- Information bounds and quick detection of parameter changes in stochastic systemsIEEE Transactions on Information Theory, 1998
- A a comparison of the markov chain and the integral equation approaches for evaluating the run length distribution of quality control chartsCommunications in Statistics - Simulation and Computation, 1991
- Wald's approximations to the average run length in cusum proceduresJournal of Statistical Planning and Inference, 1978