系列パターンマイニングとは、頻出する部分系列パターンを高速に抽出する方法の総称です。 やみくもに系列パターンマイニングを行うと不要なパターンも出力されます。 本プログラムでは連続系列と不連続系列との出力を制御する (modified prefixspan)ことにより、n 項関係抽出に適したマイニングを行うことができます。
Windows で利用可能な exe ファイルがパッケージの中に含まれています。
以下のような系列データがあるとする：
a b c a b c a b d a b c a c d a b c a b c d a b c a b c d a b c
頻度４以上の部分系列(type)を枚挙するには以下のようにする：
実行例： % prefixspan -m 4 < data2 a/5 b/4 // a/4 b/4 c/4 a/5 b/4 // a/4 // c/4 a/5 b/4 // b/4 c/4 a/5 b/4 // c/4 ...
結果の中で "//"は、前後の要素の間に１つ以上の他の要素が入っていることを表わす。この他の要素が入っている部分をギャップと呼ぶ。 -s オプションを用いることにより出力する系列中の最小ギャップ数を、 -S オプションを用いることにより出力する系列中の最大ギャップ数を変更することができる。 次の例では、ギャップ数がちょうど１である系列を出力する。 これは頻出する２つ組の枚挙を適す：
実行例： % prefixspan -m 4 -s 1 -S 1 < data2 a/5 b/4 // a/4 b/4 c/4 a/5 b/4 // b/4 c/4 a/5 b/4 // c/4 a/5 // a/5 b/5 c/5 a/5 // b/5 c/5 a/5 // c/5 a/5 // d/4 a/4 b/4 c/4 b/5 // a/4 b/4 c/4 b/5 // b/4 c/4 b/5 // c/4 c/5 // b/4 c/4 c/5 // c/4 d/4 a/4 // c/4 d/4 // b/4 c/4 d/4 // c/4
-S オプションを用いることにより、連続 ngram のみの抽出をすることができる：
実行例： % prefixspan -m 4 -S 0 < data2 a/5 b/4 b/5 c/4 c/5 d/4 a/4 b/4 c/4
ギャップの中の要素が多い場合、つまりギャップの前後の２要素があまりにも離れている場合、 あまり関連性のない系列であることがある。ギャップ中の要素を制御するために -g オプションを用いることにより最小ギャップ長を、 -G オプションを用いることにより最大ギャップ長を変更することができる。 次の例では、ギャップ長がちょうど１である系列を出力する：
実行例： % prefixspan -m 4 -g 1 -G 1 -s 1 -S 1 < data2 d/4 a/4 // c/4 d/4 // b/4 c/4
上記例では、１行内に同じパターンが n (n>1)回出現しても１回として数えている。 １行内に同じパターンが n (n>1)回出現した場合に n 回として数える （tokenごとに数える）には、以下のようにする：
実行例： % prefixspan -m 7 -c token < data2 a/10 b/9 c/8 a/10 // c/13 b/9 c/8 c/9
ここでは頻度 7 回以上のものを出力している。 結果をよくみると隣接する a-b と、隣接しない a-b とを別々に数えているのがわかる。 隣接する 2 要素の間にも「長さ 0 のギャップがある」として、ギャップがあるものと一緒に数えたい場合には -0 オプションを用いる：
実行例： % prefixspan -m 7 -c token -0 < data2 a/10 b/9 c/8 a/10 b/9 // c/12 a/10 // b/14 c/13 a/10 // b/14 // c/17 a/10 // c/14 b/9 c/8 b/9 // c/12 c/9
まとめると以下の表のような数え方がある：
| 連続 ngram のみ | 2つ組抽出 | 2つ組抽出(長さ 0 のギャップを許す) | 2つ組抽出(ギャップの最大長は 3) | |
|---|---|---|---|---|
| tokenごと (１行内に同じパターンが n (n>1)回出現すると n 回として数える) | -c token -S 0 | -c token -s 1 -S 1 | -c token -s 1 -S 1 -0 | -c token -s 1 -S 1 -G 3 |
| typeごと (１行内に同じパターンが n (n>1)回出現しても １回として数える) | -S 0 | -s 1 -S 0 | -s 1 -S 1 -0 | -s 1 -S 1 -G 3 |
default では、右最大パターンのみ出力する。 -a オプションを用いることにより、全パターンを出力する:
実行例： % prefixspan -m 5 < data2 a/5 // a/5 b/5 c/5 a/5 // a/5 // c/5 a/5 // b/5 c/5 a/5 // c/5 b/5 c/5 % prefixspan -a -m 5 < data2 5 a 5 a // a 5 a // a b 5 a // a b c 5 a // a // c 5 a // b 5 a // b c 5 a // c 5 b 5 c
-w オプションを用いることにより、出現場所を出力する:
実行例： % prefixspan -w -m 3 -S 1 -G 1 < data2 <pattern> <what>a/5 b/4 c/3</what> <where>0 3 4</where> </pattern> <pattern> <what>a/5 c/0 c/3</what> <where>0 3 4</where> </pattern> <pattern> <what>b/5 c/4</what> <where>0 2 3 4</where> </pattern> <pattern> <what>c/5 d/3 a/3 b/3 c/3</what> <where>2 3 4</where> </pattern> <pattern> <what>c/5 d/3 a/3 c/0 c/3</what> <where>2 3 4</where> </pattern> <pattern> <what>c/5 d/3 b/0 b/3 c/3</what> <where>2 3 4</where> </pattern> <pattern> <what>c/5 a/0 a/3 b/3 c/3</what> <where>2 3 4</where> </pattern> <pattern> <what>d/4 a/4 b/4 c/4</what> <where>1 2 3 4</where> </pattern> <pattern> <what>d/4 a/4 c/0 c/4</what> <where>1 2 3 4</where> </pattern> <pattern> <what>d/4 b/0 b/4 c/4</what> <where>1 2 3 4</where> </pattern>
-a と -w オプションを同時に用いることもできる：
実行例： % prefixspan -a -w -m 4 -S 1 -G 1 < data2 <pattern> <freq>5</freq> <what>a</what> <where>0 1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>a b</what> <where>0 1 3 4</where> </pattern> <pattern> <freq>5</freq> <what>b</what> <where>0 1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>b c</what> <where>0 2 3 4</where> </pattern> <pattern> <freq>5</freq> <what>c</what> <where>0 1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>d</what> <where>1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>d a</what> <where>1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>d a b</what> <where>1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>d a b c</what> <where>1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>d a // c</what> <where>1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>d // b</what> <where>1 2 3 4</where> </pattern> <pattern> <freq>4</freq> <what>d // b c</what> <where>1 2 3 4</where> </pattern>
数え飛ばしたい要素をファイルに書き出しておく(例えば stopwords)。 -k オプションにより、このファイルを指定しておくことにより、その要素を読み飛ばす：
実行例：c % cat stopwords a c % prefixspan -k stopwords < data2 b/5 d/1 // b/1 b/5 // b/4 b/5 // d/2 // b/2 d/4 // b/4
a c b a c b a b a b a c b a b a b a c b a c a c
の中に 「a // b」 というパターンはいくつあるだろうか？
行単位に数えると：
% prefixspan < data3 ... a/5 // b/4 ... ...
パターン単位に数えると（「a // b」と 「a b」 は区別して数え、「a // b」の "//"は "a" でも "b" でも可能）：
% prefixspan -c token < data3 ... a/10 // b/8 ... ...
パターン単位に数えると（「a // b」と 「a b」 は区別して数え、「a // b」の "//"はかならず "a" でも "b" 以外）：
% prefixspan -c token -x < data3 ... a/10 // b/4 ... ...
パターン単位に数えると（「a // b」と 「a b」 は同じとして数え、「a // b」の "//"は "a" でも "b" でも可能）：
% prefixspan -c token -0 < data3 ... a/10 // b/12 ... ...
パターン単位に数えると（「a // b」と 「a b」 は同じとして数え、「a // b」の "//"はかならず "a" でも "b" 以外）：
% prefixspan -c token -x -0 < data3 ... a/10 // b/8 ... ...
このうちパターン単位でとびとびに数えると、 "a"に対して 2 以上の "a//b"が可能であったり、"a b"が複数回数えられる場合があるため、確率モデルや共起尺度を得るための基礎データとして不向きな数え方もある。まとめると以下のようになる：
| 数える単位 | 数え方 | オプション | P("a//b"|"a") | 注意点 |
|---|---|---|---|---|
| 行単位 | 4/5 | |||
| パターン単位 | 「a // b」と 「a b」 は区別して数え、「a // b」の "//"は "a" でも "b" でも可能 | -c token | 8/10 | "a"に対して、2 以上の "a//b"が可能 |
| パターン単位 | 「a // b」と 「a b」 は区別して数え、「a // b」の "//"はかならず "a" でも "b" 以外： | -c token -x | 4/10 | |
| パターン単位 | 「a // b」と 「a b」 は同じとして数え、「a // b」の "//"は "a" でも "b" でも可能 | -c token -0 | 12/10 | "a"に対して、2 以上の "a//b"が可能、"a b"は複数回数えられる場合がある |
| パターン単位 | 「a // b」と 「a b」 は同じとして数え、「a // b」の "//"はかならず "a" でも "b" 以外： | -c token -x -0 | 8/10 | "a b"は複数回数えられる場合がある |