A fast Nyström method based spectral clustering algorithm

The usage of sampling thought in the spectral clustering effectively solves the high computational complexity problem of the spectral clustering algorithm. However, traditional random sampling may reduce the stability or validity of some spectral clustering algorithms. To make up the insufficiencies of the spectral clustering algorithm involving the random sampling, a Fast NYStröm method based spectral clustering algorithm (FNYS) is designed in this paper. FNYS adopts a sampling selection strategy using the probability distribution function to improve the quality of the sampling points. The quality of spectral clustering algorithm is improved by introducing the strategy. FNYS chooses some samples judiciously by a probability distribution function and solves the problem of eigendecomposition using the Nyström method. The experiments on several UCI datasets show that FNYS has better clustering quality than several current popular spectral clustering methods and is faster than other two spectral clustering algorithms using the Nyström method.