DEIM Forum 2014 D4-4

マルチ最小サポートを用いて継続時間と時間間隔を考慮した
時系列パターンマイニングアルゴリズム
史旭†

新谷 隆彦†

大森

匡†

藤田

秀之†

† 電気通信大学大学院情報システム研究科 〒 182–8585 東京都調布市調布ヶ丘 1-5-1
E-mail: †shixu@hol.is.uec.ac.jp, ††{shintani,omori,fujita}@is.uec.ac.jp
あらまし

時系列パターンマイニングはイベントの発生順序を考慮したパターンを抽出する重要な技術である．しかし，従来の手法は，イベントが時間的にどれだけ継続したか，また二つのイベント間にどれだけ間隔があるかを考慮しないため，意思決定を十分に支援できない場合がある．本研究では，イベントそれぞれの継続時間と時間間隔を階層に分割し，マルチレベルで継続時間と時間間隔を考慮した時系列パターンを抽出することを目的とする．さらに階層のレベルに従って異なる最小サポートとするマルチ最小サポートを用いて時系列パターンを抽出するアルゴリズムを提案する．
キーワード

時系列パターンマイニング，継続時間，時間間隔，マルチ最小サポート

XU SHI† , Takahiko SHINTANI† , Tadashi OHMORI† , and Hideyuki FUJITA†† The University of Electro-Communications, Graduate School of Information Systems
1-5-1 Chofugaoka, Chofu-shi, Tokyo, 182–8585 Jappan
E-mail: †shixu@hol.is.uec.ac.jp, ††{shintani,omori,fujita}@is.uec.ac.jp

1. は じ め にるため，上位レベルのパターンの出現頻度が高くなる．最小サポートを高く設定した場合，下位レベルのパターンが抽出され蓄積された膨大なデータから潜在的に価値のある情報を見つない場合がある．下位レベルのパターンを抽出するためには最け出すデータマイニング技術の 1 つとして，時系列パターンマ

小サポートを低く設定する必要があるが，この場合には大量のイニングの研究が進められてきた [1,2]．時系列パターンマイニ

パターンが抽出されてしまう．そのため，階層を持つデータにングによってイベントの発生順序を示すパターンが抽出される

対してはレベル毎に異なる最小サポートを設定するマルチ最小

が，イベントの継続時間とイベント間の時間間隔は考慮されてサポートが利用される場合がある [3]．

来なかった．そのため，抽出されたパターン中のイベントがど本研究ではイベントの継続時間と時間間隔のレベルに従ってれだけ継続したか，また二つのイベント間にどれだけ時間間隔異なる最小サポートとするマルチ最小サポートにより継続時間があるかを知ることはできない．この問題を解決するために，と時間間隔を考慮した時系列パターンを抽出する．

イベントの継続時間とイベント間の時間間隔を考慮した時系列
パターンの抽出手法が必要となる．

2. 関 連 研 究

時系列パターンを抽出するには継続時間と時間間隔を離散化

時系列パターンマイニングに関する研究はこれまでに数多くしてアイテムにしなければならない．継続時間はイベント毎に，行われてきた．イベントの発生順序のみを考慮する手法として，時間間隔はイベント間毎に分布や範囲が異なるため，時間を適

幅優先探索でパターン候補作成型の手法である GSP[1] と深さ切に分割することが困難である．そこで，本研究ではそれぞれ優先探索でパターン成長型の手法である PrefixSpan[2] が提案

イベントの継続時間とイベント間の時間間隔を階層に分割し，されている．time window と呼ばれる所定の時間窓の間に発生

マルチレベルで継続時間と時間間隔を考慮した時系列パターン

する時系列パターンであるエピソードを抽出する手法も提案さを抽出する手法を検討する．

れている [4]．エピソードでは時間間隔が大きなパターンの抽

また，従来の時系列パターンマイニングは閾値として単一の出を回避できるが，様々な時間間隔を持つパターンを抽出する

最小サポートを設定していた．階層で上位レベルのパターンのことはできない．イベント間の時間間隔情報を扱った時系列パ

出現頻度は下位レベルのパターンの出現頻度を合わせた値となターンを抽出する研究がある [5,6]．I-PrefixSpan[5] は時間間

隔を平均的にいくつかの時間帯に分割し，単一レベルで時間間隔を考慮した時系列パターンを抽出する．また，I-PrefixSpanを拡張した MULTI-PrefixSpan[6] は時間間隔を階層に分割することで時間間隔が異なるレベルに属するパターンも抽出することができる．しかし，これら手法ではイベントの継続時間を考慮することができない．また，階層を考慮したイベン
トの組合せパターンを階層レベル毎に異なる最小サポートで

図1あるマルチ最小サポートにより抽出するアルゴリズムである

継続時間の階層

MMS-Cumulate[7] が提案されているが，この手法では時系列を生成する．イベントセット毎にイベントが属する継続時間のパターンを抽出することができない．

クラスタ集合を追加したシーケンスを継続クラスタシーケンスと呼ぶ．そして，継続クラスタシーケンスの集合を継続クラス

3. 問 題 定 義
3. 1 シーケンスデータ

タデータと呼び，第 4 節で提案する手法は本データを利用する．
時間間隔の階層は与えられた最小と最大の時間間隔からなる本研究では開始時刻と終了時刻を持つイベントからなるデー

時間帯を平均的に深さ Il ，それぞれの親ノートが Ik 個の子ノー

タを処理対象とする．イベント名 (event)，開始時刻 (tstart )，トを持つ階層に分割する．生成された各のノードを１つの時間

end) の組をイベントセット，イベントの開始時

帯として，いつからいつまでの時間単位を表す．図 2 には最小

刻 の 順 で ソ ー ト し た イ ベ ン ト セット を シ ー ケ ン ス と 呼 び ，

時間間隔を 0，最大時間間隔を 27，Ik を 2，Il を 3 とした場合

