1

距離行列と一連の点が与えられた場合、これらの点の座標をどのように計算しますか?

編集：これは飛行機です。

この質問はここで回答されましたが、さまざまな距離行列を試してみると、固有ベクトルと同様に M 行列が負の値を持っていたため、この答えを実際に使用できませんでした。したがって、平方根を取得すると、プログラム (R) は関連するエントリに対して "NaN" を出力します。これは、D(i,j)^2 が D(1,j)^2 + D(i,1)^2 より大きいたびに発生すると思います。

たとえば、距離行列があるとします。

0    73   102  496  432  184
73    0   303  392  436  233
102  303    0  366  207  353
496  392  366    0  172  103
432  436  207  172    0  352
184  233  353  103  352    0

式 M(i,j) = (0.5)(D(1,j)^2+D(i,1)^2-D(i,j)^2) を使用すると、(既に負のエントリがある) ):

0      0.0      0.0      0.0      0.0      0.0
0   5329.0 -38038.0  48840.5    928.5  -7552.0
0 -38038.0  10404.0  61232.0  77089.5 -40174.5
0  48840.5  61232.0 246016.0 201528.0 134631.5  
0    928.5  77089.5 201528.0 186624.0  48288.0
0  -7552.0 -40174.5 134631.5  48288.0  33856.0

次に、非ゼロの固有値と固有ベクトルを取得します。

477718.27  101845.63   16474.30  -13116.72 -100692.49


        [,1]       [,2]        [,3]        [,4]        [,5]
 0.00000000  0.0000000  0.00000000  0.00000000  0.00000000
-0.05928626  0.3205747  0.84148945  0.04869546 -0.42806691
-0.16650486 -0.5670946 -0.04507520 -0.58222690 -0.55647098
-0.73371713  0.2827320  0.07386302 -0.45957443  0.40627254
-0.59727407 -0.4623603  0.07806418  0.64968004 -0.03617241
-0.27144823  0.5309625 -0.52755471  0.15920983 -0.58372335

負の固有値と固有ベクトルの両方があるため、sqrt(eigenvector(i)*eigenvalue(i)) を計算すると、負の値になります。ここに私の最終的な出力があります:

[,1]     [,2]      [,3]     [,4]      [,5]
   0   0.0000   0.00000  0.00000   0.00000
 NaN 180.6907 117.74103      NaN 207.61291
 NaN      NaN       NaN 87.38939 236.71174
 NaN 169.6910  34.88326 77.64089       NaN
 NaN      NaN  35.86158      NaN  60.35139
 NaN 232.5429       NaN      NaN 242.43877

これは、角度を使用せずに座標点を計算する唯一の明確な方法ですか? そうである場合、D(i,j)^2 が D(1,j)^2 + D(i,1)^2 より大きくならないように距離行列を修正する必要がありますか。

ありがとう。

4

3 に答える 3

6

データに一貫性がありません

あなたの座標は、ℝ⁴ の点の位置と一致しておらず、ましてや低次元の空間とは一致していません。二乗距離行列のメンガー行列式を計算することで、その事実を知ることができます。

