Given a set of points and their mutual similarities we want to find clusters of similar points and separate distant or dissimilar points. Spectral clustering methods have in common that they use piecewise (almost) constant eigenvectors of matrices derived from the mutual distances or similarities of the points to be separated. In this setting clusters are indicated by the same eigenvector entries. Properties of algorithms based on this idea are studied and their performance for given data sets is analyzed by several authors (e.g. …). There are situations (see …), where the partition indicated by eigenvectors is the exact optimal solution of a (very reasonable) clustering criterion.
The present research focusses on a theoretical analysis, where the connection to random walks is exploited. To this end the following is fundamental: An aperiodic, irreducible and reversible Markov chain admits agglomeration with respect to the equivalence classes $\left( A_{1},\ldots ,A_{k}\right)$ of states, iff its transition matrix has $k$ linearly independent right eigenvectors, which are piecewise constant with respect to the partition $\left(A_{1},\ldots ,A_{k}\right)$. Since it is reasonable to consider equivalence classes themselves as clusters, we investigate (see …), which properties are shared by points in one class.
Forschungs-