determinare i punti dall'insieme delle distanze a coppie

Question

data una matrice di distanze tra punti esiste un algoritmo per determinare un insieme di punti n-dimensionali che ha queste distanze? (o almeno minimizza l'errore)

una specie di versione n-dimensionale del problema del turnpike.

Il meglio che posso trovare è l'utilizzo del ridimensionamento multidimensionale.

Answer 1

Sei sulla buona strada con il ridimensionamento multidimensionale (MDS), ma MDS non è pratico per set di dati di grandi dimensioni, poiché la sua complessità temporale è quadratica nel numero di punti. Potresti voler guardare FastMap, che ha una complessità temporale lineare ed è più adatta all'indicizzazione. Vedi:

  

Christos Faloutsos e King-Ip Lin:   " FastMap: un algoritmo veloce per   Indicizzazione, data mining e   Visualizzazione di tradizionale e   Set di dati multimediali, in Proc.   SIGMOD , 1995, doi: 10.1145 / 223784.223812

Answer 2

Puoi " cheat " e utilizzare un metodo numerico iterativo per questo. Prendi tutti i punti per essere in qualche & Quot; random & Quot; posizioni inizialmente, e poi attraversarle, allontanandole proporzionalmente alla distanza richiesta. Ciò preferirà alcuni punti, ma prendendo una media delle mosse prima di applicarle, quindi applicare la media rimuoverà questo problema. Questo è un algoritmo O (n & # 178;), ma molto semplice da implementare e comprendere. Nell'esempio 2-d di seguito l'errore è & Lt; & Lt; 10%, anche se potrebbe non comportarsi così bene se le distanze indicate non sono realistiche.

Esempio 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

Esiste un algoritmo per farlo in Programming Collective Intelligence , p . 49, & Quot; Visualizzazione dei dati in due dimensioni & Quot ;, che potrebbe essere adattato per n-dimensioni.

Ehi, è un ridimensionamento multidimensionale, quindi immagino che tu sia sulla strada giusta.

Answer 4

Non riesco a modificare l'originale, perché non ho abbastanza rappresentante, ma ho cercato di riaffermare il problema qui.

L'OP ha una matrice NxN di input di distanze. Vuole creare un array di output, dimensione N, di coordinate N-dimensionali che rappresentano punti, in cui la distanza tra ciascun punto è memorizzata nella matrice di input.

Nota che questo non è risolvibile nel caso generale:

Supponiamo che io abbia una matrice come questa

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

A è 1 unità di distanza (diciamo 1 metro) di distanza da B, e A è di un metro di distanza da C. Ma B e C si trovano nello stesso punto.

In questo caso particolare la somma minima degli errori è di 1 metro e ci sono un'infinita varietà di soluzioni che ottengono quel risultato