終了時刻 (tstart end
, tend, tend, t2 ) · · · (eventn , tstart⟨(event1 , tstartnn )⟩ の時間間隔階層の例を示す．
11 )(event2 , t2と表現する．ここで，(eventi , tstart, tend) は i 番目に開始されi
i
るイベントを示す．イベント i の継続時間は tend
− tstart，イii
ベント i と j(i < j) 間の時間間隔は tstart− tendとなる．時間ji
間隔がマイナスの場合はイベント j がイベント i の終了する前に開始したこと，ゼロの場合はイベント j がイベント i の終了

図2

時間間隔の階層した直後に開始したことを意味する．ID 毎に並べたシーケン

3. 3 継続時間と時間間隔を考慮した時系列パターン

スの集合をシーケンスデータと呼び，表 1 に例を示す．

以上継続時間と時間間隔の階層に基づいて，継続時間と時間

表 1 シーケンスデータ
ID
1
2
···

シーケンス
⟨(C, 1, 5)(A, 6, 7)(D, 7, 20)(B, 15, 25)(E, 25, 32)(B, 35, 40)⟩⟨(A, 2, 6)(F, 4, 7)(B, 8, 9)(A, 9, 17)(C, 22, 26)(B, 26, 30)⟩···

3. 2 継続時間と時間間隔の階層
時系列パターンを抽出するには継続時間と時間間隔を離散化してアイテムにしなければならない．しかし時間を細かい分割する場合，一定数以上なパターンを抽出することが困難である．
時間を粗い分割する場合，詳細な継続時間情報と時間間隔情報
を取れなくなってしまう．そこで，本研究ではそれぞれイベン
トの継続時間とイベント間の時間間隔を階層に分割し，さまざ
まな範囲で分割した離散値として扱う．これによりマルチレベ
ルで継続時間と時間間隔を考慮した時系列パターンを抽出する．
イベント毎に継続時間の分布が異なるため，継続時間はイベ
ント毎に深さ Dl ，それぞれの親ノートが Dk 個の子ノートを持つ階層に分割する．分割には K-means クラスタリング [8] を用い，イベントを含む全てのシーケンスにおいて出現する継続時間の値を対象に，範囲分割する．生成された各ノードを 1 つのクラスタとして，そのノードにおける最小値と最大値間の区間を表す．図 1 に Dk を 2，Dl を 3 とした場合のイベント Aの階層の例を示す．
イベントが属す継続時間クラスタを示すために，それぞれイベントの継続時間階層によって，そのイベントが属す全ての継続時間クラスタの集合をイベントセットにおけるイベント名と差し替え，([eventi cluster], tstart, tend) の継続クラスタセットii

間隔を考慮したマルチレベルの時系列パターン (以降パターンと呼ぶ) を定義する．
［定義 1］ 継続時間アイテム (Ditem)：継続時間の階層における個々のクラスタを継続時間アイテムとする．
［定義 2］ 時間間隔アイテム (Iitem)：時間間隔の階層における個々の時間帯を時間間隔アイテムとする．
［定義 3］ パ タ ー ン：継 続 時 間 ア イ テ ム を 先 頭 と 末 尾 とし て ，継 続 時 間 ア イ テ ム と 時 間 間 隔 ア イ テ ム を 交 互 に現れる開始時刻の順に並べたリストをパターンと呼び，⟨Ditem1 Iitem(1,2) Ditem2 Iitem(2,3) · · · Iitem(n−1,n) Ditemn ⟩と表現する．ここで，Ditemi は i 番目に開始される継続時間
アイテム，Ditemj (j = i + 1) は Ditemi の次に開始される継続時間アイテムを示す．Iitem(i,j) は Ditemi と Ditemj 間の時間間隔が属する時間間隔アイテムを表す．
［定義 4］ パターンの長さ：パターンを構成する継続時間アイ
テムの数である．
［定義 5］ シーケンスがパターンを含む：継続クラスタシーケ
ンスの中に，パターンを構成する全ての継続時間アイテムが存在する．それらの継続時間アイテムの出現順序がパターンにおける継続時間アイテムの出現順序と一致し，また継続時間アイ
テム間の個々時間間隔がパターンに対応する時間間隔アイテムに属す場合，シーケンスがパターンを含むと言う．
［定義 6］ パターンの出現頻度：継続クラスタデータにパターンを含む異なるシーケンスの件数をパターンの出現頻度と呼ぶ．

［定義 7］ パターンのサポート：パターンの出現頻度に対する［定義 10］ 長さ 3 以上のパターンのレベル：長さ 3 以上のパ

継続クラスタデータ中の全てのシーケンス件数の割合である．

ターンの場合，パターンに現れる連続する Ditem と Iitem と［定義 8］ 頻出パターン：パターンのサポートは与えられたサ

Ditem からなる長さ 2 のパターンのうち，最下位のレベルを持

ポートの最小値 (最小サポートと呼ぶ) を満たすパターンを頻つ長さ 2 のパターンのレベルをこのパターンのレベルとする．

出パターンとする．

階層で上位レベルのパターンの出現頻度は下位レベルのパ

本研究では 2 つの継続時間アイテム間の時間間隔が最小時間ターンの出現頻度を合わせた値となるため，上位レベルのパ

間隔以上，最大時間間隔未満となる頻出パターンのみを抽出す

ターンの出現頻度が下位レベルのパターンの出現頻度より高る．また，イベントが 1 つのシーケンスに重複して出現する場

くなる傾向がある．そのため，最小サポートについて，上位レ

合，そのイベントからなる異なる継続時間アイテムと時間間隔

ベルのパターンに相対的に高い最小サポート，下位レベルのパアイテムによって生成された全てのパターンを抽出する．図 3

ターンに相対的に低い最小サポートによりパターンの頻出をには時間間隔を図 2 に示す例の階層に分割する状態で，ある継判断する必要がある．本研究では，パターンのレベルに従い，続クラスタシーケンスにおいて重複して出現する 2 つのイベン

各レベルで異なる最小サポートを設定し，複数の最小サポート

ト A，B からなる考慮するパターンの例を挙げる．

(マルチ最小サポートと呼ぶ) を用いて頻出パターンを抽出する．
3. 5 パターンの包含関係
同じ出現回数を持つ同じ長さの 2 つのパターン例えば，⟨aIb⟩と ⟨aI1 b⟩ がある場合，I1 が I の子ノードとして，I より細か
い時間間隔の時間帯を表すため，⟨aI1 b⟩ のほうが ⟨aIb⟩ より明
確に a が終了した後に b の開始時刻を示すことができる．また，⟨aIb1 ⟩ と ⟨aIb11 ⟩ がある場合，b11 が b1 の子ノードとして，b1 より細かい継続時間の範囲を表すため，⟨aIb11 ⟩ のほうが ⟨aIb1 ⟩ より明確にイベント B の継続時間を示す．この場合，⟨aI1 b⟩ と ⟨aIb⟩，また ⟨aIb1 ⟩ と ⟨aIb11 ⟩ を包含関係を満たすパターンと定義し，包含関係を満たす 2 つのパターンのうちより明確な情報を提供する ⟨aI1 b⟩ と ⟨aIb11 ⟩ のほうがより良い意思
図 3 考慮するパターン

3. 4 パターンのレベルとマルチ最小サポート
パターンは継続時間アイテムと時間間隔アイテムから構成さ
れ，継続時間アイテムと時間間隔アイテムはそれぞれ階層を持つことから，パターンに対しても継続時間の階層と時間間隔の階層を両方考慮してパターンの階層を定義する必要がある．
［定義 9］ 長さ 2 のパターンのレベル (P level2 )：P level2 =levelDitem1 + levelIitem(1,2) + levelDitme2 で計算する．ここで，levelDitem は継続時間アイテムのレベル，levelIitem は時間間隔アイテムのレベルを表す．
従って，継続時間と時間間隔をそれぞれ 3 レベルの階層に分割する場合，長さ 2 のパターンは上位レベル 0 から，下位レベ
ル 6 までの 7 レベルの階層に分けられる．ここで，イベントの継続時間を Dk = 2，Dl = 3，時間間隔を Ik = 2，Il = 3 の階層に分割し，生成されるイベント A の継続時間アイテム a，a0 ，a00 とイベント B の継続時間アイテム b，b0 ，b00 ，また時間間隔アイテム I ，I1 ，I11 からなる 7 つのレベルに属する長さ 2 のパターンの例を表 2 に挙げる．

決定のサポートができるパターンと考えられる．
［定義 11］ パターン m，n が以下 4 つの条件に従う場合，mと n が包含関係を満たすとする：（ 1 ） m と n は，同じ長さ l のパターンである．
（ 2 ） m と n は，1 番目の継続時間アイテムから，(l − 1) 番
目の継続時間アイテムまでの間の全ての継続時間アイテムと時間間隔アイテムが一致する．
（ 3 ） m と n は，l 番目で同じ継続時間アイテムを持ち，かつ (l − 1) 番目の継続時間アイテムと l 番目の継続時間アイテム
間の時間間隔アイテムが時間間隔階層の上下関係を満たす．
或は m と n は，(l − 1) 番目の継続時間アイテムと l 番目の継
続時間アイテム間の時間間隔アイテムが同じで，かつ l 番目の継続時間アイテムが継続時間階層の上下関係を満たす．
（ 4 ） m と n は，同じ出現回数である．
本研究では継続時間と時間間隔を階層に分割し，マルチレベ
ルでパターンを抽出するため，大量のパターンが抽出されてしまう．従って，パターンが包含関係を満たす場合，継続時間と時間間隔情報をより明確に示すパターンのみを抽出することで，より実用性の高いパターンを得られることが期待できる．さら

表2
レベル
0
1
2
3
4
5
6

長さ 2 のパターンのレベル

長さ 2 のパターン⟨aIb⟩⟨a0 Ib⟩, ⟨aI1 b⟩, ⟨aIb0 ⟩⟨a00 Ib⟩, ⟨a0 I1 b⟩, ⟨a0 Ib0 ⟩, ⟨aI1 b0 ⟩, ⟨aIb00 ⟩, ⟨aI11 b⟩⟨a00 I1 b⟩, ⟨a00 Ib0 ⟩, ⟨a0 I11 b⟩, ⟨a0 I1 b0 ⟩, ⟨a0 Ib00 ⟩, ⟨aI11 b0 ⟩, ⟨aI1 b00 ⟩⟨a00 I11 b⟩, ⟨a00 I1 b0 ⟩, ⟨a00 Ib00 ⟩, ⟨a0 I11 b0 ⟩, ⟨a0 I1 b00 ⟩, ⟨aI11 b00 ⟩⟨a00 I11 b0 ⟩, ⟨a00 I1 b00 ⟩, ⟨a0 I11 b00 ⟩⟨a00 I11 b00 ⟩に，パターン数の爆発を抑え，抽出計算コストの削減にも役に立つと考えられる．

4. 提 案 手 法
本研究では継続時間を持つイベントを階層に分割した継続時
間アイテムと時間間隔を階層に分割した時間間隔アイテムを処理する必要がある．GSP のような候補作成型の手法では大量の候補パターンが作成され，処理効率が悪くなることが予想さから長さ (l + 1) のパターンを探索するため，長さ l のパターンれる．そこで，本研究では GSP より数多くのパターンを効率のレベルで頻出とならないパターンから，長さ (l + 1) のパターよく抽出できるパターン成長型の手法である PrefixSpan を参ンを抽出することはできない．しかし，長さ l のパターンを 1

考としたアルゴリズムを提案する．

つ伸ばした長さ (l + 1) のパターンを作成するときにパターンの

4. 1 PrefixSpan
まずはじめに PrefixSpan について述べる．PrefixSpan はイ

レベルが下がる場合がある．下位レベルに対応する最小サポー

ベントの出現順序のみを考慮した時系列パターンを効率よく抽レベルに対応する最小サポートでは頻出パターンとなる可能性

出するアルゴリズムであり，主に以下 3 つのステップからなる．

があるが，Prefix とする長さ l のパターンが枝刈りされてしま•ステップ 1： シーケンスデータをスキャンして，長さ 1の頻出パターン α を抽出する．

•

トのほうが小さな値となるため，長さ (l + 1) のパターンが下位う場合，そのパターンを抽出できない．従って，DI-PrefixSPM
では，最下位パターンレベルの最小サポートを満たすパターン

ステップ 2： それぞれ長さ 1 の頻出パターン α に対し，を全て抽出した後に，マルチ最小サポートを用いて頻出パター

PrefixSpan(α, l, DB |α ) を呼び出す．ここで，α を Prefix，lンを選択する手法とした．しかし，DI-PrefixSPM では上位レを α の長さ，DB |α を α の射影データベースとする．

ベルの非頻出のパターンも最下位レベルの最小サポートを満た•

ステップ 3： PrefixSpan(α, l, DB |α ) を再帰で実行する．

(1)DB |α をスキャンし，α に加えることが可能な頻出イベン

す場合には数えされてしまうため，冗長なパターンを大量に探索することになり，処理効率が落ちてしまう問題がある．

ト β を見つけ出す．(2) 各頻出イベント β について，β を α に

4. 3 DI-SufPrefixSPM

連接し，α を拡張したパターン α′ を生成して，長さ (l + 1) のDI-PrefixSPM の問題点を解決し，冗長なパターンの計算を頻出パターンとして出力する．(3) 各 α′ について，α′ の射影

回避しながら，マルチ最小サポートを満たす全ての継続時間とデータベース DB |α′ を生成し，PrefixSpan(α′ , l + 1, DB |α′ )

時間間隔を考慮した時系列パターンを抽出するアルゴリズムを呼び出す．

Duration Interval-Suﬃx Prefix Sequential Pattern Mining(以4. 2 DI-PrefixSPM

降 DI-SufPrefixSPM と呼ぶ) を提案する．

継続時間と時間間隔を考慮した時系列パターンを抽出す

DI-PrefixSPM においてマルチ最小サポートを用いて頻出パるために，PrefixSpan を拡張したナイーブなアルゴリズム

ターンを抽出しようとしたとき，全ての頻出パターンを抽出でDuration Interval-Prefix Sequential Pattern Mining(以降 DI-

きない場合がある．あるパターンを伸ばしたときにそのレベル

PrefixSPM と呼ぶ) を提案する．

よりも下位レベルのパターンとなる場合があることが原因とな

4. 2. 1 DI-PrefixSPM のアルゴリズム

ることに注目する．DI-SufPrefixSPM では，パターンに現れる

本手法では，それぞれのイベントの継続時間階層を記録した

連続する Ditem と Iitem と Ditem からなる長さ 2 のパター

継続クラスタデータ，時間間隔階層，パターンレベルごとのマンのうち，最下位レベルを持つ長さ 2 のパターンをベースパ

ルチ最小サポートを入力する．主に 2 つのステップからなる．

ターンと定義する．ベースパターンのレベルに対応する最小サ•ステップ 1：PrefixSpan と同じ手順で最下位パターンレベルの最小サポートを満たすパターンを抽出する．

•

ステップ 2：抽出されたそれぞれのパターンについて，パ

ターンのレベルに対応する最小サポートを用いて頻出パターン
を選択する．

ポートを用いてパターンを前後に伸ばすことによって，頻出パ
ターンを抽出する．

4. 3. 1 DI-SufPrefixSPM のアルゴリズム
本手法では，PrefixSpan と同様に頻出パターンである Prefix
を伸ばすことと Prefix に対する射影を行うことを繰り返すこと

また，PrefixSpan はイベントの発生順序のみを考慮するアルによって頻出パターンを抽出するだけでなく，頻出パターンをゴリズムであり，時間間隔を考慮しないため，1 件のシーケン

Suﬃx(接尾) にして，Suﬃx Projection という射影方法によっ

スにイベントが重複して出現しても順序が変わらない場合には，て生成される Suﬃx 射影データベースを用いることで頻出パ

Prefix ごとに 1 件のシーケンスに対して 1 回の射影を行うこと

ターンを抽出する必要がある．Suﬃx Projection とは，射影元で新たなパターンを生成するためのシーケンスデータが得られのシーケンスから射影対象の Suﬃx より前に存在する継続クラ

る．しかし，時間間隔を考慮する場合，重複して出現するイベ

スタセットからなるシーケンスのみを抽出する射影である．そントから生成された異なるパターンを抽出するため，Prefix ご

して，与えられた継続クラスタデータベースに対し，Suﬃx に対とに 1 件のシーケンスに対してイベントの重複する回数の射影

する射影を行った結果のデータベースを Suﬃx 射影データベーを行う必要がある．本研究ではそれぞれのシーケンスに対して，

スと言う．Suﬃx 射影データベースにはその Suﬃx を接尾に持複数回の射影を行うことによって生成された射影データベース

つ頻出パターンを見つけ出すために必要な継続クラスタデータ

をマルチ射影データベースと呼ぶ．

が全て含まれることになる．Suﬃx を伸ばすことと Suﬃx に対

4. 2. 2 DI-PrefixSPM の問題点する射影を行うことを繰り返すことによって頻出パターンを抽DI-PrefixSPM は PrefixSpan と同様に Prefirx を伸ばすこと出する．また，本研究では Prefix 毎にマルチ射影データベーと射影データベースの生成によって頻出パターンを抽出する．しスを生成すると同様に Suﬃx 毎に 1 件の継続クラスタシーケ

かし，長さ毎にマルチ最小サポートを用いてパターンを枝刈り

ンスに対して継続時間アイテムの重複する回数の射影を行い，することができない．それは DI-PrefixSPM が長さ l の PrefixSuﬃx 毎にマルチ射影データベースの生成が必要である．

それぞれのイベントの継続時間階層を記録した継続クラス

Algorithm 1 DI-SufPrefixSPM(DB, Ihierarchy, minsup[pl])タデータ，時間間隔階層，パターンレベルごとのマルチ最小サ
ポートを入力する．主なステップを以下に示す．

•

ステップ 1：入力された継続クラスタデータベースにおいて，最下位パターンレベルの最小サポートを満たす長さ 1 のパターンを抽出する．

•

ステップ 2：長さ 1 のパターンを Suﬃx(接尾) として，

Suﬃx より前方に出現する継続時間アイテムを探索し，マルチ
最小サポートを用いて長さ 2 の頻出パターンを抽出し，ベース
パターンとする．

•

ステップ 3：それぞれのベースパターンを Suﬃx として

Suﬃx 射影を行い，ベースパターンのレベルに対応する最小サポートを用いて，前方に出現する 条件 1 を満たす継続時間アイ
テムを加え，再帰で頻出パターンである Suﬃx を成長させる．

– 条件 1 その継続時間アイテムは Suﬃx の 1 番目における継続時間アイテムと構成する長さ 2 のパターンがベースパ
ターンのレベルより上位になること．

•

ステップ 4：それぞれのベースパターンを Prefix として

Prefix 射影を行い，ベースパターンのレベルに対応する最小サ

Input: DB : 継続クラスタデータベース
Ihierarchy : 時間間隔階層
minsup[pl] : パターンレベルに対応する最小サポート
Output: 継続時間と時間間隔を考慮した頻出時系列パターン
Subroutine: GeneratePrefixMDB(α′ , l′ , P ref ixM DB |α )GenerateSuﬃxMDB(α′ , l′ , Suf f ixM DB |α )PrefixDISPM(α, l, baselevel, P ref ixM DB |α )SuﬃxDISPM(α, l, baselevel, Suf f ixM DB |α )Parameters: α, α′ : 継続時間と時間間隔を考慮した時系列パターン
l :α の長さl′ :α′ の長さ
P ref ixM DB |α :α のマルチ Prefix 射影データベース
Suf f ixM DB |α :α のマルチ Suﬃx 射影データベース
L : 継続時間と時間間隔を考慮した頻出時系列パターンの集合
Ll : 長さ l の継続時間と時間間隔を考慮した頻出時系列パターンの集合
baselevel : ベースパターンのレベル
H2 : 包含関係を満たした長さ 2 の上位レベルパターンの集合
Sup : サポート
Ditem : 継続時間アイテム
Iitem : 時間間隔アイテム

1: Li =SuﬃxDISPM(null, 0, minsup[最下位レベル], DB)
2: for α in L2 do
3:
P ref ixM DB |α =GeneratePrefixMDB(α, 2, DB)
4:
Lii =PrefixDISPM(α, 2, baselevel, P ref ixM DB |α )5: end for
6: for α in Li do
7:
P ref ixM DB |α =GeneratePrefixMDB(α, l, DB)
8:
Liii =PrefixDISPM(α, l, baselevel, P ref ixM DB |α )9: end for
10: L = Li + Lii + Liii
11: L を出力

ポートを用いて，後方に出現する 条件 2 を満たす継続時間アイ
テムを加え，再帰で頻出パターンである Prefix を成長させる．

– 条件 2 その継続時間アイテムは Prefix の一番最後における継続時間アイテムと構成する長さ 2 のパターンがベースパ
ターンのレベルより上位，または同じレベルになること．

•

5. 評 価 実 験DI-PrefixSPM と DI-SufPrefixSPM の比較実験を通して，マルチ最小サポートにおける最下位レベルの最小サポートを変化

ステップ 5：ステップ 3 で抽出されたそれぞれの頻出パさせた場合の処理性能，シーケンス長またはシーケンス数を増ターンを Prefix として Prefix 射影を行い，そのパターンにお加させた場合の処理性能，そして，マルチ最小サポートによる

けるベースパターンのレベルに対応する最小サポートを用いて，枝刈りの効果の 3 つの観点から 2 つのアルゴリズムの性能を評

後方に出現する 条件 2 を満たす継続時間アイテムを加え，再帰価する．また，包含関係を満たすパターンの抽出の回避によっで頻出パターンである Prefix を成長させる．

て，計算コストがどれだけ減少したかも考察する．

以上 5 つのステップにおいて，ステップ 3，4，5 は再帰で呼2 つのアルゴリズムを Java 言語で実装し，人工的に作成しび出され，別々に長さ l から長 (l + 1) の頻出パターンを抽出すたデータを用いて，継続時間と時間間隔を最大 3 レベルの階層

るが，条件 1 と条件 2 の制限によって各ステップで抽出されるに分割した条件下で，評価実験を行った．実験で使うマシンは頻出パターンが全て異なるため，重複して探索することなく全Intel(R) Xeon(R) 3.07GHz の CPU と 12GB のメモリを用いての頻出パターンを抽出できる．

る．Java version は 1.7 であり，OS は ubuntu 12.04 である．

アルゴリズムを Algorithm1 に示す．サブルーチンとなる

5. 1 実験データ

主な処理手順である Suﬃx を伸ばす処理 (SuﬃxDISPM) と人工生成データは [9] で紹介する synthetic data generation

Prefix を伸ばす処理 (PrefixDISPM) はそれぞれ Algorithm2

algorithm においてイベントに継続時間と時間間隔を追加し，と Algorithm3 に示す．

Potentially large シーケンスにおけるイベントの継続時間クラ4. 3. 2 DI-SufPrefixSPM の問題点

スタが異なる分布になるように作成した．表 3 にデータ生成でDI-SufPrefixSPM はマルチ最小サポートを用いた長さごと設定する各パラメータを示す．そして，各パラメータを変更しの枝刈りによって，頻出とならないパターンの計算を回避す

た 5 つの実験データを作成し，表 4 に示す．ここで，Ne =1000，ることで良い処理効率を実現する．しかし，DI-PrefixSPM で

Lp =5，Np =1000，Dmax=27，I=0〜27 は一定値とした．

後ろ方向に頻出パターンを伸ばすのみであったことに対して，

DI-SufPrefixSPM では後ろ方向だけでなく，前方向にも頻出パターンを伸ばす必要とある．従って，マルチ最小サポートに
よって枝刈りされるパターンが多い場合は DI-SufPrefixSPMの処理効率が良いが，そうではない場合は DI-SufPrefixSPMの処理性能が低下する場合があると考えられる．

表 3 パラメータの説明
パラメータ
Ne
Ns
Ls
Np
Lp
Dmax
I

説明
イベント数
シーケンス数
シーケンス平均長Maximal Potentially large シーケンス数
Maximal Potentially large シーケンスの平均長さ
継続時間の最大値
時間間隔の区間

表 4 実験データ
ID
1
l0
l2
n0
n2

Ns
100,000
100,000
100,000
50,000150,000

LS
15
10
20
15
15

Algorithm 2 SuﬃxDISPM(α, l, baselevel, Suf f ixM DB |α )Algorithm 3 PrefixDISPM(α, l, baselevel, P ref ixM DB |α )Subroutine: GenerateSuﬃxMDB(α′ , l′ , Suf f ixM DB |α )Method:Subroutine: GeneratePrefixMDB(α′ , l′ , P ref ixM DB |α )Method:1: if l = 0 then2:
L1 = {α | supα >= minsup[最下位レベル]}3:
for α in L1 do
4:
Suf f ixM DB |α =GenerateSuﬃxMDB(α, 1, DB)
5:
SuﬃxDISPM(α, 1, null, Suf f ixM DB |α ) を呼び出す
6:
end for
7: end if
8: if l = 1 then9:
初期化 hashmapE
10:
for list M in Suf f ixM DB |α do
11:
初期化 listP12:
for 射影シーケンス in M do
13:
tstart を得る
14:
for Ditem in 射影シーケンス do
15:interval = tstart − tend , Ihierarchy によって {Iitems} を

1: 初期化 hashmapE
2: for list M in P ref ixM DB |α do
3:
初期化 listP4:
for 射影シーケンス in M do
5:tend を得る
6:
for Ditem in 射影シーケンス do
7:interval = tstart − tend
8:
Ihierarchy によって，{Iitems} を生成
9:for Iitem in {Iitems} do10:β = αの一番最後の Ditem + (IitemDitem)11:
if β の レ ベ ル が baselevel よ り 上 位 ，ま た は baselevel と 同 じ

生成

16:
for Iitem in {Iitems} do
17:
if !P .contains((DitemIitem)) then18:
P, E.key ← (DitemIitem), E.key.value + +19:
end if
20:
end for21:
end for22:
end for23:
end for24:
for (DitemIitem) in E do
25:
α′ = (DitemIitem) + α′
26:
if !包含関係&&Supα′ >= minsup[α のラベル] then27:baselevel = α′ のラベル, l′ = 2, L2 ← α′28:
end if29:
if 包含関係 then30:
H 2 ← α′31:
end if32:
end for33:
for α′ in L2 do
34:
Suf f ixM DB |α′ =GenerateSuﬃxMDB(α′ , 2, Suf f ixM DB |α )35:
SuﬃxDISPM(α′ , 2, baselevel, Suf f ixM DB |α′ ) を呼び出す
36:
end for37: end if
38: if l > 0 then39:
初期化 hashmapE
40:
for list M in Suf f ixM DB |α do
41:
初期化 listP
42:
for 射影シーケンス in M do
43:
tstart を得る
44:
for Ditem in 射影シーケンス do
45:interval = tstart − tend , Ihierarchy によって {Iitems} を
生成
for Iitem in {Iitems} do
β = (DitemIitem) + αの一番目の Ditem
if β の レ ベ ル が baselevel よ り 上 位&&!β ∈ H2&&!P .contains((DitemIitem)) then49:
P, E.key ← (DitemIitem) , E.key.value + +50:
end if
51:
end for52:
end for53:
end for54:
end for55:
for (DitemIitem) in E do
56:
α′ = (DitemIitem) + α
57:
if !包含関係&&Supα′ >= minsup[baselevel] then58:l′ = l + 1, Ll′ ← α′59:
end if
60:
end for61:
for α′ in Ll′ do
62:
Suf f ixM DB |α′ =GenerateSuﬃxMDB(α′ , l′ , Suf f ixM DB |α )63:
SuﬃxDISPM(α′ , l′ , baselevel, Suf f ixM DB |α′ ) を呼び出す
64:
end for65: end if&&!P .contains((IitemDitem)) then12:
P, E.key ← (IitemDitem), E.key.value + +13:
end if14:
end for15:
end for16:
end for17: end for
18: for γ in Li do
19:
if γ の P ref ix = α then20:
E.key ← (IitemDitem) = γ − γ の P ref ix, E.key.value = Supγ
21:
Li から削除22:
end if
23: end for
24: for (IitemDitem) in E do
25:
α′ = α + (IitemDitem)26:
if !包含関係&&Supα′ >= minsup[baselevel] then27:l′ = l + 1′
28:
Ll′ ← α29:
end if
30: end for
31: for α′ in Ll′ do
32:
P ref ixM DB |α′ =GeneratePrefixMDB(α′ , l′ , P ref ixM DB |α )33:
PrefixDISPM(α′ , l′ , baselevel, P ref ixM DB |α′ ) を呼び出す
34: end for

46:
47:
48:

(a) 実行時間(b) 頻出パターン

図 4 データ 1 の実行結果

ンの数を表す．図 4 によると，最下位レベルの最小サポートが小さくなるに従って，DI- PrefixSPM と DI-SufPrefixSPMの実行時間が指数的に増加する．これは最小サポートの設定が低いほど，頻出となるパターンが増加することが原因である．また，最下位レベルの最小サポートが小さくなるに従って，

DI-PrefixSPM と DI-SufPrefixSPM の処理時間の差が増大していることが分かった．
図 5(a) に最下位レベルの最小サポート毎に 2 つのアルゴリ
ズムが処理したパターンの数を表す．図 5(b) には最下位レベ

5. 2 最小サポートの変化と処理性能

ルの最小サポートが 0.5%の場合，処理したパターンの数とマ

データ 1 を用いてパターンレベルの最小サポート間の差

ルチ最小サポートにより頻出と判断されたパターンの数を表す．

を 0.05%に設定し，最下位レベルの最小サポートを 0.6%から

図 5(a) から，最下位レベルの最小サポートが小さくなるに従っ

0.3%まで変化させた場合の 2 つアルゴリズムの実行時間，処理て，DI-PrefixSPM と DI-SufPrefixSPM が実行中に処理した

したパターンの数，抽出する頻出パターンの数を考察する．

パターンの数の差が増大していることが分かった．これは 2 つ

図 4(a) に 2 つのアルゴリズムが各最下位レベルの最小サポーのアルゴリズムの処理時間の差が増大する原因となる．図 5(b)トでの実行時間を表す．また図 4(b) には各最下位レベルの最小によって，最下位レベルの最小サポートが 0.5%の場合，DI-

サポートで，2 つのアルゴリズムによって抽出された頻出パター

PrefixSPM により処理したパターンの数が DI-SufPrefixSPM

の 2 倍以上となる．頻出パターンとして抽出されるのは処理し

DI- SufPrefixSPM は DI-PrefixSPM より処理効率がよくなる．

たパターンよりかなり少ない数の 2175 件である．つまり，マ

これはシーケンスの長が長いほど，1 件のシーケンスが新たな

ルチ最小サポートによって，処理中で長さ毎に枝刈りできるパパターンを含む可能性が高くなり，それら枝刈りの対象になるターンがたくさん存在し，DI-PrefixSPM がステップ 1 の処理パターンが DI-PrefixSPM のステップ 1 によってたくさん計算

でそれらのパターンを全て計算してしまうため，実行時間がされ，処理効率が落ちてしまう．

DI-SufPrefixSPM より遅くなった．

図 8(a) にはシーケンス数が 100000，最下位レベルの最小サポートが 0.5%の場合，シーケンス平均長は 10，15，20 でDI-PrefixSPM と DI-SufPrefixSPM が実行中に処理したパターンの数を示す．図 8(a) によると，シーケンス長の増加に従って，処理したパターンの数について DI-PrefixSPM のほうがDI-SufPrefixSPM より大幅に増加していることが分かった．
そして図 4(a) と図 7 から，同じシーケンス平均長で，シーケンスの数を 50000 ずつ増加させた場合，シーケンス数の増加に(a) 処理パターン(b) 最下位最小サポート=0.5%

図 5 データ 1 の実行中の処理パターン

よって，DI-PrefixSPM と DI-SufPrefixSPM の実行時間の差が増加することが分かった．つまり，シーケンスの数が多いほど，DI- SufPrefixSPM は DI-PrefixSPM より処理効率がよく

5. 3 シーケンス長，シーケンス数の変化と処理性能なる．これはシーケンス数の増加と共に，処理途中で生成され表 4 の 5 つのデータを用いて，パターンレベルの最小サポーるパターンが多くなり，それらのパターンがマルチ最小サポー

ト間の差を 0.05%に設定し，最下位レベルの最小サポートをトにより頻出にならないが，DI-PrefixSPM のステップ 1 では

0.6%から 0.3%まで変化させた場合のシーケンスの長さとシーケ

それらパターンに対する無駄な計算をたくさん行った．

ンスの数の増加に対する DI-PrefixSPM と DI-SufPrefixSPM

図 8(b) にはシーケンス平均長が 15，最下位レベルの最小サポートが 0.5%の場合，シーケンス数は 50000，100000，150000の実行時間の変化を考察する．
図 6 には同じシーケンス数を持ち，シーケンス平均長が 10で DI-PrefixSPM と DI-SufPrefixSPM が実行中に処理したパと 20 のデータ l0，l2 の実行時間を示す．図 7 には同じシーケ

ターンの数を示す．図 8(b) によると，シーケンス数の増加に

ンス平均長であり，シーケンスの数が 50000 と 150000 のデー

従って，DI-PrefixSPM と DI-SufPrefixSPM により処理した

タ n0，n2 の実行時間を示す．

パターンの数の差が拡大していることが分かった．

(a) データ l0 の実行時間(b) データ l2 の実行時間

図 6 シーケンス長と実行時間(a) シーケンス長と処理パターン(b) シーケンス数と処理パターン

図 8 シーケンス長，シーケンス数と処理パターン

5. 4 枝刈りと処理性能
4.3.2 節で述べた DI-SufPrefixSPM の問題点より，マルチ最小サポートの設定は DI-SufPrefixSPM の処理効率に影響する．
各パターンレベルに対応する最小サポート間の差が大きければ大きいほど枝刈りのパターンが多くなり，DI-SufPrefixSPM の処理効率がよくなる．最小サポート間の差が小さければ小さい
ほど，枝刈りのパターンが少なくなり，DI-SufPrefixSPM の処(a) データ n0 の実行時間(b) データ n2 の実行時間

図 7 シーケンス数と実行時間

図 4(a) と図 6 によって，同じシーケンス数でシーケンス平
均長を 5 ずつ増加させた場合，シーケンス長の増加に従って，

DI-PrefixSPM と DI-SufPrefixSPM の実行時間の差が増加す
るすることが分かった．つまり，シーケンスの長さが長いほど，理効率が落ちる．
ここでデータ 1 を対象に，最下位レベルの最小サポートが0.5%の場合，各パターンレベルに対応する最小サポート間の差を 0.01%，0.03%，0.05%に設定した場合の DI-Suf PrefixSPMと DI-PrefixSPM の実行時間と処理したパターンの数を比較す
る．結果を図 9 に示す．
図 9 によると，各パターンレベルに対応する最小サポート間

(a) 実行時間比較(b) 処理パターン比較

図 9 枝刈りと処理性能(a) 実行時間

図 10(b) 処理パターン

包含関係と DI-SufPrefixSPM の処理性能の差が高くなるに従って，マルチ最小サポートにより枝刈り対
象になるパターンの数が増加し，DI- SufPrefixSPM により処理したパターンの数が減少することで，DI-SufPrefixSPM の実行時間が減少している．DI-PrefixSPM がパターン探索処理のステップ 1 では最下位レベルの最小サポートによりパターンを抽出することで，最下位レベルの最小サポートが同じ場
合，各パターンレベルに対応する最小サポート間の差の変化による処理したパターン数の変化がないため，DI-PrefixSPMの実行時間がほとんど変わらない．また，各パターンレベルに(a) 実行時間

図 11(b) 処理パターン

包含関係と DI-PrefixSPM の処理性能対応する最小サポート間の差が 0.01%のときに，マルチ最小

ル毎に異なる最小サポートを設定するマルチ最小サポートを用

サポートの枝刈り効果が弱いため，DI-SufPrefixSPM と DI-

いて，継続時間と時間間隔を考慮した頻出時系列パターンを抽出

PrefixSPM が実行中に処理したパターンの数の差が小さく，する 2 つのアルゴリズム DI-PrefixSPM と DI-SufPrefixSPM

DI-SufPrefixSPM は DI-PrefixSPM より実行時間が多くかかを提案した．実験を通して，マルチ最小サポートの設定によるることになった．一方，各パターンレベルに対応する最小サポー

が，枝刈りを可能とした DI- SufPrefixSPM は DI-PrefixSPM

ト間の差が 0.03%と 0.05%の場合，マルチ最小サポートによるよりも優れていること，また，包含関係を満たすパターンを考

枝刈りによって，DI-SufPrefixSPM と DI-PrefixSPM が実行

慮することで DI-PrefixSPM と DI-SufPrefixSPM の処理効率中に処理したパターンの数の差が拡大し，DI-SufPrefixSPM のが高まることを示した．

実行時間は DI-PrefixSPM より早くなった．

5. 5 パターン包含関係の影響
パターン包含関係の影響について，包含関係を満たすパター
ンを考慮することなく，全て抽出する場合と包含関係を満たす
パターンの抽出を回避する場合の処理性能の変化を考察する．
データ 1 を使って，各パターンレベルの最小サポート間の差を 0.05%に設定し，最下位レベルの最小サポートを 0.6%から

0.4%まで変化させ，DI-SufPrefixSPM の処理において，包含関係を考慮しない場合の実行時間と処理したパターンの数を図10 に示す．また，DI-PrefixSPM の処理において，包含関係を考慮しない場合の実行時間と処理したパターンの数を図 11 に示す．図 10 と図 11 から，最下位レベルの最小サポートが小さくなるに従って，DI-SufPrefixSPM と DI-PrefixSPM において，包含関係を考慮しない場合処理したパターンの数が包含関係を考慮した場合処理したパターンの数より大幅に増加し，実行時間に大きな影響を与えたことが分かった．

6. お わ り に本研究では，イベントの継続時間と時間間隔情報を考慮した
時系列パターンを抽出するアルゴリズムを検討した．継続時間と時間間隔を離散化してアイテムにするときに，時間を適切に分割することが困難であることを考慮し，継続時間と時間間隔をそれぞれ階層に分割した．また，階層を持つデータに対してはレベ

文

献[1] R.Srikant, R.Agrawal, Mining Sequential Patterns: Generalization and Performance Improvements , Extending
Database Technology, pp.3-17, 1996.
[2] J.Han, J.Pei, B. Mortazavi-Asl., Q. Chen, U. Dayal, and M.C. Hsu, FreeSpan: frequent pattern-projected sequential
pattern mining , ACM SIGKDD Conference on Knowledge
Discovery and Data, pp.355-359, 2000.
[3] J.Han, M.Kamber, Data mining: concepts and techniques , Second Eedition, Morgan Kaufmann, 2006.
[4] H.Mannila, H.Toivonen, A.I.Verkamo, Discovery of frequent episodes in event sequences , Data Mining andKnowledge Discovery, pp.259-289, 1997.
[5] Y.L.Chen, M.C.Chiang, and M.T. Ko., Discovering Timeinterval Sequential Patterns in Sequence Databases , Expert Systems with Applications, pp.343―354, 2003.
[6] Y.H.Hu, F.Wu, and C.I. Yang, Mining Multi-level Timeinterval Sequential Patterns in Sequence Databases , Software Engineering and Data Mining, pp.23-25, 2010.
[7] M.C.Tseng, W.Y.Lin, Eﬃcient mining of generalized association rules with non-uniform minimum support , Data
and Knowledge Engineering, pp.41-64, 2007.
[8] MacQueen, J.B., Some methods for classification andanalysis of multivariate observations , Proceedings of the
Symposium on Mathematics and Probability, 5th, Berkely,
pp.281―297, 1967.
[9] R.Agrawal and R.Srikant, Mining sequential patterns ,Research Report RJ 9910, IBM AI-maden Research Center, San Jose, California, 1994.