* PrefixSpan [#a9e4843c]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

PrefixSpanは,系列パターンの列挙問題を,系列のprefixとpostfixという考えを使って,深さ優先探索で解くアルゴリズム.

はじめは,<(a)> ... <(f)> といった,アイテムが1個だけの系列から探索を始める.
ここで,<(a)> の場合,系列 <(a)> をマッチさせた残りの部分をpostfixと呼び,系列データのpostfixのみを保持する.

例えば,次の系列データについて
 <(a) (abc) (ac) (d) (cf)>, <(ad) (c) (bc) (ae)>, <(ef) (ab) (df) (c) (b)>, <(e) (g) (af) (c) (b) (c)>
&lt;(a)> についてのpostfixを残したprojected-databaseは
 <(abc) (ac) (d) (cf)>, <(_d) (c) (bc) (ae)>, <(_b) (df) (c) (b)>, <(_f) (c) (b) (c)>
を保持する.次に,<(a)> を拡張した
 <(a) (a)> <(a) (b)> <(ab)> <(a) (c)> <(a) (d)> <(a) (f)>
という系列を,このpostfixのデータベースについて評価する.頻出するパターンが見つかれば,それを順次長くしていく.

このように深さ優先で系列パターンを列挙する.長い系列は実際には少ないので,projected-databaseは系列パターンの長さと共に小さくなる.

その他,bi-level projection や,AprioriAllと同様の単調性を利用した,さらなる効率化も導入されている.

> -- しましま

**関連項目 [#e9bf9e5a]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[系列パターン]]
-[[バスケットデータ]]
-[[データマイニング]]
-[[頻出パターンマイニング]]
-[[AprioriAll]]
#br
-[[検索:PrefixSpan]]

**リンク集 [#g07156f1]

//関連するWWW資源があればリンクしてください.

*** Freeware [#e196567e]

-[[PrefixSpan>http://chasen.org/~taku/software/prefixspan/]] @ くどう

**関連文献 [#fc2861c9]

//この%項目%に関連する書籍や論文を紹介してください.

-基本文献~
J.Pei, J.Han, B.Mortazavi-Asl, H.Pinto, Q.Chen, U.Dayal, and M.-C. Hsu, "PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth", Proc. of The 17th Int'l Conf. on Data Engineering, pp.215-224 (2001)~
[[GoogleScholarAll:PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth]]
-[[Book/Data Mining - Concepts and Techniques]] 8.3.2節

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