StreamKM++: A Clustering Algorithm for Data Streams - todo314 @ ウィキ

StreamKM++: A Clustering Algorithm for Data Streams

• In JEA 2012
  • Journal of Experimental Algorithmics
• In ALENEX 2010

概要

• コアセットを使ったストリームk-meansアルゴリズム

アルゴリズム

• ストリームモデルでコアセットを頑張って計算する
• 確かマルチパス
• 最後にk-means++を適用

コアセット

• Pの(k,ε)コアセット
  • 重み付き集合Sと重み関数wの組
  • $$ \forall C \subset \mathbb{R}^{d}(|C|=k) \quad (1-\epsilon)cost(P,C) \leq cost_w (S,C) \leq (1+\epsilon)cost(P,C) $$

実験

データセット

• Tower, Census1990, BigCrossが注目
  • 数M点、数十次元でかなり大きい

特性調査

• コアセットサイズと実行時間の関係
  • 大体比例している
• コアセットサイズとk-meansコストの関係
  • すぐに収束しているようにみえる
• m=200kに固定

比較対象

• BIRCH
  • 汎用的なクラスタリングアルゴリズム
• StreamLM
  • ？
• k-means++

実験結果

実行時間

• BIRCHはすごく速い
• StreamLSはkに比例して増加
  • 2e4 secとかかかっている
• k-means++もkに依存して遅くなっている
• StreamKM++はBIRCHよりは遅いけど、kの値に影響されにくい
  • BigCrossで2時間位

k-meansコスト

• BIRCHは明らかに劣っている
• StreamKM++とStreamLMはどっこいどっこい
• k-means++も同じくらい

まとめ

• データセットが超でかいし、それでもちゃんと動いているのはすごい

ALENEX JEA k-means streaming algorithm

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