1
$\begingroup$

I have understood why k-means can get stuck in local minima. Now, I am curious to know how the spectral k-means helps to avoid this local minima problem.

According to this paper A tutorial on Spectral, The spectral algorithm goes in the following way

  1. Project data into $R^n$ matrix

  2. Define an Affinity matrix A , using a Gaussian Kernel K or an
    Adjacency matrix

  3. Construct the Graph Laplacian from A (i.e. decide on a normalization)

  4. Solve the Eigenvalue problem

  5. Select k eigenvectors corresponding to the k lowest (or highest) eigenvalues to define a k-dimensional subspace

  6. Form clusters in this subspace using k-means

In step 6, it is using k-means. How is it overcoming the local minima problem of k-means? Moreover, what are the benefits of spectral over k-means?

If someone gives detailed insight upon this, it will be very helpful for me.

$\endgroup$

1 Answer 1

1
$\begingroup$

They are totally different approaches. Spectral Embedding is a representation of your data and it maps close data points next to each other in a new feature space. This helps k-means to deal with more separable clusters rather than original space. But this is not my answer to your question! The answer is that you need to know not only the algorithm of Spectral Clustering but how it maps data into a new vector space. If you read about that you will understand it easily. I give it a try here:

  1. Spectral Embedding (on which you apply a simple clustering and get Spectral Clustering!) is basically a graph embedding method. What graph means is out of scope of this answer and I assume you know it. In graphs, a good clustering puts those nodes who have many "within connections" (with each other) and a few "between connections" (with other parts of graph) into a cluster. See bellow image to understand more.

    enter image description here

    Red nodes have several connections to each other but one single connection relates them to other parts of graph. It is a good cluster, right?

    An application example could be suggesting friends in Facebook. Facebook is a graph in which each node is a person and each connection implies friendship on FB. You have many connections with your circle of friends and others have the same "cluster of friends" too. If we cluster people on FB graph, we can check which people in same cluster are not friends and we suggest them to each other, right?!

    Based on brilliant work of Miroslav Fiedler called "Algebraic Connectivity of Graphs", this graph clustering can happen easily by finding those edges that removing them, clusters data in the way I mentioned above.

    Spectral Clustering is mainly doing it. Now the question is "How can I get benefit of such graph representation in a clustering problem which is hard for k-means?"

  2. Look at image bellow. It is a famous example of non-linearly separable data that k-means easily fails to cluster (because red points are between any two blue points which are on different sides of blue circle. K-means gets confused here!)

    enter image description here

    Now we convert our data into a graph using the rule each data point is a node and every node is connected to its k-nearest neighbours. How will that graph look like?! It will densely connect the nodes related to blue points to each other, and nodes related to red points to each other and probably very little connection between any blue and red node as they are barely in neighbourhood of each other. What we did was "converting non-linearly separable but connected circles in original space into connected bunches of nodes in graph representation". Now we just need to turn the graph representation into numerical vectors and Taddaaa! we will have those strange clsusters as two beautifully separable bunches of points here k-mean does not get confused anymore!

DISCLAIMER: There are many simplifications and not accurately use of terms in my answer. I tried to be intuitive more than accurate (e.g. our example data will result in two disconnected subgraphs which need numerical solution to be clustered using spectral clustering but does not affect the concept anyways)

$\endgroup$
9
  • $\begingroup$ I have understood your beautiful answer,. After reading many papers and blogs related to this , I have reached to this point math.stackexchange.com/questions/4421842/… and the lines written in bold part are now clear for me. Nonlinearity gets solved by Spectral through it's spectral embedding magic tool. But still my concern is after feeding those points to k-means converging to local minina may occur. How it is avoided? $\endgroup$
    – Amartya
    Apr 11 at 14:45
  • $\begingroup$ Ah ok ... so keep something in mind. K-means never falls into local minima if clusters are separated gaussians! This is the rule you need to know and then my answer makes sense to you. spectral clustering maps all related points in original space to a bunch of points next to each other (as I explained). In this new mapping, clusters are much more gaussian-like than original space. That is the trick! in our example one cluster is literally inside the other one but their spectrally embedded version creates two separated cluster which are much closer to the concept of being normally distributed. $\endgroup$ Apr 11 at 17:01
  • $\begingroup$ In other words, spectral embedding helps to create non-convex clusters as it follows the minimum (or normalized) cut approach toward clustering problem $\endgroup$ Apr 11 at 17:11
  • $\begingroup$ I have completely understood the intution behind this.Thank you very much.Just one question clusters are seperated gaussians means the data points are distributed in bell shaped right? As per my knowledge the RSS function is a non convex one , so bydefault if we are going to optimize it we can stop in a local minima.... so how this rule incorporates 'K-means never falls into local minima if clusters are separated gaussians! ' $\endgroup$
    – Amartya
    Apr 11 at 17:39
  • 1
    $\begingroup$ thank you so much, I can't find better answer than this over the web. These SE forums is indeed amazing :) $\endgroup$
    – Amartya
    Apr 12 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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