DEIM Forum 2013 E1-2

確率的なイベントストリームに対するイベントパターン問合せ加藤翔†

石川 佳治†,†††

名古屋大学大学院情報科学研究科††
国立情報学研究所
E-mail: kato@db.itc.nagoya-u.ac.jp, y-ishikawa@nagoya-u.jp
あらましストリーム形式で大量に発生するイベントの中から，パターン問合せなどの技術を用いてより高次のイベントを検出しようとする複合イベント処理（CEP）に注目が集まっている．本研究では特に，各イベントに生起確率が付与された確率的イベントストリームに対する CEP に着目する．本研究は，与えられた正規表現のパターンに対し，ひとまとまりの意味をなす問合せ結果の集合を得るための，二つのパターン問合せのセマンティクスを提案する．
キーワード

確率的イベントストリーム，複合イベント処理（CEP）
は，「時刻 1 において部屋 A に 60 %，廊下 B に 40% の確率

1. は じ め にで存在」といった形の存在確率の情報が含まれる [5], [6]．この

今日では，センサ機器が広く普及しており，様々な環境下においてセンサから得られたデータを取得できるため，これらのようなデータも，先の行動認識の例と同様，確率的イベントス
トリームとして表現することができる．

センサデータの有効活用が重要となってきている．たとえば，

本研究では，確率的イベントストリームの中から，ある特定ユビキタスコンピューティングや医療情報処理の分野において，のイベントパターンを問い合わせる問題を考える．ストリー

センシングに基づいて人々の行動状況をモニタリングしようとム形式のデータに対するパターン問合せは，データストリーいう試みが盛んに進められている [1]〜[3]．しかし，センサデー

ムに関する研究や，近年話題となっている複合イベント処理

タにはノイズが含まれることがあり，そのようなセンサデータ（complex event processing, CEP）[7] における基盤技術となっから人々の行動を適切に推定することは容易ではない．また，ている [8]．たとえば，図 1 に示したデータにおいて，「歩いてセンサデータにノイズが含まれていなくても，似た動きであるいた人が，しばらく腰かけた後で立ち上がった」というイベが異なる行動を区別することは困難なことがある．これらは，

ントパターンを問い合わせたいとする．このような問合せはセンサデータから人々の行動を認識した結果には曖昧性が存在

walk sit+ stand という正規表現で記述できるが，この問合せすることを意味する．行動認識の結果は，たとえば「時刻 1 か

結果はら 10 まで徒歩，11 から 25 まで階段を上る，25 から 40 まで停止」といったように，時間と検出された行動のセットで一般には与えられるが，認識結果の曖昧性が適切には表現できていない．そこで，このような行動認識結果を確率的イベントスト
リーム（probabilistic event stream）として表現することが考

時刻 1〜4 において walk, sit, sit, stand と行動した
確率：70% × 20% × 70% × 80% = 7.84%
時刻 2〜4 において walk, sit, stand と行動した
確率：80% × 70% × 80% = 44.8%

えられる．たとえば，行動認識プログラムが図 1 のように各時となり，重複した時間帯において複数のマッチが発生する．確

点ごとに確率が付与された行動データを出力することが考え

率的イベントストリームに対するイベントパターン問合せに関られる．より多くの情報が含まれていることから，このようなする既存研究 [5], [6] では，マッチしたものを確率の高い順に報データを用いた次のステップにおいてより質の高い判断を行う

告するなどのアプローチがとられる．しかし，これらの複数のことが可能となりうる．

マッチは，いずれもこの時間帯にパターンに合致した行動が発時刻 1： walk 70%，sit 20%，car 10%

生したことを表しており，個々を区別することは必ずしも重要

時刻 2： walk 80%，sit 20%

ではない．むしろ，これらの問合せ結果を総合的に判断して，

時刻 3： sit 70%，stand 30%

この時間帯に該当する行動があったと判断する方が妥当である

時刻 4： stand 80%, bicycle 20%
.
.
..
..

と考えられる．

図 1 行動認識の例

他の例として，RFID タグを用いたユーザ追跡の例を挙げる．
たとえばワシントン大の RFID Ecosystem プロジェクト [4] では，ユーザに RFID タグを付与して行動モニタリングを行っている．部屋や廊下などに RFID タグリーダを設置しておき，ユーザの位置を推定しデータベース化する．その出力の一部に

このような考え方から，本稿では与えられた問合せパターンに対する複数のマッチを統合し，ひとまとまりの問合せ結果とする手法を提案する．得られた問合せ結果は，それ自体ユーザに提示されることもあれば，次の段階としてデータマイニング
等のさらに高次の処理に渡されることもありうる．後者の場合
は，イベントパターン問合せは，必要な情報を抽出する一種のフィルタリングシステムとして働くことになる．本稿では複数

のマッチングのセマンティクスを提案し，それらの処理方式に

ta

ついて，特にデータストリーム処理の観点から議論する．

1

0.9 0.12

0.2 0.83

1.0

4

0.4 0.6

2. 確率的イベントストリーム
本研究で対象とする確率的イベントストリームを以下のよう

b5に定義する．
図2［定義 1］ 確率的イベントストリーム（probabilistic event se-cd

0.4 0.6

確率的イベントストリームの例（その 1）

