Spectral clustering and graph Laplacians
Turn the data into a graph of similarities, and the clusters become pieces of the graph that are barely connected to each other. The eigenvectors of one matrix, the graph Laplacian, find those pieces. Proof for the disconnected case, the cut objectives behind it, and the Ng–Jordan–Weiss algorithm.
55 min
After this lesson you can
- Build a similarity graph from data and write down its degree matrix and Laplacian
- Prove that f-transpose L f equals half the weighted sum of squared differences, and that L is positive semi-definite
- Prove that the zero eigenvalues of L count the connected components, with indicator vectors as eigenvectors
- Derive the two-way spectral relaxation of a balanced graph cut
- Implement the Ng–Jordan–Weiss algorithm and explain why it succeeds where k-means fails
In this lesson
- From points to a graph
- What a good cut looks like
- The graph Laplacian
- Why the smallest eigenvectors: the relaxation
- The algorithm, and the plate
- What can go wrong
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.