PrefixSpan

PrefixSpan †

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)>

<(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と同様の単調性を利用した，さらなる効率化も導入されている．

-- しましま