We advocate Laplacian K-modes for joint clustering and density mode finding,
and propose a concave-convex relaxation of the problem, which yields a parallel
algorithm that scales up to large datasets and high dimensions. We optimize a
tight bound (auxiliary function) of our relaxation, which, at each iteration,
amounts to computing an independent update for each cluster-assignment
variable, with guaranteed convergence. Therefore, our bound optimizer can be
trivially distributed for large-scale data sets. Furthermore, we show that the
density modes can be obtained as byproducts of the assignment variables via
simple maximum-value operations whose additional computational cost is linear
in the number of data points. Our formulation does not need storing a full
affinity matrix and computing its eigenvalue decomposition, neither does it
perform expensive projection steps and Lagrangian-dual inner iterates for the
simplex constraints of each point. Furthermore, unlike mean-shift, our
density-mode estimation does not require inner-loop gradient-ascent iterates.
It has a complexity independent of feature-space dimension, yields modes that
are valid data points in the input set and is applicable to discrete domains as
well as arbitrary kernels. We report comprehensive experiments over various
data sets, which show that our algorithm yields very competitive performances
in term of optimization quality (i.e., the value of the discrete-variable
objective at convergence) and clustering accuracy.

我们提出了一种新的算法 Laplacian K-modes，并通过优化一个紧密的辅助函数提高了其可伸缩性，进而实现了大规模数据的并行化聚类和密度模式查找，并在各种数据集上进行了全面的实验。

可扩展的拉普拉斯 K-modes

Scalable Laplacian K-modes

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.

提出一种新算法 - Laplacian K-modes 聚类算法，它融合了聚类中三种不同的思想：K-means 中的隐式分配变量，mean-shift 中的密度估计，和图拉普拉斯正则化效应中的近邻点相似性分配，该算法可以解决难以聚类的问题，同时提供了一个预测新点的软分配映射。