Spectral Clustering

Preface

Clustering usually starts the same way. You have a table of observations, you turn each observation into a point in space, and you look for groups of points that sit close together. K-means is the standard tool for this, and most of the time it works fine.

But sometimes the groups you care about are not blobs. They are curved, or twisted, or spread out in a shape that no centroid can describe well. A patient similarity network, a set of cells sitting along a developmental trajectory, two interleaving spirals: in all of these cases, “close in space” is not the same thing as “belongs to the same group.”

Spectral clustering however, instead of asking where each observation sits, it asks who each observation is connected to, and it uses that network of relationships to build an entirely new set of coordinates. Once those new coordinates exist, an ordinary method like k-means usually works again, because the hard part of the problem has already been solved.

To follow the chapter you only need to be comfortable with observations, distance, similarity, and the basic idea of clustering.

Start with Spectral clustering, intuition first.