A spectral clustering library, rescued from my PhD
One of the tricks in my PhD was to stop simulating every possible plan the other team might have. Instead, the system generated lots of candidate paths, grouped the similar ones together, and only simulated one from each group. The grouping was done by spectral clustering, and I’ve now pulled that code out into a small C++ library of its own: pthimon/clustering.
What it does
Most clustering methods want to know how many clusters you’re after. That’s a problem when the whole point is to find out. How many genuinely different routes are there across this map? You don’t know until you look.
Spectral clustering starts from an affinity matrix: for n things, an n × n table of how similar each pair is. You can think of it as a graph, where every item is joined to every other by an edge weighted by how alike they are. Take the eigenvectors of that matrix, and items that belong together end up close to each other in the new coordinates. From there you have two options, and the library does both:
- k-means, if you already know how many clusters you want;
- self-tuning, which works out the number of clusters itself.
The self-tuning method is Zelnik-Manor and Perona’s. It rotates the eigenvectors, trying to line them up so that each item sits clearly in one cluster and none of the others. It tries this for different numbers of clusters, scores how cleanly each one lines up, and picks the best. My code is a C++ port of their MATLAB version.
The port
I wrote it back in March 2009, using the Eigen 2 matrix library. It builds with CMake, and I’ve only tried it on Linux.
Because it’s a straight port, one file has a slightly odd style. The rotation code allocates its matrices on the heap, but passes them around as references rather than pointers. That lets Eigen’s operator overloading read naturally, and the C++ keeps the same shape as the MATLAB original.
Where it stands
It’s the thesis code, pulled out into its own repo, plus a README explaining the idea. It isn’t much, but if you need clustering in C++ and don’t know how many clusters to ask for, it might save you an afternoon with MATLAB.