Diffusion K-means clustering on manifolds: Provable exact recovery via semidefinite relaxations
Diffusion K-means clustering on manifolds: Provable exact recovery via semidefinite relaxations
复制标题
DOI：
10.1016/j.acha.2020.03.002
复制
发表时间：
2021-02-19
影响因子：
2.5
通讯作者：
Yang, Yun
中科院分区：
文献类型：
--
作者：
Chen, Xiaohui;Yang, Yun
我们引入了黎曼子流形上的扩散 K 均值聚类方法，该方法根据扩散距离最大化簇内连通性。扩散 K 均值在相似性图上构建随机游动，其中顶点作为流形上随机采样的数据点，边缘作为捕获流形局部几何形状的内核给出的相似性。扩散K均值是一种多尺度聚类工具，适用于混合维度中具有非线性和非欧几何特征的数据。给定簇的数量，我们通过半定规划（SDP）提出了一种多项式时间凸松弛算法来求解扩散 K 均值。此外，我们还提出了一种适应簇数量的核范数正则化SDP。在这两种情况下，我们都表明，在适当的簇间可分离性和子流形的簇内连通性下，可以实现扩散 K 均值的 SDP 的精确恢复，它们共同量化了流形聚类问题的难度。我们进一步通过使用从最近邻居估计的局部自适应带宽提出局部扩散 K 均值。我们表明，局部扩散 K 均值的精确恢复完全适应局部概率密度和底层子流形的几何结构。 (C) 2020 Elsevier Inc. 保留所有权利。
We introduce the diffusion K-means clustering method on Riemannian submanifolds, which maximizes the within-cluster connectedness based on the diffusion distance. The diffusion K-means constructs a random walk on the similarity graph with vertices as data points randomly sampled on the manifolds and edges as similarities given by a kernel that captures the local geometry of manifolds. The diffusion K-means is a multi-scale clustering tool that is suitable for data with non-linear and non-Euclidean geometric features in mixed dimensions. Given the number of clusters, we propose a polynomial-time convex relaxation algorithm via the semidefinite programming (SDP) to solve the diffusion K-means. In addition, we also propose a nuclear norm regularized SDP that is adaptive to the number of clusters. In both cases, we show that exact recovery of the SDPs for diffusion K-means can be achieved under suitable between-cluster separability and within-cluster connectedness of the submanifolds, which together quantify the hardness of the manifold clustering problem. We further propose the localized diffusion K-means by using the local adaptive bandwidth estimated from the nearest neighbors. We show that exact recovery of the localized diffusion K-means is fully adaptive to the local probability density and geometric structures of the underlying submanifolds. (C) 2020 Elsevier Inc. All rights reserved.