quence）S は，
S = e1 , e2 , . . . , et , . . .

(1)と与えられる無限の系列である．

et = {et1 , et2 , . . . , et|V | }(2)

は，時刻 t におけるイベント集合（event set）であり，各 eti ∈ etをイベント（event）と呼ぶ．V はイベント値のドメインであ図 3 単純照合の例

り，離散的であるとする．各イベント eti には生起確率 Pr(eti )が付与されているとし，|V |∑れたとする．これは，イベント a が発生した後，b というイベントが 1 回以上発生し，c というイベントが発生したというパPr(eti ) = 1

ターンを表現している．ここで図 2 に示されるような確率的イ(3)

ベントストリームが与えられたとする．時刻 t = 1 から t = 5i=12が成り立つとする．

以下の例では，表記を簡略化するため，V の要素を a, b, . . . とまでの各時刻にイベントが発生し，それぞれに対して表に示す
ような生起確率が付与されているとする．

いうアルファベットで表す．また，イベント集合を表す際には，

単純にパターン問合せを行うと，次のような四つの問合せ結生起確率が 0 である値は省略して，et = {a, c, d} のように示果が得られる（注 1）．図 3 にこれらを図示する．個々の問合せ結すことにする．

果のことを，本研究ではマッチ（match）と呼ぶ．

先の定義にあるように，本研究では，以下のような想定を行っている．
（ 1 ） イベントの値は離散的なドメイン V からとられる．
（ 2 ） 単位時間ごとにイベント集合が得られる：イベントの欠落は考えない．また，発生したイベントが発生順には到達し

m1=⟨(1, a), (2, b), (3, b), (4, c)⟩(0.432)

m2=⟨(1, a), (2, b), (3, b), (4, b), (5, c)⟩(0.1152)m3=⟨(2, a), (3, b), (4, c)⟩(0.12)

m4=⟨(2, a), (3, b), (4, b), (5, c)⟩(0.032)ない，いわゆるアウトオブオーダー（out of order）型のイベ

たとえば m1 は，t = 1, 2, 3, 4 においてそれぞれ a, b, b, c にントストリームは考えない．なお，ここでは「単位時間」といマッチしたことを意味している．マッチ m に対応する時区間

う用語を用いたが，実際には一定時間きざみである必要はなく， （time segment）を ts(m) で表す．たとえば ts(m1 ) = [1, 4]となる．また，マッチ m の開始時刻，終了時刻を，それぞれイベント集合間の前後関係が明確に決まればよい．
（ 3 ） ある時点におけるイベント値の発生確率を足すと 1 にstart ts(m), end ts(m) で表す．マッチ m の時刻 t におけるエなる：状況によっては，未知の値のイベントを考慮したいこと

ントリを m[t] で表し，時刻 t におけるイベントおよび確率を′もある．その場合には，V = V ∪ {⊥} という，未知の値 ⊥ で′拡張したドメイン V を考えればよいので，本質的な問題ではない．

m[t].ev, m[t].pr で表す．
マッチ に 対 す る 確 率 を 計 算 す る こ と が で き る ．そ の マッ
チがどの程度の確率で合致したかを表すことから，マッチ（ 4 ） 時刻 t におけるイベントの生起確率 Pr(eti ) (i =の一致確率（match probability）と呼ぶ．上に示したマッチ

1, . . . , |V |) は，他の時刻におけるイベントの生起確率とは独立

結果の右端の括弧内の数値がこれを表しており，たとえばしている：すなわち，Markovian Streams [5], [6] に見られるよPr(m1 ) = 0.9 × 0.8 × 1.0 × 0.6 = 0.432 と計算される．以うな，イベントの生起が時間的な相関を持つような状況は考え

上より，パターン p = ab+ c に対する問合せ 結果として，ていない．

{m1 : 0.432, m2 : 0.1152, m3 : 0.12, m4 : 0.032} という四以上のとおり，確率が付与されており，同じ時刻にいくつかのつのマッチからなる集合を返すというのが一つの考え方である．

値が同時に発生しうることを除けば，単純なイベントストリー

このような問合せ結果を，本研究では単純照合（simple match）

ムを想定している．

と呼ぶことにする．

3. 確率的イベントストリームに対するパターン
マッチング
3. 1 パターンマッチングの例
単純な正規表現のパターン p = ab+ c が問合せとして与えら（注 1）：イベントストリームに対するパターン問合せでは，たとえば a, f, b, . . .
というイベント系列に ab というパターンのマッチを許したい場合がある．すな
わち，パターンに出現しない文字（ここでは f）をスキップするというものである．本稿では簡単のため，このようなスキップを許さない処理を想定する．このような問合せ戦略は [8] では strict contiguity と呼ばれている．

［定義 2］ 確 率 的 イ ベ ン ト ス ト リ ー ム S に パ タ ー ン p

4. 2 グループの確率が 与 え ら れ た と き の 単 純 照 合 に 基 づ く マッチ の 集 合 を ，

ここで問題となるのが，完全オーバラップに基づいて得られsimple match(S, p) で表す．

2

3. 2 単純照合の問題点

るグループ M についてどのように確率を付与するかである．
問合せ結果として意味をなすように確率を与えたい．

単純照合の考え方は分かりやすいものであり，ユーザがそのここで図 3 に示したマッチの例を見直してみると，単純照合

