Reliable Clustering on Uncertain Graphs - todo314 @ ウィキ

Reliable Clustering on Uncertain

• Lin Liu, Ruoming Jin, Charu Aggarwal, Yelong Shen
• ICDM 2012

概要

• uncertain graphsをクラスタリングしたい
• 清浄(purity)と均衡(size balance)に基づく信頼度尺度
• k-meansっぽい局所改善手法

問題定式化

• $$1 \leq i \leq N$$: ランダムグラフのID（試行数）
• $$1 \leq j \leq L_i$$: 各ランダムグラフの連結成分
• $$1 \leq k \leq K$$: 各クラスタ
• $$ C_k^{i,j} $$: $$G_i$$における(クラスタk)∩(連結成分j)

Purity

• 最小化 $$ \mathcal{F}_p = \sum_{i} \Pr[G_i] \sum_{1 \leq j \leq L_i} |C^{i,j}| H(\{ C_1^{i,j}, \ldots, C_K^{i,j} \}) $$
  • Hは$$|C^{i,j}|$$で正規化したエントロピー
  • 各連結成分がどれかのクラスタに含まれてるとエントロピー最小で嬉しい

Size balance

• 最大化: $$ \mathcal{F}_e = |V| H(\{C_1, \ldots, C_k\}) $$
  • 要はクラスタの大きさだけ見ればいい（グラフとは無関係）

一般化信頼度クラスタリング

• 最小化: $$ \mathcal{F} = \mathcal{F}_p - \mathcal{F}_e $$
• 観察: $$ \mathcal{F} = \sum_{i} \Pr[G_i] \sum_{1 \leq k \leq K} |C_k| H(\{ C_k^{i,1}, \ldots, C_k^{i,L_i} \}) $$
  • 各クラスタ内の連結成分に関するエントロピーだから，クラスタ全体が連結だと0

性質

• 何か符号化と関連があるけど，読みにくいので省略

提案手法

1. 適当にKクラスタに割り当て
2. 収束まで反復
   1. $$ \{ C_k^{i,1}, \ldots, C_k^{i,L_i} \} $$をハフマン符号化
   2. 各頂点を現在の割当で符号長最小のクラスタに割当て

• 収束する（Fが減少する）
• 各クラスタが連結だと嬉しい
  • 一旦連結成分でバラして，Fが増えにくい成分対を併合

実験

• データセット
  • DBLP: 辺重みに応じて確率を割り当て
  • PPI: BioGRIDデータベース，ちゃんとした確率
  • Karate: 値は適当
  • Politics-Books: 値は適当
• 効果の尺度
  • F自身
  • 各クラスタ内の頂点対の連結確率
  • 各クラスタ全体の連結確率
  • どれも大体既存のクラスタリングより良い
• 速度: 微妙

まとめ

• う～んイマイチ

ICDM uncertain graphs クラスタリング ネットワーク信頼性

2016/01/07