Paper review: A Tutorial on Spectral Clustering
Lately I am experimenting with spectral clustering. I find it a very interesting approach (well, family of) to clustering and I think that the paper that most helped me to have a grasp of it was "A Tutorial on Spectral Clustering", by Ulrike von Luxburg. In case you are curious about it, here is its abstract:
"In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed".
Of course this is just a beginning, and if you are interested in the topic I would also suggest you to read at least another couple of papers such as Ng, Jordan, and Weiss: "On spectral clustering: analysis and an algorithm" or "Laplacian eigenmaps for dimensionality reduction and data representation" by Belkin and Niyogi.
While reading von Luxburg's paper, I took some notes that might be handy if you want to have a brief summary of the main concepts or explain them to somebody else. I actually reused them for a class in PoliMI, empirically demonstrating that in research nothing is unuseful ;-) Here are the slides I made, enjoy!
Leave a comment