2次元マップ上への写像に関して困っています．

質問

2次元マップ上への写像に関して困っています．

30個の地点があって，
地点間の距離表だけを持っています．
（A地点からB地点までの距離など全組み合わせ分）

その表から距離の概念を保持したまま
2次元の平面空間に写像する方法はないでしょうか？

そのマッピング後のデータを用いて
クラスタリングや，経路設計などの処理をしたいと思っているのですが
肝心のマッピングの方法がわかりません・・・

もしおわかりになる方がいらっしゃいましたら，
どんな方法があるのか概要だけでも教えていただけないでしょうか．
よろしくお願い致します．

回答No.4

sinisorsa · ベストアンサー

距離データから、座標データを求める方法としては、
距離は正確には、保存されませんが、多次元尺度構成法という方法があります。

概念的には、与えられた点の間を距離に対応するゴム紐のようなものでつなぎ、
ます。一般には、平面上には乗りませんから、無理やり、ゴム紐を伸ばしたり
縮めたりします。このときゴム紐のひずむを全体として最小にするように
平面上の配置を定めます。

平面上に配置しなくても、クラスタリングはできると思います。
座標データはなくても、点の間の距離だけを使う方法がありますよ。

何か参考になればいいですね。

お礼

ご回答ありがとうございます！
私がやりたいと思っていることとぴったりです！
多次元尺度構成法という方法があるんですね・・・！
先ほど少し調べてみたところＲなどのフリーの統計ソフトでもできるとのことなので
調べてやってみることにします。

概念を教えてくださったおかげで
多次元尺度構成法についてなんとなくイメージがわきました。
わかりやすいご説明本当にありがとうございました！

回答No.3

masudaya

感覚的ですが，すべての点の間の距離が確定していると言う前提であれれば，
適当な基準点P1をとります.n番目の点をPnとして,n番目とm番目の点との距離をP(n,m)するとき
以下の様にすれば原理的には平面空間に写像出来ます.

1）P1を（0，0），P2(P(1,2),0）とする.
2) P1から半径P(1,3)の円を描き,P2からP(2,3)の円を描き交点の好きな方をP3とする.
3) P1から半径P(1,4)の円を描き,P2から半径P(2,4)の円を描き交点を求める.
交点の内,P3から距離がP(3,4)に近い方の点をP4とする.
：
：
n) P1から半径P(1,n)の円を描き,P2から半径P(2,n)の円を描き交点を求める.
交点の内,P3から距離がP(3,n)に近い方の点をPnとする.

以上のようにすれば,写像が出来ると思います.
交点の内,P3から距離がP(3,n)に近い方の点をPnとする.
とした理由ですが,原理的にはP1,P2,P3からのnとの円を描けば1点で交わるはずですが,
実際に行うのはコンピュータだと思いますので数値計算の誤差を考慮する必要があるため
二つの交点の内,距離が近い方としました.例えば,P3との距離ではうまく決まらない場合
も考えられ,その場合は他の点も利用する必要があると思います.
以上参考になれば

お礼

詳しいご回答ありがとうございます！

私の説明不足で，その距離データは直線距離のデータではなく，
実移動距離のデータだったのをちゃんと言っていませんでした．．．すみません．
点を中心に交わった点が交わらないことがありえてしまうんです．

もともと前提がおかしいのでしょうか．．．

回答No.2

noname#185706

＃１では、距離　≡　直線距離　として回答しました。
前提が成り立たない場合には、無視してください。

お礼

お早いご回答ありがとうございます！

明確に記述せずに申し訳ございません．．．
「距離」は直線距離ではなく，実際の移動距離です．
自宅からスーパーまでの直線距離は２００[m]だけど，
実際にスーパーまで歩いていくと歩く距離は３００[m]，という状況のとき，
私がデータとして持っているのは３００[m]を指す距離の方です．

直線距離でないと2次元で表すのは難しいのかもしれません．．

回答No.1

noname#185706

i 番目の点を pi、また pi と pj の距離を dij とします。
（１）p1 と p2 を d12 の距離に書きます。方向は任意です。
（２）p3 は、p1 を中心とする半径 d13 の円と、p2 を中心とする半径 d23 の円の交点です。３点が１直線上にない場合には交点がふたつありますが、方向は任意として、どちらかをとります。
（３）pi（i >= 4）の位置は、既決の適当な３点を中心とし、それらからの距離を半径とする三つの円の交点として、一意に決まるように思いますが、どうでしょう。

（質問の意味を誤解しているかもしれません）