DEIM Forum 2019 H1-4

イベント系列からの有意なエピソードの効率良いマイニング
谷

陽太†

平田

耕一††

有村

博紀†

† 北海道大学大学院 情報科学研究科 〒 060–0814 札幌市北区北 14 条西 9 丁目†† 九州工業大学大学院 情報工学研究院 〒 820–8502 福岡県飯塚市大字川津 680-4
E-mail: †{tani,arim}@ist.hokudai.ac.jp, ††hirata@ai.kyutech.ac.jp
あらまし

本稿では，統計的有意なエピソードのイベント系列からのマイニング問題を扱う．ここで，エピソードとは，複数のイベント間の出現に関する半順序関係を表す時系列パターンである．我々は，エピソードの有意性尺度として，Tatti (DMKD, 2015) が提案した尺度を用いる．Tatti の方法は，エピソードの漸増的成長を考慮していないた
め，列挙されるエピソードごとに始めからオートマトンを構築し，有意性尺度を計算する必要がある．そのため，有意性尺度の計算に多大な時間を要する．そこで，本稿では，直列および，並列，菱形のエピソードからなる部分族のそれぞれに対して，列挙に適した有意性尺度の漸増的計算法を与える．最後に，人工データを用いた計算機実験を行い，提案手法の性能を評価した．
キーワード 列挙, グラフ, 半順序関係, 時系列データ, 統計的有意性, ランキング
るエピソードの部分族におけるランク計算の枠組みを導入する．

1 はじめに
データマイニングの一種である系列マイニングは，系列デー
タから頻出する部分系列を抽出する手法である [1]．一方，Man-

整数 i <= j に対して，[i..j] = {i, i + 1, . . . , j} は i から j までの整数区間を表す．

2. 1 イベント列

nila ら [4] によるエピソードマイニングは，イベント列に同時有限集合 Σ をアルファベットとする．Σ に対して，その要素に出現するイベントの構造であるエピソードのうち，頻出なもe ∈ Σ をイベントといい，Σ の部分集合 W ⊂=Σ をイベント集合のを抽出する手法である．

Tatti [5] は，エピソードの部分クラスである厳密エピソードという．イベント集合 W とイベント e ∈ W に対して，W \ {e}を，簡単のため W − e と表記する．

に対して，ランクの定義を与えている．ランクは，イベント列

Σ 上の長さ m のイベント列とは，S = ⟨s1 , s2 , . . . , sm ⟩ であの集合と厳密エピソードが与えられた場合に，イベント列の集る．ここで，si ∈ Σ はイベントである．イベント列 S, U, X, V

合におけるエピソードの出現確率と，実際のエピソードの出現に対して，S = U XV であるとき，X を S の部分イベン

数から，そのエピソードの有意性を測る指標である．一方で，ト列，U を X の接頭辞 (prefix) ，V を X の接尾辞 (suf-

Tatti [5] は厳密エピソードを列挙する手法は与えていない．

fix) と呼ぶ．イベント列 X の長さ k の接頭辞を prefX (k)Katoh ら [2] は，厳密エピソードの部分クラスである菱形エと表し，X の長さ k の接尾辞を sufX (k) と表す．長さ m のピソードに対して，イベント列からすべての頻出菱形エピソー

イベント列 S = ⟨s1 , s2 , . . . , sm ⟩ に対して，イベント列 Q がドを効率的に抽出するアルゴリズム PolyFreqDmd を提案しQ = ⟨si1 , si2 , . . . , sim ⟩ を満たすとき，Q は S の部分列 (sub-ている．谷ら [6] は，イベント列の集合からすべての頻出菱形

sequence) であるという．ここで，i1 , i2 , . . . , im は，昇順に並エピソードを，Katoh ら [2] の手法にしたがって列挙すると同んだ 0 以上 m 以下の整数列である．Q が S の部分列であること

時に，解となる頻出菱形エピソードのランクを Tatti [5] の手法を Q⊂=に基づいて計算するアルゴリムを与えている．谷ら [6] の手法

seq

S と表記し，Q が S の部分列でないことを Q ⊈seq Sと表記する．

の問題点として，菱形エピソードのサイズに対して，計算時間が指数的に増大する点があげられる．

2. 2 エピソード

本稿では，厳密エピソードの部分クラスである直列エピソー

エ ピ ソ ー ド [4] は ，頂 点 ラ ベ ル つ き 非 巡 回 有 向 グ ラ フドおよび並列エピソード，菱形エピソードそれぞれに対して，

G = (VG , EG , labG ) である．ここに，VG は頂点集合，EG

イベント列の集合から頻出するものを効率的に抽出するアルゴ

は辺集合，labG はラベル関数 labG : VG → Σ である．エピソー

リズムを提案する．最後に，人工的に生成したイベント列に対ドは，出現の半順序関係が定義されたイベントの多重集合とみして，本稿の手法と谷ら [6] の手法を適用し，アルゴリズムのなせる．

性能を比較した．

エピソード G がイベント列 S = ⟨s1 , . . . , sn ⟩ に出現することを S ⪰ G で表し，次の条件を満たす関数（マッチング関数と2 準備

本節では，Tatti [5] にしたがって，厳密エピソードと呼ばれ呼ぶ） f : VG → [1..n] が存在することと定める：(i) f は一対一である: (∀u, v ∈ VG ) f (u) = f (v) ⇒ u = v; (ii) f は順序

を保存する: (∀u, v ∈ VG ) (u, v) ∈ EG ⇒ f (u) < f (v); (iii)である．このとき，G の期待支持度は µ =∑S∈S p|S| となる．

