Thursday, June 16, 2011

Spectral clustering - clustering of principal components?

The success of spectral clustering is mainly based on the fact that it does not make strong assumptions
on the form of the clusters. As opposed to k-means, where the resulting clusters form convex sets (or,
to be precise, lie in disjoint convex sets of the underlying space), spectral clustering can solve very
general problems like intertwined spirals. Moreover, spectral clustering can be implemented efficiently
even for large data sets, as long as we make sure that the similarity graph is sparse. Once the similarity
graph is chosen, we just have to solve a linear problem, and there are no issues of getting stuck in local
minima or restarting the algorithm for several times with different initializations. However, we have
already mentioned that choosing a good similarity graph is not trivial, and spectral clustering can
be quite unstable under different choices of the parameters for the neighborhood graphs. So spectral
clustering cannot serve as a “black box algorithm” which automatically detects the correct clusters
in any given data set. But it can be considered as a powerful tool which can produce good results if
applied with care.

http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf

Spectral clustering is a technique for finding group structure in data. It is based on viewing the data points as nodes of a connected graph and clusters are found by partitioning this graph, based on its spectral decomposition, into subgraphs that posses some desirable properties

http://videolectures.net/mlcued08_azran_mcl/

No comments: