Chromatic Correlation Clustering - todo314 @ ウィキ

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から抜く
• 余った頂点は適当にクラスタラベルを割り当てる
• 近似比
  • 6(2Δ-1)

変種

• Chromatic Ballsがヤバイ例から学んでいく

Lazy Chromatic Balls

• uを#{(uと同ラベル)∩(uの近傍)}に比例した確率で選ぶ
• vをuの近傍から確率的に選ぶ
• Chromatic Balls: 単色の三角形を構成した時だけ追加
• Lazy: 単色の<u or v, z(今のクラスタ内頂点), w>を追加

Alternating-minimization

• クラスタ数Kを指定して，k-meansっぽいことをする

1. 今のクラスタリング情報から各頂点の「最適クラスタ」決定
2. 今のクラスタリング情報から各クラスタの「最適ラベル」決定

• 毎ステップで目的関数値は減る→局所解が見つかる

実験

• 人工データ: コストとF値
• 実データ: コストと実行時間
  • LCBがCBより悪いこともある

まとめ

• 結果（コスト・実行時間）が結構分散している？
• 計算時間はほぼ線形なのでしかし大したこと無いな
• コストはもっとイイ手法ありそう

KDD クラスタリング 相関クラスタリング 良

2015/04/13 0:48