Optimal and fast detection of spatial clusters with scan statistics

Abstract

We consider the detection of multivariate spatial clusters in the Bernoulli model with $N$ locations, where the design distribution has weakly dependent marginals. The locations are scanned with a rectangular window with sides parallel to the axes and with varying sizes and aspect ratios. Multivariate scan statistics pose a statistical problem due to the multiple testing over many scan windows, as well as a computational problem because statistics have to be evaluated on many windows. This paper introduces methodology that leads to both statistically optimal inference and computationally efficient algorithms. The main difference to the traditional calibration of scan statistics is the concept of grouping scan windows according to their sizes, and then applying different critical values to different groups. It is shown that this calibration of the scan statistic results in optimal inference for spatial clusters on both small scales and on large scales, as well as in the case where the cluster lives on one of the marginals. Methodology is introduced that allows for an efficient approximation of the set of all rectangles while still guaranteeing the statistical optimality results described above. It is shown that the resulting scan statistic has a computational complexity that is almost linear in $N$.

Published in at http://dx.doi.org/10.1214/09-AOS732 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Multiscale inference about a density
• Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms

Cited by in corpus (30)

• Detection of an anomalous cluster in a network
• Adaptive Concentration of Regression Trees, with Application to Random Forests
• Interpretable Clustering using Unsupervised Binary Trees
• Seeded Binary Segmentation: A general methodology for fast and optimal change point detection
• Change-point model on nonhomogeneous Poisson processes with application in copy number profiling by next-generation DNA sequencing
• Statistically-Robust Clustering Techniques for Mapping Spatial Hotspots: A Survey
• FDR-Control in Multiscale Change-point Segmentation
• BET on Independence
• Cluster detection in networks using percolation
• Multiscale Change-point Segmentation: Beyond Step Functions
• Nonparametric Detection of Geometric Structures over Networks
• Optimal detection of multi-sample aligned sparse signals
• Automated and Robust Quantification of Colocalization in Dual-Color Fluorescence Microscopy: A Nonparametric Statistical Approach
• The Essential Histogram
• Variational Multiscale Nonparametric Regression: Smooth Functions
• Identifying the Support of Rectangular Signals in Gaussian Noise
• Change Detection: A functional analysis perspective
• Calibrating the scan statistic: finite sample performance vs. asymptotics
• Structured Correlation Detection with Application to Colocalization Analysis in Dual-Channel Fluorescence Microscopic Imaging
• Distribution-Free Detection of Structured Anomalies: Permutation and Rank-Based Scans
• Anomaly Detection for a Large Number of Streams: A Permutation-Based Higher Criticism Approach
• Fisher exact scanning for dependency
• Sparse Anomaly Detection Across Referentials: A Rank-Based Higher Criticism Approach
• A Kernel-Based Nonparametric Test for Anomaly Detection over Line Networks
• Sharp Signal Detection Under Ferromagnetic Ising Models
• Finding Differentially Covarying Needles in a Temporally Evolving Haystack: A Scan Statistics Perspective
• Optimal Calibration for Multiple Testing against Local Inhomogeneity in Higher Dimension
• Analysis of distributional variation through multi-scale Beta-Binomial modeling
• TEAM: A Multiple Testing Algorithm on the Aggregation Tree for Flow Cytometry Analysis
• Calibrating the scan statistic with size-dependent critical values: heuristics, methodology and computation