Download presentation
Presentation is loading. Please wait.
1
九州大学 理学部 物理学科 情報理学コース 久保 浩平 2013年1月26日 13:00~14:00
正規圧縮距離を用いた クラスタリング 九州大学 理学部 物理学科 情報理学コース 久保 浩平 2013年1月26日 13:00~14:00
2
正規圧縮距離(NCD):データ間の類似尺度 NCDはコルモゴロフ記述量(𝐾(𝑥)と表記)の理論に基づいている。
𝐾(𝑥) :𝑥を究極に圧縮したときの長さ(𝐶(𝑥)で近似) 𝐾(𝑥|𝑦) :𝑦を補助情報として𝑥を究極に圧縮したときの長さ 𝐾(𝑥) 𝐾(𝑦) 𝐾(𝑦|𝑥) 𝐾(𝑥|𝑦) 𝑥と𝑦の似ていないところ →距離に使う 補助情報によって改善された部分 (𝑥と𝑦の似ているところ)
3
𝑵𝑪𝑫 𝒙,𝒚 = 𝐦𝐚𝐱{𝑪 𝒙 𝒚 , 𝑪 𝒚 𝒙 } 𝐦𝐚𝐱{𝑪 𝒙 ,𝑪 𝒚 } = 𝑪 𝒚𝒙 −𝐦𝐢𝐧{𝑪 𝒙 , 𝑪 𝒚 } 𝐦𝐚𝐱{𝑪 𝒙 , 𝑪 𝒚 }
データが文字列で表される限り、どのようなデータでもデータ間の類似度が算出できる。
4
4点条件 木距離であるための必要十分条件 𝑇= 𝑉,𝐺 , 任意の4点 𝑥,𝑦,𝑧,𝑡 ⊂𝐺に対して
𝑑 𝑥,𝑦 +𝑑 𝑧,𝑡 ≤𝑑 𝑥,𝑧 +𝑑 𝑦,𝑡 ≤𝑑 𝑥,𝑡 +𝑑(𝑦,𝑧) x y z t 4点条件
5
𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡}
𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} 右のような木で1, 4, 5, 6 の四つの葉を考える。 1 2 3 4 5 6 1 4 5 6 1 5 4 6 1 6 5 4
6
𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡}
𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} 1 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
7
𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡}
𝐶 𝑇 = {𝑢,𝑣,𝑤,𝑥}⊆𝑁 { 𝐶 𝑢𝑣|𝑤𝑥 :𝑢𝑣|𝑤𝑥が𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡} NCD 1,4 +𝑁𝐶𝐷 5,6 を計算する。 1 2 3 4 5 6 1 4 5 6
8
評価関数 評価関数を定義する上で、データの集合𝑁のコストの上界𝑀と下界𝑚を算出する。 𝑆(𝑇)は以下の式で定義する。0が最悪、1が最良。
𝑆 𝑇 = (𝑀− 𝐶 𝑇 ) (𝑀−𝑚) 𝑆 𝑇 の最大にするTを求める問題はNP困難 ヒューリスティクスを用いて近似
9
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算
以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算 操作のループがわかりやすくなるように書きなおし
10
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2
1 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
11
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2
1 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
12
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2
1 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
13
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2
1 2 3 4 5 6 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
14
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2
1 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
15
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 2
1 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
16
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 3
以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算 1 2 4 5 6 3
17
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 3
以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算 1 2 4 5 6 3
18
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 4
1 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
19
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 4
1 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
20
フローチャート ランダム二分木生成 𝑆 𝑇 の値計算 leaf_swap subtree_swap transfer 𝑆 𝑇′ の値計算 4
1 2 4 5 6 3 ランダム二分木生成 𝑆 𝑇 の値計算 以下の操作からランダムに選ぶ leaf_swap subtree_swap transfer k回繰り返す 𝑆 𝑇′ の値計算
21
まとめ 4点法の実装 課題 4点条件をもとにした目的関数を定義 ヒューリスティクスを用いた近似 高性能なアルゴリズム コスト計算の効率化
移動戦略の考案 近似アルゴリズムの考案 まとめ
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.