Abstract: The traditional spectral clustering algorithm with Gaussian kernel function as the similarity measure has the problem that the scale parameter needs to be artificially set,and the similarity is not related to the sample distribution structure.In order to solve this problem,the shared neighbors based on the natural k-nearest neighbors are defined,and a multi-scale parameter reflecting the regional density is constructed based on the nearest neighbors information of the data points,and the similarity mea-sure is redefined with the new scale parameter.This paper proposes an adaptive spectral clustering algorithm based on relative proximity(RPASC).The improved scale parameter combines the characteristics of interval scale,sequence scale and proportional scale,embodying the relative position relationship between data points and reflecting the distribution characteristics and spatial structure of different density clusters,which improves the adaptability of the algorithm to different distribution datasets.The new similarity measure adaptively reduces the similarity of data points on cluster boundaries of different densities by flexibly adjusting the size of local scale parameter,making cluster boundaries more explicit,which is conducive to discovering the true cluster morphologies.Experiments on synthetic datasets and UCI real datasets verify the effectiveness of the RPASC algorithm on multiple clustering performance indicators.

Key words: Spectral clustering,Multi-scale parameter,Shared neighbors,Natural k-nearest neighbors,Similarity measure