Overlapping correlation clustering - todo314 @ ウィキ

Overlapping correlation clustering

• Francesco Bonchi, Aristides Gionis, Antti Ukkonen
• ICDM 2011

概要

• 重複クラスタリング
  • 頂点→ラベル（小）集合
  • 点間の距離最小化
    • 集合交差指示関数
    • Jaccard係数
• 局所探索法
  • 各反復がムズい
    • 集合交差…貪欲法（集合被覆）
    • Jaccard…最小二乗法（NP-hard）

問題定義

• s(u,v): 類似度
  • [0,1]か{0,1}

非重複クラスタリング

• C_cc(V,l) = ∑同クラスタ内の(1-s(u,v)) + ∑異クラスタのs(u,v)
• {0,1}なら各辺±1の符号があって…となる

重複クラスタリング

• $$ \ell: V \rightarrow {\cal L}_+ = 2^{\cal L} - \emptyset $$
  • 頂点は複数のラベルを割り当てられる
• ラベル集合同士の類似度 H
  • これは明示的に与えられない
  • C_OCC(V,l) = ∑|H(l(u),l(v))-s(u,v)|
  • 直感: 頂点間の類似度sを保つようにlを決める
• Jaccard係数
• 集合交差指示関数 I(E,F)=[E∩F≠∅]

制約

• クラスタ数 |L|=k
• 各頂点の所属クラスタ数 |l(v)|≦p
  • ソーシャルネットワークとか考えればまぁ

問題の特徴付け

• 類似度 [0,1] or {0,1}
• 類似関数 H Jaccard or 交差
• クラスタ数制約 p or 無
• 色々見る，多項式時間で厳密解の場合も
• グラフ彩色とも関連
  • ([0,1], 交差, p=k)で0コストを達成する最小のk

アルゴリズム

• 局所探索枠組
  1. C_occ(V,l)が減少する間
  2. 各頂点vについて
  3. v以外のラベル集合を固定して，コスト最小のvのラベル集合を計算・更新
• u≠vについて
• ∑|H(l(u),l(v))-s(u,v)|を最小化する

Jaccardの場合(Jaccard triangulation)

• {<S_j, z_j>}_jが与えられるので，
• ∑|J(X,S_j)-z_j|
• を最小化するXを見つけたい
• 関連問題: Jaccard-median (z_j=1)
• x_i=[i∈X] なる指示を考えると，J(X,S_j)は簡単にかけるので，J=z_jを解きたくなる
• 最小二乗法で解く

集合交差の場合

• 整数計画で書ける
• 関連問題: positive-negative partial set-cover

ICDM クラスタリング 相関クラスタリング

2015/04/13 1:29