SEMI-SUPERVISED K-WAY SPECTRAL CLUSTERING USING PAIRWISE CONSTRAINTS

In this paper, we propose a semi-supervised spectral clustering method able to integrate some limited supervisory information. This prior knowledge consists of pairwise constraints which indicate whether a pair of objects belongs to a same cluster (Must-Link constraints) or not (Cannot-Link constraints). The spectral clustering then aims at optimizing a cost function built as a classical Multiple Normalized Cut measure, modified in order to penalize the non-respect of these constraints. We show the relevance of the proposed method with an illustrative dataset and some UCI benchmarks, for which two-class and multi-class problems are dealt with. In all examples, a comparison with other semi-supervised clustering algorithms using pairwise constraints is proposed.