Expected similarity estimation for large-scale batch and streaming anomaly detection

DOI10.1007/S10994-016-5567-7zbMATH Open1432.94044arXiv1601.06602OpenAlexW2256894031MaRDI QIDQ1689600FDOQ1689600

Authors: Markus Schneider, Wolfgang Ertel, Fabio Ramos 

Publication date: 12 January 2018

Published in: Machine Learning (Search for Journal in Brave)

Abstract: We present a novel algorithm for anomaly detection on very large datasets and data streams. The method, named EXPected Similarity Estimation (EXPoSE), is kernel-based and able to efficiently compute the similarity between new data points and the distribution of regular data. The estimator is formulated as an inner product with a reproducing kernel Hilbert space embedding and makes no assumption about the type or shape of the underlying data distribution. We show that offline (batch) learning with EXPoSE can be done in linear time and online (incremental) learning takes constant time per instance and model update. Furthermore, EXPoSE can make predictions in constant time, while it requires only constant memory. In addition, we propose different methodologies for concept drift adaptation on evolving data streams. On several real datasets we demonstrate that our approach can compete with state of the art algorithms for anomaly detection while being an order of magnitude faster than most other approaches.

Full work available at URL: https://arxiv.org/abs/1601.06602

Recommendations

• Constant time EXPected similarity estimation for large-scale anomaly detection
• DAMP: accurate time series anomaly detection on trillions of datapoints and ultra-fast arriving data streams
• A classification framework for anomaly detection
• Loda: lightweight on-line detector of anomalies
• Extreme value theory for anomaly detection -- the GPD classifier

zbMATH Keywords

kernel methodsanomaly detectionlarge-scale dataHilbert space embeddingmean map

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Statistical aspects of big data and data science (62R07) Pattern recognition, speech recognition (68T10) Informational aspects of data analysis and big data (94A16)

Cites Work

• Equivalence of distance-based and RKHS-based statistics in hypothesis testing
• Statistical comparisons of classifiers over multiple data sets
• A survey of outlier detection methodologies
• Present Position and Potential Developments: Some Personal Views: Statistical Theory: The Prequential Approach
• Support Vector Machines
• A Hilbert Space Embedding for Distributions
• Foundations of Modern Probability
• A kernel two-sample test
• A survey on concept drift adaptation
• Knowledge discovery from data streams.
• Infinite dimensional analysis. A hitchhiker's guide.
• Title not available (Why is that?)
• On the Convergence of Pattern Search Algorithms
• Estimating the support of a high-dimensional distribution
• Title not available (Why is that?)
• Approximations of the critical region of the fbietkan statistic
• Support vector data description
• 10.1162/1532443041827925
• Title not available (Why is that?)
• Constant time EXPected similarity estimation for large-scale anomaly detection

Cited In (6)

• An ordinal anomaly probability algorithm for anomaly detection problems in massive data sets
• Loda: lightweight on-line detector of anomalies
• Unsupervised streaming anomaly detection for instrumented infrastructure
• A survey of outlier detection in high dimensional data streams
• DAMP: accurate time series anomaly detection on trillions of datapoints and ultra-fast arriving data streams
• Constant time EXPected similarity estimation for large-scale anomaly detection

Uses Software

• MapReduce
• UCI-ml
• LIBSVM
• LOF
• iHOG
• HOGgles

This page was built for publication: Expected similarity estimation for large-scale batch and streaming anomaly detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1689600)