VFKM (very fast k-means)

データストリームを想定した k-means法 によるアルゴリズム. 繰り返しk-means法を何度も適用すするが,\(i\) 回目の適用時には,\(n_i\) 個のデータを処理する. そして,無限個のデータを観測したときのセントロイドの位置と,\(n_i\) 個のデータを観測したときのセントロイドの位置の差が \(\epsilon\) 以下となる確率が \(1-\delta\) 以下となることが保証されれば,得られたセントロイドを出力する.

ここで,次回で処理するデータの数 \(n_i\) が小さすぎると k-means法 の適用回数が増えて遅くなる.逆に大きすぎても1度の k-means法 の実行時間が遅くなる. そこで,前回の反復で得られたクラスタを利用し,終了条件を満たすのに必要な最小限のサンプル数をHoeffdingの不等式を用いて計算.これは最も条件がよいときのサンプル数なので,実際にはその10%増し程度のデータを使うことで効率的に計算をする.

-- しましま

関連項目

リンク集

Freeware

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:26 (2490d)