In this set of notes we’re going to learn about a clustering approach that throws out the K-means assumption that clusters fall in convex globular clusters and does something different: spectral clustering (we’ll cover just the vanilla version, improved and tweaked versions based on this can be found in standard papers on the subject). Spectral clustering clusters data points by treating them not as distinct convex globular clusters as in K-means but as connected subgraphs. This change in perspective allows separation of non-convex globular clusters – something K-means just can’t do. More importantly we’ll see that spectral clustering can ignore sparse interconnections between arbitrarily shaped clusters of data – a characteristic that makes it an especially useful graph-based clustering technique. You can find the notes below
And you can find a ZIP file with the MATLAB code used to generate figures for these notes here. The code consists of two toys that allow you to place an arbitrary number of points anywhere you want on a blank canvas and then compare various clustering algorithms – they’re hella fun to play with.