A novel spectral clustering algorithm based on neighbor relation and Gaussian kernel function with only one parameter

Spectral clustering has become a prevalent option for data clustering as it performs well on non-convex spatial datasets with sophisticated structures. The spectral clustering effects depend on the construction of the similarity graph matrix. In this paper, in order to further enhance the clustering performance, we propose a novel similarity measure function based on neighbor relations. The proposed method is called SC-NR. It uses the Gaussian kernel function to measure the similarity between two objects. Since Euclidean distance cannot fully reflect the relation between data, this method adds a weight related to the order of nearest neighbors to the distance between two points. The similarity is better expressed by weighted-Euclidean distance. In experiments, we compared the proposed method with the previous works via the external indexes, that is, clustering accuracy (ACC), normalized mutual information (NMI), and F-measure. The comparison of indexes with state-of-the-art methods demonstrates the superiority of our algorithm. The experiment includes six synthetic datasets and twelve real-world datasets. For instance, in the PenDigits dataset F-measure metric is 16.50% higher than the current algorithms.