九州大学 理学部 物理学科 情報理学コース 久保 浩平 2013年1月26日 13:00~14:00 正規圧縮距離を用いた クラスタリング 九州大学 理学部 物理学科 情報理学コース　　久保 浩平 2013年1月26日 13:00~14:00

正規圧縮距離(NCD):データ間の類似尺度 NCDはコルモゴロフ記述量(𝐾(𝑥)と表記)の理論に基づいている。 𝐾(𝑥)　 :𝑥を究極に圧縮したときの長さ(𝐶(𝑥)で近似) 𝐾(𝑥|𝑦) :𝑦を補助情報として𝑥を究極に圧縮したときの長さ 𝐾(𝑥) 𝐾(𝑦) 𝐾(𝑦|𝑥) 𝐾(𝑥|𝑦) 𝑥と𝑦の似ていないところ →距離に使う 補助情報によって改善された部分 (𝑥と𝑦の似ているところ)

𝑵𝑪𝑫 𝒙,𝒚 = 𝐦𝐚𝐱{𝑪 𝒙 𝒚 , 𝑪 𝒚 𝒙 } 𝐦𝐚𝐱{𝑪 𝒙 ,𝑪 𝒚 } = 𝑪 𝒚𝒙 −𝐦𝐢𝐧⁡{𝑪 𝒙 , 𝑪 𝒚 } 𝐦𝐚𝐱⁡{𝑪 𝒙 , 𝑪 𝒚 } データが文字列で表される限り、どのようなデータでもデータ間の類似度が算出できる。

4点条件 木距離であるための必要十分条件 𝑇= 𝑉,𝐺 , 任意の4点 𝑥,𝑦,𝑧,𝑡 ⊂𝐺に対して 𝑑 𝑥,𝑦 +𝑑 𝑧,𝑡 ≤𝑑 𝑥,𝑧 +𝑑 𝑦,𝑡 　　　 ≤𝑑 𝑥,𝑡 +𝑑(𝑦,𝑧) x y z t 4点条件

𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} 𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} 右のような木で1, 4, 5, 6 の四つの葉を考える。 １ 2 3 4 5 6 1 4 5 6 1 5 4 6 1 6 5 4

𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} 𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} １ 2 3 4 5 6 consistent 1,4|5,6 1,5|4,6 1,6|5,4 1 4 5 6 1 5 4 6 1 6 5 4

𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} 𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} NCD 1,4 +𝑁𝐶𝐷 5,6 を計算する。 １ 2 3 4 5 6 １ 4 5 6

評価関数 評価関数を定義する上で、データの集合𝑁のコストの上界𝑀と下界𝑚を算出する。 𝑆(𝑇)は以下の式で定義する。0が最悪、1が最良。 𝑆 𝑇 = (𝑀− 𝐶 𝑇 ) (𝑀−𝑚) 𝑆 𝑇 の最大にするTを求める問題はNP困難 ヒューリスティクスを用いて近似

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算 操作のループがわかりやすくなるように書きなおし

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2 １ 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2 １ 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2 １ 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2 １ 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2 １ 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2 １ 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 3 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算 １ 2 4 5 6 3

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 3 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算 １ 2 4 5 6 3

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 4 １ 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 4 １ 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 4 １ 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算

まとめ 4点法の実装 課題 4点条件をもとにした目的関数を定義 ヒューリスティクスを用いた近似 高性能なアルゴリズム コスト計算の効率化 移動戦略の考案 近似アルゴリズムの考案 まとめ