Fast and Accurate k-means For Large Datasets - todo314 @ ウィキ

Fast and Accurate k-means For Large Datasets

• Michael Shindler, Alex Wong, Adam Meyerson
• In NIPS 2011

メモ

• Shindlerはオレゴン州大学
• WongはUC Los Angeles
• MeyersonはOnline Facility Locationの著者（単独）、でGoogle

概要

• k-meansの爆速ストリームアルゴリズム
• Streaming k-means on Well-Clusterable Dataを簡易化して実装して実験しました、って感じ
• 理論がやばい（意味不

アルゴリズム

• 解の候補を高々O(klogn)個だけ保持しておく
• 入力点を新しく読む度に、入力点から最も近い解の候補との距離の自乗値に比例した確率で入力点を解の候補に追加する
  • 入力点に近い点が解の候補に有ったら入力点は割とどうでもよいが、無かったら入力点の重要度は高いという観察
• 解の候補が増えすぎたら、入力点の処理とほぼ同じ処理を自分自身に適用する
• 最後に、既存のk-meansアルゴリズムで点の数をO(klogn)からk以下に減らす
• 最近傍探索は1次元ベクトルにRandom Projectionしてる
  • へぼそう

実験

データセット

• Census1990とBigCross
  • 350MB、1.5GB

比較手法

• StreamKM++

実験結果

• （何故か）全く滅茶苦茶

戯言

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

NIPS k-means streaming algorithm

2013-10-17 23:25:40 (Thu)