KNN-SC: novel spectral clustering algorithm using k-nearest neighbors

Thumbnail Image
Kim, Jeong-Hun
Choi, Jong-Hyeok
Park, Young-Ho
Leung, Carson
Nasridinov, Aziz
Journal Title
Journal ISSN
Volume Title
IEEE Access
Spectral clustering is a well-known graph-theoretic clustering algorithm. Although spectral clustering has several desirable advantages (such as the capability of discovering non-convex clusters and applicability to any data type), it often leads to incorrect clustering results because of high sensitivity to noise points. In this study, we propose a robust spectral clustering algorithm known as KNN-SC that can discover exact clusters by decreasing the influence of noise points. To achieve this goal, we present a novel approach that filters out potential noise points by estimating the density difference between data points using k -nearest neighbors. In addition, we introduce a novel method for generating a similarity graph in which various densities of data points are effectively represented by expanding the nearest neighbor graph. Experimental results on synthetic and real-world datasets demonstrate that KNN-SC achieves significant performance improvement over many state-of-the-art spectral clustering algorithms.
k-nearest neighbors, nearest neighbor graph, potential noise detection, spectral clustering
J. Kim, J. Choi, Y. Park, C.K. Leung, and A. Nasridinov, "KNN-SC: novel spectral clustering algorithm using k-nearest neighbors," IEEE Access, 2021; 9: 152616-152627.