二维抽象距离拟合算法



假设我们得到了少量对象以及它们之间的"距离"——有什么算法可以将这些对象以近似这些距离的方式拟合到二维空间中的点?

这里的困难在于"距离"不是欧几里得空间中的距离——这就是为什么我们只能拟合/近似。

(对于那些对距离的概念究竟是什么感兴趣的人来说,它是(有限)集的幂集上的对称距离度量)。

给定对象的数量很小,您可以创建一个无向加权图,其中这些对象将是节点,任何两个节点之间的边的权重对应于这两个对象之间的距离。最终得到n*(n-1)/2条边。

一旦创建了图形,就会有很多与图形相对应的可视化软件和算法。

尝试一种三角测量方法,类似这样的方法;

  • 首先取三个相距已知距离的对象,然后根据边长在任意网格中创建一个三角形。

  • 对于每个尚未放置的附加对象,至少找到三个已知距离的其他已放置对象,并使用这些距离使用距离/距离交点(即以距离半径固定点为中心的三个圆的交点)放置对象

  • 重复此操作,直到放置完所有对象,或者不能再放置任何对象为止。

对于未放置的对象,可以开始另一个类似的练习,然后使用任何可用的距离来关联单独的簇。查找三角测量和三边测量网络以获取更多信息。

编辑:根据下面的评论,如果距离是近似的,并且包含误差元素,则可以使用上述方法为每个对象建立临时坐标,然后可以使用最小二乘法(如坐标变化)调整这些坐标。这也可以根据需要根据距离的大小对距离进行加权。有关更详细的描述,请查看Ghilani&沃尔夫关于这个主题的书。这在很大程度上取决于你的距离之间差异的性质,以及你希望你的物体如何基于这些距离在欧几里得空间中表示。这种关系需要作为任何解决方案的一部分进行建模和应用。

这是多维缩放的一个例子,或者更一般地说,是非线性降维。有相当多的工具/库可用于实现这一点(请参阅第二个链接以获取列表)。

最新更新