4
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ 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 --> $\endgroup$
    – passerby51
    Commented Nov 11, 2016 at 18:27
  • $\begingroup$ 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. $\endgroup$
    – passerby51
    Commented Nov 11, 2016 at 18:29
  • $\begingroup$ @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! $\endgroup$
    – Bob
    Commented Nov 11, 2016 at 19:16
  • $\begingroup$ 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? --> $\endgroup$
    – passerby51
    Commented Nov 11, 2016 at 19:30
  • $\begingroup$ 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. $\endgroup$
    – passerby51
    Commented Nov 11, 2016 at 19:31

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.