Clustering data through an analogy to the Potts model

A new approach for clustering is proposed, based on an analogy to a physical model, where the ferromagnetic Potts model at thermal equilibrium is used as an analog computer for this hard optimization problem.

Abstract

A new approach for clustering is proposed. This method is based on an analogy to a physical model; the ferromagnetic Potts model at thermal equilibrium is used as an analog computer for this hard optimization problem. We do not assume any structure of the underlying distribution of the data. Phase space of the Potts model is divided into three regions; ferromagnetic, super-paramagnetic and paramagnetic phases. The region of interest is that corresponding to the super-paramagnetic one, where domains of aligned spins appear. The range of temperatures where these structures are stable is indicated by a non-vanishing magnetic susceptibility. We use a very efficient Monte Carlo algorithm to measure the susceptibility and the spin spin correlation function. The values of the spin spin correlation function, at the super-paramagnetic phase, serve to identify the partition of the data points into clusters. Many natural phenomena can be viewed as optimization processes, and the drive to understa...