f は頂点ラベルを保存する: (∀v ∈ VG ) labG (v) = sf (v) . このイベント列の集合 S に対して，|Xi | = |Si |(1 <=i<= |S|) ととき，イベント列 S はエピソード G をカバーするともいう．

なるようなランダムなイベント列の集合 X を考える．非負整イベント列の集合 S 上で，エピソード G をカバーするイベント列の集合を CS (G) = { S ∈ S | S ⪰ G } と書く．このとき，Gの観測支持度（単に支持度とも呼ぶ）を sup(G | S) = |CS (G)|数n>
= 0 に対して sup(G | X ) = n となる確率は，
T ⊂S S∈T

∏

p|S|

=

と定義する．さらに，エピソード G と最小頻度 α > 0 に対して，sup(G | S) >= α となるとき，G は頻出であるという．本稿∑ ∏p(sup(G | X ) = n | X ∼ q) =(1 − p|S| )S∈S\T|T |=nでは，C の添字 S は自明な場合省略する．

で あ る ．こ の 値 は n が 十 分 に 大 き い と き ，平 均 µ で 分 散∑
σ 2 = S∈S p|S| (1 − p|S| ) の正規分布 N (µ, σ) から推定できる．

2. 3 エピソードの部分族

以降，この値を求める場合，正規分布から推定することとする．

すべての要素間に順序関係が定義されている場合，そのエピ
ソードは直列であるという [4]．いかなる要素間にも順序関係が定義されていない場合，そのエピソードは並列であるという．

Tatti [5] は，イベント列の集合 S とイベント列生成モデル q
において，エピソード G の有意度ランク (単にランクとも呼ぶ) を次のように定義している．

イベントの集合 E とイベント a, b に対して，a 7→ E 7→ b を菱定義 2 (有意度ランク [5]). イベント列の集合 S とイベント列

形エピソード [2] という．これは，E 中のすべてのイベントは生成モデル q において，エピソード G のランクとは，

a の後，b の前に出現することを意味する．以降，a と b を先頭()
r(G | S ∼ q) = − log p sup(G | X ) >=n|X∼qと末尾と呼び，E を本体と呼ぶ．単に a 7→ b で，b が a の後に

n−1
(
∑ (
))
= − log 1 −p sup(G | X ) = k | X ∼ q

出現することを表す．
一般に与えられたイベント列 S とエピソード G に対して，
カバー S ⪰ G の判定は NP 困難である [5]．この困難性は主にマッチング関数の一対一性に起因する．そのため，Tatti [5] は，次の厳密エピソードを導入した．1

k=1

である．

2. 5 エピソードからの有限オートマトンの構築
Tatti [5] は，イベント列がエピソード G をカバーするかを，

定義 1 (厳密 [5]). エピソード G = (VG , EG , labG ) が厳密有限オートマトンを用いて判定する方法を提案している．さらで あ る と は ，任 意 の 異 な る 頂 点 u と v ∈ VG に 対 し て ，に，この有限オートマトンをカバー確率と G のランクの計算にlabG (u) = labG (v) ならば，u から v への有向パス，またはも用いる．

v から u への有向パスが存在することをいう．
Tatti [5] の定義では，エピソードの DAG の推移閉包を考え

オートマトンを構築するに際し，Tatti [5] は次の接頭辞部分
グラフを導入した．

て，二頂点が同じラベルをもつならば両者をつなぐ有向辺があ定義 3 (接頭辞部分グラフ [5]). エピソード G = (V, E) に対しることと定義している．これは本稿の定義と同値である．

て，部分エピソード H = (W, F ) が G の接頭辞部分グラフで上記の直列エピソードと菱形エピソードは，いずれも厳密エ
ピソードである．2 並列エピソードは，同じラベルを持つイベあるとは，次の条件 1 および 2 を満たすことをいう．

ントが存在しない場合に限り，厳密エピソードである．以後，

v ∈ W かつ (w, v) ∈ E ならば w ∈ W(1)

本稿では，厳密エピソードであるもののみを，並列エピソードv, w ∈ W かつ (v, w) ∈ E ならば (v, w) ∈ F(2)として扱う．

G の接頭辞部分グラフ全体の集合を P re(G) で表す．

2. 4 エピソードのカバー確率とランク

例として，G = a 7→ {b, c} 7→ d のとき，P re(G) は次の通り

本稿では，イベント列のランダム生成モデルとして，イベン
トの生起確率のベクトル q = (qe )e∈Σ ∈ [0, 1]|Σ| で定められる∑
記憶のない情報源を仮定する．ここに， e qe = 1 である．
エピソード G とイベント列生成モデル q に対して，G のカバー確率とは，q にしたがって生成された長さ k のランダムなイベント列 X が G をカバーする確率

pk = p(G | q, k) = p(X ⪰ G | |X| = k, X ∼ q)である．

P re(G) = {∅, a, a 7→ b, a 7→ c, a 7→ {b, c}, a 7→ {b, c} 7→ d}
ここで，∅ は頂点数 0 のエピソードである．
エピソード G = (V, E, lab) に対して，次のように G の有限オートマトン A(G) = (P re(G), Σ, δ, H0 , Hf ) を構築する [5]．
（ 1 ） 状態集合は，すべての接頭辞部分グラフのなす集合

P re(G) である．初期状態は空な頂点集合の誘導するグラフ
H0 = (∅, ∅, ∅) とし，受理状態は Hf = G である．
（ 2 ） 状態 H1 , H2 ∈ P re(G) に対し，H2 から頂点を 1 つ

1：Katoh と Hirata [3] は，Tatti [5] と独立に厳密エピソードの族を提案し，線形エピソードによるそれらの特徴付けを与えている．

