通过单纯形路径距离实现对相交流形的鲁棒聚类
Robust Multi-Manifold Clustering via Simplex Paths
- 构建基于二面角的单纯形图，用最大角路径距离度量流形差异
- 在噪声、曲率和小夹角下仍能准确分离流形，优于现有方法
- 算法可扩展性强，计算复杂度接近线性，适合大规模数据
本文提出一种新颖的几何方法用于多流形聚类（MMC），即在可能相交的情况下将一组d维流形划分成各自的流形组件。首先在d-单纯形上构建局部图，以相邻单纯形间的二面角作为图权重，进而计算该单纯形图中的无穷路径距离。这一过程得到一个定义在单纯形上的度量，称为最大角路径距离（LAPD）。我们分析了在随机采样下的LAPD性质，并证明在适当的去噪处理后，该度量能以高概率分离不同流形组件。在合成与真实数据集上的大量实验验证表明，该方法对噪声、曲率及小相交角具有鲁棒性，且普遍优于其他MMC算法。此外，本文提供了高度可扩展的实现，利用无穷路径距离的近似方案，达到准线性计算复杂度。
原文摘要 · Abstract (English)
This article introduces a novel, geometric approach for multi-manifold clustering (MMC), i.e. for clustering a collection of potentially intersecting, d-dimensional manifolds into the individual manifold components. We first compute a locality graph on d-simplices, using the dihedral angle in between adjacent simplices as the graph weights, and then compute infinity path distances in this simplex graph. This procedure gives a metric on simplices which we refer to as the largest angle path distance (LAPD). We analyze the properties of LAPD under random sampling, and prove that with an appropriate denoising procedure, this metric separates the manifold components with high probability. We validate the proposed methodology with extensive numerical experiments on both synthetic and real-world data sets. These experiments demonstrate that the method is robust to noise, curvature, and small intersection angle, and generally out-performs other MMC algorithms. In addition, we provide a highly scalable implementation of the proposed algorithm, which leverages approximation schemes for infinity path distance to achieve quasi-linear computational complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。