AprioriAll

AprioriAllは,系列パターンの列挙問題を,バスケットデータ解析のAprioriで利用されるのと同様の単調性を利用し,幅優先探索で解くアルゴリズム

系列中にあるアイテム集合の数を系列の長さという. ここで,長さ k の系列が頻出であるには,長さ k-1 の全ての部分系列が頻出でなけれ ばならないことを利用する. 例えば,\(\langle(a) (cd) (be)\rangle\) が頻出になるには,\(\langle(cd) (be)\rangle\),\(\langle(a) (be)\rangle\),および \(\langle(a) (cd)\rangle\) が頻出でなければならない.

この性質を使って候補系列を生成し,実際に頻出かどうかを調べる. 短い系列から順に幅優先探索で全体を調べる.

GSP (Generalized Sequential Patterns) はこのAprioriAllの改良手法.系列パターン中のマッチするアイテム集合の間の長さの制限や,効率化などが図られている.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:10:43