ような問合せ結果を望んでいる場合も十分考えられるので，基の経路にオーバラップがあることがわかる．たとえば m1 と本となるパターン問合せのセマンティクスである．しかし，たm2 には，時刻 t = 2, 3 においてはいずれも b が対応している．

とえば行動追跡において，ユーザがひとまとまりの行動を取得

行動認識のコンテクストで説明すると，複数のマッチが同じ時するためにパターン問合せを行う状況を考えると，単純照合の刻に同じ行動を共有していることになる．そのため，単純照合アプローチは必ずしも適切ではない．図 2 において，イベント

におけるマッチの一致確率を単純に足し合わせるのは合理的で

a, b, c を行動とみなすと，時刻 t = 1 付近では a，t = 3 付近

ない．

では b，t = 5 付近では c が発生していることが分かる．すな

図を見ると，モニタリングの対象者は，時刻 t = 1 では

わち，図に示されている確率的イベントストリームは実際には

a という行動をとり（確率 0.9），t = 2 では a または b

ひとまとまりの行動を表しているが，単純照合ではこれをまとという行動をとり（両者の確率を足すと 1），t = 3 では b

まったものとして抽出できないことがわかる．

という行動をとり（確率 1），t = 4 では b または c とい

そこで本稿では，確率的イベントストリームに対する複数のう行動をとり（両者の確率を足すと 1），t = 5 では c とパターン問合せのセマンティクスを示し，それらの処理方式にいう行動をとっている（確率 0.4）．そこで本研究では，こついて述べる．ユーザは，処理の要求に応じて適切なセマンの場合のグループ M = {m1 , m2 , m3 , m4 } に対する確率を0.9 × (0.2 + 0.8) × 1.0 × (0.4 + 0.6) × 0.4 = 0.36 と与える．

ティクスを選択することになる．

この確率は，直観的には，与えられたパターン p = ab+ c がこ

4. パターン問合せのセマンティクスの確率的イベントストリームにおいてどの程度成立しているか

以下で定義するパターン問合せのセマンティクスは，いずれを表しており，パターンに対するグループの一致確率と考えるもひとまとまりのイベント系列をどのように取り出すかということができる．確率が 1 となるのは，その確率的イベントスト

考え方に基づいている．どのようにまとまりを構成するかで異リームが与えられたパターンにすべて合致した場合で，逆に 0なるセマンティクスが得られる．

となるのはまったく合致しなかった場合である．この点で，確率的にも意味をなす．

4. 1 完全オーバラップ
完全オーバラップを次のように定義する．
［定義 3］ M ⊂= simple match(S, p) を単純照合によるマッチの部分集合とする．M が完全オーバラップ（complete overlap）

以上の議論をもとに一致確率を以下のように定義する．
［定義 4］ グループ M の一致確率（match probability）をの性質を有するとは，M が∀m, m′ ∈ M such that m =| m′ , ts overlap(m, m′ )∏Pr(M ) =∑e[t].pr(8)t ∈ ts(M ) e∈{m[t].ev|m∈M }(4)を満たす極大な集合（任意の simple match(S, p) の要素を追加した場合に上の式が満たされなくなる）である場合をいう．ここで ts overlap(m, m′ ) は m と m′ の時区間（ts(m) と ts(m′ )）に交わりがあるときに真になる述語である．M に対応する時区間を，M に含まれるマッチについて最大の時区間をとることで2と定義する．

ただし，e[t].pr は，時刻 t におけるイベント e の確率の値を表すとする．たとえば，図 2 においては a[1].pr = 0.9 である．

4. 3 部分オーバラップ
完全オーバラップのセマンティクスにより，与えられたパターンに対し関連するひとまとまりの問合せ結果をグループという形でまとめることが可能となる．しかし，完全オーバラッ

start ts(M ) = min{start ts(m) | m ∈ M }(5)プのグループ M において任意の二つの要素が必ずオーバラッ

end ts(M ) = max{end ts(m) | m ∈ M }(6)

プしなければならないという制約は，状況によっては強すぎることがある．例として，図 4 について，先と同様に ab+ c といにより，ts(M ) = [start ts(M ), end ts(M )]と定義する．

うパターン問合せを考える．単純照合の結果は(7)2

完全オーバラップのセマンティクスを用いると，確率的イベ
ントストリームから，それぞれ完全オーバラップの性質を持つ

m1=⟨(1, a), (2, b), (3, c)⟩m2=⟨(1, a), (2, b), (3, b), (4, c)⟩m3=⟨(2, a), (3, b), (4, c)⟩m4=⟨(4, a), (5, b), (6, c)⟩

ような 0 個以上複数個のマッチの集合が得られる．たとえば，と な る ．完 全 オ ー バ ラップ の セ マ ン ティク ス に 基 づ け ば ，

先の例に示した確率的イベントストリームについては，完全M = {m1 , m2 , m3 } および M ′ = {m2 , m3 , m4 } が得られ

オーバラップであるマッチの集合 {m1 , m2 , m3 , m4 } がただ一る．m1 と m4 の時区間がオーバラップしていないため別々のつ得られる．その対応する時区間は [1, 5] である．本研究では，

