Regularized Spectral Learning

Abstract

Spectral methods cluster data represented as pairwise similarities between data points. The similarities are considered as given, but in any practical application, they have to be constructed by a domain expert. In this paper we address the problem of automatically learning the similarities as a function of observed features, in order to optimize spectral clustering results on future data. We formulate a new objective for learning in spectral clustering, that balances a clustering quality term, the gap, and a stability term, the eigengap, with the later in the role of a regularizer. We prove a large eigengap corresponds to clustering stability and that using the eigengap as a regularizer is natural. We derive an algorithm to optimize this objective and choose the optimal regularization. Experiments which confirm the validity of the approach are presented.