取り除くことで H1 が導かれる場合，遷移関係 δ ⊂=P re(G) ×

2：菱形エピソード a 7→ E 7→ b は，定義より本体 E が集合であり，同じ要素

Σ × P re(G) は，取り除いた頂点のラベル e ∈ Σ をもつ辺を重複して含まないため，厳密エピソードとなる．

(H1 , e, H2 ) をもつ．

Algorithm 1 CalcProbStrict(A = (P re, Σ, δ, Ho , Hf ), q =Algorithm 2 RankedSeries(S, q, Σ, α)(qe )e∈Σ , n)Input: イベント列の集合 S,
イベント列の生起確率のベクトル q,

Input: 有限オートマトン A,

アルファベット Σ,
最小頻度 0 < α <= |S|.

イベント列の生起確率のベクトル q,
非負整数 n.

p(H0 , 0) 以外の p(H, i) := 0（i := 0 → n）

Output: 頻出直列エピソードとそのランク.
1: Σ0 := 頻出するイベントの集合 (Σ0 ⊂Σ);=
2: for all ( a ∈ Σ0 ) do

for all i := 1 → n do

3:

G0 := (a);for all H ∈ P re do

Output: pk (k = 1, . . . , n) の列.
p(H0 , 0) := 1;//カバーされるイベント系列集合

4:

C0 := CS (G0 );p(H, i) := 1;

5:

P0 := maxS∈C |S| × maxS∈C |S| の単位行列

for all d ∈ δ such that d(f, e) = H do

6:

RecRankedSeries(G0 , C0 , P0 , S, q, Σ0 , α);p(H, i) := p(H, i) − qe ;7: end forend forp(H, i) := p(H, i) × p(H, i − 1);

Algorithm 3 RecRankedSeries(G, C, P, S, q, Σ, α)for all d ∈ δ such that d(H, e) = f do

Output: 直列エピソード G を先頭とする頻出直列エピソードすべて

p(H, i) := p(H, i) + qe × p(f, i − 1);の集合.
1: if ( |C| >= α ) thenend for2:

P ′ := CaclProbSeries(G, P, maxS∈C |S|, q)

end for3:

output ⟨G, G のランク ⟩;output ⟨p(Hf , 1), . . . , p(Hf , n)⟩;4:

for all ( e ∈ Σ) do

5:G′ := G 7→ {e};end for6:（ 3 ） 各状態 H ∈ P ref (G) と任意の e ∈ Σ に対して，e がC ′ := CC (G′ );7:

RecRankedSeries(G′ , C ′ , P ′ , S, q, Σ, α)

H から出るいかなる有向辺にもラベルとして出現しない場合，

8:

ラベル e をもつ自己ループ辺 (H, e, H) を追加する．

9: end if//カバーされるイベント系列集合

end for以上の手順で構築した有限オートマトン A(G) の領域は，Gのサイズの指数関数である．Tatti [5] は，次の補題を示した．
補題 1. 任意のイベント系列 S と，任意のエピソード G，その有限オートマトン A(G) に対して，S がエピソード G をカバーすることと，A(G) が S を受理することは同値である．
補題 2. G が厳密エピソードならば，その有限オートマトン

A(G) は決定性有限オートマトンである．

有限オートマトン A(G) において，q から生成された長さ k のランダムイベント列にしたがい，A(G) を初期状態から遷移した結果の状態が H ∈ P re(G) である確率を p(H, k) とする．このとき，p(H, k) は以下の式で求められる [5]．

∑(p(H, k) = 1 −)(qe ) p(H, k − 1)

(H,e,F )∈δ

2. 6 厳密エピソードのカバー確率の計算+

Tatti [5] は，2. 5 節で導入した有限オートマトンを用いて，与えられた G と，各文字の生起確率 q, 正整数 k >= 0 に対して，∑(qe )p(F, k − 1)

(F,e,H)∈δ

カバー確率 pk は p(Hf , k) となる．この値は，動的計画法を独立生成モデルにおける長さ k のランダム文字列による G の

用いて O(v 2 k) 時間で計算できる．ここに，v = |P re(G)| であ

カバー確率を効率良く計算する方法を与えている．

る．Algorithm 1 に，カバー確率 pk の列 (k = 1, . . . , n) を計

ア ル ゴ リ ズ ム の 入 力 は ，イ ベ ン ト 列 の 集 合 S∗={S1 , . . . , S|S| }⊂=Σ である． A(G) = (P re(G), Σ, δ, H0 , Hf )算するアルゴリズム CalcProbStrict を示す．

3の構成より，イベント列 S が A(G) に受理されるならば，かつその場合に限り，S は G をカバーする．よって，イベント列の集合 S において，A(G) に受理される S ∈ S の数が G の観測支持度となる．また，長さ k のイベント列が A(G) の受理状態に到達できる確率を求めることで，カバー確率 pk が計算できる．
イベント列の生起確率のベクトル q = (qe )e∈Σ ∈ [0, 1]|Σ| と3 直列エピソードに対するアルゴリズム
本節では，イベント列の集合からすべての頻出直列エピソードとそのランクを重複なく出力するアルゴリズム RankedSeriesを示す．S をイベント列の集合とし，α > 0 を最小頻度とする．

3. 1 アルゴリズムの流れ
Algorithm 2 に ア ル ゴ リ ズ ム RankedSeries を 示 す．
RankedSeries は，はじめに初期エピソードを計算した後，再3：Mannila ら [4] は，1 つのイベント系列 S と正整数 k を入力とし，長さ kの滑り窓モデルでのエピソード発見を議論している．Mannila らの枠組みは，S

