CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data
This addresses a specific challenge in clustering for data with varying cluster scales, offering an incremental improvement over existing spectral clustering techniques.
The paper tackles the problem of spectral clustering on multi-scale data, where clusters vary in size and density, by proposing CAST, an algorithm that integrates reachability similarity with distance-based similarity and uses trace Lasso regularization. Experimental results show that CAST provides excellent performance and high robustness across test cases, outperforming 10 other clustering methods.
We study the problem of applying spectral clustering to cluster multi-scale data, which is data whose clusters are of various sizes and densities. Traditional spectral clustering techniques discover clusters by processing a similarity matrix that reflects the proximity of objects. For multi-scale data, distance-based similarity is not effective because objects of a sparse cluster could be far apart while those of a dense cluster have to be sufficiently close. Following [16], we solve the problem of spectral clustering on multi-scale data by integrating the concept of objects' "reachability similarity" with a given distance-based similarity to derive an objects' coefficient matrix. We propose the algorithm CAST that applies trace Lasso to regularize the coefficient matrix. We prove that the resulting coefficient matrix has the "grouping effect" and that it exhibits "sparsity". We show that these two characteristics imply very effective spectral clustering. We evaluate CAST and 10 other clustering methods on a wide range of datasets w.r.t. various measures. Experimental results show that CAST provides excellent performance and is highly robust across test cases of multi-scale data.