DEIM Forum 2017 G3-1

複数ストリーム環境における Top-k 共起パターンマイニング
天方 大地†

原隆浩†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{amagata.daichi,hara}@ist.osaka-u.ac.jp
あらまし

ビッグデータおよび IoT 時代における様々なアプリケーションでは，オブジェクトはストリーム形式で発生している．ストリームから重要なパターンをリアルタイムにマイニングする技術は，そのようなアプリケーション
において必要不可欠である．本稿では，複数のストリームに現れるオブジェクト集合をモニタリングする問題に取り組む．具体的には，あるオブジェクト集合は，その集合が現れるストリームの数によってランキングされ，その上位

k 個のものをモニタリングする．この問題を正確かつ効率的に解くため，グラフと転置ファイルを組み合わせたデー
タ構造である CP-Graph，および CP-Graph を利用したアルゴリズムを提案する．CP-Graph は，与えられたパターン
がどれだけのストリームに現れるかを効率的に計算し，正解集合に含まれないパターンを枝刈りしながら解を更新できる．実データを用いた実験により，提案アルゴリズムの有効性およびスケーラビリティを確認する．
キーワード

ストリーム，共起パターン，マイニング

1. は じ め に現れる共起パターンをモニタリングする問題も考えられる [12]．
この問題も上で挙げたアプリケーションに適応できる．しかし，パターンマイニングは，多くのドメインにおける基本的な問

ユーザにとって ρ を指定することは難しく，適切な ρ を事前に題であり，市場分析 [10]，クリックストリーム [8]，ネットワー

知ることは非現実的である [8]．例えば，ρ が小さいと解のサイ

クモニタリング [5] などの幅広いアプリケーションに用いられズが大きすぎる可能性があり，ρ が大きいと解のサイズが 0 とている．ビッグデータおよび IoT 時代における様々なアプリなる可能性がある．一方，k を指定することにより，ユーザはケーションでは，オブジェクトはストリーム形式で発生してお希望の数，かつ最も共起しているパターンをモニタリングできり，ストリーム環境におけるパターンマイニング問題に関するる．それにも関わらず，本問題はこれまでに研究されていない．

研究は盛んに行われている．本稿では，複数のストリームが存課題．複数ストリームにおける排他的共起パターンマイニング

在する環境を想定し，Top-k 共起パターンマイニング問題に取問題は，以下の事実によりチャレンジングである．

り組む．

（1）リアルタイム性．例 1 に表されるように，本問題のアプリ研究動機．複数のストリーム（S1 , S2 , ..., S|S| ）が継続的にトラケーションはリアルタイム性が要求される．本問題に対する単

ンザクション（オブジェクトの集合）を生成し，それらはスライ

純な解法は，トランザクションが発生・消滅した時，全てのパ

ディングウィンドウによって管理されているとする．ここで，Pターンの µ を計算し，ソートにより上位 k 個の排他的共起パをオブジェクトの集合（パターン）とし，P が現れたストリー

ターンを抽出することである．しかし，パターンの数は指数的′ムの数を µ(P ) とする．µ(P ) >= 2 である（かつ µ(P ) = µ(P )′となる P ⊃ P が存在しない）場合，P を（排他的）共起パター（2）動的な µ と閾値．あるパターン P の µ（µ(P )）は，トラン（注 1） と呼ぶ．µ が最大である k 個の（排他的）共起パターン

ンザクションの発生および消滅により変化する．そのため，現をモニタリングする問題も幅広いアプリケーションを持つ．

時点で共起パターンでない，または排他的でないパターンも将例 1．ソーシャルネットワークサービス（SNS）の各ユーザは，

来的に排他的共起パターンになる可能性がある．同時に，現時一つのストリームと見なせる．例えばある Twitter ユーザのツ点で解に含まれる排他的共起パターンも，µ が小さくなることに増える [7] ため，この解法は現実的でない．

イートは，継続的に発生が起きるストリームである．多くのにより解に含まれなくなる可能性がある．

ユーザのツイートに同じキーワードが現れる場合，そのキー（3）効率的な枝刈りのためのデータ構造の必要性．上の 2 つ

ワードを共起パターンと見なせる．つまり，本問題を解くことの課題から，不必要なパターンの枝刈り，および与えられたパにより，新出した話題のリアルタイムな発見が可能となる． ■ターンの µ を効率的に計算するためのデータ構造が必要である．

Web ページの遷移パターンや e コマースでの購買パターンのマ
イニングも例 1 と同様に本問題のアプリケーションとして挙げられる．
ここで，ユーザが閾値 ρ を与えた時，ρ 以上のストリームで既存のデータ構造は，静的データ [13] や単一のストリーム [7]のみ考慮しているため，適用可能でない．さらに，閾値以上の共起パターンをモニタリングする問題に対するデータ構造 [12]も，本問題に対しては効率的でない．本問題では閾値（上位 k
番目の µ）が事前に知り得ないため，既存アルゴリズムの単純な適用方法は，ρ = 2 とすることである．これは，全てのパター（注 1）：(closed) co-occurrence pattern

ンを列挙する単純な解法と同義であり，非現実的である．

表 1 トランザクション集合

提案アルゴリズムの概要．リアルタイム性を満たすために最トランザクション ストリーム

初に解決すべき課題は，与えられたパターンの µ を高速に計算することである．これを実現するため，新たなデータ構造である CP-Graph を提案する．CP-Graph は，トランザクション中のオブジェクト集合をグラフで管理し，効率的にパターンを表現する．例えば，あるパターン {oi , oj } が存在する場合，oi お
よび oj は頂点（vi および vj ）と見なされ，その間には辺が存在する．さらに，各頂点 vj は転置ファイルを保持する．この転置ファイルは，oj を含むパターンの µ の上界値，および正確な値を計算するために用いられる．CP-Graph の利点として，µ({oi , ..., oj }) は，vj の転置ファイルをチェックするだけで得られる点が挙げられる．
次に解決すべき問題は，新たに解に含まれるパターンを効率的に検索することである．本問題における閾値は動的に変化するため，スライディングウィンドウ上で管理しているトランザ

オブジェクト集合

生成時刻

t1

S1

{oa , ob , ox , oy }

c′

t2

S2

{od , ox , oy }

c′

t3

S3

{oa , oc , od , ox , oy }

c′

t4

S4

{oa , ob , od , oy }c′

本稿では，ストリームデータの管理モデルとして，スライ
ディングウィンドウ [2] を用いる．ここで，w をウィンドウサ
イズとすると，w は管理する最新のデータ数（例えば 1,000,000個のデータをウィンドウに含める），または時間の長さ（例えば現在時刻から 2 時間以内に発生したデータをウィンドウに含める）として定義される．さらに，∆ をスライドサイズとする．

w がデータ数を表す場合，∆ は定数であり，w が時間の長さを表す場合，∆ = 1 [time-unit] である．本稿の提案アルゴリズム
はどちらのモデルにも適用可能であるため，以降の説明では w
は時間の長さとし，cnow を現在時刻とする．

クションが更新された場合，閾値を推定し，無駄な検索を削減

問題定義．k ，w，および S が与えられたとする．本問題は，µする必要がある．この閾値の推定，および解の更新を CP-Graphが最大となる k 個の排他的共起パターンをモニタリングするこを用いて効率的に実行する．実データを用いた実験により，提とである．

案アルゴリズムの有効性およびスケーラビリティを確認する．

例 2．スライディングウィンドウ上で管理されているデータを表 1

本稿の構成．以下では，2. 章で本稿の問題の定義および性質をに表す．oy は 4 つのストリームで現れているため，µ({oy }) = 4

紹介し，3. 章で関連研究について述べる．4. 章で本稿の提案アである．同様に，µ({ob }) = 2 であるが，µ({ob , oy }) = 2 であルゴリズムについて説明し，5. 章で性能評価のために行った実るため，{ob } は排他的共起パターンでない．k = 3 とすると，

験の結果を紹介する．最後に 6. 章で本稿をまとめる．

cnow における正解集合は，{oy }，{oa , oy }，および {od , oy } である．
（最後の 2 つのパターンについては，{ox , oy } と交換可能

2. 予 備 知 識

である．
）

■

本稿では，複数のストリーム（S1 , S2 , ..., S|S| ）が存在する環

トランザクションは継続的に生成されるため，スライドごと境を想定する．各ストリーム Si は，継続的にトランザクションの解の更新は正確かつ高速であることが求められる．これを実を生成する．あるトランザクション tj は，ストリームの識別子

現するアルゴリズムを設計するため，本問題の性質を紹介する．

とオブジェクト集合のタプルである．例えば，Si が tj を生成

性質 1．スライディングウィンドウ上に現れる全てのパターン

した場合，tj = ⟨i, O⟩ である．ここで，O 内のオブジェクトはを列挙することは，#P 完全である [9]．

辞書順でソートされていると想定する [7]．つまり，oi ∈ O お

しかし，本問題は他のパターンマイニング問題 [1], [6] と同様

よび oj ∈ O が与えられた時，oi ≺ oj である．本問題を定義すに，アプリオリ（apriori）性質を持つ．つまり，2 つのパターるために，本稿で用いるシンボルおよび用語を以下で定義する．

′
ン P および P ′ について，P ⊂ P ′ であれば µ(P ) >= µ(P ) で

定義 1（µ(P )）．P = {op , ..., oq } をオブジェクト集合（パターある．これにより性質 1 を緩和できると同時に，性質 2 が得らン）とすると，µ(P ) = |{Si ∈ S}| である．ここで，S はスト

れる．

リームの集合であり，Si は P を含むトランザクションを生成

性質 2．P を排他的共起パターンとする．P が解に含まれなけしたストリームである．

れば，P の上位集合も解に含まれることはない．

定義 2（共起パターン）．µ(P ) >= 2 であれば，P は共起パター

性質 2 により探索空間を削減できるが，本問題は以下の課題を

ンである．

持つ．

本問題では，closed（排他的）の概念を導入する [3], [11]．P
であれば，P と P ′ を共に出力することは無駄である．なぜな性質 3．P を共起パターンとし，ta = ⟨i, O⟩（P ⊂O）について=考える．(i) 新しいトランザクション tb = ⟨i, O ′ ⟩（P ⊂O′ ）が生=成された場合においても，µ(P ) が増加するとは限らない．(ii)

ら，P が解に含まれていない，かつ P ′ が解に含まれていれば，

ta がウィンドウから除外されても，µ(P ) が減少するとは限ら′′

および P の上位集合 P が与えられたとする．µ(P ) = µ(P )′µ(P ) = µ(P ) と分かるからである．

ない．

定義 3（排他的共起パターン）．P を共起パターンとする．

証明．ページ数の制限により，全ての証明を割愛する．

′

′

′

µ(P ) = µ(P ) かつ P ⊂ P となる P が存在しなければ，P は排他的共起パターンである．

□

性質 4．P1 ，P2 ，...，および Pk を cnow における Top-k 排他
的共起パターンとする．Pi （i ∈ [1, k]）が消滅しない場合や

µ(Pi ) が減少しない場合においても，上位 k 番目の µ（τnow ）ステップ 2（A の更新）．cnow − 1 における解と CP-Graph から，cnow における k 番目に大きい µ（閾値）を推定し，その閾が cnow + 1 において減少する場合がある．

値を用いて A を更新する．

3. 関 連 研 究

4. 1 CP-Graph

静的データやストリームデータに対するパターンマイニング

解を高速に更新するためには，必要な排他的共起パターンの問題は多くの関心を集めており，これまでに多数のアルゴリズ

列挙とその µ の計算を効率的に行う必要がある．CP-Graph は

ムが提案されている．本稿では複数ストリーム環境におけるパ

この要件を満たすようにデザインされており，V と E によりターンマイニングに関する既存研究 [4], [12] に焦点を当てる．

構成されている．V （E ）は，cnow における頂点（辺）集合で

文献 [4] では，H-Stream と呼ばれるアルゴリズムが提案されある．端的に言うと，ウィンドウ上のトランザクションに現れている．しかし，このアルゴリズムは正確な解をモニタリング

る oi は，頂点 vi と見なされ，パターンを表すために辺を作成することを保証していない．文献 [12] では，Seg-tree と呼ばれする．以下に詳細を説明する．

