Spatial Cluster Detection Through a Dynamic Programming Approach

Abstract

This chapter reviews a dynamic programming scan approach to the detection and inference of arbitrarily shaped spatial clusters in aggregated geographical area maps, which is formulated here as a classic knapsack problem. A polynomial algorithm based on constrained dynamic programming is proposed, the spatial clusters detection dynamic scan. It minimizes a bi-objective vector function, finding a collection of Pareto optimal solutions. The dynamic programming algorithm is adapted to consider geographical proximity between areas, thus allowing a disconnected subset of aggregated areas to be included in the efficient solutions set. It is shown that the collection of efficient solutions generated by this approach contains all the solutions maximizing the spatial scan statistic. The plurality of the efficient solutions set is potentially useful to analyze variations of the most likely cluster and to investigate covariates.

Appendix

Multi-objective Optimization Problem

Multi-objective optimization involves minimizing or maximizing simultaneously multiple objective functions subject to a set of constraints. A multi-objective optimization problem may be defined as Ehrgott (2000):

$$\displaystyle{ \begin{array}{l} \min \ \ \mathbf{f}(\mathbf{x}) = (f_{1}(\mathbf{x}),f_{2}(\mathbf{x}),\cdots \,,f_{d}(\mathbf{x})) \\ \mbox{ subject to:}\ \ \mathbf{x} = (x_{1},x_{2},\ldots,x_{m}) \in \mathbb{X}\end{array} }$$

(6)

in which x is the decision variable vector or solution, $\mathbb{X}$ is the feasible set, and d is the number of objective functions. The goal in multi-objective optimization is to find the solutions that “minimize” f(x), in the Pareto-optimality sense. In order to state such a definition, consider the vectors $\mathbf{u,v} \in \mathbb{R}^{d}$ and the binary relation ≺:

$$\displaystyle{ \begin{array}{rcl} \mathbf{u} \prec \mathbf{v}&\Longleftrightarrow&\mathbf{u} \leq \mathbf{v}\mbox{ and }\mathbf{u}\neq \mathbf{v} \\ \mathbf{u} \leq \mathbf{v}&\Longleftrightarrow&u_{i} \leq v_{i},\,\mbox{ for all }i = 1,\ldots,d \\ \mathbf{u}\neq \mathbf{v}&\Longleftrightarrow&\exists i \in \left \{1,\ldots,d\right \}:\, u_{i}\neq v_{i}\end{array} }$$

Pareto-optimality is defined as follows:

Definition 2.

A feasible solution $\mathbf{x^{{\ast}}}\in \mathbb{X}$ is called optimal solution of the multi-objective optimization Problem (6) if there is no $\mathbf{x} \in \mathbb{X}$ such that f(x) ≺ f(x ^∗).

An optimal solution x ^∗ is called efficient solution, and f(x) is called nondominated point. The set of all efficient solutions is denoted by $\mathbb{X}_{E}$, and $\mathbb{Y}_{N} = \mathbf{f}(\mathbb{X}_{E})$ denotes the set of all nondominated points. If f(x) ≺ f(y) we say x dominates y and f(x) dominates f(y). If f(x) ≺ f(y) or f(y) ≺ f(x) does not hold, x and y are called indifferent, and f(x) and f(y) are called indifferent.

Given the multi-objective optimization Problem (6), the feasible solutions $\mathbf{x},\mathbf{y} \in \mathbb{X}$ are called equivalent if f(x) = f(y). A complete set of efficient solutions is any subset $\mathbb{X}^{{\prime}}\subseteq \mathbb{X}$, such that $\mathbf{f}(\mathbb{X}^{{\prime}}) = \mathbb{Y}_{N}$. A minimal complete set of efficient solutions is a complete set of efficient solutions without any equivalent solutions. Note that the maximal complete set of efficient solutions is unique, while a minimal complete set is not unique in general.