正規圧縮距離を用いたクラスタリング

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

Download Report