Streaming k-means approximation

Streaming k-means approximation

  • Nir Ailon, Ragesh Jaiswal, Claire Monteleoni
  • In NIPS
  • 2009

メモ

  • Google Researchとコロンビア大学の人々

概要

  • ストリーム k-means アルゴリズムの提案
  • O(log k)近似

アルゴリズム

k-means #

  • O(1)近似
  1. ランダムにXの中から3 log k点選び,Cに追加
  2. C ← Pから選んだ 3log k 点
  3. k-1回繰り返す
    1. C ∪= Pからδ(x,C)に比例する確率で選んだ3log k点

本命

  • O(log k)近似
  1. PをP1,…,Pl に分割
  2. 各Piについて k-means #を実行してO(k log k)個クラスタ中心Tiを求める
  3. Sw ← T1,…,Tlを重みつき(クラスタに属する点の個数)で併合
  4. S_wに対してk-means ++を実行しk個のクラスタ中心を得る

実験

データセット

  • 10,000点くらい
    • 小せぇ

比較対象

  • batch Lloyd's
  • online Lloyd
  • DC-1, DC-2
    • 上で説明したの

k-meansコスト

  • 提案手法の方が良い
    • batchとくらべても1/10以下
  • DC-1とDC-2の差はわずか

まとめ

  • データ小さいな…
    • Censusとか使ってほしい
  • Lloydよりも良いというのが面白い
    • k-means++入れたらどうなる…?
  • 理論入ってないとNIPSは通らんのだなあ、多分

参考

NIPS k-means streaming algorithm

2013-10-17 23:24:57 (Thu)

最終更新:2013年10月17日 23:24