Spectral clustering: Difference between revisions

Revision as of 13:36, 12 September 2012

Revision as of 17:48, 11 December 2012

Line 15:

This partitioning may be done in various ways, such as by taking the median <math>m</math> of the components in <math>v</math>, and placing all points whose component in <math>v</math> is greater than <math>m</math> in <math>B_1</math>, and the rest in <math>B_2</math>. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in this fashion.

A related algorithm is the '''[[Meila–Shi algorithm]]''',<ref>Marina Meilă & Jianbo Shi, "[http://www.citeulike.org/user/mpotamias/article/498897 Learning Segmentation by Random Walks]", Neural Information Processing Systems 13 (NIPS 2000), 2001, pp. 873–879.</ref>, which takes the [[eigenvector]]s corresponding to the ''k'' largest [[eigenvalue]]s of the matrix <math>P = D^{-1}S</math> for some ''k'', and then invokes another algorithm (e.g. [[k-means clustering]]) to cluster points by their respective ''k'' components in these eigenvectors.

An efficiency improvement of spectral clustering is the '''[[spectral neighborhood (SPAN) algorithm]]''',<ref>Liangcai Shu, Aiyou Chen, Ming Xiong, Weiyi Meng, "[http://www.cs.binghamton.edu/~meng/pub.d/ICDE11_conf_full_065_update.pdf Efficient Spectral Neighborhood Blocking for Entity Resolution]", IEEE International Conference on Data Engineering (ICDE), pp.1067-1078, Hannover, Germany, April 2011.</ref>, which performs spectral clustering without explicitly computing the similarity matrix, and therefore dramatically improves the scalability of the standard spectral clustering algorithm.

== Relationship with ''k''-means ==

Line 52:

| title = Kernel ''k''-means: spectral clustering and normalized cuts

| booktitle = Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

| pages = 551--556551–556

| organization = ACM

}}</ref>

Line 63:

{{refimprove|date=June 2012}}

{{primary sources|date=June 2012}}

== References ==

<references />