るデータ構造，および CooMine と呼ばれるアルゴリズムを提辺. トランザクション t = ⟨j, O⟩ が与えられた時，以下の 2 つ案している．
（詳細は文献 [12] を参照．
）図 1 は，表 1 におけるの要件を満たすように辺を作成する．

トランザクション集合から構成される Seg-tree を簡潔に示している．トランザクションが与えられた時，最もマッチ数が多い
プレフィックスノードに対して差分のノードを追加し，Seg-treeの各テイル（tail）ノードが，対応するトランザクションを保持する．ユーザが閾値 ρ を与えた時，CooMine は ρ 以上のス
トリームに現れるパターンを，Seg-tree を用いて高速に検索する．CooMine は Top-k モニタリングを考慮しておらず，1. 章で述べた通り，ρ = 2 とすることが単純な適用方法である．また，

CooMine は µ の更新を考慮していないため，本稿の問題を効率的に解決しない．これを 5. 章で明らかにする．

𝑜𝑑

𝑜𝑏

𝑜𝑏

𝑜𝑥

𝑜𝑐

𝑜𝑐

𝑜𝑥

𝑜𝑦

𝑜𝑑

𝑜𝑑

𝑜𝑑

𝑜𝑦

𝑜𝑥

𝑜𝑦

辺が存在する．例えば，{op , or } ⊂ O が排他的パターンである
場合，ep,r が作成される．この要件は，排他的パターンを直接辿り，排他的共起パターンを効率的に列挙するための重要な要件である．
各辺 e は，ラベルの順序付き集合（e.L）を持つ．今，cnow におされる．以降，ep,q と表記する場合は，op ≺ oq とする．
頂点. トランザクション t = ⟨j, O⟩（oq ∈ O）が cnow におい

𝑜𝑦
Tlist

𝑜𝑦

（2）O 中に排他的パターンが存在する場合，対応する頂点間にP = O\P ′ である．各ラベルは，作成時刻順（c）により管理

𝑜𝑎

𝑜𝑦

される．

が ep,q .L に挿入される．P ′ = {∀oq ∈ O | op ≺ oq } とすると，

Hlist
𝑜𝑎

𝑜𝑦

例えば，O = {op , oq , or } であれば，辺 ep,q および eq,r が作成

いて ep,q が作成されると想定する．この時，ラベル ⟨P, j, cnow ⟩根𝑜𝑥（1）O において，順に現れるオブジェクト間に辺が存在する．

𝑜𝑦𝑜𝑦

図 1 表 1 におけるトランザクション集合から構成される Seg-tree

4. 提案アルゴリズム
提案アルゴリズムは，不必要なパターンの枝刈りやインク
リメンタルな解の更新を実現するために，ウィンドウ上のトラ
ンザクションをインメモリ型インデックスで管理する方針をとる．提案するインデックスは，CP-Graph（Co-occurrence Pattern

Graph）と呼ばれ，CP-Graph を利用したアルゴリズムにより解の更新を行う．ここで，A を正解集合とし，A の各要素は，排他的共起パターンとその µ のタプルである．A の更新アルゴリ
ズムは，ウィンドウの各スライドにおいて，以下のステップを順に行う．

て生成された時，vq ∈/ V であれば vq を作成する．各頂点 vq
は，タプル集合 vq .S ，フラグ vq .f ，および転置ファイル vq .Iを持つ．O に含まれるオブジェクトに対応する頂点に対して，⟨j, cnow ⟩ がそのタプル集合に追加される．
（⟨j, c⟩ ∈ vq .S であれば，c は cnow に置換される．
）vq .S が cnow に更新されれば，−−−−→
vq .f = 1 であり，そうでなければ vq .f = 0 である．⟨P, j, c⟩ を∪⟨P, j, c⟩ ∈ ep,q .L に対するポインタとする．vq .I は， E ep,q .Lに現れる全てのオブジェクトの集合およびポスティングリスト−−−−→
により構成される．各ポスティングリスト vq .I(o) は，⟨P, j, c⟩∪の集合であり，o ∈ P かつ ⟨P, j, c⟩ ∈ E ep,q .L である．
例 3．図 2 は，表 1 のトランザクションに基づく CP-Graph のグラフ構造を示している．そのトランザクション集合では，オブジェ
クト oa ，ob ，oc ，od ，ox ，および oy が現れるため，CP-Graphは頂点 va ，vb ，vc ，vd ，vx ，および vy を持つ．また，t1 により，
辺 ea,b ，eb,x ，および ex,y が生成される．同様に，排他的パターン（例えば {oa , oy }）も辺（ea,y ）が作成されている．次に，各∪辺のラベル集合に焦点を当てる．例えば， E ei,y .L（oi ≺ oy ）に現れるオブジェクトの集合は，{oa , ob , oc , od , ox } である．そのため，vy .I はポスティングリストとして，vy .I(oa )，vy .I(ob )，ステップ 1（インデックスの更新）．新たなトランザクション

vy .I(oc )，vy .I(od )，および vy .I(ox ) を持つ. （vy .I(oa ) によりを CP-Graph に反映させ，ウィンドウから除外されたトランザ

ポインタが管理されているラベルは，太字で示されている．
）■

クションを CP-Graph から取り除く．
（4. 2 節）

たす必要がある．ここで，1 つ目の要件を満たすのは容易である．トランザクション中のオブジェクト集合において，順に現
𝑣𝑎

𝑣𝑏

𝑣𝑥

𝑣𝑦

れるオブジェクト間に辺を作成すれば良い．しかし，この作成方法だけでは 2 つ目の要件を満たせない．{op , or } を排他的パ𝑣𝑐
辺𝑒

ターンとすると，op と or が順に現れるトランザクションが存

𝑣𝑑

在しない可能性がある．例えば，例 2 において {oa , oy } は排他ラベル集合 𝑒. 𝐿

的パターンだが，表 1 のトランザクションにおいて，oy が oa𝑒𝑎,𝑏𝑜𝑎 , 1, 𝑐′ , 𝑜𝑎 , 4, 𝑐 ′𝑒𝑎,𝑐𝑜𝑎 , 3, 𝑐 ′

𝑒𝑎,𝑑

𝑜𝑎

