Persistence-Based Clustering in Riemannian Manifolds
Persistence-Based Clustering in Riemannian Manifolds
复制标题
DOI：
10.1145/2535927
复制
发表时间：
2013-11-01
影响因子：
2.5
通讯作者：
Skraba, Primoz
中科院分区：
文献类型：
--
作者：
Chazal, Frederic;Guibas, Leonidas J.;Skraba, Primoz
我们提出了一个聚类方案，结合了模式搜索阶段与集群合并阶段在相应的密度图。虽然模式检测是由一个标准的基于图的爬山计划，我们的方法的新奇在于它使用的拓扑持久性，以指导合并的集群。我们的算法提供了额外的反馈在一组点的形式在平面上，称为持久性图（PD），这可证明反映的密度模式的连续性。在实践中，这种反馈使用户能够选择相关的参数值，以便在温和的采样条件下，算法将输出正确数量的聚类，这是一个可以在持久性理论中正式发声的概念。此外，输出聚类的空间位置与密度峰值的吸引盆的空间位置相关联。该算法只需要粗略估计数据点的密度，以及它们之间的（近似）成对距离。因此，它适用于任何度量空间。同时，它的复杂性仍然是实用的：虽然输入距离矩阵的大小可能高达数据点数量的二次方，但仔细的实现只使用线性量的内存，并且运行时间几乎不比读取输入多。
We present a clustering scheme that combines a mode-seeking phase with a cluster merging phase in the corresponding density map. While mode detection is done by a standard graph-based hill-climbing scheme, the novelty of our approach resides in its use of topological persistence to guide the merging of clusters. Our algorithm provides additional feedback in the form of a set of points in the plane, called a persistence diagram (PD), which provably reflects the prominences of the modes of the density. In practice, this feedback enables the user to choose relevant parameter values, so that under mild sampling conditions the algorithm will output the correct number of clusters, a notion that can be made formally sound within persistence theory. In addition, the output clusters have the property that their spatial locations are bound to the ones of the basins of attraction of the peaks of the density.The algorithm only requires rough estimates of the density at the data points, and knowledge of (approximate) pairwise distances between them. It is therefore applicable in any metric space. Meanwhile, its complexity remains practical: although the size of the input distance matrix may be up to quadratic in the number of data points, a careful implementation only uses a linear amount of memory and takes barely more time to run than to read through the input.