The spatial scan statistic [1] is the most used measure for cluster strenght. The evaluation of all possible subsets of regions in a large dataset is computationally infeasible. Many heuristics have appeared recently to compute approximate values that maximizes the logarithm of the likelihood ratio. The Fast Subset Scan [2] finds exactly the optimal irregularly spatial cluster; however, the solution may not be connected. The spatial cluster detection problem was formulated as the classic knapsack problem [3], and modeled as a bi-objective unconstrained combinatorial optimization problem. Dynamic programming relies on the principle that, in an optimal sequence of decisions or choices, each sub-sequence must also be optimal. During the search for a solution it avoids full enumeration by pruning early partial decision solutions that cannot possibly lead to optimal solutions.
Objective
We propose a fast, exact algorithm to make detection and inference of arbitrarily shaped connected spatial clusters in aggregated area maps based on constrained dynamic programming.