グループとなる．完全オーバラップは，相互に関連が強いといこのようにして提案の照合セマンティクスで得られるマッチのう点で一つの意味があるが，M, M ′ のように重複する要素を含

集合を グループ（group）と呼ぶことにする．

む複数の結果を返してしまうことがある．

t

a

t

a

1

0.9 0.1

1

1.0

2

0.2 0.82

0.1 0.9

3

c

d

b

c

0.7 0.33

0.2 0.8

0.2

4

0.8 0.1 0.1

0.1

5

1.0

0.1 0.7 0.2

6

4

0.8

5

0.1 0.86
図4b

確率的イベントストリームの例（その 2）

図5

そこで，制約を大幅に緩めた部分オーバラップを導入する．
［定義 5］ M ⊂= simple match(S, p) を単純照合によるマッチの部分集合とする．M が部分オーバラップ（partial overlap）のm3

性質を有するとは，M がm4∀m ∈ M, ∃m′ ∈ M such that m =| m′ , ts overlap(m, m′ )(9)を満たす極大な集合である場合をいう．M に対応する時区間を完全オーバラップの場合と同様に定義する．

2

部分オーバラップのセマンティクスでは，先の例の場合，

M = {m1 , m2 , m3 , m4 } という一つのグループが得られる．部
分オーバラップでは，問合せ結果のグループの個数が完全オー
バラップに比べ同等以下になるので，問合せ結果を絞り込んで提示することができるという利点もある．
完全オーバラップと部分オーバラップのどちらのセマンティ
クスを採用するかは，対象とするアプリケーションやユーザの意向に依存する．場合によっては，同じ確率的イベントスト
リームに二つのセマンティクスを同時に適用し，その問合せ結果を比較することも考えられる．

5. 確率の閾値の導入
確率的イベントストリームを対象としたパターン問合せでは，生起確率が十分大きいもののみを検出したいという要求が大きいと考えられる．そのため，確率に対する閾値を導入する．
第一に，グループに対する閾値を設定することが考えられる．
この閾値を問合せ閾値（query threshold）と呼ぶ．たとえば，

4. 1 に示した完全オーバラップの例において，閾値を 20%と設

0.8 0.2

確率的イベントストリームの例（その 3）

m1=⟨(1, a), (2, b), (3, c)⟩(0.72)

m2=⟨(1, a), (2, b), (3, b), (4, c)⟩(0.018)=⟨(1, a), (2, b), (3, b), (4, b), (5, b), (6, c)⟩(0.0144)=⟨(2, a), (3, b), (4, c)⟩(0.002)m5=⟨(2, a), (3, b), (4, b), (5, b), (6, c)⟩(0.0016)m6=⟨(4, a), (5, b), (6, c)⟩(0.64)という六つのマッチとなる．これを見ると，m1 , m6 の確率は高いのに対し，その間の m2 , m3 , m4 , m5 は確率がかなり小さいことがわかる．つまり，この場合は m1 と m6 が独立したイベント
系列であり，m2 , m3 , m4 , m5 はノイズのため検出されたのかもしれないと考えられる．しかし，部分オーバラップのセマンティ
クスをそのまま用いた場合，M = {m1 , m2 , m3 , m4 , m5 , m6 }が問合せ結果となってしまう．
そこでマッチに対する確率の閾値を設定する．たとえばマッチ閾値を 5%とすると m1 , m6 のみが単純照合の結果となり，部分オーバーラップのセマンティクスの下でも M = {m1 } と

M ′ = {m6 } という分離されたグループが得られる．このように，マッチに対する閾値はノイズの影響を差し引き，グループが過度に連結されてしまうことを防ぐために利用できる．

6. アルゴリズム
6. 1 グループに関するアルゴリズム
アルゴリズムで使用する記号を表 1 にまとめる．グループに関するアルゴリズムは，グループ管理とグループ出力の二つがある．

定することができる．例で述べたとおり，その例ではグループの一致確率は 0.36 であったため，閾値を満たすことから問合d

表 1 アルゴリズム中で使用する記号
記号

意味

ri

アクティブラン

一方，単純照合により得られる個別のマッチに対する閾値を

mj

受理ラン（マッチ）設定することも考えられる．これをマッチ閾値（match thres-

x.ts

x が開始した時刻（x は r もしくは m）

x.te

x が受理された時刻（x は r もしくは m）（注 2）

せ結果が出力されることになる．

hold）と呼ぶ．たとえば，同じく 4. 1 の例においてマッチの閾A

アクティブランの集合（∀ri , ri ∈ A）

M

受理ランの集合（∀mj , mj ∈ M ）

gk

グループ

だし， m4 はどの時刻においても M に含まれる他のマッチ

G

グループの集合（∀gk , gk ∈ G）とオーバラップがあるため，M の時区間や一致確率に変化は

Ak

gk に属するアクティブランの集合

ない．

Mk

gk に属する受理ランの集合

値を 5%とした場合，m4 が閾値を満たさないため，完全オー
バラップに基づくグループは M = {m1 , m2 , m3 } となる．たマッチに対する閾値は，部分オーバラップのセマンティクス
において必要以上にグループが連結してしまうことを抑制するために使用することができる．図 5 の例を用いて説明する．

Xtemp

ラン（r や m）が一時的に格納される集合

tl

