6
$\begingroup$

From the image linked to below, it looks like when the data actually consists of K isotropic clusters, Spectral Clustering does as well as K-means. But for other, non-convex clusters, Spectral Clustering outperforms k-means. Is this true? When should I use K-Means clustering instead of Spectral Clustering?

Also, to find clusters of the forms shown in rows 1 and 2, what similarity function do I need to use in conjunction with SpectralClustering?

Scikit learn's clustering method comparisons

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

k-means is much much much faster.

K-means is hard to beat performance wise, so it will work on larger data sets. That is probably the key factor.

K-means is $O(n.k.d.i)$, i.e. linear.

For large data sets, anything of $O(n^2)$ or worse is prohibitive.

Spectral clustering is in $O(n^3)$.

Which means it won't work for any reasonably large data set. It took already 7 seconds on a strong CPU for that second image - don't try this on larger data, you will not be happy.

P.S. that image is outdated. The current version can be found in the sklearn documentation (not embedding, as I don't know if the image is CC-BY-SA-3.0 licenseable or not... your image upload may be violating copyright, although I doubt you'll get into trouble ...)

Note the runtime information. k-means and DBSCAN take <0.02s on each of these tiny toy data sets, whereas spectral clustering is 23-734 times slower. Only affinity propagation is similarly bad.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. So from the link you provided, it looks like spectral clustering is suited for 'non-flat geometries' whereas k-means is suited to 'flat geometries'. Speed aside, is k-means a more powerful (in a pseudo-statistical sense) tool than spectral clustering when you are actually interested in flat geometries. Meaning, if the true clusters are flat, isotropic groups, is spectral clustering more likely to be sidetracked by noise and pickup non-flat clusters instead? $\endgroup$
    – user3279453
    Commented May 4, 2015 at 18:30
  • 1
    $\begingroup$ k-means itself is all but robust to noise... don't look to hard for theoretical advantages. Real data doesn't adhere to theoretical models well. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented May 4, 2015 at 19:51
  • $\begingroup$ So as a rule of thumb, if computation time/speed isn't an issue, your feeling is I wont go awry if I replace k-means with spectral analysis as my go-to cluster technique? $\endgroup$
    – user3279453
    Commented May 4, 2015 at 21:20
  • $\begingroup$ Choosing k is hard enough. Sure you want to choose all the parameters of spectral clustering (in particular kernel parameters aren't the easiest to set...) $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented May 4, 2015 at 21:53

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.