Streaming k-means on Well-Clusterable Data
-
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, Brian Tagiku
-
In SODA 2011
メモ
-
UCLA(カリフォルニア大学ロサンゼルス校)の人々らしい
概要
アルゴリズム
-
点xを読み込む
-
xと暫定の施設との距離の自乗値に比例した確率でxを施設に追加する、そうでない場合は、xを最近の施設に割り当てる
-
施設の数が増えすぎたら、確率の比例定数をβ倍してまたやり直す
ポイント
解析
-
確率の比例定数がfで終わった時の目的関数値
-
アルゴリズムが停止した時の確率の比例定数fはどの位の値であるか
-
の2つから、近似比を算出している。
-
時間計算量は、自明なO(logOPT)から、O(nklogn)に落とせることを証明
戯言
SODA k-means streaming algorithm
2013-10-17 23:25:42 (Thu)
最終更新:2013年10月17日 23:25