APPROXIMATE SPECTRAL LEARNING USING NYSTROM METHOD

Abstract

Constrained clustering algorithms as an input have a data set and constraints which inform it whether to put two items in the same cluster or not. Spectral clustering algorithms compute cluster assignments from eigenvectors of a matrix that is computed from the data set. In this paper, we study the class of constrained spectral clustering algorithms that incorporate constraints by modifying the graph adjacency matrix. The proposed algorithm combines Nystrom method with the existing spectral learning algorithm to produce a linear (in the number of vertices) time algorithm. We tested our algorithm on real world data sets and we demonstrated that it shows better results on some data sets than the original algorithm. In the end, we propose an algorithm for constrained multi view data clustering.