「Chromatic Correlation Clustering」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 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っぽいことをする
+ 今のクラスタリング情報から各頂点の「最適クラスタ」決定
+ 今のクラスタリング情報から各クラスタの「最適ラベル」決定
- 毎ステップで目的関数値は減る→局所解が見つかる
* 実験
- 人工データ: コストとF値
- 実データ: コストと実行時間
-- LCBがCBより悪いこともある
* まとめ
- 結果（コスト・実行時間）が結構分散している？
- 計算時間はほぼ線形なのでしかし大したこと無いな
- コストはもっとイイ手法ありそう
&tags()
2015/04/13 0:48
* 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っぽいことをする
+ 今のクラスタリング情報から各頂点の「最適クラスタ」決定
+ 今のクラスタリング情報から各クラスタの「最適ラベル」決定
- 毎ステップで目的関数値は減る→局所解が見つかる
* 実験
- 人工データ: コストとF値
- 実データ: コストと実行時間
-- LCBがCBより悪いこともある
* まとめ
- 結果（コスト・実行時間）が結構分散している？
- 計算時間はほぼ線形なのでしかし大したこと無いな
- コストはもっとイイ手法ありそう
&tags()
2015/04/13 0:48
