Spectral Clustering

[See my other software on SOFTPEDIA.]


This is a demonstration of a Spectral Clustering algorithm using an efficient iterative Lanczos eigensolver.

The algorithm is a direct implementation of Jianbo Shi's seminal paper " Normalized Cuts and Image Segmentation".

The iterative Lanczos algorithm was implemented with guidelines from CS267 lecture notes and from Axel Ruhe's description of the Lanczos Algorithm.


This demo splits a set of points into two sets. The points can be created manually (click and drag on the screen) or randomly generated into clusters.

The algorithm assumes that points farther than 20 pixels away from the nearest neighbor cannot be in the same cluster as that nearest neighbor (this is the spatial delta factor in Jianbo Shi's paper).

Here is a screenshot of the main window:

The Lanczos eigensolver is faster than the QL eigensolver and takes less memory. With default memory settings, the application can handle around 500 points with the QL algorithm and around 1000 points with the Lanczos algorithm.

The spatial radius is used to determine how granular to make the clusters. A small spatial radius will create smaller clusters (and take less time to find them), whereas a large spatial radius will create larger clusters (and take longer to find them). The spatial radius is intuitively similar to the visibility radius around any point: the longer the radius, the farther out the algorithm searches for clusters around any given point.


Here is the complete source for this demo.

The most interesting parts are LanczosDecomposition.java and ClusteringAlgorithm.java.


In order to run this demo, you must have Java WebStart installed on your computer:
  1. Check that you have Java WebStart installed by launching a demo application at the demos site. If you do not have Java WebStart installed, download it from here.
  2. Launch the demo:
    The main window will appear on the screen shortly.