Spectral clustering — the core idea.
hardAnswer
- Build similarity graph on data (k-NN or ε-neighborhood).
- Compute graph Laplacian L.
- Find eigenvectors of the k smallest eigenvalues → embed points into .
- Run k-means in this embedding.
- Captures non-convex, manifold-shaped clusters that k-means can't handle.
- Cost: eigendecomposition or with Nyström — scales to ~50k.
- Modern uses: community detection in graphs, image segmentation.
Check yourself — multiple choice
- Same as k-means
- Build similarity graph → eigenvectors of Laplacian → k-means in embedding; captures non-convex shapes; or Nyström for scale
- Random
- Not real
Spectral clustering: Laplacian eigenvectors + k-means → non-convex clusters.
#clustering
Practise Unsupervised Learning
214 interview questions in this topic.