Spectral

Spectral

1. Idea

Clusters = graph cuts. Build similarity graph ($W_{ij}$ large when $x_{i}, x_{j}$ close), cut weakest links so within-cluster similarity stays high. Handles moons, rings where $k$-means fails.

2. Steps

1. similarity W (RBF: exp(-γ ||xi-xj||²), k-NN graph)
2. Laplacian L = D - W (D = row sums on diagonal)
3. bottom-k eigenvectors of L → rows as new features
4. k-means on rows

Second-smallest eigenvector (Fiedler) gives best 2-way cut.

3. Why Eigenvectors?

Relaxed cut minimization ⟺ eigenproblem. Rows of eigenvector matrix separate cleanly even when original space tangles.

4. Practice

Choose $σ$ / $k$-NN scale carefully; $O(n³)$ naive → use landmarks / sparse $k$-NN for big $n$. Normalize Laplacian for uneven sizes.

5. Exam Points

• Graph + Laplacian + eigenvectors steps — 7 marks, very frequent.
• Why non-convex shapes work — 3 marks, frequent.
• Fiedler vector role — 2 marks, frequent.