D <- as.matrix(read.table(textConnection("\
0    73   102  496  432  184
73    0   303  392  436  233
102  303    0  366  207  353
496  392  366    0  172  103
432  436  207  172    0  352
184  233  353  103  352    0")))
n <- nrow(D)
det(rbind(cbind(D^2, 1), c(rep(1, n), 0)))
# Result: 3.38761e+25

座標が 5 次元未満の空間の点から実際に得られた場合、この行列式はゼロでなければなりません。そうではないため、距離に一貫性がないか、点が十分に高い次元の空間でシンプレックスを形成しています。

ただし、次元に関係なく、いくつかのケースで三角形の不等式に違反するため、データは依然として一貫性がありません。

a b c   ac   abc    ab    bc
1 2 4: 496 > 465 =  73 + 392
1 3 4: 496 > 468 = 102 + 366
1 3 5: 432 > 309 = 102 + 207
1 6 4: 496 > 287 = 184 + 103
2 1 3: 303 > 175 =  73 + 102
2 6 4: 392 > 336 = 233 + 103
3 1 6: 353 > 286 = 102 + 184
5 4 6: 352 > 275 = 172 + 103

a から c に直接移動すると、b を経由するよりも時間がかかることはありませんが、データによるとそうです。

シンプルな平面アプローチ

平面内の点と一致するデータがある場合 (つまり、4 つの点の組み合わせに対するすべてのメンガー行列式がゼロに評価される場合)、次を使用して座標を取得できます。

distance2coordinates <- function(D) {
  n <- nrow(D)
  maxDist <- which.max(D)
  p1 <- ((maxDist - 1) %% n) + 1
  p2 <- ((maxDist - 1) %/% n) + 1
  x2 <- D[p1, p2]
  r1sq <- D[p1,]^2
  r2sq <- D[p2,]^2
  x <- (r1sq - r2sq + x2^2)/(2*x2)
  y <- sqrt(r1sq - x^2)
  p3 <- which.max(y)
  x3 <- x[p3]
  y3 <- y[p3]
  plus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 - y)^2)
  minus <- abs(D[p3,]^2 - (x3 - x)^2 - (y3 + y)^2)
  y[minus < plus] <- -y[minus < plus]
  coords <- data.frame(x = x, y = y)
  return(coords)
}

アイデアは、開始点として最大距離を持つ 2 つのポイントを選択することです。原点に置き、もう一方を正の x 軸に置きます。次に、方程式に従って、2 つの円の交点として、これからすべての他の x 座標を計算できます。

I:     x²       + y² = r₁²
II:   (x - x₂)² + y² = r₂²
I-II:  2*x*x₂ = r₁² - r₂² + x₂²

これらの x 座標が与えられると、符号まで y 座標も取得できます。次に、これら 2 つの開始点のいずれかから十分に離れた 3 番目の点を選択して、標識を決定します。

このアプローチでは、不正確な入力を処理する試みはまったく行われません。正確なデータを想定し、距離行列の一部のみを使用してポイントを見つけます。すべての入力データに最もよく一致するポイント セットは見つかりません。

あなたのデータでは、平方根へのいくつかの引数が負になるため、これは失敗します。これは、関係する 2 つの円がまったく交差しないことを意味し、そのため、三角形の不等式が破られます。

そうである場合、D(i,j)^2 が D(1,j)^2 + D(i,1)^2 より大きくならないように距離行列を修正する必要がありますか。

D(i,j) ≤ D(i,k) + D(k,j) が役立ちます。つまり、すべてのトリプルで正方形がない場合です。これにより、三角形の不等式がどこでも成り立つことが保証されます。結果は平面である必要はありません。そのためには、メンガーの行列式をすべて修正する必要があります。

于 2013-08-07T17:09:02.623 に答える
0

これは解決可能です

質問で指定した距離行列を満たすデカルト型の座標を確認したい場合は、次の画像をご覧ください。
距離行列と座標 入力行列は、a、b、c、d、e、および f と呼ぶ 6 つのノード間の距離を示します。距離行列を満たす 6 つのノードすべてに座標を割り当てるには、合計 5 つの次元が必要です。これらの次元のうち 2 つは虚数です。これは、三角形の規則を破った結果です。結果は、コサインの法則と少しの数値計算を使用して到達しました。

  • (0, 0, 0, 0, 0)
  • b (73, 0, 0, 0, 0)
  • c (-521.07, 510.99i, 0, 0, 0)
  • d (669.05, -802.08i, 664.62, 0, 0)
  • e (12.72、-163.83i、488.13、158.01i、0)
  • f (-103.45、184.11i、84.52、138.06i、262.62)
于 2016-07-28T23:31:39.793 に答える