Streaming k-means approximation
-
Nir Ailon, Ragesh Jaiswal, Claire Monteleoni
-
In NIPS
-
2009
メモ
-
Google Researchとコロンビア大学の人々
概要
-
ストリーム k-means アルゴリズムの提案
-
O(log k)近似
アルゴリズム
k-means #
-
ランダムにXの中から3 log k点選び,Cに追加
-
C ← Pから選んだ 3log k 点
-
k-1回繰り返す
-
C ∪= Pからδ(x,C)に比例する確率で選んだ3log k点
本命
-
PをP1,…,Pl に分割
-
各Piについて k-means #を実行してO(k log k)個クラスタ中心Tiを求める
-
Sw ← T1,…,Tlを重みつき(クラスタに属する点の個数)で併合
-
S_wに対してk-means ++を実行しk個のクラスタ中心を得る
実験
データセット
比較対象
-
batch Lloyd's
-
online Lloyd
-
DC-1, DC-2
k-meansコスト
-
提案手法の方が良い
-
DC-1とDC-2の差はわずか
まとめ
-
データ小さいな…
-
Lloydよりも良いというのが面白い
-
理論入ってないとNIPSは通らんのだなあ、多分
参考
NIPS k-means streaming algorithm
2013-10-17 23:24:57 (Thu)
最終更新:2013年10月17日 23:24