Fast and Provably Good Seedings for k-Means

Fast and Provably Good Seedings for k-Means

  • Olivier Bachem, Mario Lucic, Hamed Hassani, Andreas Krause
  • NIPS 2016

概要

  • Approximate K-Means++ in Sublinear Time K-MC^2の改善版
    • データに対する強い仮定があるという欠点有り
  • 頂点の標本分布を「一様」から「k-means++の最初の反復っぽい奴」に変える
    • 但し、一回の全点スキャンが必要
  • 仮定無しで、MCMCの連鎖長をバウンドし、期待近似比を保証
  • 実験したら提案手法AFK-MC^2はK-MC^2より実際かなり良い

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
  • 欠点
    1. データに対する仮定(一様まばら)が実際(heavy-tailed)には無さそう
    2. 連鎖長がパラメタα,βに依存するのでタイトに計算するのが大変
    3. $$ 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