Random walks to identify anomalous free-form spatial scan windows

Often, it is required to Identify anomalous windows over a spatial region that reflect unusual rate of occurrence of a specific event of interest. A spatial scan statistic-based approach essentially considers a scan window and computes the statistic of a parameter(s) of interest, and identifies anomalous windows by moving the scan window in the region. While this approach has been successfully employed in identifying anomalous windows, earlier proposals adopting spatial scan statistic suffer from two limitations: 1) In general, the scan window should be of a regular shape (e.g., circle, rectangle, cylinder). Thus, most approaches are capable of identifying anomalous windows of fixed shapes only. However, the region of anomaly, in general, is not necessarily of a regular shape. Recent proposals to identify windows of irregular shapes identify windows much larger than the true anomalies or penalize large-sized windows. 2) These techniques take into account autocorrelation among spatial data but not spatial heterogeneity. As a result, they often result in inaccurate anomalous windows. To address these limitations, in this paper, we propose a random-walk-based Free-Form Spatial Scan Statistic (FS³). We construct a weighted Delaunay nearest neighbor (WDNN) graph to capture both spatial autocorrelation and heterogeneity. We then use random walks to identify natural free-form scan windows that are not restricted to a predefined shape. We use spatial scan statistics to identify anomalous windows and prove that they are not random but indeed are formed as a result of an anomaly. Application of FS³ on real data sets has shown that it can identify more refined anomalous windows with better likelihood ratio of it being an anomaly than those identified by earlier spatial scan statistic approaches.