Chromatic Correlation Clustering
-
Francesco Bonchi, Aristides Gionis, Francesco Gullo, Antti Ukkonen
-
KDD 2012
概要
-
Correlation clustering: 各頂点対に類似度がありクラスタリング
-
今回は,頂点対にラベルがついたクラスタリング
-
応用
-
タンパク質間相互作用ネットワーク,関係ネットワーク,共著ネットワーク
問題定義
Correlation Clustering
-
$$ \text{cost}({\cal C}) = \sum_{(x,y) \in V \times V: {\cal C}(x) = {\cal C}(y)} (1-\text{sim}(x,y)) + \sum_{(x,y) \in V \times V: {\cal C}(x) \neq {\cal C}(y)} \text{sim}(x,y) $$
-
cost(C)を最小化するクラスタリングを求める
Chromatic Correlation Clustering
-
各辺にはラベルが張られている
-
$$ \ell : V \times V \rightarrow L \cup \{\ell_0\} $$
-
クラスタリング $$ {\cal C} : V \rightarrow \mathbb{N} $$
-
クラスタラベル関数 $$ c\ell : {\cal C}[V] \rightarrow L $$
-
を求めよ
-
$$ \text{cost}({\cal C}, c\ell) = \sum_{(x,y)\in V\times V: {\cal C}(x) = {\cal C}(y)} ( 1-[\ell(x,y) = c\ell({\cal}(x))] ) + \sum_{(x,y)\in V\times V: {\cal C}(x) \neq {\cal C}(y)} [\ell(x,y) \neq \ell_0] $$
-
クラスタが同じ頂点対について:クラスタラベル≠辺ラベルならコスト++
-
クラスタが違う頂点対について:辺ラベル≠NULLならコスト++
Chromatic Ballsアルゴリズム
-
元のBallsアルゴリズム
-
適当に辺(u,v)を選ぶ
-
l(u,x)=l(v,x)=l(u,v)なxをu,vと同じクラスタCに追加
-
CをVから抜く
-
余った頂点は適当にクラスタラベルを割り当てる
-
近似比
変種
-
Chromatic Ballsがヤバイ例から学んでいく
Lazy Chromatic Balls
-
uを#{(uと同ラベル)∩(uの近傍)}に比例した確率で選ぶ
-
vをuの近傍から確率的に選ぶ
-
Chromatic Balls: 単色の三角形を構成した時だけ追加
-
Lazy: 単色の<u or v, z(今のクラスタ内頂点), w>を追加
Alternating-minimization
-
クラスタ数Kを指定して,k-meansっぽいことをする
-
今のクラスタリング情報から各頂点の「最適クラスタ」決定
-
今のクラスタリング情報から各クラスタの「最適ラベル」決定
実験
-
人工データ: コストとF値
-
実データ: コストと実行時間
まとめ
-
結果(コスト・実行時間)が結構分散している?
-
計算時間はほぼ線形なのでしかし大したこと無いな
-
コストはもっとイイ手法ありそう
KDD クラスタリング 相関クラスタリング 良
2015/04/13 0:48
最終更新:2015年05月18日 15:32