A parameter-free similarity graph for spectral clustering

• This study introduces a pre-processing step for spectral clustering.
• A parameter-free similarity graph, Density Adaptive Neighborhood (DAN), is proposed.
• DAN works on the data sets with arbitrary shaped clusters and density variations.
• DAN is robust to the number of attributes, geometric distortion and decimation.
• DAN facilitates the use of spectral clustering algorithms in various domains.

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.