Punkte aus Satz von paarweisen Abständen Bestimmung

Question

Da eine Matrix von Entfernungen zwischen den Punkten ist es ein Algorithmus zum Erzeugen einen Satz von n-dimensionalen Punkten zu bestimmen, die diese Abstände haben? (Oder zumindest minimiert den Fehler)

wie eine Art n-dimensionale Version des Turnpike Problem.

Das Beste, was ich mit oben kommen kann multidimensionale Skalierung verwendet wird.

Answer 1

Sie sind auf dem richtigen Weg mit multidimensionale Skalierung (MDS), aber MDS ist unpraktisch für große Datenmengen, wie seine Zeit, Komplexität in der Anzahl der Punkte quadratisch ist. Sie können bei FastMap, die lineare Zeitkomplexität aussehen wollen und ist besser Indizierung geeignet. Siehe auch:

  

Christos Faloutsos und König-Ip Lin:   „FastMap: ein schneller Algorithmus für   Indizierung, Data-Mining und   Visualisierung der traditionellen und   Multimedia Datasets, in Proc.   SIGMOD , 1995, doi: 10,1145 / 223.784,223812

Answer 2

Sie können „betrüge“ und verwenden ein iteratives numerisches Verfahren für diese. Nehmen alle Punkte in einigen „random“ Positionen zu sein, zunächst, und dann durchlaufen sie, bewegen sie sich voneinander weg proportional zu dem erforderlichen Abstand. Dies wird einige Punkte bevorzugen, aber einen Durchschnitt der Züge nehmen, bevor sie sie anwenden, dann die durchschnittliche Anwendung wird dieses Problem beseitigen. Dies ist ein O (n²) Algorithmus, aber sehr einfach zu implementieren und zu verstehen. In dem 2-d Beispiel unter dem Fehler << 10%, obwohl es nicht so gut verhalten kann, wenn die angegebenen Abstände 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;
}

Answer 3

Es gibt einen Algorithmus, dies zu tun in Programmierung Collective Intelligence , p . 49, "Anzeigen von Daten in zwei Dimensionen", die für n-Dimensionen angepasst werden.

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

Answer 4

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

Die OP hat einen Eingang NxN-Matrix von Entfernungen. Er möge einen Ausgangsarray, die Größe N, von N-dimensionalen Koordinaten repräsentieren Punkte erzeugen, wobei der Abstand zwischen jedem Punkt in der Eingangsmatrix gespeichert ist.

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

Angenommen, ich habe eine Matrix wie folgt

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

A ist 1 Einheit des Abstandes (etwa 1 m) entfernt von B und A einen Meter entfernt von C, aber B und C sind in 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