# Spectral vs Kmeans

What makes Spectral clustering better than Kmeans clustering? I understand that Kmeans clustering is the final step of Spectral. But why is it that the previous steps involved in Spectral clustering make it a more convenient clustering approach?

Visually speaking, k means cares about distance (Euclidean?) while spectral is more about connectivity since it is semi-convex.

So, your problem will direct you to which to use (geometrical or connectivity).

Spectral clustering usually is spectral embedding, followed by k-means in the spectral domain.

So yes, it also uses k-means. But not on the original coordinates, but on an embedding that roughly captures connectivity. Instead of minimizing squared errors in the input domain, it minimizes squared errors on the ability to reconstruct neighbors. That is often better. The main reason why spectral clustering is not too popular is because it is slow (usually involves building a O(n²) affinity matrix, and finding the eigenvectors can be up to O(n³) time) and you still need to rely on the original distances/similarities to build the input graph before embedding. Most of the difficulty of clustering is in handling the data to get reliable distances/similarities...

• Original similarities, not distances. The goal of spectral embedding a.k.a. Laplacian Eigenmaps is to keep original similarities of the original samples in the embedded space. Then k-means uses the distances in the embedded space. – Matthieu Brucher Oct 26 '18 at 8:19
• The similarities in the input matrix are usually - in particular when you are comparing it to k-means as the OP - derived from distances. Often just binary, the knn graph. So I am reluctant to call this input graph "original similarities" when they are derived from distances. – Has QUIT--Anony-Mousse Oct 26 '18 at 8:45
• But they are similarities. What you try to use are similarity measures, between 0 and 1. They may be derived from distances, but they don't have to. They are by essence similarities. Whether you are reluctant are not, the truth is, they are similarities. – Matthieu Brucher Oct 26 '18 at 8:51
• But that is the second step in that use case. You (don't have to, but usually you do) derive them from distances. And when you don't know what to use as distances, your similarities will be problematic, too. – Has QUIT--Anony-Mousse Oct 26 '18 at 13:00
• You can derive them from any Mercer kernel. They may not always start from actual distances. Then I agree that computing meaningful distances or similarities can be difficult. But sometimes, it's easier to compute distances, sometimes it's easier to compute similarities. But you don't have to have distances to compute similarities (especially when Euclidian distances are not relevant). – Matthieu Brucher Oct 26 '18 at 13:02