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

Question

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

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

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

Answer 1

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

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

Answer 2

Вы можете «обмануть» и использовать для этого итерационный численный метод. Сначала возьмите все точки, чтобы они находились в «случайных» положениях, а затем переберите их, перемещая их друг от друга пропорционально требуемому расстоянию. При этом предпочтение будет отдаваться некоторым точкам, но, взяв среднее число ходов перед их применением, затем применение среднего уберет эту проблему. Это алгоритм O (n²), но его очень просто реализовать и понять. В приведенном ниже 2-м примере погрешность составляет << 10%, хотя она может вести себя не так хорошо, если указанные расстояния нереалистичны. </p>

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, «Просмотр данных в двух измерениях», который может быть адаптирован для 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 метр, и существует бесконечное множество решений, которые достигают этого результата