Outlier Detection in Graph Streams
-
Charu C. Aggarwal, Yuchen Zhao, Philip S. Yu
-
ICDE 2011
概要
-
タイトルのまんま
-
問題としては初出なので、ちゃんとした比較対象はない
-
outlierって何?
-
互いに異なるコミュニティに属する人々がつながった!
-
異分野の人たちが共著するとか
-
興味深い!
-
グラフでかいし難しい!
モデリング
-
※辺がどんどんくるストリームモデルを想定
-
C = C_1,…C_kはVの分割
-
p_ij(C): C_iとC_jの間に辺が張られる確率
-
辺ijの尤度: p_I(i,C),I(j,C)
-
1個じゃやばい!ロバストじゃない!一杯分割を用意する
-
合成尤度: MF(i,j,C_1,…C_r) = median{p_I(i,C_1),I(j,C_1), p_I(i,C_r),I(j,C_r)}
-
グラフの尤度: GF(G,C_1,…,C_r) = [Π_{(i,j)}MF(i,j,C_1,…,C_r)]^{1/|G|}
-
pはどうやって見積もるの?
-
non-sample estimated p_ij^n: iとjの属する分割のサイズの積で重み付け
-
sample-estimated p_ij^s: 分割iとjの間にある辺の割合
-
estimated: p_ij(C_m) = λp_ij^n(C_m) + (1-λ)p_ij^s(C_m)
サンプリング
-
密なクラスタに分割したいね
-
単調な集合関数がキーらしい
-
連結成分の数: 単調非増加
-
最大の連結成分のサイズ: 単調非減少
-
f: 最大の連結成分のサイズとする
-
ランダムにしたいので、辺にハッシュ関数をかませる
-
適当な閾値使ってfがそれ以上になったら、ちまちま分割の数を増やす感じ?
-
割りと適当に見えるが多分気のせい
実験
-
GOutlier: Graph Stream Outlier Detection Method
-
比較手法がないので、GMicroとか言うのを使う
-
データセットはDBLPとInternet Movie Database Data Setと合成
-
評価基準
-
False Positive Rate
-
False Negative Rate
-
実際のグラフは面白い結果が出るよ
-
合成は答えが分かっているので比較
まとめ
-
飛ばして読んだので良く分からん
-
これは評価すんの難しいなあと思った
-
Charu C. Aggarwalはよく見る気がする
ICDE outlier streaming algorithm
2014-01-07 00:07:59 (Tue)
最終更新:2014年01月07日 00:07