Comparing Spectral partitioning / clustering (with Normalized Graph Laplacian) with KMeans Clustering in R

In this article, the clustering output results of Spectral clustering (with normalized Laplacian) is going to be compared with KMeans on a few shape datasets. The following figures taken from the slides from the Coursera Course: Mining Massive Datasets by Stanford University describe the basic concept of spectral clustering and the spectral partitioning algorithm.



  1. The spectral clustering algorithm has many variants. In this article, The following algorithm (by Ng. et al) is going to be used for spectral clustering (with normalized Laplacian).algo.png
  2. The following figures / animations show the spectral clustering results with different Gaussian similarity kernel bandwidth parameter values on different shape datasets and also the comparison with the results obtained using the KMeans counterpart.circlescirclesmoonsmoons
  3. Finally, both KMeans and Spectral clustering (with bandwidth=0.1) algorithms are applied on an apples and oranges image to segment the image into 2 clusters. As can be seen from the next figure, the spectral clustering (by clustering the first two dominant eigenvectors of the Normalized Laplacian) could separate out the orange from the apples, while the simple KMeans on the RGB channels could not.


    4. The following simpler spectral partitioning approach (thresholding on the second dominant eigenvector) can also be applied for automatic separation of the foreground from the background.


The following figure shows the result of spectral partitioning for automatic
separation of foreground from the background on another image.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s