An improvement of spectral clustering algorithm based on fast diffusion search for natural neighbor and affinity propagation

Spectral clustering algorithm has become more popular in data clustering problems in recent years, due to the idea of optimally dividing the graph to solve the data clustering problems. However, the performance of the spectral clustering algorithm is affected by the quality of the similarity matrix. In addition, the traditional spectral clustering algorithm is unstable because it uses the K-means algorithm in the final clustering stage. Therefore, we propose a spectral clustering algorithm based on fast diffusion search for natural neighbor and affinity propagation (FDAP-SC). The algorithm obtains neighbor information more efficiently by changing the way of determining the number of neighbors. And it uses the shared nearest neighbors and the shared reverse neighbors between two points to construct the similarity matrix. Moreover, the algorithm regards all data points as nodes in the network and then calculates the clustering center of each sample through message passing between nodes. In this paper, we first experimentally on real datasets to verify that our proposed method for determining the number of neighbors outperforms the traditional natural nearest neighbor algorithm. We then demonstrate on synthetic datasets that FDAP-SC can handle complex shape datasets well. Finally, we compare FDAP-SC with several existing classical and novel algorithms on real datasets and Olivetti face datasets, proving the superiority and stability of FDAP-SC algorithm performance. Among the seven real datasets, FDAP-SC has the best performance on five datasets, and in the Olivetti face datasets, FDAP-SC achieves more than 87.5% accuracy.

Automated summary

Spectral clustering algorithm has become popular in recent years for data clustering problems. However, its performance is affected by the quality of the similarity matrix and its stability is compromised by the use of the K-means algorithm. Therefore, FDAP-SC proposes a new approach that improves neighbor information retrieval and uses shared nearest neighbors for constructing the similarity matrix. It also calculates clustering centers through message passing between nodes. Experimental results show that FDAP-SC outperforms existing algorithms in terms of neighbor determination, handling complex shape datasets, and achieving high accuracy on various datasets.