determinando los puntos del conjunto de distancias por pares

Question

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

más o menos como una versión n-dimensional del problema del Turnpike.

Lo mejor que se me ocurre es usar escalamiento multidimensional.

Answer 1

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

Christos Faloutsos y King-Ip Lin: "FastMap:. Un algoritmo rápido para de indexación, extracción de datos y Visualización de Conjuntos de datos multimedia tradicionales y, en Proc SIGMOD, 1995, doi:10.1145/223784.223812

Answer 2

No puedo editar el original, porque no tengo suficiente repetición, pero he intentado volver a exponer 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 representan puntos, donde la distancia entre cada punto se almacena en la matriz de entrada.

cuenta que esto no es soluble en el caso general:

Supongamos que tengo una matriz como esta

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

A es 1 unidad de distancia (por ejemplo 1 metro) de distancia de B, y A está a un metro de distancia 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 variedad infinita de soluciones que lograr ese resultado

Answer 3

Existe un algoritmo para hacer esto en Programming Collective Intelligence, p. 49, "Visualización de datos en dos dimensiones", que podría adaptarse para n dimensiones.

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

Answer 4

puede "trampa" y utilizar un método numérico iterativo para esto. Tome todos los puntos para estar en algunas posiciones "al azar" al principio, y luego bucle a través de ellos, alejándolos entre sí de forma proporcional a el requir distancia ed. 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²), pero muy simple de implementar y comprender. En el ejemplo 2-d siguiente, el error es < < 10%, aunque puede que no se comporte tan bien si las distancias dadas son poco realistas.

C++ Ejemplo:

#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; 
}