14

（対称）k x k距離行列として与えられる有限メトリック空間があります。これをユークリッド空間 R^(k-1) に (ほぼ) アイソメトリックに埋め込むアルゴリズムが必要です。距離によって与えられる連立方程式を解くことによって正確に行うことが常に可能であるとは限りませんが、(非常に小さな) 制御可能なエラーが埋め込まれたソリューションを探しています。

現在、出力次元が (k-1) に設定された多次元スケーリング (MDS) を使用しています。一般に、MDS は周囲の埋め込み次元を (k-1) 未満 (通常は 2 または 3) に削減しようとしている状況に最適化されている可能性があり、私の制限されたアルゴリズムにはより良いアルゴリズムがあるかもしれません。場合。

質問: ユークリッド距離を使用して R^{k-1} でサイズ k のメトリック空間を実現するための優れた/高速なアルゴリズムは何ですか?

いくつかのパラメーターとポインター:

(1) 私の k は比較的小さいです。3 < k < 25 とします。

(2) R^{k-1} に埋め込むかどうかは実際には気にしません。それが物事を単純化する/物事を高速化する場合、アイソメトリックである限り、R ^ Nも問題ありません。R^k や R^(2k+1) に増やした場合に、より高速なアルゴリズムやエラーの少ないアルゴリズムがあれば幸いです。

(3) Python の実装を示すことができれば、さらに嬉しいです。

(4) MDS より優れたものは何でも機能します。

4

2 に答える 2

1

LLEを試してみませんか 。そこにもコードがあります。

于 2012-03-02T17:49:10.053 に答える
0

わかりました、ここで約束されているように、簡単な解決策：

表記法:は、点との間の距離の2 乗d_{i,j}=d_{j,i}を表します。を点数とする．点とその点の- 番目の座標を とします。ijNp_iip_{i,k}k

アルゴリズムを正しく導出できることを祈りましょう。後で説明がありますので、派生を確認できます（インデックスがたくさん表示されるのは嫌いです）。

アルゴリズムは動的計画法を使用して正しい解に到達します

Initialization:
p_{i,k} := 0 for all i and k

Calculation:
for i = 2 to N do
   sum = 0
   for j = 2 to i - 1 do
     accu = d_{i,j} - d_{i,1} - p_{j,j-1}^2
     for k = 1 to j-1 do
       accu = accu + 2 p_{i,k}*p_{j,k} - p_{j,k}^2
     done
     p_{i,j} = accu / ( 2 p_{j,j-1} )
     sum = sum + p_{i,j}^2
   done
   p_{i,i-1} = sqrt( d_{i,0} - sum )
done

重大なインデックスの間違いをしていない場合 (通常はそうしています)、これでうまくいくはずです。

この背後にあるアイデア:

作業を楽にするために、原点に任意の最初の点を設定します。のときにp_i座標を設定しない点ではありません。つまり、2 番目のポイントでは最初の座標のみを設定し、3 番目のポイントでは 1 番目と 2 番目の座標のみを設定します。kk > i-1

ここで、すべての点 p_{k'}の座標があり、すべてが満たされるようk'<iに の座標を計算したいとします( の点の制約についてはまだ気にしません)。私たちが持っている一連の方程式を書き留めるとp_{i}d_{i,k'}k>k'

d_{i,j} = \sum_{k=1}^N (p_{i,k} - p_{j,k} )^2

p_{i,k}との両方p_{j,k}がゼロに等しいためk>k'、これを次のように減らすことができます。

d_{i,j} = \sum_{k=1}^k' (p_{i,k} - p_{j,k} )^2

また、ループ不変式により、 の場合はすべてp_{j,k}ゼロになることに注意してくださいk>j-1。したがって、この方程式を分割します。

d_{i,j} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k} )^2 + \sum_{k=j}^{k'} p_{i,j}^2

最初の式については、次のようになります。

d_{i,1} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k} )^2 + \sum_{k=j}^{k'} p_i{i,1}^2

これは後で特別な処理が必要になります。

ここで、正規方程式のすべての二項式を解くと、次のようになります。

d_{i,j} = \sum_{k=1}^{j-1} p_{i,k}^2 - 2 p_{i,k} p_{j,k} + p_{j,k}^2 + \sum_{k=j}^{k'} p_{i,j}^2

これから最初の方程式を引くと、次のようになります。

d_{i,j} - d_{i,1} = \sum_{k=1}^{j-1} p_{j,k}^2 - 2 p_{i,k} p_{j,k}

すべての j > 1 に対して。

これを見ると、p_i の座標のすべての正方形がなくなり、必要な正方形だけが既にわかっていることがわかります。これは、線形代数の方法を使用して簡単に解くことができる一連の線形方程式です。実際、この一連の方程式にはもう 1 つ特別なことがあります。方程式は既に三角形の形式になっているため、解を伝播する最後のステップのみが必要です。最後のステップとして、平方根を 1 つ取るだけで解ける 1 つの二次方程式が残ります。

私の推論に従っていただければ幸いです。少し遅れて、私の頭はそれらのインデックスから少し回転しています。

編集:はい、インデックス作成の間違いがありました。修理済み。テストする時間があれば、Python でこれを実装しようとします。

于 2011-09-29T22:05:07.353 に答える