Fast and Provably Good Seedings for k-Means
-
Olivier Bachem, Mario Lucic, Hamed Hassani, Andreas Krause
-
NIPS 2016
概要
K-MC^2
-
Metropolis-Hastings
-
知らないけどサンプルしたい分布 p
-
関係ないけど知っている(素手で設定)分布 q
-
qに従ってサンプル
-
$$ \pi(x_{j-1}, y_j) = \min \left( \frac{p(y_j)}{p(x_{j-1})}\frac{q(x_{j-1})}{q(y_j)}, 1 \right) $$
-
今回はp(y_j)/p(x_j-1)は簡単に計算できる
-
q(x)=1/n
-
欠点
-
データに対する仮定(一様まばら)が実際(heavy-tailed)には無さそう
-
連鎖長がパラメタα,βに依存するのでタイトに計算するのが大変
-
$$ m = \Theta(k \log^2 n \log k) $$の時だけしか保証を調べてない(トレードオフが無い)
提案手法 AFK-MC^2
-
最初のクラスタ中心c1だけサンプルする
-
$$ q(x \mid c_1) = \frac{1}{2}\frac{ \mathrm{d}(x,c_1)^2 }{ \sum_{x' \in {\cal X}} \mathrm{d}(x', c_1)^2} + \frac{1}{2} \frac{1}{|{\cal X}|} $$
-
第一項: 真の$$D^2$$標本分布
-
第二項: ある種の正則化
-
主結果:
-
$$ m=1+\frac{8}{\epsilon}\log \frac{4k}{\epsilon} $$
-
$$ \mathbb{E}[\phi_C({\cal X})] \leq 8(\log_2 k + 2)\phi^k_{\mathrm{OPT}}({\cal X}) + \epsilon \mathrm{Var}({\cal X}) $$
-
前処理時間=O(nd)、サンプリング処理時間=O(ε^-1 k^2 d log k/ε)
-
※Var(X)はk=1の最適値と一致
実験
-
比較手法: k-means++, Random, K-MC^2, AFK-MC^2
-
精度: 連鎖長が同じなら、AFK-MC^2の方がかなり良い
-
連鎖長に対する精度を見てみてもいい感じ
-
距離計算回数の意味でも比較
まとめ
-
MCMC強い
-
手法はとてもシンプルだが、理論的解析が必須でしかも既存の弱い所を補強しているので全体的に良いと思う
NIPS k-means k-means++ クラスタリング
2016/12/31
最終更新:2016年12月31日 00:55