帰関数 RecRankedSeries を呼び出す．Algorithm 3 に，ア

中の長さ k のすべての部分文字列からなる系列集合を考えることで，本稿の枠組

ルゴリズム RecRankedSeries を示す．RecRankedSeries

みで扱える．

は，初期エピソードから開始して，自身を再帰的に呼び出しなAlgorithm 4 CalcProbSeries(G, PG′ , n, q = (qe )e∈Σ )Input: 直列エピソード G,
PG′ の表,3. 4 カバー確率の計算
CalcProbSeries では，カバー確率 PG (k, t) の表を計算する．与えられたエピソード G が直列エピソードであるとき，

イベント列の生起確率のベクトル q,
非負整数 n.

Output: 表 PG .

2. 5 節で導入した有限オートマトンを用いずに，与えられた Gと，各文字の生起確率 q, 正整数 k >= 0 に対して，独立生成モ

G′ := G の末尾一文字を削ったエピソード

デルにおける長さ k のランダム文字列による G のカバー確率

e := G の末尾一文字を漸増的に計算することができる．

PG の各要素 := 0
for all k := 1 → n do
for all t := 0 → n do
if j = 0 thenq := 1for all i := 0 → k − 1 do

イベント列 Y と整数 k に対し，長さ k のイベント列で，Y を部分列として含むものの集合を Q(Y, k) = {X | X ∈Σk , Y ⊂=seqX} と す る ．イ ベ ン ト 列 X の 接 頭 辞 の 集 合 をρ(X) = {prefX (i) | i ∈ {1, . . . , |X|}} とする．イベント列 X, Y
に対し，Y を部分列として含む X の接頭辞の中で，もっとも短PG (k, t) := PG (k, t) + PG′ (k − 1, i) ∗ q ∗ (qe )いものの長さを spl(X, Y ) = min{ |Q| | Q ∈ ρ(X), Y ⊂=q := q ∗ (1 − qe )とする．イベント列 Y と整数 k, m に対し，Q(Y, k) の要素で，end for
else

seq

Q}

かつ，Y を部分列として含む自身の最初の接頭辞の長さが m−kであるものの集合を Qtail (Y, k, m) とする．すなわち，PG (k, t) := PG (k − 1, t − 1)
end if

Qtail (Y, k, m) = {X | X ∈ Q(Y, k), spl(X, Y ) = k − m}end forend forで あ る ．イ ベ ン ト 列 Y と イ ベ ン ト σ ，整 数 k, m に 対 し ，output PG

Qtail (Y, k, m) の要素で，かつ，自身の長さ m の接尾辞に σを含まないものの集合を Qtf (Y, k, m, σ) とする．すなわち，がら，深さ優先探索により，初期解を拡大して得られるすべて

Qtf (Y, k, m, σ) = {X | X ∈ Qtail (Y, k, m), ⟨σ⟩ ⊈seq sufX (m)}の直列エピソードを重複なく生成する．再帰の各繰り返しで，

RecRankedSeries は受け取った本体のサイズが m の直列エピソード (親エピソード) を拡張して，サイズ m + 1 の直列エピソード (子エピソード) を生成する．その後，観測支持度を求め，対応する表 PG を構築する．これを用いてランクを計算である．
補題 3. Σ をアルファベットとし，Y を Σ 上のイベント列，σをイベントとする．さらに，q をイベント列生成モデル，k, tを整数とする．このとき，する．

3. 2 初期エピソードの計算

∑ (
(
) k−1
)
P Qtail (Y σ, k, 0) =P Qtf (Y, k − 1, t, σ) qσ
t=0

アルゴリズム RankedSeries は，はじめに最もサイズの小さい解として，すべてのイベント a ∈ Σ に対して，単エピソーが成り立つ．

ド Ga = (a) を生成する．さらに，Ga と，Ga をカバーするイ

Proof. 定義より，Qtail (Y σ, k, 0) の要素 X は，末尾が σ でベント列の集合 C = C(Ga )，および Ga から構築した表 PGa

あ り，さ ら に X の 長 さ k − 1 の 接 頭 辞 prefX (k − 1) は((
) )Qtf Y, k − 1, k − 1 − spl prefX (k − 1), Y , σ の要素であ()
る．ここで，spl prefX (k − 1), Y は 0 から k − 1 の整数値でを引数とし，再帰関数 RecRankedSeries を呼び出す．

3. 3 エピソードの更新
RecRankedSeries では，親エピソード G の末尾に新しいイベントを追加して，すべて直列エピソードを深さ優先探索する．親である直列エピソード G が与えられたとき，任意のイベ
ント e ∈ Σ に対して，エピソード G の末尾に e を加えて得られる直列エピソード G′ = (G 7→ e) を子エピソードとして生成する．
その後，CalcProbSeries を用いて，G′ のカバー確率を計
算し，G′ のランクを求める．
以上の手続きを再帰的に繰り返すことで，任意の最小頻度 αに対して，アルゴリズム RankedSeries は，イベント列の集
合 S から頻出直列エピソードとそのランクを重複なく出力する．

あるため，Qtail (Y σ, k, 0) の要素は，整数 t (0 <=t<
= k − 1)の各値について，次の条件を満たす k 個の集合に分割できる：(i) 自身の長さ k − 1 の接頭辞が Qtf (Y, k − 1, t, σ) の要素; (ii)
自身の末尾のイベントが σ. ここで，分割した各集合の確率は

