Pairwise clustering using a Monte Carlo Markov Chain

In this work an application of MCMC is proposed for unsupervised data classification, in conjunction with a novel pairwise objective function, which is shown to work well in situations where clusters to be identified have a strong overlap, and the centroid oriented methods (such as K-means) fail by construction. In particular, an exceptionally simple but difficult situation is addressed when cluster centroids coincide, and one can differentiate between the clusters only on the basis of their variance. Performance of the proposed approach is tested on synthetic and real datasets.