wyznaczania punktów z zestawem par odległości

Question

podanych macierzy odległości pomiędzy punktami ma algorytm do określania zestawu punktów n-wymiarowej, które posiada te odległości? (lub przynajmniej minimalizuje błąd)

coś w rodzaju n-wymiarowej wersji problemu z paletą.

Najlepsze co mogę wymyślić to wielowymiarowe skalowanie.

Answer 1

Jesteś na dobrej drodze dzięki wielowymiarowemu skalowaniu (MDS), ale MDS jest niepraktyczny dla dużych zbiorów danych, ponieważ złożoność czasu jest kwadratowa pod względem liczby punktów. Możesz spojrzeć na FastMap, która ma liniowy czas złożoności i lepiej nadaje się do indeksowania. Zobacz:

Christos Faloutsos i Król-IP Lin: „FastMap: a. Szybki Algorytm indeksowanie, pozyskiwania danych i Wizualizacja Tradycyjne i multimedialnych zbiorów danych, w Proc SIGMOD, 1995, doi:10.1145/223784.223812

Answer 2

Nie mogę edytować oryginału, ponieważ nie mam wystarczającej liczby przedstawicieli, ale próbowałem rozwiązać problem tutaj.

OP posiada wejście NxN macierzy odległości. Chce utworzyć tablicę wyjściową o wielkości N, współrzędnych N-wymiarowych reprezentujących punkty, gdzie odległość między każdym punktem jest przechowywana w macierzy wejściowej.

Należy zauważyć, że nie jest rozpuszczalny w przypadku ogólnym:

Załóżmy, że ma matrycę, jak to

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

A wynosi 1 jednostka odległość (powiedzmy 1 metr) od B i A jest jeden metr od C. Ale B i C są w tym samym miejscu.

W tym konkretnym przypadku minimalna suma błędów wynosi 1 metr, a tam są nieskończenie wiele rozwiązań, które osiągają ten rezultat

Answer 3

Istnieje algorytm ten sposób w Programming Collective Intelligence, s. 49, "Wyświetlanie danych w dwóch wymiarach", które można dostosować do wymiarów n.

Hej - to wielowymiarowe skalowanie - więc myślę, że jesteś na dobrej drodze.

Answer 4

można „oszukać” i użyć iteracyjną metodę numeryczną do tego. Weź wszystkich punktów, aby być w niektórych „losowych” pozycjach początkowo, a następnie pętla przez nich, przenosząc je z dala od siebie, proporcjonalnie do wymaganie ed odległość. Będzie to preferować niektóre punkty, ale biorąc średnią ruchów przed ich zastosowaniem, a następnie zastosowanie średniej usunie ten problem. Jest to algorytm O (n²), ale bardzo prosty w implementacji i zrozumieniu. W 2-d przykład poniżej błędu jest < < 10%, choć nie mogą zachowywać się tak dobrze, jeżeli odległości podane są nierealne.

C++ Przykład:

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