, 4, 𝑐 ′そこで，2 つ目の要件を満たし，かつ効率的に CP-Graph を, 3, 𝑐 ′の直後に現れることはない．

𝑒𝑎,𝑥

𝑜𝑎

𝑒𝑎,𝑦

𝒐𝒂 , 𝟒, 𝒄′

更新するアプローチが必要となる．今，t = ⟨i, O⟩（|O| >= 3,
op , or ∈ O, および op と or は O において順に現れない）が与𝑒𝑏,𝑑𝑜𝑎 , 𝑜𝑏 , 4, 𝑐 ′𝑜𝑎, 𝑜𝑏 , 1, 𝑐 ′えられたとする．もし ep,r ∈/ E であれば，ep,r を作成する必

𝑒𝑏,𝑥
𝑒𝑏,𝑦

𝒐𝒂 , 𝒐𝒃 , 𝟒, 𝒄′𝑒𝑐,𝑑𝑜𝑎 , 𝑜𝑐 , 3, 𝑐 ′𝑒𝑑,𝑥𝑜𝑑 , 2, 𝑐 ′ , 𝑜𝑎 , 𝑜𝑐 , 𝑜𝑑 , 3, 𝑐 ′𝑒𝑑,𝑦𝒐𝒂 , 𝒐𝒃 , 𝒐𝒅 , 𝟒, 𝒄′𝑒𝑥,𝑦𝒐𝒂 , 𝒐𝒃 , 𝒐𝒙 , 𝟏, 𝒄′ , 𝑜𝑑 , 𝑜𝑥 , 2, 𝑐 ′ , 𝒐𝒂 , 𝒐𝒄 , 𝒐𝒅 , 𝒐𝒙 , 𝟑, 𝒄′

要があるか考える．具体的には，{op , or } が排他的パターンである場合，ep,r を作成する必要がある．これを確かめるために，µ({op , or }) および maxoq ∈O′ µ({op , oq , or }) を計算する．また，

図 2 表 1 のトランザクションに基づく CP-Graph のグラフ構造と各辺

O′ = {oq | eq,r ∈ E, ⟨{oi , ..., op , ..., oq }, j, c⟩ ∈ eq,r .L} (1)で あ る ．（ も し µ({op , or }) = maxoq ∈O′ µ({op , oq , or }) で
あ れ ば ，{op , or } は 排 他 的 パ タ ー ン で な い ．）こ こ で ，のラベル集合次に，CP-Graph を用いてあるパターンの µ およびその上界
値をどのように計算するか説明する．パターン {op , oq } が与えられた時，vq .I を用いて µ({op , oq }) の上界値は容易に得られる．
定理 1．頂点 vq について，µ({op , oq }) <= |vq .I(op )| が成り立つ．

maxoq ∈O′ µ({op , oq , or }) の計算は時間がかかる．なぜなら，∀oq ∈ O′ に対して，vr .I(oi ) = argmin {|vr .I(op )|, |vr .I(oq )|}をスキャンしなければならないからである．そのため，多少のフォルスポジティブを許容することにより，この計算コストを削減する．O′ において識別子が最も小さいオブジェクトである oq′ を特定し，µ({op , or }) および µ({op , oq′ , or }) を計算す

アプリオリ性質により，|vq .I(op )| は {op , oq } の上位集合の µる．これらは，vr .I(op ) のスキャンにより同時に計算可能であの上界値でもある．CP-Graph において v.I をハッシュテーブル

る．その結果，µ({op , or }) > µ({op , oq′ , or }) であれば ep,r をで実装することにより，|vq .I(op )| は O(1) で計算可能である．
定理 1 を利用することにより，不必要なパターンの列挙を枝刈りできる．また，あるパターン P の µ(P ) の計算も効率的に実行できる．

• |P | = 1 の場合．P = {op } とすると，|vp .S| = µ(P ) であり，作成する．
（µ({op , oq′ , or }) <= maxoq ∈O′ µ({op , oq , or }) が成り立つため，フォルスネガティブは起きない．
）この処理を連鎖更新と呼ぶ．
挿入アルゴリズム．cnow において t = ⟨i, O⟩ が発生したとする．
今，or を O における j 番目のオブジェクトとする．もし vr ∈/V

定数時間で求められる．

であれば，vr を作成する．その後，vr .S を更新し，vr .f = 1• |P | = 2 の場合．P = {op , oq } とすると，vq .I(op ) に含まれとする．

る全てのストリームの識別子を S に追加し，|S| を返す．これ

ここで，j >
= 2 とし，oq を O における（j − 1）番目のオブは Θ(|vq .I(op )|) 時間で求められる．

ジェクトとする．eq,r ∈/ E であれば，eq,r を作成する．P を，O• |P | >= 3 の場合．P = {oa , op , ..., oq } とする．ラベルのアクにおける 1 番目から（j − 1）番目におけるオブジェクトの集合

セス回数を削減するために，o∗ =argmin∀ei,q ∈E,oi ∈P|vq .I(oi )|.

を計算する．その後，∀⟨P ′ , j, c⟩ ∈ vq .I(o∗ )（P \{oq }⊂P ′ か=
つ j = 1, 2, ..., |S|）に対して，|P | = 2 の場合と同様の処理を実行する．この処理の計算量は，Θ(n + |vq .I(o∗ )|) であり，

n = |{∀ei,q ∈ E | oi ∈ P }| である．
4. 2 CP-Graph の更新
本節では，CP-Graph をインクリメンタルに更新する手順について説明する．

4. 2. 1 新しいトランザクションの挿入
4. 1 節で紹介した通り，辺を作成する際は，2 つの要件を満とすると，eq,r .L に ⟨P, i, cnow ⟩ を追加する．そして，∀op ∈ P
に対して，⟨P, i, cnow ⟩ のポインタを vr .I(op ) に追加する．
さらに，j >
| oq ）であるか= 3 である場合，∃eq′ ,r ∈ E （oq′ =確認する．eq′ ,r ∈/ E である場合，P = {op , ..., or }（|P | >= 3）には必ず oq が含まれており，{op , or } は排他的パターンでないことが保証される．一方，eq′ ,r ∈ E である場合，∀op ∈ P \{oq }（ep,r ∈
/ E ）に対して，連鎖更新を実行する．
（連鎖更新によって辺が作成された場合も，前述の方法と同様にラベルが追加される．
）その後，消去リスト Ldel に ⟨cnow , vr , op , 0⟩ を挿入する．
上の操作後，j < |O| であれば，（j + 1）番目のオブジェクトに対して上の操作を実行する．一方 j = |O| であれば，Ldel に⟨cnow , vr , oq , 1⟩ を挿入し，t に関する更新を終了する．

