K-way Fast Approximate Spectral Clustering
Guofeng Zhu, Chenjian Wu, Hong Chen · 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) · 2019
In recent years, k-way spectral clustering is one of the most popular clustering algorithms. Due to its computational complexity of O(n3), with n the number of data points it is a challenging task to apply traditional spectral clustering algorithms for large-scale data sets. In this paper, we propose a novel algorithm called k-way Fast Spectral Clustering (KFSC) based on kd-tree. This algorithm is based on a theoretical analysis that provides a statistical characterization of the effect of local distortion on the mis-clustering rate. The computational complexity is O(ndl) + O(m3) + O(m2), where l is the depth of kd-tree, m is the number of representative sets (set of similar data points) and d is the dimension of data. Extensive experimental results on real data sets and synthetic data sets demonstrate that the proposed methodology outperforms Normalized cut (Ncut) in terms of computation, while achieving comparable clustering accuracy.