![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
データストリームを想定した k-means法 によるアルゴリズム． 繰り返しk-means法を何度も適用すするが，\(i\) 回目の適用時には，\(n_i\) 個のデータを処理する． そして，無限個のデータを観測したときのセントロイドの位置と，\(n_i\) 個のデータを観測したときのセントロイドの位置の差が \(\epsilon\) 以下となる確率が \(1-\delta\) 以下となることが保証されれば，得られたセントロイドを出力する．
ここで，次回で処理するデータの数 \(n_i\) が小さすぎると k-means法 の適用回数が増えて遅くなる．逆に大きすぎても1度の k-means法 の実行時間が遅くなる． そこで，前回の反復で得られたクラスタを利用し，終了条件を満たすのに必要な最小限のサンプル数をHoeffdingの不等式を用いて計算．これは最も条件がよいときのサンプル数なので，実際にはその10%増し程度のデータを使うことで効率的に計算をする．
-- しましま