連鎖が途切れた時刻

T

連鎖が途切れた時刻の集合（∀tl , tl ∈ T ）この確率的イベントストリームについてパターン ab+ c による問合せの単純照合は，（注 2）：その時点では受理された時刻が不明である r については，現時刻を返す
ことにする．

6. 1. 1 完全オーバラップにおけるグループの管理

Algorithm 2 新規ラン生成時のアルゴリズム (partial)

完全オーバラップにおける，新規ランの生成時およびランの失1: procedure GroupMaintenanceForNewRun(rnew )if G =| ∅ then敗に対するグループ管理のアルゴリズムを述べる．まず，新規ラ2:ンの生成時におけるグループ管理の流れをアルゴリズム 1 に示

3:

す．入力は新規ランである．まず，2 行目にあるように，グルー4:

xtemp ← getN ewest(Ai ∪ Mi )5:

if xtemp .te == rnew .te then

プが一つ以上存在するかどうか調べる．存在しない場合は 16 行目に移る．createN ewGroup({x1 , x2 , . . . , xn }) は，ランの集合{x1 , x2 , . . . , xn } を要素に持つ新しいグループを生成するものでfor all gi ∈ G do

Ai ← Ai ∪ {rnew }

6:

break

7:

end if8:

ある．つまり，グループが一つも存在しない場合は，新規ランの

9:

end forみを要素に持つグループを新たに生成する（2 行目，16 行目）．グ10:

if ∀x ∈ A ∪ M, x.te < rnew .ts then

ループが存在する場合は 3 行目〜14 行目に移る．各グループに対11:

して，以下の操作を行う．なお，getN ewest({x1 , x2 , . . . , xn })12:は，min{xi .te |xi ∈ {x1 , x2 , . . . , xn }} を返す．

13:•

グループに属する受理ラン集合から最も若い受理ランを抽出し（5 行目），その受理ランが受理した時刻と新規ランのcreateN ewGroup({rnew })end ifelse
createN ewGroup({rnew })14:

end if15:

16: end procedure

開始時刻を比較する（6 行目）．もし，新規ランの開始時刻の方が大きい場合は次のグループに移る（7 行目）．等しい場合
もしくは受理ラン集合が空（4 行目）の場合，そのグループの処理においては単純な処理が行われることがほとんどであるとアクティブラン集合に新規ランを加える（10 行目）．

考えられる．

新規ランがどのグループにも加えられることがなかった場合

まず，新規ランの生成時におけるグループ管理の流れをアル（12 行目），13 行目に移り，すべてのアクティブランを要素とゴリズム 2 に示す．入力は新規ランである．まず，2 行目にあする新しいグループを生成する．

るように，グループが一つ以上存在するかどうか調べる．存在

次に，ランの失敗に対するグループ管理についてであるが，しない場合は 14 行目に移り，新規ランのみを要素に持つグルー完全オーバラップにおいては，失敗したランを含むグループかプを新たに生成する．存在する場合は 3 行目〜12 行目に移る．

らそれを取り除くだけである．

各グループに対して，以下の操作を行う．

•

グループに属するラン集合から最も若いランを抽出し（4Algorithm 1 新規ラン生成時のアルゴリズム (complete)行目），そのランが受理した時刻（ランがアクティブランの場

1: procedure GroupMaintenanceForNewRun(rnew )合には現時刻）と新規ランの開始時刻を比較する（6 行目）．も2:
3:

if G =| ∅ thenfor all gi ∈ G do
if Mi =
| ∅ then

4:5:mtemp ← getN ewest(Mi )6:

if mtemp .te < rnew .te thencontinue7:

end if

8:
9:
10:

17:

ループを生成する．
次に，ランの失敗によりランが除去されたグループにおけるグループから除去されるランである．まず，2 行目〜4 行目にif ∀m ∈ M, m.te < rnew .ts then16:

（10 行目），11 行目に移り，新規ランを要素とする新しいグ

Ai ← Ai ∪ {rnew }

12:

15:

新規ランがどのグループにも加えられることがなかった場合

グループ管理をアルゴリズム 3 に示す．入力は，失敗したためend for

14:に加え（6 行目），処理を終える（7 行目）．

end if11:

createN ewGroup(A)13:

し等しければ，新規ランをそのグループのアクティブラン集合

end ifelse
createN ewGroup({rnew })end if

18: end procedure

あるように，各グループに対して，ランが除去されたことでグループに属するランの連鎖が途切れていないか調べる．途切れていない場合，この処理は終了である．途切れていた場合，途切れた時刻の集合を T として 5 行目〜16 行目に移る．途切れた各時刻 ti に対して以下の操作を行う．

•

対象のグループに属する受理ラン集合のうち，途切れた

時刻以前の受理ランをグループの受理ラン集合から除去する（6行目〜11 行目）．除去された受理ラン集合を要素に持つ新しい6. 1. 2 部分オーバラップにおけるグループの管理

グループを生成する（12 行目）．

部分オーバラップにおける，新規ランの生成時およびランの最後に，対象のグループに属する受理ラン集合に除去されずに失敗に対するグループ管理のアルゴリズムを述べる．部分オー

