An Efficient Quantile Spatial Scan Statistic for Finding Unusual Regions in Continuous Spatial Data with Covariates

Travis Moore, Weng-Keen WongUAI 2018 · OpenReview

Abstract

Traditional spatial scan statistics (SSS) are essential for identifying geographic hotspots but face challenges with continuous data, outliers, and the need to account for local covariates. We introduce the Quantile Spatial Scan Statistic (QSSS), which leverages quantile regression to identify anomalies at specific distribution points (e.g., the 90th percentile) rather than just the mean. By employing a non-parametric rank test and a novel incremental QR update method, QSSS achieves dramatic computational efficiency and superior robustness compared to traditional mean-based approaches.

Introduction

Identifying unusual geographic regions—such as disease clusters or economic anomalies—is a critical task in spatial analysis. However, standard methods often rely on comparing means, making them sensitive to outliers and unable to detect "tail-end" phenomena. Furthermore, real-world data is frequently influenced by covariates (e.g., population density affecting crime rates), which must be controlled for to find truly "unusual" regions. QSSS addresses these issues by focusing on quantiles and providing an efficient framework for covariate adjustment.

Methods

QSSS replaces traditional mean-based comparisons with quantile regression. To maintain computational feasibility, the authors introduce three key innovations:

  • The Rank Test: A non-parametric alternative to the Likelihood Ratio Test that avoids re-estimating regression coefficients for every candidate region, significantly reducing the computational burden.
  • Incremental QR Updates: Spatial scans involve evaluating thousands of overlapping windows. QSSS uses Givens rotations to perform exact incremental updates of the QR decomposition, reducing the update cost from $O(n^2)$ to $O(np)$.
  • Gumbel Approximation: To determine statistical significance without thousands of slow Monte Carlo simulations, QSSS uses a Gumbel distribution correction for faster p-value calculation.
The incremental Rank Test provides a massive speedup as the number of data points (N) increases, compared to the non-incremental version.

Results and Discussion

The QSSS framework was tested on synthetic and real-world datasets, including eButterfly and USDA economic data.

Computational Efficiency

At $N=16,000$, the incremental update took only 2.83 ms, approximately 60 times faster than the naive approach (166.9 ms). This efficiency allows researchers to perform complex spatial scans on standard hardware that were previously computationally prohibitive.

Robustness and Accuracy

In synthetic tests with 10 covariates, the Rank test achieved an F1 score of 0.535, significantly outperforming mean-based tests (0.182). A case study using eButterfly data demonstrated that while mean-based scans are easily distracted by single "super-observers" (outliers), the QSSS at the 50th percentile successfully identified genuine biological patterns like migration corridors.

A comparison on eButterfly data shows that the 50th percentile scan (a) is robust to outliers, whereas the mean-based scan (b) is skewed by a single high-count data point.

Conclusion

QSSS provides a powerful, efficient, and robust tool for spatial anomaly detection in continuous data. By allowing users to scan for specific quantiles while adjusting for covariates, it opens new avenues for understanding complex spatial phenomena. Future work will explore irregularly shaped scanning windows and spatiotemporal extensions to track how these regions move over time.

Summary updated

BibTeX
@inproceedings{moore2018efficient,
  author = {Travis Moore and Weng-Keen Wong},
  title = {{An Efficient Quantile Spatial Scan Statistic for Finding Unusual Regions in Continuous Spatial Data with Covariates}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=NT1dZ0ueBBL},
}
Figure