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

-- しましま

関連項目

リンク集

Freeware

関連文献


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