残っている受理ランとすべてのアクティブランを要素に持つ新バラップのセマンティクスでは，グループの総数は基本的に 0〜しいグループを生成し（15 行目），16 行目で対象のグループを1 であり，そのような場合にはグループ管理のアルゴリズムは削除する．

単純である．しかし，ランの失敗によりグループの総数が一時

6. 1. 3 グループの出力

的に二つ以上になる場合が存在する．この場合を考慮するため

グループの出力は，グループに属するアクティブラン集合が以降で述べるアルゴリズムは単純でない部分があるが，実際の空になった場合に，そのグループの時区間がこれまでに出力さAlgorithm 3 ラン除去におけるアルゴリズム (partial)
1: procedure GroupMaintenanceForRemovedRun(rdelete )
2:
3:
4:

5:

for all gk ∈ G do
Remove rdelete from Ak
if ¬(∀x ∈ Mk ∪ Ak , ∃x′′x , ts overlap(x, x′ )) then

∈ Mk ∪ Ak such that x =|for all ti ∈ T dofor all mj ∈ Mk do

6:

if mj .ts < ti then7:

Xtemp ← Xtemp ∪ {mj }8:Remove mj from Mk

9:end if

10:
11:

end for12:

createN ewGroup(Xtemp )Clear Xtemp

13:
14:

end for15:

createN ewGroup(Mk ∪ A)

16:

Delete gk

17:
18:

end ifend for

19: end procedure

図 7 決定的イベントストリーム生成に用いるモデル

ば，先と同じ照合パターンに対して図 6 の右側のような確率的イベントストリームを考える．現時刻を 3，問合せ閾値を 0.2とする．現時刻におけるアクティブランを除いたグループの一致確率は，0.9 × 1.0 × 0.2 = 0.18 である．この時点では問合せ
閾値を下回るが，次の時刻 4 ではアクティブランが受理に達し，グループの一致確率は 0.9 × 1.0 × (0.8 + 0.2) × 0.9 = 0.81 に確定し，問合せ閾値を上回る．そこで，受理ランの時区間のみ
において，グループの一致確率の計算方法を適用して得られる値を 最大一致確率（maximum match probability）とし，問合せ閾値による閾値の比較対象とする．
問合せ閾値による処理の打ち切りは，最大一致確率が問合せ
閾値を下回った場合にそのグループを解消することで行う．

7. 評 価 実 験
図 6 一致確率では不適切な確率的イベントストリームの例

7. 1 使用した確率的イベントストリームれたグループの時区間に包含されていなければ実行される．グ

今回使用する確率的イベントストリームには人工データを用

ループの出力では，グループの一致確率，グループの時区間，いた．本実験では，まず初めに曖昧性のない決定的なイベント

グループに属するマッチ集合をユーザに提示する．

ストリームを生成した．次に，生成した決定的なイベントスト

6. 2 確率の閾値に関するアルゴリズム

リームに擬似的な観測ノイズを与えることで確率的なイベント

6. 2. 1 マッチ閾値による処理の打ち切り

ストリームを生成した．決定的なイベントストリームは図 7 のマッチ閾値による処理の打ち切りは，単純に，入力イベント

ような，遷移先が各時刻において確率的に決定されるモデルにによりランが遷移した際に，その時点でのランの一致確率とよって生成した．擬似的な観測ノイズとは，正しくない観測値

マッチ閾値を比較し，一致確率が閾値を下回った場合にそのラの割合である．本実験では，擬似的な観測ノイズのパラメータ

ンを削除することで処理を打ち切るものである．

として最小値，最大値を与えた．観測ノイズの値は，各時刻に

6. 2. 2 問合せ閾値による処理の打ち切り

おいてその範囲内からランダムに決定される．

マッチ閾値による閾値の比較対象はその時点でのランの一本実験ではノイズが与えられる前のイベントストリームを致確率であるが，問合せ閾値による閾値の比較対象はその時知ることができる．そのため，実験では加工前のイベントスト

点でのグループの一致確率では不適切な場合がある．たとえリームの情報も用いて評価を行った．具体的には，確率的イベ

ば，照合パターン p = ab+ c に対して図 6 の左側のような確

ントストリームの元となった決定的イベントストリームに対し率的イベントストリームを考える．ここで，現時刻を 4，問合て単純照合のセマンティクスで得られるマッチ集合を，検出させ閾値を 0.2 とする．現時刻におけるグループの一致確率は，れるべき 解（solution）であるとし，解に含まれるマッチを 解

0.9 × 1.0 × (0.2 + 0.8) × 0.1 = 0.09 である．この時点では問マッチ（solution match）として評価に用いた．なお，解マッ

合せ閾値を下回っている．しかし，次の時刻 5 では，グループ

チの数は 81 である．実験で用いる人工データのパラメータのに属するアクティブランが失敗することでグループの一致確率

基本情報を表 2 に記す．

は 0.9 × 1.0 × 0.8 = 0.72 に確定し，問合せ閾値を上回る．よって，この時点で処理を打ち切ることは不適切である．
先の例では，アクティブランを除いたグループにおいて現時点の一致確率を問合せ閾値の比較対象とするとうまくいく．しかし，そのような手法も場合によっては不適切である．たとえ

表 2 人工データのパラメータ
イベントの数10000

イベントの種類

4

ノイズの最小値，最大値[0%, 1%]〜[30%, 40%]

