Semi-supervised K-Way Spectral Clustering with Determination of Number of Clusters

In this paper, we propose a new K-way semi-supervised spectral clustering method able to estimate the number of clusters automatically and then to integrate some limited supervisory information. Indeed, spectral clustering can be guided thanks to the provision of prior knowledge. For the automatic determination of the number of clusters, we propose to use a criterion based on an outlier number minimization. Then, the 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 some UCI datasets. For experiments, a comparison with other semi-supervised clustering algorithms using pairwise constraints is proposed.