Spectral Clustering (Normalized Cut)

Controls

Clusters k: 3 σ (similarity bandwidth): 0.15 Points per cluster: 30 New Sample Run Clustering

Algorithm

1. Build affinity matrix W: W_ij = exp(−‖x_i−x_j‖²/2σ²)

2. Degree matrix D: D_ii = Σ_j W_ij

3. Normalized Laplacian: L = D⁻¹/²(D−W)D⁻¹/²

4. Take k smallest eigenvectors → embed points

5. Run k-means on embedded coordinates

Eigenspectrum

Bar chart below shows eigenvalues λ₁ ≤ λ₂ ≤ ... of L. The spectral gap (jump after λ_k) reveals the natural number of clusters.