Anomaly detection and classification for streaming data using pdes*

Bilal Abbasi, Jeff Calder, Adam M. Oberman

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Nondominated sorting, also called Pareto depth analysis (PDA), is widely used in multiobjective optimization and has recently found important applications in multicriteria 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.

Original languageEnglish (US)
Pages (from-to)921-941
Number of pages21
JournalSIAM Journal on Applied Mathematics
Volume78
Issue number2
DOIs
StatePublished - Jan 1 2018

Fingerprint

Streaming Data
Anomaly Detection
Partial differential equations
Sorting
Partial differential equation
Continuum Limit
Pareto
Ranking
Statistical Convergence
Algorithm Analysis
Approximate Algorithm
Sorting algorithm
Multi-criteria
Multiobjective optimization
Streaming
Multi-objective Optimization
Anomaly
Convergence Rate
Classify
Numerical Experiment

Keywords

  • Anomaly detection
  • Classification
  • Continuum limits
  • Longest chain problem
  • Nondominated sorting
  • Pareto depth analysis
  • Partial differential equations
  • Streaming data
  • Upwind finite difference schemes
  • Viscosity solutions

Cite this

Anomaly detection and classification for streaming data using pdes*. / Abbasi, Bilal; Calder, Jeff; Oberman, Adam M.

In: SIAM Journal on Applied Mathematics, Vol. 78, No. 2, 01.01.2018, p. 921-941.

Research output: Contribution to journalArticle

Abbasi, Bilal ; Calder, Jeff ; Oberman, Adam M. / Anomaly detection and classification for streaming data using pdes*. In: SIAM Journal on Applied Mathematics. 2018 ; Vol. 78, No. 2. pp. 921-941.
@article{f9e4ffba665c4652a6bf02660ed9273c,
title = "Anomaly detection and classification for streaming data using pdes*",
abstract = "Nondominated sorting, also called Pareto depth analysis (PDA), is widely used in multiobjective optimization and has recently found important applications in multicriteria 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.",
keywords = "Anomaly detection, Classification, Continuum limits, Longest chain problem, Nondominated sorting, Pareto depth analysis, Partial differential equations, Streaming data, Upwind finite difference schemes, Viscosity solutions",
author = "Bilal Abbasi and Jeff Calder and Oberman, {Adam M.}",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/17M1121184",
language = "English (US)",
volume = "78",
pages = "921--941",
journal = "SIAM Journal on Applied Mathematics",
issn = "0036-1399",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

TY - JOUR

T1 - Anomaly detection and classification for streaming data using pdes*

AU - Abbasi, Bilal

AU - Calder, Jeff

AU - Oberman, Adam M.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Nondominated sorting, also called Pareto depth analysis (PDA), is widely used in multiobjective optimization and has recently found important applications in multicriteria 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.

AB - Nondominated sorting, also called Pareto depth analysis (PDA), is widely used in multiobjective optimization and has recently found important applications in multicriteria 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.

KW - Anomaly detection

KW - Classification

KW - Continuum limits

KW - Longest chain problem

KW - Nondominated sorting

KW - Pareto depth analysis

KW - Partial differential equations

KW - Streaming data

KW - Upwind finite difference schemes

KW - Viscosity solutions

UR - http://www.scopus.com/inward/record.url?scp=85047781454&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85047781454&partnerID=8YFLogxK

U2 - 10.1137/17M1121184

DO - 10.1137/17M1121184

M3 - Article

AN - SCOPUS:85047781454

VL - 78

SP - 921

EP - 941

JO - SIAM Journal on Applied Mathematics

JF - SIAM Journal on Applied Mathematics

SN - 0036-1399

IS - 2

ER -