VFKM の変更点

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