Golden
Spectral clustering

Spectral clustering

A simple implementation of clustering that can be solved efficiently by standard linear algebra software.

Spectral clustering is a simple implementation of clustering that can be solved efficiently by standard linear algebra software, and it has been shown to outperform other clustering algorithms such as k-means in some circumstances. 



Spectral clustering algorithms typically follow 3 main steps:

  1. Pre-processing: Compute a similarity graph and represent it with an adjacency matrix which has a similarity between each vertex and its elements.
  2. Data decomposition: Compute the eigenvalues and eigenvectors of the matrix using a Graph Laplacian. Then, map the data points into lower-dimensional space based on one or more of the eigenvectors.
  3. Grouping: Use k-means to cluster these data points into k clusters.

Comparison With Other Clustering Methods

Spectral clustering is easy to implement, reasonably fast for sparse data sets having several thousand elements, and it provides good clustering results. Unlike, k-means and other common clustering techniques, spectral clustering doesn't make strong assumptions on the statistics of the clusters, which can help create more accurate clusters when those strong assumptions aren't relevant. 



For larger data sets, however, spectral clustering is computationally expensive and can be more complex to implement. 

Timeline

People

Name
Role
Related Golden topics







Further reading

Title
Author
Link
Type
Date

Spectral Clustering for beginners

Amine Aoullay





Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification

Yongyu Wang, Zhuo Feng

Academic paper



Unified Spectral Clustering with Optimal Graph

Zhao Kang, Chong Peng, Qiang Cheng, Zenglin Xu

Academic paper



Documentaries, videos and podcasts

Title
Date
Link

Spectral Clustering Three Steps | Stanford University

April 12, 2016

Companies

Company
CEO
Location
Products/Services









References