Data clustering by markovian relaxation and the information bottleneck method

We introduce a new, non-parametric and principled, distance based clustering method. This method combines a pairwise based ap-proach with a vector-quantization method which provide a mean-ingful interpretation to the resulting clusters. The idea is based on turning the distance matrix into a Markov process and then examine the decay of mutual-information during the relaxation of this process. The clusters emerge as quasi-stable structures dur-ing this relaxation, and then are extracted using the information bottleneck method. These clusters capture the information about the initial point of the relaxation in the most effective way. The method can cluster data with no geometric or other bias and makes no assumption about the underlying distribution.