A Multiscale Spectral Method for Learning Number of Clusters

We propose a novel multiscale, spectral algorithm for estimating the number of clusters in a data set. Our algorithm computes the eigenvalues of the graph Laplacian iteratively for a large range of values of the scale parameter, and estimates the number of clusters from the maximal eigengap. Thus variation of the scale parameter, which usually confuses the clustering problem, is used to infer the number of clusters in a robust and efficient way. Commute distances are used to transform the distance matrix into a block-diagonal form, allowing the algorithm to succeed on irregularly shaped clusters, and the algorithm is applied to test data sets (both simulated and real-world) for method validation.