Consensus clustering: The Filtered Stochastic Best-One-Element-Move Algorithm

The consensus clustering problem is to find a clustering partition that has minimum average distance to a set of given partitions, generated from a number of different clustering algorithms or different runs of the same clustering algorithm. Different definitions of partition distance and different optimization methods lead to many consensus clustering algorithms. In this paper, a new algorithm is proposed for solving the median partition problem, combining the idea of the Best One Element Move (BOEM) algorithm and stochastic gradient descent (SGD) with a filtering step. Simulation results demonstrate that this new algorithm converges faster than the vanilla version of BOEM and performs competitively with other algorithms. Moreover, it sheds some light on how to use SGD methods in discrete domain problems, and on the efficacy of introducing memory in estimation of local gradients.