Timeline for Why does Kernel K-means work better than spectral clustering in this case?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 20, 2018 at 6:49 | history | tweeted | twitter.com/StackStats/status/965840878681149441 | ||
| Nov 12, 2016 at 19:25 | comment | added | passerby51 | You could do SVD based spectral clustering in the directed case, but I am not convinced you have a genuine directed similarity in your case. (Also, not convinced that the directedness is the root of the problem). If you are building your similarity matrix based on "n" data points, the most natural one is for x_i and x_j to have a single number as their similarity. | |
| Nov 11, 2016 at 21:52 | comment | added | Bob | I think one reason spectral algorithm has a low performance is the fact that my Adjacency matrix $W$ is directed and i symmentrize it which will distort the original formation of the data representation. So i'm looking for ways to do spectral clustering on directed graph preserving the directed formation. | |
| Nov 11, 2016 at 19:49 | comment | added | Bob | @passerby51: I run both algorithm 1000 times with different initial points to find the best performance. And i constructed $A$ for the RBF kernel exactly as you mentioned. Do you know an efficient matlab source code for spectral clustering? I was wondering.. | |
| Nov 11, 2016 at 19:31 | comment | added | passerby51 | By the way, in the spectral clustering, there is k-means step after you compute the low-D eigenvector representation of your data points .... Are you performing that step?. Unless you specify more specifically how each algorithm is implemented, it is hard to say much. | |
| Nov 11, 2016 at 19:30 | comment | added | passerby51 | usually you build the adjaceny matrix with entries $A_{ij} = K(x_i,x_j)$ where $K$ is the kernel function. This gives you a symmetric matrix, or a weighted undirected graph. Regarding the better performance, as I mentioned there is a lot of details missing. There is no single k-means algorithm. It depends on how you initialize. What initialization are you using? Random assignment? If so, do you run it once or multiple times with multiple random initial guesses? --> | |
| Nov 11, 2016 at 19:16 | history | edited | Bob | CC BY-SA 3.0 |
added 19 characters in body
|
| Nov 11, 2016 at 19:16 | comment | added | Bob | @passerby51: $W$ is not similarity matrix, you can consider it as an Adjacency matrix for a directed graph, so i need to symmetrize it for spectral clustering. Also i'm fine with the performance of kernel k-means, my problem is that the spectral clustering performance is much lower than k-kmeans even using the same similarity matrix! | |
| Nov 11, 2016 at 18:29 | comment | added | passerby51 | For example, how do you initialize "kernel k-means" iterations? Do you choose a random assignment of clusters for initialization? For example, you can use the estimate obtained from kernel spectral clustering as your initialization. I also don't understand why you need to symmetrize W. Usually a similarity matrix is symmetric by definition. | |
| Nov 11, 2016 at 18:27 | comment | added | passerby51 | This is interesting. Care to share your data (and/or your code)? The two approaches are related. See for example the paper titled "Kernel k-means, Spectral Clustering and Normalized Cuts". At a high-level spectral clustering can be thought of as a relaxation of the original kernelized k-means problem, while the iterative algorithm you refer to as kernel k-means is a local search on the original k-means objective. In general, if you have a good initial starting cluster assignment, these iterative procedures work really well. There is a lot of details not clear from your post --> | |
| Nov 11, 2016 at 17:13 | history | asked | Bob | CC BY-SA 3.0 |