4. 2. 2 ウィンドウから外れたトランザクションの消去

Algorithm 1: A-R EVISITED (A)新たなトランザクションの挿入処理の際，トランザクション

Input: CP-Graph and A //A is the answer set at cnow − 1
Output: M //M is a set of µを要約した情報を Ldel に挿入している．Ldel に含まれている情報はトランザクションの全ての情報でないにも関わらず，ウィンドウから外れたトランザクションの消去を正確に実行できる．
性質 5．cnow における Ldel の最初の要素を ⟨cnow −w, vr , oq , f ⟩（oq =| ∅）とする．eq,r .L の最初のラベルの作成時刻は cnow −w

1

M←∅

2

Sort ⟨P, µ(P )⟩ ∈ A in descending order of |P |3

for ∀⟨P, µ(P )⟩ ∈ A do

4

6

である．

if ∃o ∈ P such that v ∈/ V thenµ(P ) ← 05

else
if ∀o ∈ P, v.f = 1 then7

このアプローチは，メモリ効率を上げるだけでなく，消去の必8要があるラベルを O(1) で特定できるという利点がある．

9

削除アルゴリズム．⟨cnow − w, vr , oq , f ⟩ ∈ Ldel が与えられた

10時，（i）oq = ∅，（ii）f = 0，および（iii）f = 1 の 3 つの場合

11がある．場合（i）の時，ウィンドウから外れるトランザクショµ(P ) ← µ-C OUNT (P )if µ(P ) <= 1 thenA ← A − {⟨P, µ(P )⟩}else
Let P ′ be a co-occurrence pattern where ⟨P ′ , µ(P ′ )⟩ ∈ A and12µ(P ′ ) has been computed

ンは or のみ保持しているため，vr .S を更新し，vr .f = 1 とす

13

f ←0

れば良い．場合（ii）および（iii）の時，eq,r .L の最初のラベル

14for ∀⟨P ′ , µ(P ′ )⟩ ∈ A where µ(P ) = µ(P ′ ) doを ⟨{op , ..., oq }, i, cnow − w⟩ とする．f = 0 であれば，eq,r は15

連鎖更新により作成されているため，このラベルを削除すれ

if P ⊂ P ′ then16

A ← A − {⟨P, µ(P )⟩}

17

f ←1

ば良い．また，eq,r .L = ∅ となれば，eq,r も削除する．一方，

18

f = 1 であれば，vr から順にラベルに対応する辺を辿り，ラベ

19

if ∀o ∈ P ∪ P ′ , v.f = 1 then20µ ← µ-C OUNT (P ∪ P ′ )21

if µ = µ(P ) then

22

f ←1

23

break

ル，辺，および頂点を更新する．
（v.S および e.L が ∅ であれ
ば, CP-Graph から v および e を削除する．
）その後，Ldel から⟨cnow − w, vr , oq , f ⟩ を削除する．

break

4. 3 閾値の計算
性質 4 より，CP-Graph の更新後，閾値を計算する必要があ

if f = 0 then24

M ← M ∪ {µ(P )}25

る．また，トランザクションの挿入および削除により，いくつかの共起パターンの µ は更新されている．CP-Graph は，cnow − 1から µ の更新が起きたパターンを容易に識別できる．∃o ∈ Pに対して v ∈/ V であれば，P はウィンドウ上に存在しないことが分かる．同様に，v.f = 0 であれば，P を含むトランザク
ションは生成も削除も行われていないことが分かる．そのため，

26

return M

ることを試みる（アルゴリズム 1）．まず，集合 M（初期値 ∅）を準備する．次に，A の要素を |P | の大きい順にソートする．
その後，∀⟨P, µ(P )⟩ ∈ A に対して以下の操作を行う．まず，性質 6 から µ(P ) を得る（4–8 行）．P が共起パターンでなくなれ

以下の性質が成り立つ．
性質 6．µ′ を cnow − 1 における P の µ(P ) とすると，0µ(P ) =
µ′ば，⟨P, µ(P )⟩ を A から取り除く（9–10 行）．P が共起パターンであれば，性質 7 から P が排他的共起パターンであるか計算する（12–23 行）．性質 7 における場合（i）および（ii）のど(∃o ∈ P, v ∈/ V)(∃o ∈ P, v.f = 0)

ちらにも該当しなければ，µ(P ) を M に挿入する（25 行）．

cnow −1 における解に含まれるパターンが排他的共起パターン

であり，∀o ∈ P に対して v.f = 1 であれば，µ(P ) の値は不明でなくなった場合，|M| < k である．この時，閾値は CP-Graphである．

を辿ることによって計算する．CP-Graph は，与えられたパター

次に，µ の更新により，cnow − 1 において解に含まれていたンの µ を（|P | <= 2 の場合に特に）効率的に計算できるため，パターンが cnow において排他的共起パターンでなくなること

アルゴリズム 2 により，タイトな閾値を計算できる．

がある．以下の性質により，そのようなパターンを特定できる．

閾値の計算アルゴリズム．まず，|M| = k であれば，M にお性質 7．cnow において，全ての ⟨P, µ(P )⟩ ∈ A について µ(P )ける k 番目に大きい値を閾値とする（2 行）．|M| < k であれが 正 確 な 値 で あ る と す る ．⟨P, µ(P )⟩ が 与 え ら れ た 時 ，（i）ば，CP-Graph から閾値を求める．M における |M| 番目に大µ(P ) = µ(P ) かつ P ⊂ P である ⟨P , µ(P )⟩ が A に存在

きい値を µ′ とし，σ = |{µ ∈ M | µ = µ′ }| とする（4 行）．次

しないか，（ii）P ̸⊂ Q かつ µ(P ) = µ(Q) = µ(P ∪ Q) となる′に，∀vj ∈ V について，µ({oj }) を計算し，2 <= µ({oj }) <=µ

