Distribution-free detection of structured anomalies: permutation and rank-based scans

Ery Arias-Castro, Rui M. Castro, Ervin Tánczos, Meng Wang

Research output: Contribution to journalArticleAcademicpeer-review

21 Citations (Scopus)
1 Downloads (Pure)

Abstract

The scan statistic is by far the most popular method for anomaly detection, being popular in syndromic surveillance, signal and image processing, and target detection based on sensor networks, among other applications. The use of the scan statistics in such settings yields a hypothesis testing procedure, where the null hypothesis corresponds to the absence of anomalous behavior. If the null distribution is known, then calibration of a scan-based test is relatively easy, as it can be done by Monte Carlo simulation. When the null distribution is unknown, it is less straightforward. We investigate two procedures. The first one is a calibration by permutation and the other is a rank-based scan test, which is distribution-free and less sensitive to outliers. Furthermore, the rank scan test requires only a one-time calibration for a given data size making it computationally much more appealing. In both cases, we quantify the performance loss with respect to an oracle scan test that knows the null distribution. We show that using one of these calibration procedures results in only a very small loss of power in the context of a natural exponential family. This includes the classical normal location model, popular in signal processing, and the Poisson model, popular in syndromic surveillance. We perform numerical experiments on simulated data further supporting our theory and also on a real dataset from genomics. Supplementary materials for this article are available online.

Original languageEnglish
Pages (from-to)789-801
Number of pages13
JournalJournal of the American Statistical Association
Volume113
Issue number522
DOIs
Publication statusPublished - 3 Apr 2018

Funding

This work was partially supported by a grant from the U.S. National Science Foundation (DMS 1223137) and a grant from the Nederlandse organisatie voor Wetenschappelijk Onderzoek (NWO 613.001.114).

Keywords

  • Permutation tests
  • Rank tests
  • Scan statistic

Fingerprint

Dive into the research topics of 'Distribution-free detection of structured anomalies: permutation and rank-based scans'. Together they form a unique fingerprint.

Cite this