Spectral Clustering

[See my other software on SOFTPEDIA.]

Abstract

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.

Documentation

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:

Clear: clears all points on the screen.
Refresh: refreshes the screen.
Generate: generates the specified number of clusters, where each cluster contains the specified number of points.
Algorithm: selects the eigensolver (more on this below).
Spatial Radius: selects the spatial radius (more on this below).
Cluster: performs the clustering and redraws the points on the screen using different colors.

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.

Source

Here is the complete source for this demo.

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

Demo

In order to run this demo, you must have Java WebStart installed on your computer:

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.
Launch the demo:

The main window will appear on the screen shortly.