⟨Q, µ(Q)⟩ が A に存在すれば，P は排他的共起パターンでない

であれば，

′

′

′

′

ことが分かる．
（ii）の場合，Q も排他的共起パターンではなく，∀o ∈ P ∪ Q に対して v.f = 1 である．
以上の 2 つの性質を考慮し，cnow − 1 における解から閾値を得µp (oj ) = argmax µ({oi , oj }).
∀ei,j ∈Eを計算する．µp (oj ) は，oj を最後のオブジェクトとするパター

Algorithm 2: T HRESHOLD -C OMPUTATION (M)

Algorithm 3: A-R EFINEMENT (τ, τnow−1 )Input: CP-Graph and M

Input: CP-Graph, τ , τnow−1 //τ is the threshold obtained by Algorithm 2
Output: A

Output: threshold1

if |M| = k then1i←1
if τ > τnow−1 then2

return the kth highest µ among M

23µ′ ← the |M|th highest µ among M3

σ ← |{µ ∈ M | µ = µ′ }|′5 for ∀vj ∈ V where 2 <= µ({oj }) <= µ do44µ (oj ) ← 0

7

for ∀ei,j ∈ E dop

8µ ← µ-C OUNT({oi , oj })9if µ > µp (oj ) then8case i = 0
for ∀vj ∈ V where |vj .S| >= τ and vj .f = 1 do
vj .f = 010Q ← {⟨{oj }, µ({oi })⟩}p

if µ({oj }) > µ (oj ) then11

while Q =| ∅ doM ← M ∪ µ({oj })12⟨P, µ(P )⟩ ← Q.front //let P = {oa ..., oq }13

µ ← 0, B ← ∅14for ∀eq,r ∈ E where |vr .I(oq )| >= τ do12157µp (oj ) ← µ

if |M| < k + σ thenreturn 2

14

i←0

9

10

11

if τ = τnow−1 and Algorithm 1 returns M of |M| = k then

6

6

13

5

i←0
else

′
if ∃⟨P ′ , i′ , c⟩ ∈ eq,r .L such that P ⊂=P then15

return the (k + σ)th highest µ among M

17µ′ ← µ-C OUNT (P ∪ {or })if µ′ >
= τ then18

if vr .f = 1 then16

ン集合の中における最大値である．そのため，µ({oj }) > µ (oj )pであれば，{oj } またはその上位集合 {oj , ..., oj ′ } は排他的共起パターンであり，µ({oj }) は M に追加される（5–12 行）．そB ← B ∪ ⟨P ∪ {or }, µ(P ∪ {or })⟩19

if µ′ > µ then20µ ← µ′

21

して，M の中で（k + σ ）番目の µ を閾値とする．k 番目としないのは，M には σ 個の µ′ が存在するからである．
（もし|M| < k + σ であれば，閾値は 2 とする．
）以上の操作により，
定理 2 が成立する．

if µ(P ) > µ then22′
if ∄⟨P ′ , µ(P ′ )⟩ ∈ A such that P ⊂=P and23µ(P ) = µ(P ′ ) then

Let Pk be the co-occurrence pattern with the kth24

定理 2．cnow における k 番目に大きい µ を τnow とし，アル
ゴリズム 2 によって得られる閾値を τ とすると，τnow >=τでhighest µ
A ← A ∪ ⟨P, µ(P )⟩ − ⟨Pk , µ(Pk )⟩

25

else

26

ある．

if ∃⟨P ′ , µ(P ′ )⟩ ∈ A such that P ′ ⊂=P and27

4. 4 解 の 更 新µ(P ) = µ(P ′ ) then閾値の計算後，CP-Graph を辿ることにより A を更新する．

A ← A − {∀⟨P ′ , µ(P ′ )⟩ ∈28′
A | P ′⊂
=P, µ(P ) = µ(P )}アプリオリ性質と τ により，|v.S| < τ である頂点は全て枝刈りできる．つまり，|vi .S| >= τ である vi が与えられた時，共起パターン P = {oi , ..., oj }（µ(P ) >= τ ）を列挙し，A を更新すA ← A ∪ ⟨P, µ(P )⟩29

if |A| = k then30

る．以下の場合があればさらに探索空間を削減できる．

31

定理 3．以下の 2 つの場合を考える．

32

τ ← the kth highest µ in A
Q ← Q − ⟨P, µ(P )⟩ //pop Q.front
Q ← {∀⟨P ′ , µ(P ′ )⟩ ∈ Q | µ(P ′ ) >= τ} ∪{∀⟨P ′ , µ(P ′ )⟩ ∈ B | µ(P ′ ) >
= τ}

33

（I）τ > τnow−1 ．
（II）τ = τnow−1 かつアルゴリズム 1 において |M| = k である．
アルゴリズム 2 の実行後に，場合（I）または（II）であった時，

A に新しく P が追加されるならば，∀o ∈ P に対して v.f = 1
である．
ここから，A の更新アルゴリズムである A-R EFINEMENT（ア

34
35
36

case i = 1
Execute the same operation as case i = 0 without the condition of v.f = 1
return A

ルゴリズム 3）を紹介する．説明の簡易化のために，定理 3 にし µ({oj , oq }) >= τ か つ vq .f = 1 で あ れ ば ，バッファB に ⟨{oj , oq }, µ({oj , oq })⟩ を 挿 入 す る ．こ こ で ，µ(oj ) >おける場合（I）または（II）の状態であることを想定し，説明max µ({oj , oq }) であれば，{oj } は排他的共起パターンであの最後にいずれの場合でもない状態の時の差分について紹介る可能性がある．

する．

（3）次に，{oj } の上位集合が A に存在するか確認する．もし|vj .S| >= τ かつ vj .f = 1 である vj ∈ V が与えられたとする．

′′′′{oj }⊂=P かつ µ({oj }) = µ(P ) となる ⟨P , µ(P )⟩ が A に存

（1）まず vj .f = 0 とし，キュー Q に ⟨oj , µ({oj })⟩ を挿入する．

在しなければ，A における k 番目の要素と ⟨{oj }, µ({oj })⟩ を（2）{oj , oq } に焦点を当てる．このとき，|vq .I(oj )| >= τ かつ置換し，τ を更新する．

