遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

木のグラフにおける相関（２）鎖状のグラフと相関の関係

グラフ 木 R 全域木 最小全域木
  • 鎖状のグラフとは、枝分かれのない木グラフのこと
  • ノードは１次元座標で表すこともできて、隣接するノードの位置座標の差をノード間距離と言う
  • このようなノード数Nのグラフがあったとき、それぞれのノードの値を表す長さNのベクトルVを考える
  • Vの値がノードの並び順に照らして、順序をなしているとき、木の位置座標とノードの値にはよい相関があると言い、Vの値がノードの並び順に照らして、順序を守っていないとき、木の位置座標とノードの値にはよい相関がないと言う
  • ノードの「位置座標」のベクトルをX、ノードの値ベクトルをYとすれば

N<-10
X<-sort(runif(N))
Y<-sort(runif(N))
plot(X,Y,type="l")
  • ここで、相関のよさは、\sum_{i=1}^{N-1} d(V_i,V_{i+1})(隣接するノードの値Yの差の総和)が最小であることにも表れている
  • この量が最小であることは、Xの値に意味を持たせても、持たせずに、ノードの位置については、順序だけを考えても(ノン・パラメトリックな枠組み)同様である
  • ここで、X,Yの２軸について、マンハッタン距離を考えることにすれば、Xの値を考慮しても考慮しなくても、関係はなくなり、このグラフの辺のマンハッタン距離の和が小さいこと(max(X)-min(X)+max(Y)-min(Y)が最小値)が「相関のよさ」に対応していることになる
  • ちなみに、ノードの位置を変えずにYの値について、１ペアで交換すると、そのペアの値に関する|Y_i-Y_j|\times 2の分だけ、マンハッタン距離が長くなるという関係にある
  • こちらへ続く