******************
Title:  "An Out-of-Sample Extension for Spectral Clustering based on
Weighted Kernel PCA"
Authors:  Carlos Alzate and Johan A. K. Suykens
Institution: ESAT-SCD-SISTA, K. U. Leuven.
Presentation: Oral

Abstract:

The objective of clustering is to discover patterns and structures of a
dataset in an unsupervised manner.  This fundamental problem has become
increasingly important in machine learning, image processing and pattern
recognition.  Spectral clustering methods use the eigenvectors of an
affinity matrix derived from the data.  This matrix is generally
interpreted as the adjacency matrix of an undirected graph and the
clustering of the data consists of fulfilling some partitioning
criterion.  In general,  the optimization of this criterion is normally
NP-hard.  An approximate solution can be obtained by relaxing a discrete
constraint present in the partitioning criterion.  This relaxed solution
is given by an eigenvalue problem of the affinity matrix.   Spectral
clustering methods are known to perform well  in cases where classical
techniques (k-means, linkage, etc.) fail.  However, the clustering they
provide is only for training points without an extension to
out-of-sample data points.

Kernel PCA is an unsupervised learning method used for nonlinear feature
extraction.  The objective is to find projected data in a kernel induced
feature space with maximal variance.  The solutions  correspond to the
eigenvectors of the kernel matrix of the data.  In this work,  we
present an extension to out-of-sample points for spectral clustering
methods based on weighted kernel PCA.  The proposed extension is based
on primal-dual insights provided by the weighted kernel PCA framework.
Empirical results with toy and real-life data show improvements in terms
of generalization to new data.
***************