* 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節

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