определение точек из множества парных расстояний

Question

Учитывая матрицу расстояний между точками, существует ли алгоритм для определения набора n-мерных точек, которые имеют эти расстояния? (или, по крайней мере, минимизирует ошибку)

вроде как n-мерная версия проблемы магистрали.

Лучшее, что я могу придумать, это использование многомерного масштабирования.

Answer 1

Вы находитесь на правильном пути с многомерным масштабированием (MDS), но MDS нецелесообразно для больших наборов данных, поскольку его временная сложность квадратична по количеству точек. Возможно, вы захотите взглянуть на FastMap, который имеет линейную сложность по времени и лучше подходит для индексации. См:

  

Христос Фалуцос и Кинг-Ип Лин:   " FastMap: быстрый алгоритм для   Индексирование, Data Mining и   Визуализация традиционных и   Наборы мультимедийных данных, в Proc.   SIGMOD , 1995, doi: 10.1145 / 223784.223812

Answer 2

Вы можете & обмануть " и использовать итерационный численный метод для этого. Возьмите все точки в некоторый & Quot; random & Quot; позиции, а затем проходите через них, перемещая их друг от друга пропорционально требуемому расстоянию. При этом предпочтение будет отдаваться некоторым точкам, но, взяв среднее число ходов перед их применением, затем применение среднего уберет эту проблему. Это алгоритм O (n & # 178;), но очень простой в реализации и понимании. В приведенном ниже 2-м примере ошибка составляет & Lt; & Lt; 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;
}

Answer 3

Алгоритм для этого есть в программировании коллективного интеллекта , стр. , 49, & Quot; Просмотр данных в двух измерениях & Quot;, которые можно адаптировать к n-измерениям.

Эй, это многомерное масштабирование, так что я думаю, вы на правильном пути.

Answer 4

Я не могу редактировать оригинал, потому что мне не хватает представителя, но я попытался здесь повторить проблему.

ОП имеет входную матрицу расстояний NxN. Он хочет создать выходной массив размером N из N-мерных координат, представляющих точки, где расстояние между каждой точкой сохраняется во входной матрице.

Обратите внимание, что это не решаемо в общем случае:

Предположим, у меня есть такая матрица

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

A - 1 единица расстояния (скажем, 1 метр) от B, а A - один метр от C. Но B и C находятся в одном месте.

В данном конкретном случае минимальная сумма ошибок составляет 1 метр, и существует бесконечное множество решений, которые достигают этого результата