ペアワイズ距離のセットからポイントを決定する
質問
ポイント間の距離の行列が与えられた場合、これらの距離を持つn次元のポイントのセットを決定するアルゴリズムはありますか? (または、少なくともエラーを最小限に抑えます)
ターンパイク問題のn次元バージョンのようなもの。
私が思いつくのは、多次元スケーリングを使用することです。
解決
多次元スケーリング(MDS)を使用して正しい軌道に乗っていますが、MDSは時間の複雑さがポイント数で2次であるため、大規模なデータセットには実用的ではありません。線形の時間の複雑さを持ち、インデックス作成により適したFastMapをご覧ください。参照:
Christos FaloutsosおよびKing-Ip Lin: <!> quot; FastMap:の高速アルゴリズム インデックス作成、データマイニング、 従来の視覚化 Procのマルチメディアデータセット。 SIGMOD 、1995、 doi:10.1145 / 223784.223812
他のヒント
<!> quot;チート<!> quot;これには反復数値法を使用します。すべてのポイントを取り、いくつかの<!> quot; random <!> quot;最初に配置してから、それらをループし、必要な距離に比例して互いから離れるように移動します。これはいくつかのポイントを優先しますが、それらを適用する前に移動の平均を取ると、平均を適用することでこの問題がなくなります。これはO(n <!>#178;)アルゴリズムですが、実装と理解が非常に簡単です。以下の2次元の例では、エラーは<!> lt; <!> lt;です。 10%。ただし、指定された距離が非現実的である場合、それほどうまく動作しない場合があります。
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;
}
Collective Intelligenceのプログラミング、p 。 49、<!> quot; 2次元でのデータの表示<!> quot;。n次元に適合させることができます。
ちょっと-多次元のスケーリング-だから、あなたは正しい軌道に乗っていると思います。
担当者が不足しているため、オリジナルを編集することはできませんが、ここで問題を再現しようとしました。
OPには、距離の入力NxN行列があります。彼は、ポイントを表すN次元座標のサイズNの出力配列を作成したいと考えています。ここで、各ポイント間の距離は入力行列に格納されます。
これは一般的なケースでは解決できないことに注意してください:
このような行列があるとします
A B C A x 1 2 B x 0 C x
AはBから1ユニット(1メートル)離れており、AはCから1メートル離れています。ただし、BとCは同じ場所にあります。
この特定の場合、エラーの最小合計は1メートルであり、その結果を達成するさまざまなソリューションがあります