determinar puntos del conjunto de distancias por pares

Question

dada una matriz de distancias entre puntos, ¿existe un algoritmo para determinar un conjunto de puntos n-dimensionales que tiene estas distancias? (o al menos minimiza el error)

algo así como una versión n-dimensional del problema de la autopista de peaje.

Lo mejor que se me ocurre es usar el escalado multidimensional.

Answer 1

Está en el camino correcto con el escalado multidimensional (MDS), pero MDS no es práctico para grandes conjuntos de datos, ya que su complejidad temporal es cuadrática en el número de puntos. Es posible que desee ver FastMap, que tiene una complejidad lineal de tiempo y es más adecuada para la indexación. Ver:

  

Christos Faloutsos y King-Ip Lin:   " FastMap: un algoritmo rápido para   Indexación, minería de datos y   Visualización de Tradicional y   Conjuntos de datos multimedia, en Proc.   SIGMOD , 1995, doi: 10.1145 / 223784.223812

Answer 2

Puedes " engañar a " y use un método numérico iterativo para esto. Tome todos los puntos para estar en algún & Quot; random & Quot; posiciones inicialmente, y luego recorrerlas, alejándolas proporcionalmente de la distancia requerida. Esto preferirá algunos puntos, pero tomar un promedio de los movimientos antes de aplicarlos, luego aplicar el promedio eliminará este problema. Este es un algoritmo O (n & # 178;), pero muy simple de implementar y comprender. En el ejemplo de 2-d a continuación, el error es & Lt; & Lt; 10%, aunque puede que no se comporte tan bien si las distancias indicadas no son realistas.

Ejemplo de 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

Existe un algoritmo para hacerlo en Programación de inteligencia colectiva , p . 49, & Quot; Visualización de datos en dos dimensiones & Quot ;, que podría adaptarse para n dimensiones.

Hola, es una escala multidimensional, así que supongo que estás en el camino correcto.

Answer 4

No puedo editar el original, porque no tengo suficiente representante, pero he tratado de repetir el problema aquí.

El OP tiene una matriz de distancias NxN de entrada. Quiere crear una matriz de salida, tamaño N, de coordenadas N-dimensionales que representen puntos, donde la distancia entre cada punto se almacena en la matriz de entrada.

Tenga en cuenta que esto no se puede resolver en el caso general:

Supongamos que tengo una matriz como esta

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

A está a 1 unidad de distancia (digamos 1 metro) de B, y A está a un metro de C. Pero B y C están en el mismo lugar.

En este caso particular, la suma mínima de errores es de 1 metro, y hay una infinita variedad de soluciones que logran ese resultado