8. 実験 1：提案手法の機能（閾値設定なし）

る．図のノイズ 3〜4%の groupT のマッチ数においては，部分オーバラップは平均して完全オーバラップの 8 倍以上である．

まず，提案手法が実際にどのように機能するか調べるため，

これは，ノイズにより部分オーバラップのグループが過度に連閾値を設定せずに実験を行った．提案手法は，確率的イベント

結されたためだと考えられる．部分オーバラップの過度な連結ストリームから意味をなすひとまとまりの結果を出力するこの制御は次の実験 2 で述べる．マッチ数に関して groupT ととが目的である．実験 1 では，決定的イベントストリームか

groupF の間にも差がみられるが，これは解マッチの近くでは

ら確率的イベントストリームを生成する際のノイズの範囲をより多くの重複したマッチが生成される傾向にあることを示し[0, 1], [1, 2], . . . , [3, 4] と最大最小共に 1%ずつ変化させて，四ている．

つの確率的イベントストリームを生成した．本稿の実験では，問合せのイベントパターンとして walk sit+ stand を使用し9. 実験 2：マッチ閾値の設定

た．生成した四つの確率的イベントストリームに対して，完全実験 1 により，提案手法のそれぞれの性質・機能が明らかに

オーバラップと部分オーバラップのそれぞれでイベントパター

なった．また，ノイズの存在下では単純照合による出力結果のン問合せを行った結果を図 8 に示す．左側の縦軸には折れ線グ

多くが間違いであることが分かった．そこで実験 2 では，マッラフが対応し，右側の縦軸には棒グラフが対応する．groupT

チ閾値の設定により，マッチ集合に含まれる間違いの変化を調べた．ノイズ 3〜5%の確率的イベントストリームに対するパターン問合せにおいて，マッチ閾値を変化させたときの結果を図 9 に示す．図の groupF を見ると，マッチ閾値を増やすに(a) 完全オーバラップ

図8(b) 部分オーバラップ

閾値を設定しない場合の提案手法の効果は，出力されたグループ集合のうち，解マッチとオーバラップ
しているグループの集合を表す．解マッチの数は 81 であるため，groupT のグループ数は 81 を上限として正しい結果をど(a) 完全オーバラップ

図9(b) 部分オーバラップ

ノイズ [3,5] 固定でマッチ閾値を変化

れだけ出力したかを表す．groupF は，出力されたグループ集

連れて，間違ったグループの数が下がっていき，マッチ閾値が合のうち，解マッチにオーバラップがないグループの集合を表

5%の時点で完全に 0 になっている．一方で，groupT を見るす．つまり，groupF のグループ数は，間違った結果をどれだけと，解マッチとオーバラップのある正しいグループの数は下が出力したかを表す．図を見ると，どちらのセマンティクスでもることなく最高の数値 81 を保っている．このことから，ノイgroupT のグループ数は常に 81 であり，最高の結果である．一ズの存在下に対してマッチ閾値は有効に働くことが分かった．

方で，groupF のグループ数についてはどちらのセマンティク

このときの groupT のマッチ数を見ると，どちらのセマンティ

スでも groupT の数倍以上ある．これは，閾値を設定しない問

クスでもほぼ 1 であることが分かる．これは，提案手法のひと合せでは，問合せ結果における間違いの割合にノイズが多大なまとめにする機能がほとんど作用していないことを示す．すな

影響を及ぼすことを示している．また，間違った結果を出力しわち，このような時区間の重複するマッチがほとんどない状況ていることは提案手法が原因なのではなく，単純照合におけるでは提案手法は意味を成さない．

結果のマッチ集合にそのようなマッチが含まれていることが原因である．
次に，図の棒グラフについて述べる．groupT のマッチ数は，次に，マッチ閾値の値を固定しノイズを増加させた場合の結果を図 10 に示し，実験 1 と比較することで提案手法に対するマッチ閾値の効果を述べる．実験 1 と大きく異る点は，部分groupT の各グループが平均してどれほどのマッチを含んでいるかを示している．groupF でも同様に，groupF の各グループが平均してどれほどのマッチを含んでいるかを示している．この二つの数値は，ひとつのグループに重複したマッチがどの程度まとめられているかの傾向を見るためのものである．図を見ると，どちらのセマンティクスでもノイズが増えるにつれて，ひとまとめにされるマッチの数が増える傾向にある．これは，単純照合による出力結果においては，ある時区間を対象とした
とき，ノイズが増えるにつれてその時区間内で重複するマッチの数がより多くなることを示す．
完全オーバラップと部分オーバラップでは大きな差がみられ(a) 完全オーバラップ

図 10(b) 部分オーバラップ

マッチ閾値 0.05 固定でノイズを変化オーバラップにおける groupT のグループ数が完全オーバラッ

している．[8] では多くの最適化のアプローチが提案されていプのそれとほぼ同じである点である．部分オーバラップは定義

るが，その一部は本研究にも適用可能と考える．確率的イベン

上どこまでも連鎖が続く可能性がある．その一端が現れたのがトストリームに対するイベントパターン問合せは Markovian

実験 1 である．今回の結果から，そのような連鎖を望まない場

Stream プロジェクト [5], [6] において研究されている．特に時合はマッチ閾値を設定することが有効であることが示された．

