从一组成对距离中确定点的位置

Question

如果给定一个点之间的距离矩阵，是否有一种算法可以确定一个具有这些距离的n维点集？（或者至少最小化误差）

有点像转运问题的n维版本。

我能想到的最好方法是使用多维缩放。

- mat kelcey

---

我不知道你的矩阵长什么样，或者你真正想要做什么。你能重新表述一下问题吗？ - Mecki

Answer 1

你在使用多维缩放（MDS）方面走上了正确的道路，但是MDS对于大型数据集来说不实用，因为其时间复杂度与点数呈二次关系。你可能想要看一下FastMap，它具有线性时间复杂度，并且更适合索引。请参见：

Christos Faloutsos和King-Ip Lin： "FastMap：一种快速算法，用于 传统和多媒体数据集的索引、数据挖掘和 可视化，在Proc. SIGMOD，1995年，doi:10.1145/223784.223812

- Vebjorn Ljosa

Answer 2

您可以使用一种迭代数值方法来“欺骗”，使其与此相关。首先，将所有点置于某些“随机”位置，然后循环遍历它们，按所需距离的比例将它们彼此分开。这将更喜欢某些点，但在应用它们之前取平均移动量，然后应用平均值将消除此问题。这是一个O(n²)算法，但非常容易实现和理解。在下面的2D示例中，误差小于10%，尽管如果给出的距离不合理，则可能表现不佳。

C++示例：

#include <conio.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define DAMPING_FACTOR 0.99f

class point
{
public:
    float x;
    float y;
public:
    point() : x(0), y(0) {}
};

// symmetric matrix with distances
float matrix[5][5] =    {
                            { 0.0f, 4.5f, 1.5f, 2.0f, 4.0f },
                            { 4.5f, 0.0f, 4.0f, 3.0f, 3.5f },
                            { 1.5f, 4.0f, 0.0f, 1.0f, 5.0f },
                            { 2.0f, 3.0f, 1.0f, 0.0f, 4.5f },
                            { 4.0f, 3.5f, 5.0f, 4.5f, 0.0f }
                        };
int main(int argc, char** argv)
{
    point p[5];
    for(unsigned int i = 0; i < 5; ++i)
    {
        p[i].x = (float)(rand()%100)*0.1f;
        p[i].y = (float)(rand()%100)*0.1f;
    }

    // do 1000 iterations
    float dx = 0.0f, dy = 0.0f, d = 0.0f;
    float xmoves[5], ymoves[5];

    for(unsigned int c = 0; c < 1000; ++c)
    {
        for(unsigned int i = 0; i < 5; ++i) xmoves[i] = ymoves[i] = 0.0f;
        // iterate across each point x each point to work out the results of all of the constraints in the matrix
        // collect moves together which are slightly less than enough (DAMPING_FACTOR) to correct half the distance between each pair of points
        for(unsigned int i = 0; i < 5; ++i)
        for(unsigned int j = 0; j < 5; ++j)
        {
            if(i==j) continue;
            dx = p[i].x - p[j].x;
            dy = p[i].y - p[j].y;
            d = sqrt(dx*dx + dy*dy);
            dx /= d;
            dy /= d;
            d = (d - matrix[i][j])*DAMPING_FACTOR*0.5f*0.2f;

            xmoves[i] -= d*dx;
            ymoves[i] -= d*dy;

            xmoves[j] += d*dx;
            ymoves[j] += d*dy;
        }

        // apply all at once
        for(unsigned int i = 0; i < 5; ++i)
        {
            p[i].x += xmoves[i];
            p[i].y += ymoves[i];
        }
    }

    // output results
    printf("Result:\r\n");
    for(unsigned int i = 0; i < 5; ++i)
    {
        for(unsigned int j = 0; j < 5; ++j)
        {
            dx = p[i].x - p[j].x;
            dy = p[i].y - p[j].y;
            printf("%f ", sqrt(dx*dx + dy*dy));
        }
        printf("\r\n");
    }

    printf("\r\nDesired:\r\n");
    for(unsigned int i = 0; i < 5; ++i)
    {
        for(unsigned int j = 0; j < 5; ++j)
        {
            printf("%f ", matrix[i][j]);
        }
        printf("\r\n");
    }

    printf("Absolute difference:\r\n");
    for(unsigned int i = 0; i < 5; ++i)
    {
        for(unsigned int j = 0; j < 5; ++j)
        {
            dx = p[i].x - p[j].x;
            dy = p[i].y - p[j].y;
            printf("%f ", abs(sqrt(dx*dx + dy*dy) - matrix[i][j]));
        }
        printf("\r\n");
    }

    printf("Press any key to continue...");

    while(!_kbhit());

    return 0;
}

- Jheriko

Answer 3

这可以用《集体智慧编程》第49页“在二维中查看数据”中的算法来处理，该算法可以适用于n维数据。嘿，这是多维尺度分析，所以我想你走对了路。

- Lou Franco

Answer 4

我无法编辑原始内容，因为我的声望不够，但我已经尝试在这里重新陈述问题。

原帖提供了一个N x N距离矩阵的输入。他想要创建一个输出数组，大小为N，表示点的N维坐标，其中每个点之间的距离存储在输入矩阵中。

请注意，这在一般情况下是无法解决的：

假设我有一个像这样的矩阵

   A  B  C  
A  x  1  2  
B     x  0  
C        x  

A与B相距1个单位的距离（比如1米），A与C相距1米。但是B和C在同一位置。

在这种特殊情况下，最小误差的总和为1米，并且有无数种解决方案可以实现该结果。

- Airsource Ltd

---

我同意这个问题通常是无法解决的；因此我的“最小化误差条款”。 - mat kelcey