⟨P , i, c⟩ ∈ ej,q .L であり，{oj , oq }⊂（|vq .I(oj )| <=P である．
′′τ と な る {oj , oq } は 定 理 1 に よ り 枝 刈 り で き る ．）も（4）そ の 後 ，Q の 先 頭 の 要 素 を ポップ す る ．B の 各 要 素（⟨{oj , oq }, µ({oj , oq })⟩）が µ({oj , oq }) >= τ であれば，Q に挿入する．

トランザクションの集合を T ，T に含まれるオブジェクトのも し Q = ∅ で あ れ ば ，|v.S| >= τ となる別の頂点に対 し て（1）–（4）の 操 作 を 実 行 す る ．そ う で な け れ ば ，

集合を D とする．表 2 は，それぞれのデータ集合の統計値を表している．

Q の 先 頭 の 要 素（⟨{oj , oq }, µ({oj , oq })⟩）に 対 し て ，µ =表 2 データセットの統計値

max∀eq,r ∈E µ({oj , oq , or }) を計算し，操作（2）と同様にバッ

データセット|T |T における |D| の平均|D|

ファを更新する．ここで，eq,r .L は {oj , oq , or } を持つラベルを保OnlineRetail541,909

4.36

2,603

持している．もし µ({oj , oq }) > µ であれば，操作（3）と同様のTwitter

5,677,156

4.06

477,990′⊂′={oj , oq } かつ µ({oj , oq }) = µ(P ) となる P について ⟨P , µ(P ′ )⟩ ∈ A であれば，A から ⟨P ′ , µ(P ′ )⟩5. 2 実 験 結 果

場合について考える．P′′を取り除き，⟨{oj , oq }, µ({oj , oq })⟩ を加える．その後，操作（4）

本節では，k および w を変えて行った実験の結果を示す．ス

を実行し，Q をチェックする．上記の操作を |v.S| >= τ となるライディングウィンドウモデルとして，OnlineRetail は数に基全ての v ∈ V について実行する．最後に，定理 3 における場合

づくウィンドウ，Twitter では時間に基づくウィンドウを用いた．

（I）および（II）の状態でなければ，“v.f = 1” という条件を除OnlineRetail を用いた実験におけるデフォルト設定は，k = 50，

外する．

5. 評 価 実 験
本章では，提案アルゴリズムの性能評価のために行った実験の結果を紹介する．

5. 1 セッティング
本実験では以下の 2 つのアルゴリズムを評価した．

∆ = 50，および w = 200, 000 である．一方，Twitter を用いた実験におけるデフォルト設定は，k = 50 および w = 7, 200[sec]である．

k の影響．まず，表 3 はインデックス更新時間を示している．
CP-Graph（および Seg-tree）の構造は k に依存しないため，インデックス更新時間（およびメモリ使用量）は k の影響を受けない．ここで，Seg-tree の方が CP-Graph よりもインデックス• [12] における提案アルゴリズム（Seg-tree と表記する）．
（こ

更新時間が短いことが分かる．トランザクション t = ⟨i, O⟩ がれは，既存研究において，複数ストリームから共起パターンを与えられた時，Seg-tree は O 中のオブジェクトに対応する頂点

正確にマイニングできる唯一のアルゴリズムである．
）3. 章でを作成し，順に現れる頂点間に辺を作成する．一方，CP-Graph

述べた通り，CooMine は動的な閾値に対応していないため，新は |O| >
= 3 の場合に連作更新を行う．また，CP-Graph はトラン

たな（ウィンドウから外れた）トランザクションから閾値を推ザクションの削除の際に，転置ファイルも更新しなければなら定するアプローチを CooMine に組み込んだ．

ない．そのため，CP-Graph のインデックス更新時間が Seg-tree• 本稿の提案アルゴリズム（CP-Graph と表記する）．

に比べて長くなる．

上の 2 つのアルゴリズムは C++で実装されており，すべての実

表 3 インデックス更新時間 [msec]

験は 3.4GHz Intel Core i7 および 32GB RAM で構成される PC

OnlineRetail Twitter上で行った．

Seg-tree

0.15

2.12

評価指標. 本実験では，以下の 3 つの指標を評価した．

CP-Graph

73.3

14.54

• インデックス更新時間：ウィンドウの各スライドにおけるインデックスの平均更新時間

表 4 はメモリ使用量を示しており，CP-Graph のメモリ使用
量は Seg-tree よりも大きいことが分かる．これは，e.L および• 解を更新するまでの時間：ウィンドウの各スライドにおけるv.I を管理しているためである．しかし，CP-Graph のメモリ使平均処理時間（インデックスの更新時間を含む．
）

用量はメインメモリに容易にフィットする程度である．

• メモリ使用量：インデックスによるメモリの平均消費量

表 4 メモリ使用量 [MB]

データセット. 本実験では，2 つの実データ OnlineRetail（注 2）およOnlineRetail Twitter

び Twitter を用いた．OnlineRetail は 2010/01/12 から 2011/09/12

Seg-tree

38.49

32.90

間で得られたオンライン購買に関するトランザクションの集

CP-Graph

60.19

44.03

合である．各トランザクションに，[0,9999] から選ばれたラン
ダムな整数値をストリームの識別子として与えた．Twitter は，

図 3 は，解を更新するまでの時間の結果を示している．まず，

2015/4/3 から 2015/4/9 で得られた英語ツイートの集合である．

Seg-tree の処理時間は，A を更新する時間が大部分を占めてい一つのツイート中に現れる単語をオブジェクトとすることによることが分かる．一方，CP-Graph の処理時間はインデックス更り，1 つのツイートを 1 つのトランザクションと見なす [12]．1
人のユーザを 1 つのストリームと見なすと，ストリームの数は

3,341,975 である．

新時間が大部分を占めていることが分かる（表 3 を参照）．また，CP-Graph の性能は Seg-tree を大きく上回る．CP-Graph は
インデックスの更新時間がやや長いものの，与えられたパター
ンの µ の計算や閾値の計算を効率的に実行できるため，A を更新する時間が早い．Seg-tree はインデックスは高速に更新でき（注 2）：https://archive.ics.uci.edu/ml/datasetsSeg-tree

100

