Non-exhaustive, Overlapping k-means

Non-exhaustive, Overlapping k-means

  • Joyce Jiyoung Whang, Inderjit S. Dhillon, David F. Gleich
  • SDM 2015

概要

  • 既存のクラスタリング(特にk-means)手法は、外れ値の重複のどちらかだけだった
  • NEO-K-Means (Non-Exhaustive Overlapping K-Means) を提案
  • 重み付きカーネルk-meansとの互換性もある
    • 外れ値&重複有りグラフクラスタリングに使える

定式化

  • $$ U=[u_{ij}]_{n \times k} $$: $$ \mathbf{x}_i $$がクラスタ$$j$$の属する
  • 重複の具合の制約: $$ \mathrm{trace}(U^\top U) = (1+\alpha)n $$
    • これだけは上手くいかない―外れ値じゃない奴が外れ値扱いされる―
  • 外れ値の数の制約: $$ \sum_{1 \leq i \leq n} \mathbb{I}\{ (U\mathbf{1})_i=0 \} \leq \beta n $$
    • これで調整する
  • Lloydっぽいアルゴリズム
    • $$n-\beta n$$点を最近クラスタに配置
    • $$ \beta n + \alpha n $$点を重複有りで(現状配置無しの)最近クラスタに配置
    • ちゃんと目的関数値は減少する
  • αとβの選び方…なんか適当に頑張る
  • Weighted kernel k-means
    • $$ w_i \|\phi(\mathbf{x}_i - \mathbf{m}_j)\|^2 $$←こんな感じ
    • Normalized Cutによるクラスタリングはこの形で表せる
    • NEOも入れると、外れ値&重複有りグラフクラスタリングが出来て便利

実験

  • ベクトルデータ、グラフデータで実験
  • F1スコアとnormalized cutの値を見ると良さげ
  • 比較手法: MOC, OKM, restricted OKM, explicit/implicit sparsity constrained clustering

まとめ

  • もうちょっとアルゴリズムがいい感じで、楽しい結果だったらトップレベル(だから後続研究はKDDだけど)
  • もう少し汎用的で、自動的にパラメータを設定するとか、
  • representativeなもの(?)だけとってくるとか出来ると良さそう

SDM k-means クラスタリング

2017/03/27

最終更新:2017年03月27日 03:03