PrefixSpan の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• PrefixSpan へ行く。

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