4
$\begingroup$

What is spectral clustering? I have little background in statistics. I have tried to search for notes online but they assume quite a lot of knowledge.

Would be good if you are able to find some notes online which teach the basics and the math foundations for spectral clustering

I have found notes like this one which require a lot of background knowledge which are not suitable for me

Improve this question
$\endgroup$
2
  • $\begingroup$ Are there specific things that you'd like to understand? What do you need spectral clustering for? $\endgroup$
    – Valentin Calomme
    Commented Jul 10, 2018 at 12:39
  • $\begingroup$ This tutorial on spectral clustering is very good imo arxiv.org/pdf/0711.0189.pdf $\endgroup$
    – Eric A. Bunch
    Commented Dec 6, 2018 at 17:46

2 Answers 2

Reset to default
6
$\begingroup$

Spectral clustering is an algorithm for data clustering that uses the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions.

The similarity matrix includes the relative similarity of each pair of points in the available dataset.

Improve this answer
$\endgroup$
2
1
$\begingroup$

Spectral clustering is a family of algorithms for treating larger datasets with complex-network representations. "Large" means "more than a few thousands of nodes but not gigantic". The slides you've linked to say the mathematical theory was developed since the 1970s for undirected graphs. Extensions exist for directed graphs and undirected graphs (see slide 20/20 in the tutorial you've linked to).

For some background, maybe read chapter 11, specifically 11.2 and 11.5 of M.E.J. Newman's Book "Networks". The 11.2 Chapter Title is called "Dividing networks into clusters". Chapter 11.5 is "Spectral [graph] partitioning" - the method from which spectral clustering evolved according to slide 20 in http://ranger.uta.edu/~chqding/Spectral/spectralA.pdf you've linked to.

The thick (800 page) book "Networks" is an interdiciplinary introduction, and it is very verbose, and it starts from basics. However the book discusses many other things besides clustering. It is also not online, maybe get it through inter-library loan.

I also like the introduction of Andrew Ng's et al's 2002 short Paper "On spectral clustering: Analysis and an algorithm" see "https://ai.stanford.edu/~ang/papers/nips01-spectral.pdf

... Despite the empirical successes, different authors still disagree which eigenvectors to use and how to derive clusters from them [...] also, the analysis of these algorithms [...] focus on simplified algorithms that only use one eigenvector at a time"

But this was 2002, a lot might have changed since then.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.