Kernel Spectral Clustering: Model Representations, Sparsity and Out-of-sample Extensions
Johan A. K. Suykens, Carlos M. Alzate · 2011
In this talk we propose a kernel-based learning framework for spectral clustering. We conceive underlying predictive models with primal and (Lagrange) dual model representations, where the training equation is a generalized eigenvalue problem related to random walks spectral clustering. The primal model is expressed in terms of feature maps, whose existence is guaranteed by specifying positive definite kernels at the dual level. The method enables making out-of-sample extensions and evaluating the underlying models on training, validation and test data. In this way piecewise constant properties of the eigenvector solutions in spectral clustering can be extended beyond the training data level. The model selection procedure (to select kernel parameters and the number of clusters) aims at achieving such desirable structural properties at validation level, with good generalization. The out-of-sample extension property can also be used for obtaining sparse model representations. The approach is effective for handling large scale problems and outperforms a Nystrom approximation that employs a finite dimensional approximation to the feature map based on a subset of the data. For image segmentation problems we show how highly sparse kernel-based models can be obtained. The primal constrained optimization problem of kernel spectral clustering is also suitable for incorporating additional prior knowledge into the model, by inserting additional sets of constraints. Both the optimal model representations and a modified generalized eigenvalue problem follow from the conditions for optimality. We illustrate the methods on applications of image segmentation and clustering electrical power grid time-series.