Spectral Clustering — Normalized Cut

Spectral Clustering & Normalized Cut

Spectral clustering embeds data into the eigenspace of the graph Laplacian, then applies k-means in that space. Given similarity matrix W_ij = exp(−‖x_i−x_j‖²/2σ²), the normalized Laplacian is L_sym = D^−1/2(D−W)D^−1/2. The k smallest eigenvectors form a low-dimensional embedding where clusters become linearly separable.

This solves the normalized cut problem (Shi-Malik 2000): partition the graph to minimize cut weight relative to cluster volume. The method handles non-convex clusters that k-means cannot find. Click "Run Spectral Clustering" to see the eigenvector embedding and cluster assignments.