图上

通过 Lipschitz 嵌入和图上的最短路径精确计算流形度量

数据敏感度量自然出现在机器学习中，并且在一些著名方法中起着核心作用，例如 k-NN 图方法、流形学习、水平集方法、单链接聚类和基于欧氏 MST 的聚类（详情见第 5 节和附录 A）。构建合适的数据敏感度量是一个活跃的研究领域。我们考虑一个简单的数据敏感度量，它有一个底层流形结构，称为最近邻度量。该度量最早在 [CFM + 15] 中引入。它及其近似变体在过去已被多位研究人员研究过 [HDHI16、CFM + 15、SO05、BRS11、VB03]。在本文中，我们展示了如何精确计算任意维度的最近邻度量，这解决了任何基于流形的度量最重要和最具挑战性的问题之一。