10
10

20

30

40

50

60

70

80

90 100Seg-tree
インデックス更新時間 [msec]

解を更新するまでの時間 [msec]

1000

CP-graph

1000

100

10
10

20

30

40

k

50

60

70

80

Seg-tree

140
120

100
80
60
40
20
0

90 100

10

20

100
90
80
70
60
50
40
30
20
10
0
3600

30

40

50

7200

w [K]

k

(a) 解を更新するまでの時間（OnlineRe- (b) 解を更新するまでの時間（Twitter）

CP-graph

160

CP-graph

インデックス更新時間 [msec]

CP-graph
解を更新するまでの時間 [msec]

Seg-tree
10000

10800

14400

18000

w [sec](a) インデックス更新時間（OnlineRetail） (b) インデックス更新時間（Twitter）

tail）

るが，パターンの µ を計算する時間が長く，そのパターンが排他的であるかどうかを確認する時間も長い．

w の影響．次に，ウィンドウサイズの影響の結果（図 4）について紹介する．図 4(a)–4(b) から分かるように，ウィンドウサイ

Seg-treeCP-graph

10000

1000

100

10
10

ズが大きくなると Seg-tree と CP-Graph は共にインデックス更

20

30

40

50

解を更新するまでの時間 [msec]

k の 影 響解を更新するまでの時間 [msec]

図3

Seg-treeCP-graph

7200

14400

10000
1000

100
10
1
3600

10800

w [K]

18000

w [sec]

新時間が長くなる．CP-Graph における連鎖更新では，複数の(c) 解を更新するまでの時間（OnlineRe- (d) 解を更新するまでの時間（Twitter）

頂点，辺，およびラベルをチェックする必要がある．ウィンド

tail）

ウサイズが大きいと，それらの数も大きくなるため，連鎖更新

Seg-treeが大部分である．また，CP-Graph の処理時間は Seg-tree よりも早く，性能差はウィンドウサイズが大きくなるにつれて顕著になる．CP-Graph はあるパターン，例えば {oi , ..., oj } の µ を，

vj .I を用いるだけで計算できる．そのため，ウィンドウサイズ
に対してロバストであり，この結果は閾値の計算が効率的であり，タイトな閾値を与えていることを示している．
図 4(e)–4(f) はメモリ使用量を表している．Seg-tree および

CP-Graph のメモリ使用量はウィンドウサイズに対して線形に増加している．CP-Graph では，ウィンドウサイズが大きくなると，辺が管理するラベル集合や頂点が管理する転置ファイルのサイズが大きくなる．そのため，Seg-tree よりも CP-Graph の方がメモリ使用量が大きい．

6. お わ り に
近年の実世界アプリケーションにおいて，ストリームデータ
に対するパターンマイニングに多くの関心が集まっている．本稿では，複数のストリームが存在する環境において，最も多くのストリームに現れるパターンの上位 k 個のものをマイニングする問題に対する効率的なアルゴリズムを提案した．筆者らの知る限り，本問題はこれまでに着手されていない．本稿で提案した CP-Graph は，グラフと転置ファイルを組み合わせたデー
タ構造であり，与えられたパターンの µ を効率的に計算できる．
また，CP-Graph は閾値の推定も効率的に実行でき，それにより解の更新を高速に行う．実データを用いた実験の結果から，提案アルゴリズムの有効性およびスケーラビリティを確認した．
謝辞．本研究の一部は，文部科学省科学研究費補助金・基盤研
究 (A)(JP26240013) ，若手 (B)(JP16K16056)，および JST 国際
科学技術共同研究推進事業（戦略的国際共同研究プログラム）の研究助成によるものである．ここに記して謝意を表す．

メモリ使用量 [MB]k の影響と同様に，CP-Graph の処理はインデックスの更新時間

Seg-treeCP-graph120

140

メモリ使用量 [MB]解を更新するまでの時間に焦点を当てる．図 4(c)–4(d) から，

CP-graph160にかかる時間も長くなる．

120

100
80
60
40
20
0
10

20

30

40

50

100

80
60
40
20
0
3600

w [K]

7200

10800

14400

18000

w [sec](e) メモリ使用量（OnlineRetail）

図4

文(f) メモリ使用量（Twitter）

w の影響

献

[1] R. Agrawal and R. Srikant. Fast algorithms for mining association
rules. In VLDB, pages 487–499, 1994.
[2] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models
and issues in data stream systems. In PODS, pages 1–16, 2002.
[3] Y. Chi, H. Wang, P. S. Yu, and R. R. Muntz. Moment: Maintaining
closed frequent itemsets over a stream sliding window. In ICDM,
pages 59–66, 2004.
[4] J. Guo, P. Zhang, J. Tan, and L. Guo. Mining frequent patterns acrossmultiple data streams. In CIKM, pages 2325–2328, 2011.
[5] R. Gwadera and F. Crestani. Discovering significant patterns in
multi-stream sequences. In ICDM, pages 827–832, 2008.
[6] J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate
generation. In SIGMOD, pages 1–12, 2000.
[7] B. Mozafari, H. Thakkar, and C. Zaniolo. Verifying and mining frequent patterns from large windows over data streams. In ICDE, pages
179–188, 2008.
[8] A. Salam and M. S. H. Khayal. Mining top-k frequent patterns without minimum support threshold. KIS, 30(1):57–86, 2012.
[9] L. Troiano and G. Scibelli. Mining frequent itemsets in data streams
within a time horizon. DKE, 89:21–37, 2014.
[10] V. S. Tseng, C.-W. Wu, P. Fournier-Viger, and P. S. Yu. Efficient algorithms for mining the concise and lossless representation of highutility itemsets. TKDE, 27(3):726–739, 2015.
[11] J. Wang, J. Han, Y. Lu, and P. Tzvetkov. Tfp: An efficient algorithm
for mining top-k frequent closed itemsets. TKDE, 17(5):652–663,
2005.
[12] Z. Yu, X. Yu, Y. Liu, W. Li, and J. Pei. Mining frequent co-occurrence
patterns across multiple data streams. In EDBT, pages 73–84, 2015.
[13] X. Zhu and X. Wu. Discovering relational patterns across multiple
databases. In ICDE, pages 726–735, 2007.