Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming - todo314 @ ウィキ

Non-exhaustive, Overlapping Clustering via Low-Rank Semidefinite Programming

• Yangyang Hou, Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon
• KDD 2015

概要

• Non-exhaustive, Overlapping k-meansの続き
• 元の反復アルゴリズムはあまり良くなかったりする
• 違う解き方を考案

1. 凸SDPで緩和
2. そのままだと大変なので低ランク近似

• 初期化・丸めもちょっと頑張る
• 実験してみたら良かった
• 重複有りコミュニティ検出にも使える
  • kernel k-meansとグラフクラスタリングが等価だから

KDD SDP k-means

2017/06/14