Content deleted Content added
m →Relationship with k-means: fix references |
| |
||
Line 1:
In [[multivariate statistics]] and the [[cluster analysis|clustering]] of data, '''spectral clustering'''<ref> U. von Luxburg, "A tutorial on spectral clustering", Stat. Comp. Vol. 17, Issue 4 , 395-416 (2007), [http://papercore.org/vonLuxburg2007 Papercore summary http://papercore.org/vonLuxburg2007 ] </ref> techniques make use of the [[Spectrum of a matrix|spectrum]] ([[eigenvalues]]) of the [[similarity matrix]] of the data to perform [[dimensionality reduction]] before clustering in fewer dimensions. The similarity matrix is provided as an input and consists of a quantitative assessment of the relative similarity of each pair of points in the dataset.[[File:K-means v.s. Spectral Clustering.png|thumb|A figure showing the relative strengths of K-means and spectral clustering.<ref>{{Citation
| Author = Martin, Charles
| url = http://charlesmartin14.wordpress.com/2012/10/09/spectral-clustering/
| date = October 9, 2012}}</ref>]]
== Algorithms ==
Line 18 ⟶ 21:
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.
Spectral clustering is closely related to [[Nonlinear dimensionality reduction]], and dimension reduction techniques such as locally-linear embedding can be used to reduce errors from noise or outliers.<ref>{{Citation
| author = Dhillon, I.S. and Guan, Y. and Kulis, B.
| title = Spectral clustering based on local linear approximations.
| journal = Electronic Journal of Statistics | volume = 5 | page = 1537-1587
| year = 2011}}</ref>
== Relationship with ''k''-means ==
| |||