Data Clustering by Markovian Relaxation and the Information Bottleneck Method
Naftali Tishby, Noam Slonim · 2000
We introduce a new, non-parametric and principled, distance based clustering method. This method combines a pairwise based approach with a vector-quantization method which provide a meaningful 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 during 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 eective way. The method can cluster data with no geometric or other bias and makes no assumption about the underlying distribution. 1 Introduction Data clustering is one of the most fundamental pattern recognition problems, with numerous algorithms and applications. Yet, the problem itself is ill-dened: the goal is to nd a \\reasonable" partition of data points...