在给定测地线的成对距离矩阵的情况下,哪些算法可用于生成流形的欧几里德嵌入？

Question

我有一个方形矩阵D(目前表示为一个形状为numpy的阵列(572,572)),似乎对应于沿大致圆柱形物体表面的点之间的成对距离.即,该值D[i,j]对应于沿该空心圆柱体表面的任何路径的最小长度.如何构建这些572个点的三维(或n维)嵌入欧几里德空间,以保留那些测地距离？

目前的尝试

局部线性嵌入和isomap等算法能够采用成对测地距离的矩阵并输出嵌入,以便成对的欧氏距离与原始测地线相同.虽然这通常不是同一个任务,但是在输出碰巧接近某个维度的超立方体的情况下,实际发生了所需的变换(考虑瑞士卷),因为嵌入本身就是一个流形,因此欧几里德距离对应于测地线距离.

对于像气缸这样稍微复杂的物体,情况并非如此.通过将测地距离视为欧几里德,期望圆柱上的对映点被映射到彼此远离期望的位置,并且相应的全局优化问题将经常导致分支结构,其中分支的末端对应于最远的对映点,放大气缸随机采样中的小扰动.通常,这些算法的天真应用似乎并不能解决手头的问题.

另一种有点富有成效(虽然昂贵)的方法是一种粗暴的蒙特卡罗技术.我从具有不同参数的管状物体中生成随机样本,直到我找到一组参数生成与我的类似的测地距离矩阵,直到排列(通过求解将该距离矩阵转换为采矿和测试的线性系统处理效率不是太低)查看结果是否接近排列矩阵).然后通过找到与上述近置换矩阵最接近的置换矩阵来执行从我的572点到保持成对距离的对象的近似最佳映射.

这会产生合理的结果,但它预先假定数据的形状并且非常昂贵.我已经执行了一些更明显的优化,比如使用小的随机样本而不是整个数据集,并使用基于梯度的技术进行参数估计,但更通用的技术会很好.

注意事项

这个问题当然没有一个独特的解决方案.即使假设可以通过有限均匀采样在3空间中明确地识别流形,也只是压缩圆柱体产生具有相同测地线和不同欧氏距离的形状(因此不同的嵌入).这不会比LLE和Isomap产生不同的解决方案更让我困扰,我会对任何合理的答案都很好.

关于从有限样本中唯一地识别流形,为了论证,我可以很好地使用来自包中dist_matrix_的拟合Isomap类的属性scikit-learn而没有任何特殊参数来找到测地线.这是一个不必要的MDS步骤,但它并不是非常昂贵,而且开箱即用.然后我们想要一个嵌入,它最小化原始测地距离矩阵和dist_matrix_属性之间的frobenius距离.

Answer 1

虽然我最初排除了局部线性嵌入和其他类似技术，但这似乎很仓促。由于流形实际上是局部线性的，因此采样充分、良好的流形具有以下特性：其小测地距离与其相应的欧几里德距离大致相同。

考虑到这一点，任何将最近的测地线邻居视为最近的欧几里德邻居并通过测地距离近似欧几里德距离的重建将近似保留全局测地距离，直到累积误差项。这意味着所有仅使用局部距离的标准算法都能够提供近似正确的嵌入。这些包括但不限于

• 局部线性嵌入
• 等位图
• 光谱嵌入

一些经典的嵌入算法在此应用程序中将无法正常工作，因为它们试图保留所有距离，并且大测地线可能无法很好地表示欧几里德距离。例如，如果不进行修改，多维缩放就不太合适。

注意LLE 在我的初步分析中似乎产生较差结果的原因是，我的假设之一被违反了——流形被充分采样。我将其应用于具有已知所需行为的简单形状，但我错误地使用了太少的点来确保分析中的快速反馈循环。更好采样的流形的行为与预期的完全一样。