Christiane Takacs,
"Hitting Time Properties of Spectral Clusters"
: Bulletin of the International Statistical Institute 56th session, 2007
Original Titel:
Hitting Time Properties of Spectral Clusters
Sprache des Titels:
Englisch
Original Buchtitel:
Bulletin of the International Statistical Institute 56th session
Original Kurzfassung:
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 (see \cite{wy},
\cite{ta1}) and the utilization of the eigenstructure (\cite{wy}).
The methods are motivated by equivalence properties of spectral
clusters (see \cite{ms}, \cite{ta1}) and the fact that spectral
clusters are solutions to suitable optimization criteria
(\cite{sm}, \cite{ms}, \cite{mx}).
\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 (\cite{al}).
\begin{thebibliography}{99}
\bibitem{al} Aldous D., Fill J.A., \emph{%
Reversible Markov Chains and Random Walks on Graphs}. Draft
http://www.stat.berkeley.edu/users/aldous/RWG/book.html
\bibitem{ms} Meila M., Shi J.
(2001), A Random Walks View of Spectral Segmentation. Proceedings International Workshop on AI and Statistics
\bibitem{mx} Meila M., Xu L.
(2003), Multiway Cuts and Spectral Clustering. Homepage, http://www.stat.washington.edu/mmp/
\bibitem{sm} Shi J., Malik J.
(2000), Normalized Cuts and Image Segmentation. IEEE Transactions(PAMI)
....
Forschungs-