determinar pontos de conjunto de distâncias entre pares
Pergunta
dada uma matriz de distâncias entre pontos existe um algoritmo para determinar um conjunto de pontos n-dimensional que têm essas distâncias? (Ou pelo menos minimiza o erro)
como uma espécie de versão n-dimensional do problema Turnpike.
O melhor que posso chegar a está usando escalonamento multidimensional.
Solução
Você está no caminho certo com escalonamento multidimensional (MDS), mas MDS é impraticável para grandes conjuntos de dados, como a sua complexidade de tempo é quadrática no número de pontos. Você pode querer olhar para FastMap, que tem complexidade de tempo linear e é mais adequado para indexação. Veja:
Christos Faloutsos e King-Ip Lin: "FastMap: um algoritmo rápido para Indexação, Data-Mining e Visualização do tradicional e Multimedia conjuntos de dados, em Proc. SIGMOD de 1995, doi: 10,1145 / 223.784,223812
Outras dicas
Você pode "enganar" e usar um método numérico iterativo para isso. Pegue todos os pontos para ser em algumas posições "aleatórios" inicialmente, e depois percorrer-los, movê-los longe um do outro proporcionalmente à distância necessária. Isso vai preferir alguns pontos, mas tendo uma média dos movimentos antes de aplicá-las, em seguida, aplicar a média irá remover este problema. Este é um O (n²) algoritmo, mas muito simples de implementar e entender. No exemplo 2-d abaixo o erro é << 10%, embora possa não se comportam tão bem se as distâncias referidas são irrealistas.
Exemplo 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;
}
Há um algoritmo para fazer isso em Programação Inteligência Coletiva , p . 49, "Visualização de dados em duas dimensões", que poderia ser adaptado para n-dimensões.
Hey - é escalonamento multidimensional -. Então eu acho que você está no caminho certo
Eu não posso editar o original, porque eu não tenho rep suficiente, mas eu tentei reafirmar o problema aqui.
O OP tem uma matriz NxN entrada de distâncias. Ele quer para criar uma matriz de saída, de tamanho N, de coordenadas n-dimensional que representa os pontos, em que a distância entre cada ponto é armazenado na matriz de entrada.
Note que este não é solúvel no caso geral:
Suponha que eu tenho uma matriz como este
A B C A x 1 2 B x 0 C x
A é uma unidade de distância (digamos 1 metro) de distância a partir de B, e A é um metro de distância a partir de C. Mas B e C estão no mesmo local.
Neste caso particular a soma mínima de erros é de 1 metro, e há uma infinita variedade de soluções que alcançar esse resultado