Fast and Accurate k-means For Large Datasets

Michael Shindler, Alex Wong, and Adam Meyerson. Fast and Accurate k-means For Large Datasets. In NIPS, 2011.

k-meansアルゴリズムのストリーム版で，割りと最近のもの．

今回は適当に紹介．

k-means問題

Google先生参照．定義だけ書いておくと．
入力：n個の点x_1,x_2,…,x_n，整数k
出力：k個の点y_1,y_2,…,y_k
目的関数： $\mathrm{minimize} \quad \sum_{1 \leq i \leq n}\min_{1 \leq j \leq k}||x_i-y_j||^2$

ストリームk-means問題

まずは，ストリームアルゴリズムについて適当に説明．入力サイズが物凄く大きい場合，一次記憶装置にはデータが入りきらない．仕方がないので，データを二次記憶装置がちびちび読んでメモリ使用量を減らす，というアプローチ．空間計算量が重要．
ストリームk-means問題では，入力の内，n個の点がちびちび与えられる．nとkは最初に分かる．

提案手法

SODAに通ってるpaper[2]の結果を実用的に改良したらしい．この手法は，解の候補を高々O(klogn)個だけ保持しておく．で，入力点を新しく読む度に，入力点から最も近い解の候補との距離の自乗値に比例した確率で入力点を解の候補に追加する．これは，入力点に近い点が解の候補に有ったら入力点は割とどうでもよいが，無かったら入力点の重要度は高いという観察から．解の候補が増えすぎたら，入力点の処理とほぼ同じ処理を自分自身に適用する．最後に，既存のk-meansアルゴリズムで点の数をO(klogn)からk以下に減らす．
性能は右の通り．空間計算量：Θ(klogn)，近似比：17，時間計算量：o(nk)．

実験

データセットはCensus1990とBigCrossというデータを使っている．それぞれ350MB，1.5GBなので，そこそこでかい．比較手法はStreamKM++[1]．けど，実験結果が（何故か）全く滅茶苦茶だった．

戯言

アルゴリズムが凄くシンプルだけどシンプル過ぎでは…という印象．解の候補を多めにとっておいて後から縮小する，というアプローチ自体は普通．あと，論文中で紹介されていた定理は，結構hidden constantを無視していたり謎だったので，この辺ちゃんとして欲しいと思った（定理の証明はある）．それと，実験結果が滅茶苦茶なのは流石にヤバすぎでは…．適当にヒューリスティクス追加するだけでも近似比が良くなることを「実験的には」示せそう．

参考文献

[1] Marcel R. Ackermann, Christian Lammersen, Marcus Märtens, Christoph Raupach, Christian Sohler, and Kamil Swierkot. StreamKM++: A clustering algorithms for data streams. In ALEX, 2010.

[2] Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku. Streaming k-means on Well-Clusterable Data. In SODA, 2011.

[3] Michael Shindler, Alex Wong, and Adam Meyerson. Fast and Accurate k-means For Large Datasets. In NIPS, 2011.