* lossy countingアルゴリズム (lossy counting algorithm) [#l2692be3]
//ここには %項目の説明を書いてください.よろしければ署名しておいてください.
支持度が \(s\) であるようなシンボルを,支持度に対する許容誤差が \(\epsilon\) を保証しつつ,データストリームから列挙するアルゴリズム.
- 最初は \(\mathcal{D}\) は空.この集合の要素は \((e,f,\Delta)\).ただし,\(e\) はシンボル,\(f\) はシンボルの数,\(\Delta\) は最大許容誤差.
- 現在読んだストリームのシンボル数は \(N\),バケット幅 \(w=\lceil 1/\epsilon\rceil\),そして現在のバケットは \(b_{current}\) 番目.
- 新たなシンボル \(e\) が来たら
-- バケット内のシンボルが \(\mathcal{D}\) 中にある場合には,そのエントリーの \(f\) を一つ増やし,\(\Delta\) を \(b_{current}-1\) とする.
-- バケット内のシンボルが \(\mathcal{D}\) 中にない場合には,新たなエントリ \((e,1,b_{current}-1)\) を作る.
- バケットを読み終わったら,\(f+\Delta\le b_{current}\) のエントリーを削除する.
- 利用者の要求に応じて,支持度が \(s\) 以上のシンボルを取り出すには,\(f\ge(s-\epsilon)N\) を満たすシンボルを \(\mathcal{D}\) から取り出す.
> -- しましま
** 関連項目 [#wbd322aa]
//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[lossy counting algorithm]]
#br
-[[データストリーム]]
-[[逐次学習]]
** リンク集 [#t60d3828]
//関連するWWW資源があればリンクしてください.
** 関連文献 [#c052d819]
//この%項目%に関連する書籍や論文を紹介してください.
-基本文献~
Manku and Motwani "Approximate Frequency Counts over Data Streams" VLDB2002~
[[GoogleScholarAll:Approximate Frequency Counts over Data Streams]]
-[[Book/Data Mining - Concepts and Techniques]] 8.1.3節