A parameter-free similarity graph for spectral clustering

Abstract

Spectral clustering is a popular clustering method due to its simplicity and superior performance in the data sets with non-convex clusters. The method is based on the spectral analysis of a similarity graph. Previous studies show that clustering results are sensitive to the selection of the similarity graph and its parameter(s). In particular, when there are data sets with arbitrary shaped clusters and varying density, it is difficult to determine the proper similarity graph and its parameters without a priori information. To address this issue, we propose a parameter-free similarity graph, namely Density Adaptive Neighborhood (DAN). DAN combines distance, density and connectivity information, and it reflects the local characteristics. We test the performance of DAN with a comprehensive experimental study. We compare k-nearest neighbor (KNN), mutual KNN, ε-neighborhood, fully connected graph, minimum spanning tree, Gabriel graph, and DAN in terms of clustering accuracy. We also examine the robustness of DAN to the number of attributes and the transformations such as decimation and distortion. Our experimental study with various artificial and real data sets shows that DAN improves the spectral clustering results, and it is superior to the competing approaches. Moreover, it facilitates the application of spectral clustering to various domains without a priori information.