Li Hongmin ; Ye Xiucai ; Imakura Akira ; Sakurai Tetsuya

Abstract

Spectral clustering is one of the most popular clustering methods. However,how to balance the efficiency and effectiveness of the large-scale spectralclustering with limited computing resources has not been properly solved for along time. In this paper, we propose a divide-and-conquer based large-scalespectral clustering method to strike a good balance between efficiency andeffectiveness. In the proposed method, a divide-and-conquer based landmarkselection algorithm and a novel approximate similarity matrix approach aredesigned to construct a sparse similarity matrix within low computationalcomplexities. Then clustering results can be computed quickly through abipartite graph partition process. The proposed method achieves a lowercomputational complexity than most existing large-scale spectral clusteringmethods. Experimental results on ten large-scale datasets have demonstrated theefficiency and effectiveness of the proposed method. The MATLAB code of theproposed method and experimental datasets are available athttps://github.com/Li-Hongmin/MyPaperWithCode.