Constrained Spectral Clustering Using Nyström Method

Spectral clustering belongs to unsupervised learning. As for most unsupervised methods, how to encode semi-supervised constrains into spectral clustering remains a developing issue. In the algorithm of spectral clustering, the eigen-decomposition suffers from severe computational complexity. In this paper, we propose constrained spectral clustering using Nystrom Method. By modifying the graph adjacency matrix, we incorporate the semi-supervised constrains into the spectral clustering. Meanwhile, it’s the aim to approximately produce a linear time algorithm through combining the Nystrom method with spectral clustering algorithm. In the experiment, we validate the proposed algorithm on real-world and synthetic dataset. Compared with other cluster methods, the proposed algorithm has better performance in clustering accuracy and computational complexity.