Scalable K-Means++ - todo314 @ ウィキ

Scalable K-Means++

• Bahman Bahmani, Benjamin Moseley, Andrea Vattani, Ravi Kumar, Sergei Vassilvitskii
• VLDB 2012

概要

• $$ k\texttt{-means}\parallel $$という手法を提案
• 複数反復で複数点選ぶ
  • 選ぶところで並列化
• 一般的な理論的保証が成り立つのが良い

動機付け

• k-meansは例え理論的には良くなくても実際的な用途では強力
• k-means++が現時点で最強
• ただし，O(nkd)時間
  • Lloyd's methodの一反復と同じ
• 並列化が難しそう && k=100,1000とかで難しい

$$ k\texttt{-means}\parallel $$

• 直感
  • k-means: 反復数1，一様
  • k-means++: 反復数k, 非一様
  • この間っぽいことをしたい

アルゴリズム

1. $$ \mathcal{C} \leftarrow X $$ から一点標本
2. $$ \psi \leftarrow \phi_X(\mathcal{C}) $$
3. $$ \textbf{for}\ O(\log \psi) $$繰り返し
   1. $$ \mathcal{C}' \leftarrow $$ 確率 $$ \frac{\ell \cdot \mathrm{d}^2(x, \mathcal{C})}{\phi_X(\mathcal{C})} $$ で独立に選んだ点からなる集合
   2. $$ \mathcal{C}' \leftarrow \mathcal{C} $$
4. 各点$$ x \in \mathcal{C} $$に重みを設定する
5. 重み付き$$ \mathcal{C} $$をk-meansしてkクラスタ計算

• 並列化するのは$$ \mathcal{C}' $$の構築
• $$ \ell = O(k) $$
• $$ \psi \leq \Delta^2 n^2 $$
• $$|\mathcal{C}| = r \times \ell$$
  • r = 反復数，ℓ = 一反復辺りの期待増加数
  • $$ O(\ell \log \psi) $$クラスタが出力される
• 定理
  • α近似アルゴリズムが使われていたなら，最終的な出力はO(α)近似

実験

• $$ \ell \{0.1k, 0.5k, k, 2k, 10k\}, r = 15 $$
• ℓを色々と変えて挙動を見る
• コスト，時間，反復回数

まとめ

• こういうのは色々できそう
• log factor多めにとっておくという処理が並列化でゴリゴリ早くする

VLDB k-means 並列化

2015/11/15