P (Qtf (Y, k − 1, t, σ))qσ で求まるため，補題 3 が成立する．
また，Qtf (Y, k, t, σ) と Qtail (Y, k, t) の定義より，以下が導かれる．
補題 4. Σ をアルファベットとし，Y を Σ 上のイベント列，σ をイベントとする．さらに，q をイベント列生成モデル，k, t を整数と()()
する．このとき，P Qtf (Y, k, t, σ) = P Qtail (Y, k, t) (1−qσ )tが成り立つ．

補題 5. Σ をアルファベットとし，Y を Σ 上のイベント列とす

Algorithm 5 RankedParallel(S, q, Σ, α)る．さらに，q をイベント列生成モデル，k, t を 1 以上の整数と()()
する．このとき，P Qtail (Y, k, t) = P Qtail (Y, k − 1, t − 1)

Input: イベント列の集合 S,
イベント列の生起確率のベクトル q,
アルファベット Σ,
最小頻度 0 < α <= |S|.

が成り立つ．
ここで，直列エピソード G は部分列とみなすことができる

Output: 頻出並列エピソードとそのランク.

ことを用いると，上記の補題は次のように書き換えることがで

1: G0 := ∅;きる．

2: Σ0 := 頻出するイベントの集合 (Σ0 ⊂Σ);=

3: P0 := maxS∈C |S| × maxS∈C |S| の単位行列;

補題 6. 直列エピソード G と整数 k に対して，G をカバーする

4: C0 := CS (G0 );長さ k のイベント列の集合を Q(G, k) = {S | S ∈ Σk , S ⪰ G}

5: r0 := G0 のランク;と す る ．直 列 エ ピ ソ ー ド G と 整 数 k, t に 対 し て ，Q(G, k)

6: Q := 待ち行列;の要素であり，G をカバーする自身の最短の接頭辞の長さが k − t であるイベント列の集合を Q(G, k, t) = {S | S ∈7: Q.push(⟨G0 , P0 , C0 , r0 ⟩);8: while Q is not empty do
9:Q(G, k), maxprefS (k−i)⪰G i = t} とする．このとき，イベント⟨G, P, C, r⟩ := Q.pop();

10:

列の生起確率のベクトル q = (qe )e∈Σ ∈ [0, 1]|Σ| と，直列エピ

output ⟨G, r⟩;11:

for all ( e ∈ Σ0 (e > max(G)) ) do

ソード G = G′ 7→ e において，q から生成された長さ k のラン

12:

ダムイベント列 X が Q(G, k, t) の要素である確率 PG (k, t) は，13:以下の式で求められる．
k−1(
)
∑



PG′ (k − 1, i)(1 − qe )i (qe )PG (k, t) = i=0P (k − 1, t − 1)

14:

G

t=0
other

′

直 列 エ ピ ソ ー ド G の 長 さ k に お け る カ バ ー 確 率 pk は∑k
i=0 PG (k, i) となる．

G′ := G ∪ {e};C ′ := CC (G′ );if |C ′ | >= α then15:

P := (PG′ \{σ} )σ∈G ;16:P ′ := CaclProbParallel(G′ , P, q, maxS∈C |S|);

17:

r′ := G′ のランク;

18:

Q.push(⟨G′ , P ′ , C ′ , r′ ⟩);19:

end if

20:

end forPG (k) :=21: end while

4 並列エピソードに対するアルゴリズム

Algorithm 6 CalcProbParallel(G, P = (PG\{σ} )σ∈G , q =(qe )e∈Σ , n)

本節では，イベント列の集合からすべての頻出並列エピソー

Input: 並列エピソード G,

ドとそのランクを重複なく出力するアルゴリズム RankedPar-

各 σ ∈ G に対する PG\{σ} のベクトル P,

allel を示す．S をイベント列の集合とし，α > 0 を最小頻度

イベント列の生起確率のベクトル q,とする．

非負整数 n.

Output: 表 PG .

4. 1 アルゴリズムの流れ
Algorithm 5 に ア ル ゴ リ ズ ム RankedParallel を 示 す．
RankedParallel は，空エピソードから開始して，幅優先探索により，初期解を拡大して得られるすべての並列エピソー
ドを重複なく生成する．幅優先探索の各繰り返しで，Ranked-

Parallel は受け取った本体のサイズが m の菱形エピソード（親エピソード）を拡張して，サイズ m + 1 の並列エピソード（子エピソード）を生成する．その後，観測支持度を求め，対応する表オートマトン PG を構築する．これを用いてランクを計算する．

PG の各要素 := 0
for all k := 1 → n do
for all m := 0 → n do
PG (k, m) := PG (k − 1, m) ∗ qG + PG (k − 1, m − 1) ∗ (1 − qG )q := 1for all σ ∈ G do
G′ := G \ {σ}PG (k, m) := PG (k, m) + PG′ (k, m) ∗ q ∗ (qσ )end for() ()
q := q ∗ 1 − qG / 1 − qG′
end forend for4. 2 初期エピソードの計算

output PG

アルゴリズム RankedParallel は，はじめに最もサイズの小さい解として，すべてのイベント a ∈ Σ に対して，最小の並

親である並列エピソード G が与えられとき，e > max(E) と列エピソード Ga = (a) を生成する．

なる任意のイベント e ∈ Σ に対して，エピソード G に e を加

4. 3 エピソードの更新
RankedParallel では，親エピソード G の末尾に新しいイベントを追加して，すべて並列エピソードを幅優先探索する．

えて得られる並列エピソード G′ = (G ∪ e) を子エピソードとして生成する．
その後，CalcProbParallel を用いて，G′ のカバー確率を計算し，G′ のランクを求める．

目に出現するもの. ここで，X ∈ RW size (k ′ , W, m) について，以上の手続きを繰り返すことで，任意の最小頻度 α に対し|X|W と |prefX (k′ − 1)|W の関係は，以下のようになる．

