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