Download presentation
Presentation is loading. Please wait.
1
九州大学 理学部 物理学科 情報理学コース 久保 浩平 2013年1月26日 13:00~14:00
正規圧縮距離を用いた クラスタリング 九州大学 理学部 物理学科 情報理学コース 久保 浩平 2013年1月26日 13:00~14:00 はじめに(1)、NCDの説明(2)、4点法(3)、LZWとbzip2の比較実験(1)、改変後のやつ(3)
2
…. … hippopotamus Pigmy Chimpanzee sheep gibbon 0.475728 0.964223
Pigmy Chimpanzee …. …
3
𝑵𝑪𝑫 𝒙,𝒚 = 𝐦𝐚𝐱{𝑪 𝒙 𝒚 , 𝑪 𝒚 𝒙 } 𝐦𝐚𝐱{𝑪 𝒙 ,𝑪 𝒚 } = 𝑪 𝒚𝒙 −𝐦𝐢𝐧{𝑪 𝒙 , 𝑪 𝒚 } 𝐦𝐚𝐱{𝑪 𝒙 , 𝑪 𝒚 }
もしxとyが似ていなかったら… もしxとyが似ていたら… 𝑥𝑦 𝑦 𝑥 𝑦 𝑥 𝐶(𝑥𝑦) 𝐶(𝑦) 𝐶(𝑥|𝑦) 𝐶(𝑦) 𝐶(𝑥|𝑦) NCD
4
目的関数 𝐶 𝑢𝑣|𝑤𝑥 =𝑁𝐶𝐷 𝑢,𝑣 +𝑁𝐶𝐷(𝑤,𝑥)
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} consistentと呼ばれる木の部分構造のコストを全て 足し合わせたもの。 𝐶 𝑢𝑣|𝑤𝑥 =𝑁𝐶𝐷 𝑢,𝑣 +𝑁𝐶𝐷(𝑤,𝑥) x w u v 目的関数
5
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算
以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算 スライドで補足
6
S(T)=
Similar presentations
