The Laplacian K-modes algorithm for clustering
  In addition to finding meaningful clusters, centroid-based clustering
algorithms such as K-means or mean-shift should ideally find centroids that are
valid patterns in the input space, representative of data in their cluster.
This is challenging with data having a nonconvex or manifold structure, as with
images or text. We introduce a new algorithm, Laplacian K-modes, which
naturally combines three powerful ideas in clustering: the explicit use of
assignment variables (as in K-means); the estimation of cluster centroids which
are modes of each cluster's density estimate (as in mean-shift); and the
regularizing effect of the graph Laplacian, which encourages similar
assignments for nearby points (as in spectral clustering). The optimization
algorithm alternates an assignment step, which is a convex quadratic program,
and a mean-shift step, which separates for each cluster centroid. The algorithm
finds meaningful density estimates for each cluster, even with challenging
problems where the clusters have manifold structure, are highly nonconvex or in
high dimension. It also provides centroids that are valid patterns, truly
representative of their cluster (unlike K-means), and an out-of-sample mapping
that predicts soft assignments for a new point.
