Large-scale spectral clustering based on pairwise constraints

摘要

In this paper, we present an efficient spectral clustering method for large-scale data sets, given a set of pairwise constraints. Our contribution is threefold: (a) clustering accuracy is increased by injecting prior knowledge of the data points' constraints to a small affinity submatrix; (b) connected components are identified automatically based on the data points' pairwise constraints, generating thus isolated "islands" of points; furthermore, local neighborhoods of points of the same connected component are adapted dynamically, and constraints propagation is performed so as to further increase the clustering accuracy; finally (c) the complexity is preserved low, by following a sparse coding strategy of a landmark spectral clustering. In our experiments with three benchmark shape, face and handwritten digit image data sets, we show that the proposed method outperforms competitive spectral clustering methods that either follow semi-supervised or scalable strategies.