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.