Self-Tuning Spectral Clustering

TLDR

The paper addresses key challenges in spectral clustering, including scale selection, multi‑scale data handling, cluttered backgrounds, and automatic determination of cluster count. The authors introduce a local‑scale affinity computation, use eigenvector structure to estimate cluster number, and remove the random k‑means step from the algorithm. Local scaling improves clustering performance on multi‑scale and cluttered data.

Abstract

We study a number of open issues in spectral clustering: (i) Selecting the appropriate scale of analysis, (ii) Handling multi-scale data, (iii) Clustering with irregular background clutter, and, (iv) Finding automatically the number of groups. We first propose that a 'local' scale should be used to compute the affinity between each pair of points. This local scaling leads to better clustering especially when the data includes multiple scales and when the clusters are placed within a cluttered background. We further suggest exploiting the structure of the eigenvectors to infer automatically the number of groups. This leads to a new algorithm in which the final randomly initialized k-means stage is eliminated.