Hitting Time Properties of Spectral Clusters

Description

Spectral clustering methods use eigenvectors for data segmentation, where the underlying matrix reflects the similarity structure in the data points. Piecewise constant eigenvectors are considered as indicators of a partition. We will call its components spectral clusters or classes. Main differences in the methods concern the concrete type of matrix and the utilization of the eigenstructure. The methods are motivated by equivalence properties of spectral clusters and the fact that spectral clusters are solutions to suitable optimization criteria. \newline In the present paper we give a very general presentation of spectral clustering and a corresponding segmentation criterion, which includes the mentioned methods as special cases. Additionally we characterize spectral clusters in terms of hitting times and give a novel segmentation criterion based on hitting times. We achieve this by utilizing the similarity structure of the data to define the transition matrix P of a Markov chain which is used for spectral clustering. The result is due to the fact that the eigenvectors of P coincide with those of its fundamental matrix, whose entries may be interpreted in terms of hitting times}).

Period	23 Aug 2007
Event title	ISI 2007 - Lisboa
Event type	Conference
Location	PortugalShow on map