て，アルゴリズム RankedParallel は，イベント列の集合 S′|prefX (k − 1)|W
から頻出並列エピソードとそのランクを重複なく出力する．

|X|W =

4. 4 カバー確率の計算
CalcProbParallel では，カバー確率 PG (k, t) の表を計′

|prefX (k − 1)|W + 1|prefX (k′ − 1)|W

(i)
(ii)
(iii)

算する．与えられたエピソード G が並列エピソードであると()
確率の公理より，P RW size (W, k ′ , m) は，RW size (W, k ′ , m)

き，2. 5 節で導入した有限オートマトンを用いずに，与えられの分割である各事象の発生確率の総和で求まるため，補題 7 がた G と，各イベントの生起確率 q, 正整数 k >= 0 に対して，独
立生成モデルにおける長さ k のランダム文字列による G のカ成り立つ．

バー確率を漸増的に計算することができる．

W の補集合 Σ \ W とする．さらに，q をイベント列生成モデ

イベントの集合 W ⊂=Σ と，各イベントの正規確率 q に対し，∑
qW = σ∈W qσ とする．イベント集合 W と整数 k に対し，長さ k のイベント列で，かつ W の要素全てが 1 回以上出現してい[るものの集合を R(W, k) = {X | ∀σ ∈ W ∃i ∈ {1, . . . , k}[σ =]xi ] } とする．R(W, k) の要素でかつ σ を含まないイベント

