Spatial clustering of multivariate data using weighted MAX-SAT.

Incorporating geographical constraints is one of the main challenges of spatial clustering. In this paper we propose a new algorithm for clustering of spatial data using a conjugate Bayesian model and weighted MAX-SAT solvers. The fast and flexible Bayesian model is used to score promising partitions of the data. However, the partition space is huge and it cannot be fully searched, so here we propose an algorithm that naturally incorporates the geographical constraints to guide the search over the space of partitions. We illustrate our proposed method on a simulated dataset of social indexes.