シーケンシャルパターンマイニング

シーケンシャルパターンマイニング

シーケンシャルパターンマイニングは、値がシーケンスで配信されるデータ例間で統計的に関連するパターンを見つけるデータマイニングで構造データマイニングの特殊な例となる。

これらの中で行われるタスクとしては「シーケンス情報の効率的なデータベース化とインデックスの構築」「頻繁に発生するパターンの抽出」「シーケンスの類似性の比較」「欠落しているシーケンスデータの補完」等がある。

具体的な応用例としては、遺伝子やタンパク質の配列情報の分析(例:ヌクレオチド塩基A、G、C、Tの配列)とそれらの機能の発現解析、また株式売買やECでの大規模なトランザクション(ひとまとめの取引)で生じる、購買アイテムのパターン抽出(例:顧客が玉ねぎとじゃがいもを購入すると同じトランザクションでひき肉を購入する可能性が高い)、またワークフロー等のプロセスマイニングにも用いられる。

ここで代表的なアルゴリズムであるaprioriについて述べる。(1994年にAgrawalとSrikantにより提案されたもの) まず「相関ルール(Association Rule)」について。これは、X⇒Y(Xという条件が満たされる場合には、同時にYという条件が満たされる場合も頻繁に起きる)というもので、例として、{牛乳、パン}⇒{卵}(牛乳とパンを同時に買う人は、高い頻度で卵を買う))というものがある。

これを応用すると{緑茶、ツナおにぎり}⇒{タラコおにぎり}と{緑茶、ツナおにぎり}⇒{コンブおにぎり}があった時、{緑茶、ツナ、たらこ、コンブおにぎり}のセットを作って単体で買うよ売りも少し値段を下げると、それらが売れて購入単価が上がるというものが考えられる。また{インスタントラーメン}⇒{チャーシュー}があれば、それらの売り場の位置を近づけたり、{牛乳}⇒{パン}であれば牛乳の特売をした時にパンの仕入れ量を上げておく等の施策が考えられる。

ここで全トランザクション数に対する条件Xを満たすトランザクションの割合を支援度(support(X))と定義する。これは例として、条件X={a,b}とした時、全トランザクションがT1={a,b,c}、T2={a,d}、T3=[b,d,e}、T4={a,b,e}、T5={a,b,c}、T6={d,e}とした時、全トランザクション数は6、条件を満たすトランザクションが3なのでsupport(X)=3/6=0.5として表される。

次に確信度(confidence(X,Y))として条件Xを満たすトランザクション数に対する、条件Xと条件Yの両方を満たすトランザクション数の割合を示す。これは先程のsupport(X)を用いてconfidence(X,Y)=support(X∪Y)/support(X)として表される。

ここでAprioriアルゴリズムとはこれらを用いて、入力パラメータとして最小支持度minsupと最小確信度minconfを与えた時、全トランザクションデータから以下の条件を満たす相関ルールX⇒Yをすべて抽出するものとなる。(条件:support(X∪Y)≥minsup、confidence(X,Y)≥minconf)

このアルゴリズムを実施する上で全てを貪欲に行うと計算量が膨大になり、効率が悪い。そのためaprioriアルゴリズムでは、支持度と確信度の特徴を使って効率的に探索する(頻出アイテムの探索と相関ルールの探索の2段階に分けた探索を行う)

さらにAprioriアルゴリズム改良したものとして、GPS(Generalized Sequential Patterns)、SPADE、FreeSpan、PrefixSpan、MAPress、Seq2Pat、SPIRIT、CloSpan等のアルゴリズムが提案されている。

このアルゴリズムを利用可能なツールとしては、Javaのモジュールである「SPMF」、Rを使ったライブラリとなる「arules」、Clojureのモジュールである「apriori」、pythonのモジュールである「Efficient-Apriori」等がある。

これらの中からspmfの使い方を述べる。

1. まず動作環境として、Java1.8以上であることを確認する。
2. 次にダウンロードサイトから実行ファイルspmf.jarとtest_files.zipをダウンロードする。
3. ダウンロードしたspmf.jarをダブルクリックする。(macの場合)　wondowsの場合はspmf.jarを右クリックして、”open with...”と”Java Platform“.の選択で動作させる。

spmfが立ち上がると以下のような画面となる。

spmf画面

ここでPrefixSpanでの例を示す。

1. “Choose an algorithm“のボックスから、”PrefixSpan“を選択する。
2. “Choose input file“でテストファイルを選択する。ダウンロードして解凍したtest_fiile.zipの中から”contextPrefixSpan.txt“を選択する。(macでJava11を導入している時にはうまくファイルにアクセスできない場合がある。その時は最上位のuserフォルダーにtest_fileを格納する)
3. “Choose output file“でアウトプットするファイルを指定(あらかじめ空のresult.txtファイルを作成しておく)
4. “Choose minsup (%)”でパラメータを設定。
5. “Run algorithm“を押して動作させる。

spmf動作

先ほど作成したresult.txtファイルに結果が出力される。

1 -1 #SUP: 4
1 2 -1 #SUP: 2
1 2 -1 3 -1 #SUP: 2
1 2 -1 4 -1 #SUP: 2
1 2 -1 4 -1 3 -1 #SUP: 2
1 2 -1 6 -1 #SUP: 2
1 -1 1 -1 #SUP: 2
1 -1 2 -1 #SUP: 4
1 -1 2 3 -1 #SUP: 2
1 -1 2 3 -1 1 -1 #SUP: 2
1 -1 2 -1 1 -1 #SUP: 2
1 -1 2 -1 3 -1 #SUP: 2
.......

アルゴリズム自体は非常にシンプルでそれほど時間もかからず計算することができる。利用するポイントとしては、データの正規化にある。