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

機械学習技術 自然言語技術 人工知能技術 デジタルトランスフォーメーション技術 一般的な機械学習 アルゴリズム 推薦技術 本ブログのナビ
シーケンシャルパターンマイニング

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

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

具体的な応用例としては、遺伝子やタンパク質の配列情報の分析(例:ヌクレオチド塩基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.jartest_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
.......

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

コメント

  1. […] まず1で行う頻出パターンの導出について。頻出パターンとは、特徴量の頻繁な共起のことを言い、以前紹介したAprioriやFG-Growth等のさまざまなアルゴリズムがあるが、結果はほぼ同じで計算スピードが異なるだけなのでどれを用いるかはそれほど問題ではない。 […]

  2. […] これらのイベントは営業の引き合いや受注、お客様からの問い合わせ電話など、組織のさまざまな層で発生している。また、それらはニュース記事[4] やテキストメッセージ、SNSへの投稿、株式市況、交通情報、天気予報やその他の種類のデータかもしれない。 イベントは測定値が時刻や温度その他の、あらかじめ定義されていたしきい値を超えた「状態の変化」として定義されることもある。CEPは組織にリアルタイムでパターンを分析する新たな手法を与え、ビジネスサイドがITとサービス部門とのより良いコュミニケーションを実現するとアナリストは提唱している。 […]

  3. […] シーケンシャルパターンマイニング 繋がっているデータの繋がりパターンの抽出 […]

  4. […] それらを見つけるアルゴリズムとして、古典的なアプローチとしては、前向き推論と後ろ向き推論がある。また機械学習的なものとしては、関係性を求める関係学習、決定木を用いたルール推論、シーケンシャルパターンマイニング、あるいは確率的生成手法等様々なアプローチがある。 […]

  5. […] それらを見つけるアルゴリズムとして、古典的なアプローチとしては、前向き推論と後ろ向き推論がある。また機械学習的なものとしては、関係性を求める関係学習、決定木を用いたルール推論、シーケンシャルパターンマイニング、あるいは確率的生成手法等様々なアプローチがある。 […]

  6. […] シーケンシャルパターンマイニング 繋がっているデータの繋がりパターンの抽出 […]

  7. […] ウェブアクセスログ解析などで使用されている。シーケンシャルパターンマイニングの詳細に関しては”シーケンシャルパターンマイニング“に述べている。そちらも参照のこと。 […]

  8. […] シーケンシャルパーターンマイニングに関しては”シーケンシャルパターンマイニング“にも概要を述べている。そちらも参照のこと。 […]

モバイルバージョンを終了
タイトルとURLをコピーしました