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

Question

étant donné une matrice de distances entre les points, existe-t-il un algorithme pour déterminer un ensemble de points à n dimensions qui possède ces distances? (ou du moins minimise l'erreur)

un peu comme une version à n dimensions du problème de l'autoroute à péage.

Le mieux que je puisse trouver consiste à utiliser une mise à l'échelle multidimensionnelle.

Answer 1

Vous êtes sur la bonne voie avec la mise à l’échelle multidimensionnelle (MDS), mais la MDS n’est pas pratique pour les grands ensembles de données, car sa complexité temporelle est quadratique en nombre de points. Vous voudrez peut-être examiner FastMap, qui présente une complexité temporelle linéaire et convient mieux à l'indexation. Voir:

  

Christos Faloutsos et King-Ip Lin:   " FastMap: un algorithme rapide pour   Indexation, exploration de données et   Visualisation des images traditionnelles et   Jeux de données multimédia, dans Proc.   SIGMOD , 1995, doi: 10.1145 / 223784.223812

Answer 2

Vous pouvez " tricher " et utilisez une méthode numérique itérative pour cela. Prenez tous les points pour être dans un & Quot; random & Quot; les positions initialement, puis en boucle, les éloigner les uns des autres proportionnellement à la distance requise. Cela préférera certains points, mais en prenant une moyenne des mouvements avant de les appliquer, appliquer cette moyenne éliminera ce problème. C'est un algorithme O (n & # 178;), mais très simple à implémenter et à comprendre. Dans l'exemple 2-d ci-dessous, l'erreur est & Lt; & Lt; 10%, bien que cela puisse ne pas se comporter si bien si les distances indiquées ne sont pas réalistes.

Exemple 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

Il existe un algorithme pour cela dans Programmation de l'intelligence collective , p . 49, & "Affichage des données en deux dimensions &"; Pouvant être adapté aux n dimensions.

Hé - la mise à l’échelle multidimensionnelle - je suppose donc que vous êtes sur la bonne voie.

Answer 4

Je ne peux pas modifier l'original, car je n'ai pas assez de représentants, mais j'ai essayé de reformuler le problème ici.

Le PO a une matrice de distances NxN en entrée. Il souhaite créer un tableau de sortie, de taille N, de coordonnées à N dimensions représentant des points, où la distance entre chaque point est stockée dans la matrice en entrée.

Notez que cela n’est pas possible dans le cas général:

Supposons que j'ai une matrice comme celle-ci

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

A est à 1 unité de distance (disons 1 mètre) de B et A à 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 existe une infinité de solutions qui permettent d’atteindre ce résultat.