The detection of spatial clusters: graph and dynamic programming based methods

Abstract

This thesis addresses the spatial and space-time cluster detection problem. Two algorithms to solve the typical problem for spatial data sets are proposed. A fast method for the detection and inference of point data set spatial and space-time disease clusters is presented, the Voronoi Based Scan (VBScan). A Voronoi diagram is built for points representing population individuals (cases and controls). The number of Voronoi cells boundaries intercepted by the line segment joining two cases points defines the Voronoi distance between those points. This distance is used to approximate the density of the heterogeneous population and build the Voronoi distance Minimum Spanning Tree (VMST) linking the cases. The successive removal of edges from the VMST generates sub-trees which are the potential clusters. Finally, those clusters are evaluated through the scan statistic. Monte Carlo replications of the original data are used to evaluate the significance of the clusters. The ability to promptly detect space-time clusters of disease outbreaks, when the number of individuals is large, was shown to be feasible, due to the reduced computational load of VBScan. Numerical simulations showed that VBScan has higher power of detection, sensitivity and positive predicted value than the Elliptic PST. Furthermore, an application for dengue fever in a small Brazilian city is presented. In a second approach, the typical spatial cluster detection problem is reformulated as a bi-objective combinatorial optimization problem. We propose an exact algorithm based on dynamic programming, Geographical Dynamic Scan, which empirically was able to solve instances up to large size within a reasonable computational time. We show that the set of nonv dominated solutions of the problem, computed efficiently, contains the solution that maximizes the Kulldorffs Spatial Scan Statistic. The method allows arbitrary shaped clusters, which can be a collection of disconnected or connected areas, taking into account a geometric constraint. Note that this is not a serious disadvantage, provided that there is not a huge gap between its component areas. We present an empirical comparison of detection and spatial accuracy between our algorithm and the classical Kulldorffs Circular Scan, using the data set of Chagas disease cases in puerperal women in Minas Gerais state, Brazil.