# Why does Kernel K-means work better than spectral clustering in this case?

I want to cluster a dataset using spectral clustering. Assuming $X$ is $d \times n$ data matrix as $n$ is the number of data samples. I construct a directed Adjacency matrix $W, n \times n$ in which each row $i$ relates $x_i$ to other data points with positive weights. Then using the following Adjacency matrix with "Spectral Clustering".

$$A=\frac{(W+W^\top)}{2}$$

I compare the result with the "Spectral Clustering" when using RBF similarity kernel ($K$), the above $A$ matrix brings better results than RBF kernel (40% comparing to 58%)

But, if i use that RBF-kernel ($K$) with the kernel kmeans algorithm i achieve much better accuracy, around 90%!

So does it mean that kernel k-means is a better clustering approach for this case? or maybe i used the spectral clustering in a wrong way? BTW, i already tried "symmetric/asymmetric normalized" and "unormalized" Laplacian matrices for "Spectral Clustering" and the best is with the "unormalized" case.

• 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 --> Commented Nov 11, 2016 at 18:27
• 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. Commented Nov 11, 2016 at 18:29
• @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!
– Bob
Commented Nov 11, 2016 at 19:16
• 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? --> Commented Nov 11, 2016 at 19:30
• 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. Commented Nov 11, 2016 at 19:31