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アルゴリズム
  • 時間・空間計算量共に良く、近似比は定数。

アルゴリズム

  1. 点xを読み込む
  2. xと暫定の施設との距離の自乗値に比例した確率でxを施設に追加する、そうでない場合は、xを最近の施設に割り当てる
  3. 施設の数が増えすぎたら、確率の比例定数をβ倍してまたやり直す

ポイント

  • 三角不等式が成り立たないので証明が変わる
    • 2ノルムの距離については2-三角不等式が成り立つ

解析

  1. 確率の比例定数がfで終わった時の目的関数値
  2. アルゴリズムが停止した時の確率の比例定数fはどの位の値であるか
  • の2つから、近似比を算出している。
  • 時間計算量は、自明なO(logOPT)から、O(nklogn)に落とせることを証明

戯言

  • 若干解析が間違っている気がする。Online Facility Locationで示されている定理を改変しているが、そこである値を2倍していないように見える。もしかしたら、2倍しなくていいのかもしれないけど良く分からない
    • 多分勘違いだな…

SODA k-means streaming algorithm

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

最終更新:2013年10月17日 23:25