間的な相関を持つマルコフ遷移による確率的推移データを対象

実験 2 の最初の実験では間違ったマッチを取り除くにはマッとしている．しかし，彼らの研究では問合せ結果をひとまとまチ閾値が非常に有効であることを示したが，ある程度の大きさのノイズに対しては限界が存在することを以下に示す．ノイズ
を 15〜17%に固定してマッチ閾値を変化させたときの結果を図11 に示す．図 11 を見ると，図 9 と同様に，マッチ閾値の増加りで検出することはできない．

12. ま と め
本稿では，確率的イベントストリームに対するイベントパ
ターン問合せにおいて，ひとまとまりの結果を抽出するための二つのセマンティクスについて述べた．実験では，本手法によって，確率的イベントストリームに対するイベントパターン
問合せからまとまりのある結果を得ることができることを示した．また，各セマンティクスの違いを示した．
今後の課題としては，今回の実験は限られたパターンとデー
タにおいて行なっているため，様々な種類のパターンやデータにおいても実験を行う必要がある．また，本稿ではストリーム的な処理を対象としたが，蓄積された確率的イベントストリー(a) 完全オーバラップ(b) 部分オーバラップ

図 11 ノイズ [15-17] 固定でマッチ閾値を変化に伴って groupF のグループ数が下がっていき，マッチ閾値が13%の時点で完全に 0 になった．また，そのときの groupT のマッチ数を見ると，どちらのセマンティクスでもほぼ 1 であり，提案手法のひとまとめにする機能がほとんど意味をなしていムに遡及的に問合せを行うことも考えられ，履歴ストリームに対する索引を用いること [12] などが考えられる．これについても今後の課題としたい．

謝

辞本研究の経費の一部は内閣府最先端研究開発プロジェクト

ない．しかし一方で，groupT のグループ数は図 9 とは異なり， （FIRST）による．
徐々に下がっていき，マッチ閾値 13%では最高値の 81 から 30下がって 51 である．これは，マッチ閾値による処理の打ち切り
で解マッチとオーバラップするマッチが削除されたことを示している．よって，マッチ閾値を適切な値に設定しても，ある程度大きなノイズの存在下ではマッチ集合に間違いが含まれてしまうことが分かった．すなわち，ノイズが大きければ，出力結果に間違いが含まれることは必然であり避けることはできない．

10. 考

察

提案手法は，ある程度大きな一致確率をもつマッチにオーバラップする小さな一致確率のマッチを如何にまとめることができるかが重要である．しかし，そのようなマッチはマッチ閾値により削除される傾向にあることが分かった．一方で，マッチ閾値を用いないと，解マッチにオーバラップのないノイズのようなマッチが削除されず，部分オーバラップの過度な連鎖を引き起こした．これらのことから，マッチ閾値ではない手法でノイズのようなマッチを削除すべきかもしれない．たとえば，実験 1 の最後で述べたように，解であるべきグループはそうでないグループに比べてマッチの数が平均的に多かったため，グループに含まれるマッチの数の比較から意味を成さないグルー
プを削除できるかもしれない．今後調査が必要である．

11. 関 連 研 究関連研究について簡単に紹介する．イベントストリームに対するパターン問合せについては多くの研究がある．本研究はSASE+ [8] における問合せ処理方式（特に NFAb ）をベースと

文

献[1] HASC (Human Activity Sencing Consortium) ホームページ,
http://www.hasc.jp/.
[2] Y. Hattori and S. Inoue: “A large scale gathering system foractivity data using mobile devices”, Journal of Information
Processing, 20, 1, pp. 177–184 (2012).
[3] 栗原, 福田, 菅原：“センサ情報からの系列パターンマイニング”,
人工知能学会誌, 27, 2, pp. 112–119 (2012).
[4] The RFID Ecosystem, http://rfid.cs.washington.edu/.
[5] J. Letchner, C. Ré, M. Balazinska and M. Philipose: “Challenges for event queries over Markovian streams”, IEEE Internet Computing, 12, 6, pp. 30–36 (2008).
[6] C. Ré, J. Letchner, M. Balazinksa and D. Suciu: “Eventqueries on correlated probabilistic streams”, Proc. ACM
SIGMOD, pp. 715–728 (2008).
[7] G. Cugola and A. Margara: “Processing flows of information: From data stream to complex event processing”, ACM
Comput. Surv., 44, 3 (2012).
[8] J. Agrawal, Y. Diao, D. Gyllstrom and N. Immerman: “Efficient pattern matching over event streams”, Proc. ACM
SIGMOD, pp. 147–159 (2008).
[9] R. Sadri, C. Zaniolo, A. Zarkesh and J. Adibi: “Optimization of sequence queries in database systems”, Proc. ACM
PODS, pp. 71–81 (2001).
[10] F. Zemke, A. Witkowski, M. Cherniak and L. Colby: “Pattern matching in sequences of rows”, ANSI Standard Proposal (2007).
[11] エイホ, ラム, セシィ, ウルマン：“コンパイラ [第 2 版]：原理・技法・ツール”, サイエンス社 (2009).
[12] J. Letchner, C. Ré, M. Balazinska and M. Philipose:“Access methods for Markovian streams”, Proc. ICDE, pp.
246–257 (2009).