The following 3 animations illustrate clustering-by-projections of 4+8+12=24 points randomly sampled from 3 gaussian sources. Easy problems converge in 1-3 iterations:
The upper left pane shows the points, color-coded by source. The upper right pane shows an ideal block-diagonal angle matrix that we hope to obtain from clustering. The lower left pane shows the evolving angle matrix, with its positive eigenvalues superimposed in blue. The lower right pane shows the evolving eigenvectors, each depicted as a column of grayscale intensities. At convergence, the cluster assignments are read off the eigenvectors corresponding the the stochastic (unit) eigenvalues. The number of stochastic eigenvalues determines the number of clusters. Remaining eigenvalues near 1 indicate that clusters can be subpartitioned.
Harder problems take more (5) iterations to remove enough off-block energy to converge:
In the rightmost problem one can see the algorithm gradually assign the isolated red point to the red cluster. Even though it is closer to the blue cluster, it is more consistent with the scale of inter-point distances in the red cluster. Note that the Fiedler vector (2nd eigenvector), usually used for clustering, is often not very informative by itself.
Click here to see the same approach applied to a
nonrigid motion segmentation problem.