「Scalable K-Means++」の編集履歴（バックアップ）一覧はこちら

「Scalable K-Means++」(2015/11/15 (日) 16:46:08) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* Scalable K-Means++
- 
- VLDB 2012

* 概要
* $$ k\texttt{-means}\parallel $$という手法を提案

* 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, 非一様
-- この間っぽいことをしたい
** アルゴリズム
+ $$ \mathcal{C} \leftarrow X $$ から一点標本
+ $$ \psi \leftarrow \phi_X(\mathcal{C}) $$
+ $$ \textbf{for}\ O(\log \psi) $$繰り返し
++ $$ \mathcal{C}' \leftarrow $$ 確率 $$ \frac{\ell \cdot \mathrm{d}^2(x, \mathcal{C})}{\phi_X(\mathcal{C})} $$ で独立に選んだ点からなる集合
++ $$ \mathcal{C}' \leftarrow \mathcal{C} $$
+ 各点$$ x \in \mathcal{C} $$に重みを設定する
+ 重み付き$$ \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多めにとっておくという処理が並列化でゴリゴリ早くする

&tags()

2015/11/15