Efficient Optimization of Partition Scan Statistics via the Consecutive Partitions Property

Abstract

Abstract–We generalize the spatial and subset scan statistics from the single to the multiple subset case. The two main approaches to defining the log-likelihood ratio statistic in the single subset case—the population-based and expectation-based scan statistics—are considered, leading to risk partitioning and multiple cluster detection scan statistics, respectively. We show that, for distributions in a separable exponential family, the risk partitioning scan statistic can be expressed as a scaled f-divergence of the normalized count and baseline vectors, and the multiple cluster detection scan statistic as a sum of scaled Bregman divergences. In either case, however, maximization of the scan statistic by exhaustive search over all partitionings of the data requires exponential time. To make this optimization computationally feasible, we prove sufficient conditions under which the optimal partitioning is guaranteed to be consecutive. This Consecutive Partitions Property generalizes the linear-time subset scanning property from two partitions (the detected subset and the remaining data elements) to the multiple partition case. While the number of consecutive partitionings of n elements into t partitions scales as $O(n^{t-1})$, making it computationally expensive for large t, we present a dynamic programming approach which identifies the optimal consecutive partitioning in $O(n^{2}t)$ time, thus allowing for the exact and efficient solution of large-scale risk partitioning and multiple cluster detection problems. Finally, we demonstrate the detection performance and practical utility of partition scan statistics using simulated and real-world data. Supplementary materials for this article are available online.

KEYWORD:

• Cluster detection
• Combinatorial optimization
• Dynamic programming
• Partitioning
• Subset scan

Supplementary Materials

C$++$ and Python code: The library contains exact solvers for partition scan statistics (both risk partitioning and multiple clustering scans) for score functions satisfying the Consecutive Partitions Property. Multiple objective functions from the generalized exponential family are supported, as is determination of the optimal partition size. The C$++$ routines are standalone or exposed through Python bindings. Scripts are provided to generate synthetic data and reproduce figures from the paper.

Data Availability Statement

Code for this article is available at https://github.com/pehlivanian/PartitionSolvers.

Notes

1 In the common case in which B_all is set equal to C_all by construction, F(P) simplifies to $B_{\text{all}}{D}_{{\varphi }_0}(\overrightarrow{C}||\overrightarrow{B})$. This is similar to the expectation-based scan statistics for the separable exponential family (Neill 2012), $F(S)=B{D}_{{\varphi }_0}(C/B,1)$, but in the latter case D is the Bregman divergence rather than f-divergence corresponding to ${\varphi }_0$.

2 We note that quasi-convexity of f is sufficient for the t = 2 case (as proved in Neill 2012) but not for t > 2, since the symmetric score function 2$\overline{f}$ corresponding to a quasi-convex score function f is not necessarily quasi-convex. Subadditivity is not necessary here, since we allow empty partitions.

3 For more accurate evaluation, we also average these detection proportions over 1000 bootstrapped samples of the detection threshold.

4 Note the smaller x-axis ranges for Figures 7(a), 8(a), and 9(a) as compared to the rest of Figures 7–9. All methods had perfect detection power for $\mathrm{ϵ}>0.2$, so we focus on the lower signal strengths for the detection power graphs.

Additional information

Funding

DBN gratefully acknowledges funding support from the National Science Foundation Program on Fairness in Artificial Intelligence in Collaboration with Amazon, grant IIS-2040898.