Bestimmung von Punkten aus einem Satz von paarweisen Abständen

Question

Bei einer Matrix von Abständen zwischen Punkten gibt es einen Algorithmus zur Bestimmung einer Menge von n-dimensionalen Punkten mit diesen Abständen? (oder zumindest minimiert den Fehler)

Art wie eine n-dimensionale Version des Turnpike-Problems.

Das Beste, was ich mir vorstellen kann, ist die multidimensionale Skalierung.

Answer 1

Sie sind auf dem richtigen Weg mit multidimensionaler Skalierung (MDS), aber MDS ist für große Datensätze nicht praktikabel, da die Zeitkomplexität in der Anzahl der Punkte quadratisch ist. Vielleicht möchten Sie sich FastMap ansehen, das eine lineare Zeitkomplexität aufweist und besser für die Indizierung geeignet ist. Siehe:

Christos Faloutsos und König-Ip Lin: „FastMap: a. Schneller Algorithmus für Indizierung, Data-Mining und Visualisierung der traditionellen und Multimedia Datasets, in Proc SIGMOD, 1995, doi:10.1145/223784.223812

Answer 2

Ich kann das Original nicht bearbeiten, weil ich nicht genug rep, aber ich habe versucht, das Problem hier zu wiederholen.

Das OP hat eine Eingangs-NxN-Matrix von Entfernungen. Er möchte ein Ausgabe-Array, Größe N, von N-dimensionalen Koordinaten erzeugen, die Punkte darstellen, wobei der Abstand zwischen jedem Punkt in der Eingabematrix gespeichert wird.

anzumerken, dass dies im allgemeinen Fall nicht auflösbar ist:

Angenommen, ich habe eine Matrix, wie dies

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

A 1 Einheit des Abstandes (etwa 1 m) entfernt von B und A ist einen Meter von C entfernt. Aber B und C sind an der gleichen Stelle.

In diesem speziellen Fall die minimale Summe von Fehlern ist 1 Meter, und es gibt eine unendliche Vielfalt von Lösungen, die dieses Ergebnis zu erreichen

Answer 3

Es ein Algorithmus ist dies in Programming Collective Intelligence, p zu tun. 49, "Daten in zwei Dimensionen anzeigen", die für n-Dimensionen angepasst werden könnten.

Hey - es ist multidimensionale Skalierung - also denke ich, dass Sie auf dem richtigen Weg sind.

Answer 4

Sie können „betrügen“ und ein iteratives numerisches Verfahren für diese. alle Punkte Nehmen Sie zunächst in einigen „random“ Positionen zu sein, und dann durch sie Schleife, bewegen sie voneinander entfernt proportional zu das Requir Ed Abstand. Dies wird einige Punkte bevorzugen, aber wenn Sie einen Durchschnitt der Züge ziehen, bevor Sie sie anwenden, dann wird die Anwendung des Durchschnitts dieses Problem beheben. Dies ist ein O (n²) Algorithmus, aber sehr einfach zu implementieren und zu verstehen. Im folgenden 2-d-Beispiel ist der Fehler < < 10%, obwohl er sich möglicherweise nicht so gut verhält, wenn die angegebenen Entfernungen unrealistisch sind.

C++ Beispiel:

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