「Streaming k-means on Well-Clusterable Data」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
Streaming k-means on Well-Clusterable Data
- Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku
- In SODA 2011
* メモ
- UCLA（カリフォルニア大学ロサンゼルス校）の人々らしい
* 概要
- [[Online Facility Location]]を元にしたストリームk-meansアルゴリズム
- 時間・空間計算量共に良く、近似比は定数。
* アルゴリズム
+ 点xを読み込む
+ xと暫定の施設との距離の自乗値に比例した確率でxを施設に追加する、そうでない場合は、xを最近の施設に割り当てる
+ 施設の数が増えすぎたら、確率の比例定数をβ倍してまたやり直す
** ポイント
- 三角不等式が成り立たないので証明が変わる
-- 2ノルムの距離については2-三角不等式が成り立つ
* 解析
+ 確率の比例定数がfで終わった時の目的関数値
+ アルゴリズムが停止した時の確率の比例定数fはどの位の値であるか
- の2つから、近似比を算出している。
- 時間計算量は、自明なO(logOPT)から、O(nklogn)に落とせることを証明
* 戯言
- 若干解析が間違っている気がする。[[Online Facility Location]]で示されている定理を改変しているが、そこである値を2倍していないように見える。もしかしたら、2倍しなくていいのかもしれないけど良く分からない
-- 多分勘違いだな…
&tags()
&update()
Streaming k-means on Well-Clusterable Data
- Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku
- In SODA 2011
* メモ
- UCLA（カリフォルニア大学ロサンゼルス校）の人々らしい
* 概要
- [[Online Facility Location]]を元にしたストリームk-meansアルゴリズム
- 時間・空間計算量共に良く、近似比は定数。
* アルゴリズム
+ 点xを読み込む
+ xと暫定の施設との距離の自乗値に比例した確率でxを施設に追加する、そうでない場合は、xを最近の施設に割り当てる
+ 施設の数が増えすぎたら、確率の比例定数をβ倍してまたやり直す
** ポイント
- 三角不等式が成り立たないので証明が変わる
-- 2ノルムの距離については2-三角不等式が成り立つ
* 解析
+ 確率の比例定数がfで終わった時の目的関数値
+ アルゴリズムが停止した時の確率の比例定数fはどの位の値であるか
- の2つから、近似比を算出している。
- 時間計算量は、自明なO(logOPT)から、O(nklogn)に落とせることを証明
* 戯言
- 若干解析が間違っている気がする。[[Online Facility Location]]で示されている定理を改変しているが、そこである値を2倍していないように見える。もしかしたら、2倍しなくていいのかもしれないけど良く分からない
-- 多分勘違いだな…
&tags()
&update()
