Multiscale Fast Spectral Clustering based on k-d Tree
Chongyang Zhang, Hong Chen, Chenjian Wu, Minxin Chen · 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC) · 2019
In recent years, spectral clustering has become one of the most popular clustering algorithms. However, it is difficult to be applied to large-scale data sets due to its high computational complexity of O(n3), with n the number of data points. To solve this problem, we propose a novel spectral clustering algorithm named Multiscale Fast Spectral Clustering based on k-d tree. The computational complexity of Multiscale Fast Spectral Clustering is O(nd\log n) and its memory cost is O(m), where n, m and d are the number of samples, the super-rectangular regions, features. The super-rectangular regions are obtained by k-d tree. Extensive experiments on large data sets shows that this algorithm can get accurate clustering results and achieve significant speedups.