Improvement Of Normalized Spectral Clustering

As a a typical clustering algorithm based on graph theory,normalized spectral clustering is receiving more and more attention from researchers.However,it is difficult to be used in big data set clustering tasks due to its high computational complexity,such as high-resolution image segmentation.In order to apply the spectral clustering algorithm to the big data set,this paper does the following work(1)The quad-tree(for image segmentation tasks)and Kd tree(for point set clus-tering tasks)are used to improve the normalized spectral clustering and fast spectral clustering is proposed.This paper also gives the theoretical difference between clus-tering accuracy of fast spectral clustering algorithm and normalized spectral clustering algorithm.Experiments show that the fast spectral clustering outperforms the nor-malized spectral clustering in terms of efficiency,with comparable clustering accuracy.(2)Combining the hierarchical structure of quad-tree,normalized spectral clus-tering is further improved,and multi-scale fast spectral clustering algorithm is pro-posed.Experiments show that the multi-scale fast spectral clustering outperforms the normalized spectral clustering and fast spectral clustering in terms of efficiency,with comparable clustering accuracy.(3)An iterative method of solving a particular form of matrix eigenvalues and eigenvectors is proposed.Experiments show that the iterative method is effective.