* VFKM (very fast '''k'''-means) [#p787fdce]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

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

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

> -- しましま

** 関連項目 [#p13c2524]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[データストリーム]]
-[[クラスタリング]]
-[[k-means法]]
-[[Hoeffdingの不等式]]
-[[VFDT]]
#br
-[[検索:VFKM]]

** リンク集 [#cc7b64f1]

//関連するWWW資源があればリンクしてください.

*** Freeware [#h4ae3381]

-[[VFML (Very Fast Machine Learing)>http://www.cs.washington.edu/dm/vfml/main.html]]:
VFKMを含む幾つかのデータストリーム用の機械学習アルゴリズムの実装コード

** 関連文献 [#tfb22886]

//この%項目%に関連する書籍や論文を紹介してください.

-基本文献~
P.Domingos & G.Hulten "A General Method for Scaling Up Machine Learning Algorithms and Its Application to Clustering" ICML2001~
[[GoogleScholarAll:A General Method for Scaling Up Machine Learning Algorithms and Its Application to Clustering]]

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS