古典的MDSは以下の手順で可視化．実装に必要なところのみ．
- 要素の値が距離の2乗と見なせる非類似度行列Sを用意する
- Sにヤング・ハウスホルダー変換を施してPとする
- Pをスペクトル分解する（固有値・固有ベクトルを求める）
- 固有値の大きい方から2~3個選び，対応する固有ベクトルを取り出す
- 各固有ベクトルの要素値をプロットする（2個の固有ベクトルの時は2次元，3個の固有ベクトルの時は3次元）
一応，下部に参考リンクを挙げましたが，詳しい説明は検索すれば山ほど…．ヤング・ハウスホルダー変換は距離の2乗の行列に両側から中心化行列をかける演算のことらしいです．中心化行列は距離の基準の原点を重心に移動するための行列らしいです．
ヤング・ハウスホルダー変換:
SがN×N行列のとき
$$P = -\frac{1}{2}({\bf I}-\frac{1}{n}{\bf 11}')S({\bf I}-\frac{1}{n}{\bf 11}')$$と計算します．1は要素がすべて1のN次ベクトル[1,...,1]'です．なので11'は要素がすべて1のN×N行列．
アメリカの空港間の距離が与えられているときMDSで可視化してみます．
atl chi den hou la mi ny sf sea dc atl 0 chi 587 0 den 1212 920 0 hou 701 940 879 0 la 1936 1745 831 1374 0 mi 604 1188 1726 968 2339 0 ny 748 713 1631 1420 2451 1092 0 sf 2139 1858 949 1645 347 2594 2571 0 sea 2182 1737 1021 1891 959 2734 2408 678 0 dc 543 597 1494 1220 2300 923 205 2442 2329 0
以下コード．要numpy, matplotlib．
結果はこんなかんじ．ラベルは手作業で付けました．
ちなみに実際の位置はこんなかんじ．
View US 10 Airport in a larger map
結果を180度回転すればだいたいなんとなくあってるかな？
上の例では非類似度行列を実際の距離の行列としましたが，MDSはデータ間の非類似度を測ることができたらそれっぽく2次元(3次元)にマッピングできるよ，ってことなので色々使えるかも知れません．
ちなみにRだったらcmdscaleでMDSが実装されてて楽
No comments:
Post a Comment