Anomaly Detection and Classification for Streaming Data using PDEs

DOI10.1137/17M1121184MaRDI QIDQ4609601zbMATH OpenWikidataFDO

Authors Bilal Abbasi, Jeff Calder, Adam Oberman

Publication date 5 April 2018

Published in SIAM Journal on Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

anomaly detectionclassificationcontinuum limitslongest chain problemnondominated sortingPareto depth analysispartial differential equationsstreaming dataupwind finite difference schemesviscosity solutions

Mathematics Subject Classification ID

Viscosity solutions to PDEs (35D40) Hamilton-Jacobi equations (35F21) PDEs in connection with computer science (35Q68) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Searching and sorting (68P10) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Nondominated sorting, also called Pareto Depth Analysis (PDA), is widely used in multi-objective optimization and has recently found important applications in multi-criteria anomaly detection. Recently, a partial differential equation (PDE) continuum limit was discovered for nondominated sorting leading to a very fast approximate sorting algorithm called PDE-based ranking. We propose in this paper a fast real-time streaming version of the PDA algorithm for anomaly detection that exploits the computational advantages of PDE continuum limits. Furthermore, we derive new PDE continuum limits for sorting points within their nondominated layers and show how the new PDEs can be used to classify anomalies based on which criterion was more significantly violated. We also prove statistical convergence rates for PDE-based ranking, and present the results of numerical experiments with both synthetic and real data.

Recommendations

• Nonparametric Detection of Anomalous Data Streams
• Anomaly Detection in Streaming Nonstationary Temporal Data
• Anomaly detection in large-scale data stream networks

Cites work

• A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• A Hamilton-Jacobi equation for the continuum limit of nondominated sorting
• A PDE-based approach to nondominated sorting
• A survey of outlier detection methodologies
• A variational problem for random Young tableaux
• Concentration of Measure for the Analysis of Randomized Algorithms
• scientific article; zbMATH DE number 3630761 (Why is no real title available?)
• scientific article; zbMATH DE number 3373691 (Why is no real title available?)
• Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms
• Multivariate analysis by data depth: Descriptive statistics, graphics and inference. (With discussions and rejoinder)
• Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• Pareto-Depth for Multiple-Query Image Retrieval
• The Longest Chain Among Random Points in Euclidean Space

Cited in

(5)

• Numerical schemes and rates of convergence for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• System identification through Lipschitz regularized deep neural networks
• A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• Rates of convergence for the continuum limit of nondominated sorting
• A Hamilton-Jacobi equation for the continuum limit of nondominated sorting

This page was built for publication: Anomaly Detection and Classification for Streaming Data using PDEs

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