「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)近似
+ ランダムにXの中から3 log k点選び，Cに追加
+ C ← Pから選んだ 3log k 点
+ k-1回繰り返す
++ C ∪= Pからδ(x,C)に比例する確率で選んだ3log k点
** 本命
- O(log k)近似
+ PをP1,…,Pl に分割
+ 各Piについて k-means #を実行してO(k log k)個クラスタ中心Tiを求める
+ Sw ← T1,…,Tlを重みつき（クラスタに属する点の個数）で併合
+ 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は通らんのだなあ、多分
* 参考
- http://d.hatena.ne.jp/tsubosaka/20091230/1262156496
&tags()
&update()
Streaming k-means approximation
- Nir Ailon, Ragesh Jaiswal, Claire Monteleoni
- In NIPS
- 2009
* メモ
- Google Researchとコロンビア大学の人々
* 概要
- ストリーム k-means アルゴリズムの提案
- O(log k)近似
* アルゴリズム
** k-means #
- O(1)近似
+ ランダムにXの中から3 log k点選び，Cに追加
+ C ← Pから選んだ 3log k 点
+ k-1回繰り返す
++ C ∪= Pからδ(x,C)に比例する確率で選んだ3log k点
** 本命
- O(log k)近似
+ PをP1,…,Pl に分割
+ 各Piについて k-means #を実行してO(k log k)個クラスタ中心Tiを求める
+ Sw ← T1,…,Tlを重みつき（クラスタに属する点の個数）で併合
+ 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は通らんのだなあ、多分
* 参考
- http://d.hatena.ne.jp/tsubosaka/20091230/1262156496
&tags()
&update()
