Classification by restricted random walks

摘要

We define a random walk in a data set of a metric space. In order that the random walk depends on the pattern of the data, restrictions are imposed during its generation. Since such a restricted random walk investigates only a local subset of the data, a series of random walks has to be realized for describing the entire data set. An agglomerative graph-related classification method is introduced whose hierarchy is based on these restricted random walks. It is demonstrated on various examples that this new technique is able to detect efficiently clusters of different shapes without specifying the number of groups in advance.