補題 8. Σ をアルファベットとし，W を Σ の部分集合，W をル，σ を W の要素，m を非負整数とする．このとき，()) qW − qσ m()(
P Rf s (W, k, σ, m) = P RW size (W, k, m)qWが成り立つ．

列 の 集 合 を Rf orbid (W, k, σ) = {X | X ∈ R(W, k), ∀i ∈Proof. Rf s (W, k, σ, m) は ，各 ⟨σ1 , · · · , σm ⟩ ∈ (W − σ)m{1, . . . , k}[σ =| xi ]} とし，R(W, k) の要素でかつ W に含まに つ い て ，次 の |W − σ|m 個 の 集 合 に 分 割 で き る：

れるイベントが合計 k − m 回出現しているイベント列の集合を

Sf s (W, k, m, σ1 , · · · , σm ) = {X | X ∈ RW size (W, k, m), σ1 =RW size (W, k, m) = {X | X ∈ R(W, k), |{i | xi ∈ Σ \ W }| =xn1 , . . . , σm = xnm }, n1 , . . . , nm ∈ {n | xn ∈ W }, n1 <()· · · < nm . この分割に基づくと，P Rf s (W, k, σ, m) は，各m} とする．Rf orbid (W, k, σ) の要素でかつ RW size (W, k, m)の要素であるものを，Rf s (W, k, σ, m) = Rf orbid (W, k, σ) ∩P (Sf s (W, k, m, σ1 , · · · , σm )) の総和で求められるため，補題 8

RW size (W, k, m) とする．

が成り立つ．

補題 7. Σ をアルファベットとし，W を Σ の部分集合，W を

ここで，並列エピソード G はイベント集合とみなすことがW の補集合 Σ \ W とする．さらに，q をイベント列生成モデ

できることを用いると，上記の補題は次のように書き換えるこル，σ を W の要素，k と m を非負整数とする．このとき，とができる．

()()
P RW size (W, k, m) = P RW size (W, k − 1, m) qW()+ P RW size (W, k − 1, m − 1) qW∑ ()+
P Rf s (W − σ, k − 1, σ, m) qσ
σ∈W

長さ k のイベント列の集合を S(G, k) = {S | S ∈ Σk , S ⪰ G}とする．並列エピソード G と整数 k, t に対して，S(G, k) の要素であり，自身に含まれる G の要素の数が k − m であるイベ
ント列の集合を S(G, k, m) = {S | S ∈ S(G, k), |{n | sn ∈が成り立つ．

Σ \ G}| = m} とする．このとき，イベント列の生起確率のベク

Proof. まず，k = 1 のときを考える．
()
P RW size (W, 0, m) = 0
1)(
P RW size (W, 0, m − 1) =0

補題 9. 並列エピソード G と整数 k に対して，G をカバーする

トル q = (qe )e∈Σ ∈ [0, 1]|Σ| と並列エピソード G において，qから生成された長さ k のランダムイベント列 X が S(G, k, m)の要素である確率 PG (k, m) は，以下の式で求められる．

|W | = 0 and m = 1

PG (k, m) = PG (k − 1, m)qG()
+ PG (k − 1, m − 1) 1 − qG()m∑
1 − qG+
PG\{σ} (k, m)(qσ )1 − qG\{σ}
σ∈G

other

(
)
P Rf s (W − σ, 0, σ, m) = 0

であるため成立．
次に，k = k ′ − 1 で成立していると仮定し，k = k ′ のときを考える．RW size (W, k ′ , m) は，以下の集合に分割できる：(i)長さ k ′ − 1 の接頭辞に，W の要素全てが 1 回以上出現し，か並 列 エ ピ ソ ー ド G の 長 さ k に お け る カ バ ー 確 率 pk は ，∑PG (k) := ki=0 PG (k, i) となる．

5 菱形エピソードに対するアルゴリズム

つ k ′ 文字目が W の要素であるもの; (ii) 長さ k ′ − 1 の接頭辞

本節では，イベント列の集合からすべての頻出菱形エピソーに，W の要素全てが 1 回以上出現し，かつ k ′ 文字目が W のドとそのランクを重複なく出力するアルゴリズム RankedDi-

要素であるもの; (iii) 長さ k ′ − 1 の接頭辞に，W の要素のうち出現していない文字が 1 種類だけあり，その文字が k ′ 文字

amond を示す．S をイベント列の集合とし，α > 0 を最小頻度とする．

Algorithm 7 RankedDiamond(S, q, Σ, α)Algorithm 8 CalcProb(G, P

Input: イベント列の集合 S,(qe )e∈Σ , n)

イベント列の生起確率のベクトル q,=(PG\{σ} )σ∈G , q

Input: 菱形エピソードの末尾を取り除いたエピソード G,

アルファベット Σ,
最小頻度 0 < α <= |S|.

各 σ ∈ G に対する PG\{σ} のベクトル P,
イベント列の生起確率のベクトル q,

Output: 頻出菱形エピソードとそのランク.
1: Σ0 := 頻出するイベントの集合 (Σ0 ⊂Σ);=
2: P0 := maxS∈C |S| × maxS∈C |S| の単位行列;
3: for all a ∈ Σ0 do

非負整数 n.
′ の組.
Output: 表 PG と表 PG

PG の各要素 := 0
′ の各要素 := 0
PG

4:

Q := 待ち行列;

5:

Ga := (a);6:

⟨Pa , Pa′ ⟩ := CalcProb(G, ⟨P0 ⟩, maxS∈C |S|, q);7:

Ca := CS (Ga );q := 18:

ra := Ga のランク;

for all σ ∈ G do

9:output ⟨Ga , ra ⟩;G′ := G \ {σ}10:

for all b ∈ Σ0 do

PG (k, m) := PG (k, m) + PG′ (k, m) ∗ q ∗ (qσ )11:

Gab := (a 7→ b);

12:

Cab := CCa (Gab );if |Cab | >= α then13:

for all k := 1 → n do
for all m := 0 → n do
PG (k, m) := PG (k − 1, m)qG + PG (k − 1, m − 1)(1 − qG )′ (k, 0) := P ′ (k, 0) + P ′ (k, m) ∗ q ∗ (q )
PG
σ
G
G

end forfor all t := 1 → n do

14:

Pab := CalcProbSer(Gab , Pa , maxS∈C |S|, q);15:

rab := Gab のランク;

16:

Q.push(⟨Gab , Pa′ , Cab , rab ⟩);17:

while Q is not empty do′ (k, t) := P ′ (k − 1, t − 1)PG
G

end forq := q ∗ (1 − qG )/(1 − qG′ )end for18:⟨G = (a 7→ E 7→ b), P, C, r⟩ := Q.pop();end for19:

output ⟨G, r⟩;20:

for all ( e ∈ Σ0 (e > max(G)) ) do

′ ⟩output ⟨PG , PG

21:

G∗ := (a 7→ (E ∪ {e}));22:G′ := (a 7→ (E ∪ {e}) 7→ b);

り返し，カバー確率を計算する．

C ′ := CC (G′ );if |C ′ | >= α then

5. 2 アルゴリズムの流れ

23:
24:
25:

P = (PG′ \{σ} )σ∈G ;26:⟨P ′ , P ′′ ⟩ := CalcProb(G27:r′ := G′ のランク;28:

Q ← ⟨G′ , P ′ , C ′ , r′ ⟩;29:

end if

30:

end for31:

end while=

Algorithm 7 にアルゴリズム RankedDiamond の概要を示∗ , P, q, maxS∈C |S|);

す．RankedDiamond は，はじめに初期エピソードを計算した後，幅優先探索により，初期解を拡大して得られるすべての菱形エピソードを重複なく生成する．幅優先探索の各繰り返し
で，RankedDiamond は受け取った本体のサイズが m の菱形エピソード (親エピソード) を拡張して，サイズ m + 1 の菱形

32:

end ifエピソード (子エピソード) を生成する．その後，観測支持度33:

end forを求め，対応する表オートマトン PG を構築する．これを用いてランクを計算する．

34: end for5. 3 初期エピソードの計算
5. 1 概要アルゴリズム RankedDiamond は，はじめにサイズ 2 の直列エピソード (初期エピソード) を構築し，その 2 つの頂点を始点と終点とする．その後，このエピソードを菱形エピソードとみなし，本体に 1 つずつイベントを追加してエピソードを拡張していく．
アルゴリズム RankedDiamond は，アルゴリズム Ranked-

Series とアルゴリズム RankedParallel の考え方に基づいて，カバー確率の計算の効率化をおこなう．菱形エピソードアルゴリズム RankedDiamond は，はじめに最もサイズの小さい解として，すべてのイベント a ∈ Σ に対して，最小の菱形エピソード Ga = (a) を生成する．
アルゴリズム RankedDiamond は，はじめに最もサイズの小さい解として，すべてのイベントの組 (a, b) ∈ Σ に対して，最小の菱形エピソード Gab = (a 7→ ∅ 7→ b) を生成する．さらに，Gab と，Gab をカバーするイベント列の集合 C = C(Gab )，および Gab から構築した表 P (Gab ) を用いて，ランクを計算する．

G = a 7→ E 7→ b は，G∗ = a 7→ E と b の直列連結であるとみなし，G∗ に対して並列エピソードのアルゴリズムを適用して

5. 4 エピソードの更新

エピソードを拡張する．その後，直列エピソードのアルゴリズ

基本的なアイディアとして，親エピソード G に新しいイベムを適用して，b を再び直列連結する．これを各ステップで繰

ントを追加して，サイズが一つ大きな子エピソードを生成する

(エピソードの拡張)．しかし，このときに単に本体に新しいイベントを追加するだけでは，同じエピソードを異なる経路で複数回生成してしまうことになる．

BodyRankedDiamond で は ，親 で あ る 菱 形 エ ピ ソ ー ド
G = (a 7→ E 7→ b) が与えられとき，e > max(E) となる
任意のイベント e ∈ Σ に対して，本体 E に e を加えて得られる菱形エピソード G′ = (a 7→ (E ∪ {e}) 7→ b) を子エピソード
として生成する．

ンドで計測した．

6. 3 結果

表 1 に，イベント列集合のサイズにおけるアルゴリズム

RankedDiamond および MineRankedDmd の実行時間の平均と，出力解の個数を示す．ここで，|S| は入力データセットのサイズ，Outputs は出力解の個数である．表 1 より，Ranked-

Diamond は，MineRankedDmd に対して高速に動作することがわかる．

5. 5 ランクの計算
Algorithm 8 に ，カ バ ー 確 率 の 表 を 計 算 す る ア ル ゴ リ ズ

表 1 RankedDiamond および MineRankedDmd の実行時間

ム CalcProb を 示 す．CalcProb で は ，菱 形 エ ピ ソ ー ド|S| Outputs MineRankedDmd RankedDiamond

G = (a 7→ E 7→ b) に対し，末尾を取り除いたエピソード

200

20

0.826s

0.866sG∗ = (a 7→ E) を考える．菱形エピソード G は，G∗ の末尾に

400

279

8.668s

0.889s600

441

14.959s1.174sイベント b を直列連結したものとみなすことができる．子エピ()
ソード G′ = a 7→ (E ∪ {e}) 7→ b は，エピソード G∗ 中の E

800

626

16.084s

1.309s1000

1001

18.779s

1.646sに対してイベント e を並列に加え，その後末尾にイベント b を

1200

2330

49.291s

1.834s

直列に加えたものとみなすことができる．すなわち，G∗ に対

1400

5459

150.301s

2.348sしては，直列的なエピソードの拡張と，並列的なエピソードの

1600

8300

252.256s

2.861s拡張の両方が行われるため，それぞれに対応した確率の表を生

1800

9177

297.357s

3.233s

成する．

2000

9625

298.229s

3.495s

以上の手続きを繰り返すことで，任意の最小頻度 α に対して，アルゴリズム RankedDiamond は，イベント列の集合 S
から頻出菱形エピソードとそのランクを重複なく出力する．

6 実

験

7 おわりに本稿では，厳密エピソードの部分クラスである直列エピソー
ドおよび並列エピソード，菱形エピソードのそれぞれに対して，

本節では，5 節で提案したアルゴリズム RankedDiamond

イベント列の集合から頻出するものを効率的に抽出するアルゴと，谷ら [6] のアルゴリズム MineRankedDmd の比較実験のリズムを提案し，各アルゴリズムにおけるカバー確率の計算方

結果を示す．

法の正当性を示した．

6. 1 デ ー タ
データとして，次のようにランダム生成したイベント列集合を用いた．イベント列集合のサイズ |S| を 200 から 2000

今後の課題として，一般のエピソードに対する拡張があげられる．本稿の手法は，エピソードの更新が直列的または並列的であることを利用している．そのため，直並列グラフのような構造を持つエピソードに対する拡張が期待される．

まで 200 ずつ変化させた 10 種類のデータセットを生成した．
アルファベットはサイズ 20 の Σ = {a, b, . . . t} であり，イベ
ント列のサイズは |Si | = 20（i = 1, . . . , |S|）である．さらに，生成したイベント列の約 5% の割合で，菱形エピソード

Ga{bcd}e = a 7→ {b, c, d} 7→ e を，長さ 5 の部分イベント列として意図的に埋め込んだ．菱形エピソード Ga{bcd}e が埋め込まれた部分以外のイベントは，Σ から一様ランダムに生成した．

6. 2 方法5 節で提案したアルゴリズム RankedDiamond を C++言語で実装し，各データセットに適用した．さらに，同様のデータ
を谷ら [6] の手法に適用し，結果を比較した最小頻度は α = 100とした．アルゴリズムが仮定するイベント列の生成モデルは，
入力データセット上の各イベントの出現割合を用いた．
実行環境として，PC(Intel Core i5 2.9GHz, 8GB memory,

MacOSX 10.11.6) と g++コンパイラ (Apple LLVM ver8.0.0)を用いた．実験は 5 回繰り返して行い，計算時間を time コマ

文献[1] Rakesh Agrawal, Ramakrishnan Srikant. “Mining sequential
patterns.” Proc. 11th ICDE, 3-14, 1995.
[2] Takashi Katoh, Hiroki Arimura, Kouichi Hirata. “A
Polynomial-Delay Polynomial-Space Algorithm for Extracting Frequent Diamond Episodes from Event Sequences.”
PAKDD 2009: 172-183[3] Katoh, Takashi, and Kouichi Hirata. “A simple characterization on serially constructible episodes.” Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer,
Berlin, Heidelberg, 2008.
[4] Heikki Mannila, Hannu Toivonen, A. Inkeri Verkamo. “Discovery of Frequent Episodes in Event Sequences.” Data Min.
Knowl. Discov. 1(3): 259-289 (1997)[5] Nikolaj Tatti. “Ranking episodes using a partition model.”Data Min. Knowl. Discov. 29(5): 1312-1342 (2015)[6] 谷陽太, 古谷勇, 平田耕一, 有村博紀. (2018). “イベント系列からの有意性を考慮した菱形エピソードマイニング.” In 人工知能学会全国大会論文集 2018 年度人工知能学会全国大会 (第 32 回)
論文集 (pp. 4Pin127-4Pin127). 一般社団法人 人工知能学会.