Fast Spectral Clustering via Pseudo-Label-Based Granular-Ball Division for Large-Scale Data

Although spectral clustering is capable of identifying clusters of arbitrary shapes, its high time and space complexity poses limitations in large-scale data clustering applications. To tackle this problem, researchers have proposed using anchor points to construct the similarity matrix, thereby reducing time and space complexity. However, current methods for generating anchor points do not fit the data well and are limited in approach. To improve upon existing anchor points generation methods, we proposes a pseudo-label-based anchor points generation approach and develops a fast spectral clustering algorithm for large-scale data, named FSC-PLGB. The algorithm first randomly selects r points as an initial granular-ball, applies K-Means on these points to obtain pseudo-labels, calculates the pseudo-purity of the granular-ball based on these pseudo labels, and then performs granular-ball division based on these pseudo-purity to generate anchor points. A similarity matrix is constructed between all sample points and anchor points, and finally, spectral clustering is applied to obtain the clustering results. The experimental results demonstrate that our proposed algorithm exhibits exceptional efficiency and significant superiority on large-scale datasets. The source code is available at https://github.com/DongdongCheng/FSC-PLGB.