Spectral Clustering - Explained

Summary

The video explains how spectral clustering can separate groups that ordinary K-means struggles with, such as an inner and an outer ring. K-means relies on distances to centroids and produces linear decision boundaries, so it cannot naturally separate clusters wrapped around one another.

Spectral clustering instead represents the data as a similarity graph: nearby points are connected by stronger weighted edges, while distant points receive weights close to zero. If the rings are distinct, the graph has many strong connections within each ring and few connections between them.

The method then uses the graph’s Laplacian to reveal its structure. The Laplacian is (L = D - W), where (W) is the similarity matrix and (D) is a diagonal degree matrix whose entries are the sums of the corresponding rows of (W). The Laplacian’s eigenvalues and eigenvectors encode information about how the graph is connected. In particular, the number of zero eigenvalues corresponds to the number of connected components; a noticeable gap in the sorted eigenvalues can indicate a likely number of clusters.

For the two-ring example, the Fiedler vector—the eigenvector associated with the second-smallest eigenvalue—assigns a value to each point. Its signs separate the rings. More generally, spectral clustering embeds the data using selected Laplacian eigenvectors, then applies K-means in that transformed space, where the clusters may be easier to separate.

The video connects this approach to the normalized cut objective: minimizing the weighted connections cut between groups relative to each group’s total connectivity. Finding the exact discrete optimum is difficult, but a continuous relaxation of the problem leads to Laplacian eigenvectors. Thus, spectral clustering is presented as an eigenvector-based approach grounded in an optimization objective, rather than simply a geometric clustering trick.

Method

1. Build a similarity graph from the data.

   • Connect nearby points with weighted edges.

   • Use a Gaussian similarity weight: [ w_{ij} = e^{-\lVert x_i-x_j\rVert^2/(2\sigma^2)}. ]

   • Close points receive stronger weights; distant points receive weights near zero.

2. Form the similarity matrix (W) from the edge weights.

3. Compute the degree matrix (D), with each diagonal entry equal to the sum of edge weights for that point.

4. Construct the graph Laplacian: [ L = D - W. ]

5. Examine the Laplacian’s eigenvalues and eigenvectors.

   • The number of zero eigenvalues reflects the number of connected components.
   • A large gap between successive eigenvalues can suggest the number of clusters.
   • The Fiedler vector can divide a graph into two groups.

6. Embed the points in eigenspace using selected eigenvectors.

7. Run K-means on the embedding, where the clusters may be linearly separable even when they are not separable in the original data space.

Speakers and Sources

• Speaker: One narrator, unnamed in the subtitles.
• Source/channel: DataMListic, identified by the video metadata. No other speakers or external sources are featured in the subtitles.