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

问题描述 投票:7回答:2

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

目前的尝试

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

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

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

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

注意事项

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

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

python algorithm numpy matrix scikit-learn
2个回答
1
投票

虽然我最初排除了局部线性嵌入和其他类似技术,但这似乎已经匆忙。由于流形实际上是局部线性的,因此充分良好采样,足够好的流形具有其小的测地距离与其相应的欧氏距离大致相同的特性。

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

  • 局部线性嵌入
  • ISOMAP
  • 光谱嵌入

一些经典的嵌入算法在这个应用程序中无法正常工作,因为它们试图保留所有距离,而大的测地线可能是欧氏距离的不良表示。例如,多维缩放是不合适的,没有修改。

注意LLE似乎在我的初步分析中产生不良结果的原因是我的一个假设被违反 - 多样性被充分抽样。我将它应用于具有已知所需行为的简单形状,但我错误地使用了太少的点来确保我的分析中的快速反馈循环。更好采样的流形行为与它们应该完全一样。


0
投票

本博士论文的第四章

“关于固定观点图像序列中的运动参数化”,Manfred Georg,华盛顿大学,2010年

可用:https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1127&context=etd

讨论了这些问题中的一些,其算法取决于例如歧管是否真的是圆柱体(或圆锥体或其他部分),以及圆柱体的相对宽度和长度。

根据您的最终目标,t-SNE等替代品可能更适合;它们完全降低了全球测地距离约束,因此可以更灵活地使用圆柱形等不可能嵌入欧氏空间并保留测地线的形状。

© www.soinside.com 2019 - 2024. All rights reserved.