- 追加された行はこの色です。
- 削除された行はこの色です。
- VFKM へ行く。
* 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]]