Streaming k-means on well-clusterable data

一人輪講

V. Braverman and A. Meyerson, “Streaming k-means on well-clusterable data,” In SODA, 2011.

ストリームk-meansアルゴリズム．

概要

オンライン施設配置問題アルゴリズム[1]を元にしたストリームk-meansアルゴリズム．時間・空間計算量共に良く，近似比は定数．

提案手法

1. 点xを読み込む
2. xと暫定の施設との距離の自乗値に比例した確率でxを施設に追加する，そうでない場合は，xを最近の施設に割り当てる．
3. 施設の数が増えすぎたら，確率の比例定数をβ倍してまたやり直す．

だいたいこんな感じ．とっても簡単なのが特徴．

解析

主に
1. 確率の比例定数がfで終わった時の目的関数値
2. アルゴリズムが停止した時の確率の比例定数fはどの位の値であるか
の2つから，近似比を算出している．

時間計算量は，自明なO(logOPT)から，O(nklogn)に落とせることを証明している．

戯言

若干解析が間違っている気がする．[1]で示されている定理を改変しているが，そこである値を2倍していないように見える．もしかしたら，2倍しなくていいのかもしれないけど良く分からない．

参考文献

[1] A. Meyerson, “Online facility location,” in Proceedings 2001 IEEE International Conference on Cluster Computing, 2001, pp. 426–431.