algorithm - ペアごとの距離のセットからポイントを決定する

Question

ポイント間の距離の行列が与えられた場合、これらの距離を持つn次元のポイントのセットを決定するアルゴリズムはありますか? （または少なくともエラーを最小限に抑えます）

ターンパイク問題の n 次元バージョンのようなものです。

私が思いつく最善の方法は、多次元スケーリングを使用することです。

Answer 1

多次元尺度構成法（MDS）は順調に進んでいますが、時間計算量はポイント数で2次式であるため、MDSは大規模なデータセットには実用的ではありません。FastMapを確認することをお勧めします。これは、線形の時間計算量を持ち、インデックス作成により適しています。見る：

ChristosFaloutsosおよびKing-Iplin： "FastMap：従来のデータセットとマルチメディアデータセットのインデックス作成、データマイニング、および視覚化のための高速アルゴリズム、Proc。SIGMOD 、 1995、doi：10.1145 / 223784.223812

Answer 2

これには、「チート」して反復数値法を使用できます。すべてのポイントを最初にいくつかの「ランダムな」位置に配置し、次にそれらをループして、必要な距離に比例して互いに離れるように移動します。これはいくつかのポイントを優先しますが、それらを適用する前に動きの平均を取り、次に平均を適用することでこの問題を取り除くことができます。これはO（n²）アルゴリズムですが、実装と理解は非常に簡単です。以下の2次元の例では、エラーは<< 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;
}

Answer 3

これを行うためのアルゴリズムは、集合知プログラミングのプログラミングにあります。49、「2次元でのデータの表示」。これは、n次元に適合させることができます。

ねえ-それは多次元尺度構成法です-だから私はあなたが正しい軌道に乗っていると思います。

Answer 4

担当者が足りないため、オリジナルを編集できませんが、ここで問題を言い換えようとしました。

OPには、距離の入力NxN行列があります。彼は、ポイントを表すN次元座標の出力配列（サイズN）を作成したいと考えています。ここで、各ポイント間の距離は入力行列に格納されます。

これは一般的なケースでは解決できないことに注意してください。

このような行列があるとしましょう

   ABC  
A x 1 2  
B x 0  
C x  

AはBから1単位の距離（たとえば1メートル）離れており、AはCから1メートル離れています。しかし、BとCは同じ場所にあります。

この特定のケースでは、エラーの最小合計は1メートルであり、その結果を達成するソリューションは無限にあります。