déterminer des points à partir de l'ensemble des distances par paires

Question

étant donné une matrice de distances entre les points, y a-t-il un algorithme pour déterminer un ensemble de points n-dimensionnels qui a ces distances? (ou minimise au moins l'erreur)

en quelque sorte une version n-dimensionnelle du problème d'autoroute. Le meilleur que je peux trouver est d'utiliser la mise à l'échelle multidimensionnelle.

Answer 1

Vous êtes sur la bonne voie avec la mise à l'échelle multidimensionnelle (MDS), mais MDS n'est pas pratique pour les grands ensembles de données, car sa complexité temporelle est quadratique en nombre de points. Vous pouvez regarder FastMap, qui a une complexité temporelle linéaire et est mieux adapté à l'indexation. Voir:

Christos Faloutsos et King-Ip Lin: « FastMap:. Un algorithme rapide pour indexation, l'extraction de données et Visualisation des traditionnels et Multimedia datasets, dans Proc SIGMOD, 1995, doi:10.1145/223784.223812

Answer 2

Je ne peux pas modifier l'original, car je n'ai pas assez de rep, mais j'ai essayé de répéter le problème ici.

L'OP a une matrice d'entrée NxN de distances. Il veut créer un tableau de sortie, taille N, de coordonnées N-dimensionnelles représentant des points, où la distance entre chaque point est stockée dans la matrice d'entrée.

Notez que ce ne sont pas résoluble dans le cas général:

Supposons que j'ai une matrice de ce type

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

A est une unité de distance (par exemple 1 m) loin de B, et A est à un mètre de C. Mais B et C sont au même endroit.

Dans ce cas particulier, la somme minimale d'erreurs est de 1 mètre, et il y a une variété infinie de solutions qui permettent d'atteindre ce résultat

Answer 3

Il y a un algorithme pour ce faire dans Programming Collective Intelligence, p. 49, "Affichage des données en deux dimensions", qui pourrait être adapté pour les n dimensions. Hey - c'est une mise à l'échelle multidimensionnelle - donc je suppose que vous êtes sur la bonne voie.

Answer 4

Vous pouvez « tricher » et utiliser une méthode numérique itérative pour cela. Prenez tous les points au départ, puis boucle à travers eux dans des positions « au hasard », les éloignant l'un de l'autre proportionnellement à le besoin distance. Cela va préférer certains points, mais en prenant une moyenne des mouvements avant de les appliquer, l'application de la moyenne éliminera ce problème. C'est un algorithme O (n²), mais très simple à implémenter et à comprendre. Dans l'exemple 2-d ci-dessous, l'erreur est de < < 10%, bien qu'elle puisse ne pas se comporter si bien si les distances données sont irréalistes.

C++ Exemple:

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