DEIM Forum 2023 4a-6-5

Web データにおけるパターンの自動抽出
塚本

圭祐†

村山

太一††

天方 大地†††
原

松原

靖子††

櫻井 保志††

隆浩†††† 大阪大学工学部 〒 565–0871 大阪府吹田市山田丘 2-1††† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5†† 大阪大学産業科学研究所 〒 567–0047 大阪府茨木市美穂ヶ丘 8-1
E-mail: †{tsukamoto.keisuke,amagata.daichi,hara}@ist.osaka-u.ac.jp,††{taichi,yasuko,yasushi}@sanken.osaka-u.ac.jp
あらまし 近年，インターネットの普及に伴い Web データが増加しており，多くの場面で活用されている．Web デー
タは人々の動きや社会の動向を反映したソーシャルセンサの役割を持つことから，Web データの解析は人々の意思決定に対する重要な知見を提供することができる．Web データの解析においてパターン抽出は重要であるが，既存のパターン抽出手法の多くはセンサデータのような定間隔な時系列データを想定したものばかりである．つまり，Web
データのような不定間隔にイベントが発生するデータには適していない．本研究では，Web 上における長期間のイベントデータから自動でパターンを抽出するアルゴリズムを提案する．提案アルゴリズムは，長期間のデータを意味のある部分系列に分解しパターン抽出を行うレジーム分類の手法と，イベントデータのモデリングに用いられる点過程の１つである Hawkes 過程の組み合わせで構成されている．また，レジームの数や変化点に関する事前知識を必要とせずにモデリングを行うことで，Web データを意味のあるパターンに分類することを実現する．人工データと Web
データを用いて実験を行い，提案アルゴリズムの有効性を検証した．
キーワード 時系列解析，Hawkes 過程，Web データ，パターン抽出
時系列データのパターン抽出を行っている多くの既存研究で1 はじめに近年，インターネットの普及に伴って Web データが増加して
おり，購買履歴を用いたユーザの購買行動予測 [12] やソーシャ
ルメディアの投稿履歴を用いたインフルエンザの流行予測 [2]などの多くの場面で利用されている．Web データは人々の動き
や社会の動向を反映したソーシャルセンサの役割を持つことから，Web データの解析は人々の意思決定に対する重要な知見を提供することができる．長期間の Web データは複数のパターンから構成される．例えば，ソーシャルメディアにおける，ある映画に関する投稿では，映画公開前の予告動画公開による投稿，映画公開後の映画の感想による投稿，および関連ニュース
やグッズによる投稿などの様々なパターンが見られる．このようなパターンを抽出することで，Web における反応の変化を解析することができる．

Web データには，不定間隔にイベントが発生するデータ（イベントデータ）が多く存在する．例えば，Twitter や Reddit などのソーシャルメディアにおける投稿履歴や Web サイトにおけるアクセス履歴，EC サイトにおける購入履歴などがイベン
トデータとして蓄積されている．このようなデータをモデリングする手法として，点過程が頻繁に用いられており，特に Web
データのような過去のイベントに影響してイベントが発生する
データには，点過程モデルの 1 つである Hawkes 過程を用いたモデリングが多く行われている [5, 19]．

は，センサデータのような定間隔な時間間隔で提供されるデー
タ（定間隔データ）を扱っている．Autoplait [15] では，隠れマ
ルコフモデルの状態遷移をパターンごとにグループ化し，階層的な時系列レジームの遷移を表現している. TICC [8] では，各クラスタが多層マルコフ確率場を持つとして，時系列データのクラスタリングを行っている．このような手法はイベントデー
タをそのまま扱うことができないため，イベントデータに適用する際にはイベントデータを定間隔データに変換する必要がある．しかし，図 1(a) のように短い間隔で変換するとスパースなデータになり，図 1(b) のように長い間隔で変換するとイベ
ント発生時刻および発生間隔の情報が欠落することから，適切なパターンを抽出することは難しい．
本研究では，長期間の Web データに対してパターンの変化点において分割を行い，各分割区間ごとにイベントデータをモ
デリングをすることで，自動でパターン抽出を行うアルゴリズ
ムを提案する．図 2 はアルゴリズムの入力および出力の例である．提案アルゴリズムは，長期間のデータを意味のある部分系
列に分解しパターン抽出を行うレジーム分類の手法と Hawkes
過程を組み合わせたモデルであり，分割区間ごとにモデリングを行うことで，Web データを意味のあるパターンに分類することを実現する．さらに，提案アルゴリズムはパターン（レジーム）の数や変化点に関する事前知識を必要とせずに，レジーム
分類することが可能である．提案アルゴリズムでは，以下の 2
つのステップで構成されている．まず，Hawkes 過程の対数尤度

る．このモデルでは再投稿が行われる確率および投稿者のフォイベント時刻の集合
𝑇 = {𝑡! , 𝑡" , … , 𝑡# }イベント数[/s]イベント数[/m]ロワー数が考慮されている．最近では，ニューラルネットワーク
を用いて点過程のモデリングを行なった研究が多い．Recurrent

Marked Temporal Point Process（RMTPP）[4] は，イベン
トの発生時刻にそのイベントに紐づいた情報を考慮するため時間

時間に深層学習を用いたモデルである．Dynamic Hawkes Process(a) １秒あたりのイベント数(b) １分あたりのイベント数

図 1: イベントデータから定間隔データへの変換（DHP）[18] では，Hawkes 過程のカーネル関数の学習に現在のコミュニティの影響を考慮している．これらのモデルは 1 つ

⼊⼒：イベント発⽣時刻の集合 𝑇 = {𝑡!, 𝑡", … , 𝑡#}のパターンが存在するデータのモデリングに適している．し
𝒕𝟏

𝒕𝟐

1/1
1/1
0:00:05 0:01:10

𝒕𝟑

𝒕𝟒

𝒕𝟓

𝒕𝒏'𝟐

1/1
1/1
1/1
0:08:34 0:09:52 0:11:08

・・・

𝒕𝒏'𝟏

3/11
3/11
23:53:12 23:56:45

𝒕𝒏

かし，複数のパターンが存在するデータにおいては，複数のモ

3/11
23:59:10

デルを用いたモデリングが適している場合がある．例として，
フェイクニュースの拡散を 2 種類の Hawkes 過程を用いてモデ

イベント数 [/h](a) 入力：イベント時刻の集合 T = {t1 ，...，tn }
𝒕𝟏

𝒕𝟐

1000

1/1
1/1
0:00:05 0:01:10

𝒕𝟑

𝒕𝟒

𝒕𝒏'𝟏

3/11
1/1
1/1
0:08:34 0:09:52 ・・・23:56:45

リングを行った研究 [16] が挙げられる．この手法は，フェイク
ニュースが普通のニュースとして拡散される段階とニュースを𝒕𝒏

フェイクだと認識することで拡散される段階の 2 段階のプロセ

3/11
23:59:10

スで構成されることから，2 種類の Hawkes 過程を用いてカス500

ケードのモデリングを行っている．しかし，この研究では 2 つ
0
0

14

42

28

56

70

時間[day](b) 出力：パターン抽出

図 2: 入力および出力の例のパターンが含まれたデータにのみ適用できるもので，さらに多くのパターンがあるデータには適用できない．そこで，本研
究はパターンごとに複数の Hawkes 過程でモデリングを行なうことで，長期間のイベントデータに適用することを試みた．
時系列パターンの検出．センサなどから収集されるデータは，潜在的な特徴を持っている．その特徴の変化は，K-means [9]，を用いて分割点を推定し，コスト関数で分割を行うか判定する

線形力学系，および隠れマルコフモデルなどの手法で捉え，複ことによってイベントデータのセグメンテーションを行う．次数の時系列パターンに分類することができる．このような手法に，分割されて新たにできた区間（セグメント候補）に対してを拡張し，有用な潜在的な特徴を捉える研究が多く行われてレジームの推定を行う．具体的には，新しくできたセグメント

いる．

候補に対して，既存レジームを当てはめることができるかを判•Parsimonious Linear Fingerprinting（PLiF）[14]：様々定し，できない場合は新規レジームとして設定する．実験としな時系列パターンを含む複雑なシーケンスに対して線形力学系て，人工データを用いてレジーム分類の精度を評価し，提案アを当てはめることで，意味のある特徴を抽出する手法．

ルゴリズムの有効性を検証した．また，Web データを用いて，•AutoPlait [15]：大規模時系列データのための時系列パ

提案アルゴリズムが適切なセグメンテーションおよびレジーム

ターン自動抽出アルゴリズム．このアルゴリズムにおけるモデ推定ができているかを確認した．

ルは，各パターン間の遷移を表現するための多階層連鎖モデル

本論文の貢献は以下のとおりである．

および時系列パターンの発見のための最小記述長（MDL）原

•イベントデータに適応したモデルを提案

理 [7] に基づいた符号化スキームで構成されおり，パラメータ•

複数のレジームを自動で抽出の事前情報なしにパターン抽出を可能としている．

•

Web データに対して実験を行い，モデル性能を検証•

Toeplitz Inverse Covariance-based Clustering（TICC）[8]: 各クラスタを時間的に変化しない部分列における異なるセ2 関連研究イベント発生時間のモデリング．本研究では，Web データにおける情報拡散のモデリングを行っている．このようなデータに関して，情報拡散を捉える点過程のモデルの 1 つである，自己励起性を考慮した Hawkes 過程 [10] が注目されている．Hawkes
過程は，地震 [17]，金融 [3, 11]，購買 [21] およびソーシャルメ
ディア [1,6] における拡散過程のモデル化に有効である．Hawkes
過程を拡張した研究は多く行われている．SEISMIC [22] および TiDeH [13] は，ソーシャルネットワークにおける再投稿の情報カスケードを Hawkes 過程を拡張してモデリングし，これまでの再投稿履歴から，最終的な再投稿数の予測を行う手法であンサ間の関係を示す依存関係ネットワークとし，時系列データのセグメンテーションとクラスタリングを同時に行う手法．ある時間における各特徴量をノード，特徴量間の関係をエッジとして捉えることで多層マルコフ確率場を形成し，これを各クラスタごとに持っていると仮定している．

•

Time Adaptive Gaussian Model（TAGM）[20]：多次

元時系列データに対して，隠れマルコフモデルとガウシアング
ラフィックモデルを組み合わせてデータマイニング，予測および因果関係パターンの検出を行う手法．多次元時系列の変数間の確率的関係を理解しながら，同時に時間方向にクラスタリン
グし，その基礎的な分布をグラフモデルにより推測することができる．

このように，時系列データからパターンごとにセグメンテー

また，このときの対数尤度は以下のようになる．

ションを行い，潜在的な特徴を抽出する手法が多く研究されてL=いる．しかし，このようなモデルでは，定間隔な時間情報をn∑log(µ +∑

i=1

持ったデータに適用される手法となっており，Web データのよ− (µT +

うな不定間隔な時間情報を持ったイベントデータをそのまま適

αβe−β(ti −tj ) )

j<i
n
∑

α(1 − e(5)−β(T −ti )

))

i=1

用することはできない．

式 (5) が最大となるパラメータ集合 θ = {µ，α，β} は，データを

3 事前準備説明する最適な集合である．

本章では，提案アルゴリズムの基礎となる手法について説明する．

3. 3 レジーム分類
レジーム分類とは，入力時系列を m 個のセグメント集合

S = {s1 ，...sm } に分割し，類似セグメントをグループごとに分

3. 1 点 過 程
点過程とは，空間上にランダムに分布する点の集合に関する確率過程である [23]．本研究では点をイベントとして捉え，

Web データに適用する．観察期間 [0，T ] に n 個のイベントが発生したとき，イベント時刻の集合を T = {t1 ，t2 ，...，tn }，ti ∈ [0，T ] と表す．点過程では，強度 λ がイベントの発生しやすさを決めるパラメータである．強度が時間に応じて変化する場合は強度関数 λ(t) として表される．微小な区間 [t, t + ∆t] にイベン
トが発生する確率を求めるために，強度関数が以下のように用いられる．

類することである．例えば，図 2(b) では，複数のセグメントに分割され，各セグメントが { 青，緑，黄 } の 3 つのグループに分類されている．本研究ではこれらのグループをレジームと呼ぶ．si は i 番目のセグメントの開始点 t′is ，終了点 t′ie で構成され（つまり，si = {t′is ，t′ie }），各セグメントは重複がないものとする．本研究では，イベント時刻の集合 T = {t1 ，...，tn } が与えられたとき，提案アルゴリズムは m 個のセグメント集合

S = {s1 ，...sm } に分割してパターンの変動を捉え，レジーム分類をする．
定義 1（レジーム）それぞれのセグメント s はセグメントグ
ループの 1 つに割り当てられる．これらのグループをレジーム

P [N (t, t + ∆t) = 1] = λ(t)∆tP [N (t, t + ∆t) = 0] = 1 − λ(t)∆t(1)と呼び，レジームを表現するパラメータを θ として表す．r を最適なセグメントグループの個数としたとき，r 個のレジーム

また，強度関数は以下のように定義される．

のモデルパラメータ集合を Θ = {θ 1 ，...，θ r } と表す．

E[N (t + h) − N (t)|H(t)](2)
h
ここで，N (t) は時刻 t までのイベントの発生回数，H(t) は時さらに，各セグメントが所属するレジームを表現するため，新λ(t) = lim

h→0

たにセグメントメンバシップを定義する．

刻 t までのイベント履歴 {t1 ，t2 ，...tN (t) } を表している．
定義 2（セグメントメンバシップ）i 番目のセグメントが所属す

3. 2 Hawkes 過程

るレジームの番号を fi とし，m 個の整数列 F = {f1 ，...，fm }Web 上のイベントは，他のユーザが閲覧することで共有さとして表す．

れ，拡散される．このようなデータに対して，Hawkes 過程は過去のイベントに依存して次のイベントが発生するという特徴をこれにより，入力時系列を m 個のセグメントと r 個のレジー持っており，現象を捉える上で最適なモデルとなっている．つムで {m，r ，S ，Θ，F} として表現することができる．

まり，Hawkes 過程は一時的にイベントの発生確率が上昇する
自己励起性を持ったデータを扱う点過程モデルである．Hawkes

本研究の目的は，イベント時刻の集合 T = {t1 ，t2 ，...，tn }，過程の強度関数は以下のように定義される．

λ(t) = λ(t|H(t)) = µ +∑ϕ(t − tj )3. 4 問 題 設 定ti ∈ [0，T ] が与えられたときに，セグメンテーションを行い，

(3)

tj <t

各セグメントのレジーム分類を自動で行うこと，つまり，T を表現する最適なパラメータ集合 C = {m，r ，S ，Θ，F} を発見す

ここで，µ は基底強度，ϕ(t) は過去のイベントからの影響を表ることである．

すカーネル関数を表している．カーネル関数 ϕ(t) には，指数関K
数 αβe−βt や冪関数 (t+c)
p などが用いられ，Web データには指数関数が適していることから [1, 6]，本研究ではカーネル関
数として指数関数を採用する．

λ(t) = µ +

∑
tj <t

αβe−β(t−tj )4 提案アルゴリズム
4. 1 概要

提案アルゴリズムは，与えられたイベント時刻の集合 T = {t1

(4)

，t2 ，
...，tn } に対してレジーム変化点の検出とレジームの推定を繰り返し，最終的に最適なセグメントとレジームの抽出を行う，

トをそれぞれ sf , sb とする．
レジームDB

レジーム変化点𝜽!

𝜽"

4. 2. 2 分割の判定
次に，分割候補点を採用するかを判定する．分割の判定基準として，最小記述長原理 [7] の概念に基づいた符号化コストを用いる．これはデータを圧縮すればするほど，その根底にあるパターンを知ることができるという仮定に基づいたものである．

レジーム変化点の検出

レジームの推定

図 3: レジーム変化点の検出とレジームの推定の流れ

具体的には，分割によるイベント時刻の集合 T の符号化コストの減少量より，モデルを表現するために必要な符号化コストの増加量が上回る場合，データは圧縮されないため，分割を行

表 1: 主な記号と定義
記号

定義

n

イベント数

T

イベント時刻の集合：T = {t1 ，...，tn }わないこととする．
データが与えられたときのモデルのよさは次の式で表現できる．

CostT (T ; C) = CostM（Θ）+ CostC (T |Θ)mセグメントの数

si

セグメント:si = {t′is ，t′ie }S

T に含まれるセグメント集合：S = {s1 ，...sm }

CostT (T ; C) を判定コストとする．ここで，CostM（Θ）は Θ

Fセグメントメンバシップ：F = {f1 ，...，fm }を表現するためのモデル表現コストであり，CostC (T |Θ) は Θr

T に含まれるレジームの総数による T のデータ符号化コストである．CostT (T ; C) を最小化Θ

r 個のレジームのモデルパラメータ集合：

することで，最適なパラメータ集合 C を発見することができる．

Θ = {θ 1 ，...，θ r }i 番目のレジームのモデルパラメータθi

T を表現する最適なパラメータ集合:C

C = {m，r ，S ，Θ，F }(6)

モデル表現コストはモデル Θ を記述するために必要なビット数であり，以下の要素で構成される．ここで，cF は浮動小数点のコストを示す．

•

セグメントの個数 m：log∗ (m) ビット 1

CostC (T |Θ) Θ による T のデータ符号化コスト•

CostT (T ; C)•

レジームの個数 r ：log∗ (r) ビット∑∗
セグメント集合 S ： m
i=1 log (|si |) ビット•

レジームパラメータ集合 Θ：3rcF ビット

つまり，T を表現する最適なパラメータ集合 C = {m，r ，S ，Θ

•

レジーム割り当て F ：m log(r) ビット，F} を発見する．各レジームを表現するモデルとして Hawkes

データ符号化コストはデータを上手く表現できているかを表過程を採用し，Hawkes 過程のパラメータの集合 θ i = {µi ，αi ，す指標である．レジーム θ j が与えられた際の，セグメント siβi } を保存する．各セグメント候補に対するレジーム変化点ののデータ符号化コストは，負の対数尤度（式 (5)) となる．つま

CostM (Θ)Θ のモデル表現コスト
判定コスト

検出とレジームの推定は以下のステップで行う．

•

ステップ 1：レジーム変化点の検出（4. 2 節）•

ステップ 2：レジームの推定（4. 3 節）り，モデル Θ が与えられた際の，イベント時刻の集合 T のデー∑
タ符号化コストは，負の対数尤度の総和 − m
i=1 Li となる．
以上のことから，式 (6) は以下のようになる．

上記アルゴリズムは，すべてのセグメント候補に適用していく
もので，どのような順番で適用するかについては 4. 4 節に記す．

CostT (T ; C) = log∗ (m) + log∗ (r) + m log(r) + 3rcF

図 3 は 1 つのセグメント候補に対する，提案アルゴリズムの流れである．また，本研究における主な記号とその定義は表 1 に示す．

4. 2 ステップ 1：レジーム変化点の検出イベント時刻の集合 T のセグメント si にあたる部分集合

Ti = {t | t′is < t < t′ie ，t ∈ T ，si = {t′is ，t′ie }} を入力とし，レ+m∑log∗ (|si |) −

i=1

m
∑

Li

(7)

i=1

分割候補点を採用するかを判定するために，2 つのセグメント

sf , sb に分割した場合としていない場合の判定コストを比較す
る．分割した場合の判定コストが分割をしない場合の判定コス
トより小さいとき，分割を行う．

ジーム変化点の候補を検出することで，分割するかどうかを判定する．このアルゴリズム（Algorithm 1）は分割候補点の検出と分割の判定の 2 つで構成されている．

4. 3 ステップ 2：レジームの推定
次に，分割点前後の 2 つのセグメント sf , sb それぞれのレ

4. 2. 1 分割候補点の検出

ジームを推定する．具体的には，各セグメントに対してレジー

まず，Ti における最適な分割点を検出する．Ti を k 回分割

ムパラメータ集合 Θ に保存されているレジームで表現可能で

し，各分割点において分割点前までの対数尤度 L1 ，分割点以あるか，もしくは新規レジーム θ r+1 として保存するべきかを

降の対数尤度 L2 を計算する．L1 と L2 の和が最大となる点を検証する．このアルゴリズム（Algorithm 2）は，セグメント

分割候補点とする．分割候補点にて分割された前後のセグメン
1：log∗ はユニバーサル符号長を示す．

Algorithm 1 PatternChangeDetection

Algorithm 2 RegimeInference

Input: Set of event times T = {t1 ，...，tn },Input: Set of event times T = {t1 ，...，tn },Set of parameters C = {m，r ，S ，Θ，F },Part of parameters {r ，Θ，F },Segment candidate si = {t′is ，t′ie },Candidate segments sf , sb

Candidate segment list Qs ,Output: Part of parameters {r，Θ，F }

log-likelihood list QL

1: for each segment sf , sb do

Output: Set of parameters C = {m，r ，S ，Θ，F },for θ j ∈ Θ do

2:

Candidate segment list Qs ,3:

Lj ← log-likelihood(θ j , Ti );log-likelihood list QL

4:

if Lj > Lmax then

1: Ti ← {t|t′is < t < t′ie , t ∈ T };5:

2: P ← Cut point f or dividing t′is to t′ie into k parts;

6:

3: for each pi ∈ P do// Equation 5

Lmax ← Lj ; θ best ← θ j ; jbest ← j;end if

7:

end for4:

Ti1 ← {t|t <= pi , t ∈ Ti }; Ti2 ← {t|t > pi , t ∈ Ti };8:

if Lmax − log-likelihood(Ti ) >= γ then5:

Li1 ← log-likelihood(Ti1 );// Equation 59:6:

Li2 ← log-likelihood(Ti2 );// Equation 5

10:

7:

if Li1 + Li2 > Lmax thenfi ← jbest ;else
Push θ r+1 into Θ; fi ← r + 1;

11:r ← r + 1;

8:

Lmax ← Li1 + Li2 ; pbest ← pi ;

12:

9:

Lf ← L i1 ; L b ← L i2 ;13:

end if

14:

Push fi into F ;10:

end if

11: end for

15: end for

12: sf ← {t′is , pbest }; sb ← {pbest , t′ie };16: return {r ，Θ，F }13: Pop si from S;
14: Push sf , sb into S;

Algorithm 3 Proposed Algorithm

15: C ′ ← {m + 1, r + 1, S ，Θ，F };16: if CostT (T ; C) > CostT (T ; C ′ ) then// Equation 7

17:// Algorithm 2

18:{r ，Θ，F } ← RegimeInference(T , {r，Θ，F }, sf , sb );19:

C ← {m + 1，r，S ，Θ，F };20:

Push sf , sb into Qs ; Push Lf , Lb into QL ;21: end if
22: return C = {m，r ，S ，Θ，F}, Qs , QL

sf , sb で同一操作を行うため，分割点前のセグメント sf を用いて説明する．
セグメント sf に対して，新規レジーム θ r+1 を用いた場合の対数尤度 (式 (5)) が，既存レジーム θ i ∈ Θ を用いた場合の対Input: Set of event time T = {t1 ，...，tn }Output: Set of parameters C = {m，r ，S ，Θ，F }1: s1 ← {t1 , tn }; T1 ← {t|t′1s < t < t′1e , t ∈ T , s1 = {t′1s , t′1e }};2: L1 ← log-likelihood(T1 );// Equation 5

3: Push s1 into Qs ;// Qs : Candidate segment list

4: Push L1 into QL ;// QL : log-likelihood list

5: while Qs is not empty do
6:i ← index of minimum L ∈ QL ;7:// Algorithm1

8:{C, Qs , QL } ← PatternChangeDetection(T , C, si , Qs , QL );9:

Pop si from Qs ; Pop Li from QL ;10: end while
11: return C = {m，r ，S ，Θ，F }数尤度に対して閾値 γ 以上である場合，新規レジーム θ r+1 を

sf にあたるレジームとし，レジームパラメータ集合 Θ に加える．閾値 γ 未満である場合，対数尤度が最も大きくなる既存レ
ジームをセグメント sf にあたるレジームとする．

4. 4 アルゴリズム
ここでは，イベント時刻の集合 T に対してステップ 1 およびステップ 2 を繰り返し適用するアルゴリズム（Algorithm 3）を示す．最初の入力としてイベント時刻の集合 T を 1 つのセグメント候補として扱い，各ステップを適用する．以後の入力は，最も対数尤度が小さいセグメント候補とし，各ステップを適用する．このとき，分割によって得られた 2 つのセグメント
候補をセグメント候補リストに格納する．ただし，ステップ 1
において分割を行わないと判定したセグメント候補はセグメン
ト候補リストから除き，最終的なセグメントとする．セグメン
ト候補リストが空になったとき，アルゴリズムを終了する．

5 実

験

本章では，提案アルゴリズムの有効性を検証し，その結果を示す．ここでは，以下の 2 種類の実験を行った．

•

人工データを用いたレジーム分類精度の検証•

Web データを用いたケーススタディ

また，ステップ 1 における分割回数 k を 2000，ステップ 2 における閾値 γ をデータ期間の日数の 0.3 倍として実験を行った．

5. 1 レジーム分類精度
レジーム分類精度の検証を行うために，時系列パターンに関して正解ラベルを持つ人工のイベントデータを用いる．

5. 1. 1 評 価 指 標
評価指標には，Macro F1-score を用いる．Macro F1-scoreは式（8）のように計算される．

提案⼿法
正解ラベル

イベント数 [/h]イベント数 [/h]

提案⼿法
正解ラベル

1000

1000
500
0
0

14

28

42

500
0
0

時間[day]

14

28

42

56

Autoplait
正解ラベル

イベント数 [/h]イベント数 [/h]Autoplait
正解ラベル

1000

1000
500
0
0

14

28

42

500
0
0

14

28

42

56

時間[day](a) 人工データ (i)70

時間[day](b) 人工データ (ii)

提案⼿法

提案⼿法
正解ラベル

イベント数 [/h]

正解ラベル
2000

イベント数 [/h]70

時間[day]

1000

1000
0
0

14

28

42

56

70

84

98

112

500
0
0

時間[day]14

28

Autoplait

42

56

70

84

70

84

98

112

98

112

時間[day]

正解ラベル

イベント数 [/h]イベント数 [/h]Autoplait

正解ラベル
2000

1000

1000
0
0

14

28

42

56

70

84

98

112

500
0
0

時間[day]

14

28

42

56

時間[day](c) 人工データ (iii)(d) 人工データ (iv)

図 4: (i)，(ii)，(iii)，(iv) に提案手法および Autoplait を適用したレジーム分類結果

1 ∑
1
1
1
N
+ recallprecision（表 2）から生成される複数のイベントデータを作成し，生成N

M acro F 1-score =

k

k

(8)

した複数のイベントデータを異なる組み合わせで結合するこkとで，評価用の人工データを作成する．各イベントデータの
ここで，N は正解ラベルのクラス数を示す．

5. 1. 2 比 較 手 法
比較手法では定間隔データを入力として扱うため，イベント
データを入力として扱えない．本実験では，イベントデータを定間隔データ（1 時間あたりのイベント数）に変換したデータ

日数は 14 日とする．イベントデータの組み合わせは [8] に従い，(i) 1,2,1 , (ii) 1,2,3,2,1 , (iii) 1,2,3,4,1,2,3,4 , (iv)

1,2,2,1,3,3,3,1 とした. さらに，ノイズとして全体のイベン
ト数の 10 パーセントになるように全区間を対象にした一様分
布から乱数を作成し，評価用の人工データに加えた．

を入力とした．提案手法の有効性を評価するために用いた比較手法は以下の通りである．

•

表 2: 4 種類の Hawkes 過程のパラメータ

K-means [9]：ユークリッド距離を用いた古典的なクライベントデータスタリング手法．クラスタ数は事前に指定されている．

µ

α

β

1

0.003

0.93 0.04

Autoplait [15]：レジーム間の遷移を表現するために隠

2

0.003

0.87

れマルコフモデルを多階層連鎖的に拡張した手法．レジーム数

3

0.003

0.82 0.01

やレジーム変化点などの事前情報なしにパターン抽出を行う．

4

0.003

0.6

•

0.1
0.5

5. 1. 3 データセット
提案アルゴリズムの性能を検証するために人工データを作成した．４種類の異なる Hawkes 過程のパラメータ {µ，α，β}5. 1. 4 結果

各データセットでの Macro F1-score を表 3 に示す．また，図4 は，(i)，(ii)，(iii)，(iv) に対して提案手法と Autoplait を適
シン・ウルトラマン シン・ウルトラマン
配信決定
配信開始
アイテムの
配信の感想
スマホゲームとのコラボ
商品化

用したレジーム分類結果の例である．ここで，K-means を用いたレジーム分類ではレジームの切り替わりが激しく，多量のセ提案手法は，レジーム分類結果の図から (ii)，(iii)，(iv) においてレジームの変化点を捉えて適切にセグメンテーションおよびレジーム推定ができたことがわかる．しかし，(i) においては両端のセグメンテーションは適切に行われているが，14 から

投稿数 [/h]

グメントが生成されたため，図示しない．

2000
1000
0
9/10

11/1

10/1

11/22

時間

28 の区間では正解ラベルは 1 つのセグメントであるのにもかかわらず複数個のセグメントに分割された．これは，イベント

図 5: #ウルトラマン を含むツイートの投稿時間数が少ない区間であることからノイズの影響を大きく受けたことや Hawkes 過程からの人工データの生成は確率的であること
から区間内でばらつきができてしまったことが考えられる．提参議院選挙期間

案手法は事前にレジーム数を指定せずに分割をしているため，

選挙前の⾏動 公⽰⽇ 投票⽇

法では，イベントデータを定間隔データに変換することでイベント時刻やイベント発生間隔の詳細な情報が欠落しており，イ
ベントの変化を適切に捉えることができず，評価指標の精度が投稿数 [/h]

このようなばらつきを新たなレジームに分類していた．比較手政治に関する発⾔

300
200
100

低くなった．特に，自己励起性をもったイベントデータはイベ

0
5/8

6/1

7/1

9/1 9/12

8/1

時間

ント数が密な区間と疎な区間が短い間隔で繰り返されるデータであることから，イベント時刻やイベント発生間隔の情報の欠

図 6: #麻生太郎 を含むツイートの投稿時間

落が大きく影響していたと考えられる．
22⽇

手法

(i)

(iii)

(iv)

K-means

0.375

0.331 0.165

0.335

Autoplait

0.434

0.606 0.410

0.565

提案手法

0.750

0.997 0.999

0.999

(ii)

投稿数 [/h]

表 3: Macro F1-score によるレジーム分類精度

22⽇

22⽇

22⽇

150
100
50
0
8/3

9/1

10/1

11/1

11/23

時間

5. 2 ケーススタディ

図 7: #ショートケーキの日 を含むツイートの投稿時間

提案アルゴリズムを Web データに適用した結果を示すこと
で，本手法の有効性を検証した．

ム，通常の時間帯は緑色のレジームとなっている．

5. 2. 1 データセット
数ヶ月にわたって収集されたハッシュタグが付与されたツイー
トの投稿履歴を用いる．データの詳細は表 4 に記す．

#麻生太郎のデータセット（図 6）では，中央の緑色のセグ
メントは第 26 回参議院選挙公示日から投票日の 1 週間後までであり，選挙期間を１つのセグメントとして捉えている．また，
後半 2 つの緑色のセグメントは統一教会関連の報道や沖縄県知表 4: Web データセット

事選の期間において沖縄が戦争に巻き込まれる可能性を示唆しハッシュタグ

期間

データ数#ウルトラマン

2022/9/10–11/22

232,819#麻生太郎

2022/5/8–9/12

20,233目され，投稿数が増加している．前半 2 つの黄色のセグメント#ショートケーキの日

2022/8/3–11/23

5,731

は選挙に関する投稿，後半の黄色のセグメントは直前の緑のセた発言，国葬問題に関して岸田首相に対し圧をかけた発言が注グメントにおける投稿が収束している期間である．

5. 2. 2 結果

#ショートケーキの日のデータセット（図 7）では，ショー#ウルトラマンのデータセット（図 5）では，赤色のレジー

トケーキの日が毎月 22 日であることから，毎月 22 日に投稿がムは，動画配信サイトにおいて新作映画（シン・ウルトラマ

急増するデータセットとなっている．毎月 22 日前後のセグメン）の配信が決定した時間と配信が開始した時間であり，同じントを類似レジームで取れていることから，同一パターンのイ影響による投稿を同じレジームとして捉えられている．配信開

ベント発生を同一レジームで捉えていることがわかる．

始後は，配信に関する感想が多くツイートされており，水色のレジームとして現れている．また，スマホゲームとのコラボやグッズの販売など，大きな影響が発生した際には黄色のレジー6 おわりに本研究では長期間のイベントデータに対して，複数の Hawkes
過程を用いたイベントデータのセグメンテーションおよびレ
ジーム推定を行うアルゴリズムを提案し，評価検証を行った．

Web 上には不定間隔にイベントが発生するデータが多くある
ことから，Web データのパターン抽出を行うには，不定間隔なデータを扱うことができるアルゴリズムが必要である．提案ア
ルゴリズムは，長期間のデータを意味ある部分系列に分解し，パターン抽出を行うレジーム分類の手法と，イベントデータのモデリングに用いられる点過程の１つである Hawkes 過程の組
み合わせで構成されている．イベントデータをより適切にモデリングを行うために Hawkes 過程の対数尤度を用い，モデリン
グの切り替わり点をイベント変化点としてセグメンテーションを行った．セグメンテーションの有効性を判定するために，最小記述長原理に基づいたコスト関数を設定した．また，セグメ
ンテーションを行うと同時に，レジーム分類を行うことで，イ
ベントデータを意味あるパターンに分類することを実現した．
実験では，人工データを用いたレジーム分類によって，提案ア
ルゴリズムの有効性を評価し，また，Web データであるツイー
トの投稿履歴を用いて，提案アルゴリズムが適切なレジームを推定しているかを検証した．

謝

辞本研究の一部は JSPS 科研費，JP20H00585，JP21H03446，

JP22K17896, 国 立 研 究 開 発 法 人 情 報 通 信 研 究 機 構 委 託 研
究 NICT 03501, 総務省 SCOPE JP192107004，JSTAIP 加
速 課 題 JPMJCR21U4，ERCA 環 境 研 究 総 合 推 進 費 JP-

MEERF20201R02, の助成を受けたものです．

文

献[1] H. Alvari and P. Shakarian, “Hawkes process for understanding the inﬂuence of pathogenic social media accounts,”
Proceedings of the The 4th International Conference on
Data Intelligence and Security, pp.36–42, 2019.
[2] E. Aramaki, S. Maskawa, and M. Morita, “Twitter catches
the ﬂu: detecting inﬂuenza epidemics using twitter,” Proceedings of the Conference on empirical methods in natural
language processing, pp.1568–1576, 2011.
[3] E. Bacry, I. Mastromatteo, and J.F. Muzy, “Hawkes processes in ﬁnance,” Market Microstructure and Liquidity,
vol.1, no.01, p.1550005, 2015.
[4] N. Du, H. Dai, R. Trivedi, U. Upadhyay, M. GomezRodriguez, and L. Song, “Recurrent marked temporal point
processes: Embedding event history to vector,” Proceedingsof the ACM SIGKDD Conference on Knowledge Discovery
and Data Mining, pp.1555–1564, 2016.
[5] N. Du, M. Farajtabar, A. Ahmed, A.J. Smola, and L. Song,“Dirichlet-hawkes processes with applications to clustering continuous-time document streams,” Proceedings of the
ACM SIGKDD Conference on Knowledge Discovery andData Mining, pp.219–228, 2015.
[6] H.S. Dutta, V.R. Dutta, A. Adhikary, and T. Chakraborty,“Hawkeseye: Detecting fake retweeters using hawkes process and topic modeling,” IEEE Transactions on Informa-tion Forensics and Security, vol.15, pp.2667–2678, 2020.
[7] P.D. Grünwald, I.J. Myung, and M.A. Pitt, Advances inminimum description length: Theory and applications, MITpress, 2005.
[8] D. Hallac, S. Vare, S. Boyd, and J. Leskovec, “Toeplitz inverse covariance-based clustering of multivariate time series
data,” Proceedings of the ACM SIGKDD Conference on
Knowledge Discovery and Data Mining, pp.215–223, 2017.
[9] J.A. Hartigan and M.A. Wong, “Algorithm as 136: A kmeans clustering algorithm,” Journal of the royal statisticalsociety. series c (applied statistics), vol.28, no.1, pp.100–108,
1979.
[10] A.G. Hawkes, “Spectra of some self-exciting and mutually
exciting point processes,” Biometrika, vol.58, no.1, pp.83–
90, 1971.
[11] A.G. Hawkes, “Hawkes processes and their applications
to ﬁnance: a review,” Quantitative Finance, vol.18, no.2,
pp.193–198, 2018.
[12] C. Huang, X. Wu, X. Zhang, C. Zhang, J. Zhao, D. Yin,
and N.V. Chawla, “Online purchase prediction via multiscale modeling of behavior dynamics,” Proceedings of the
ACM SIGKDD international conference on knowledge discovery & data mining, pp.2613–2622, 2019.
[13] R. Kobayashi and R. Lambiotte, “Tideh: Time-dependent
hawkes process for predicting retweet dynamics,” Proceedings of the International AAAI Conference on Web and Social Media, vol.10, no.1, pp.191–200, 2016.
[14] L. Li, B.A. Prakash, and C. Faloutsos, “Parsimonious linear ﬁngerprinting for time series,” Proceedings of the VLDB
Endowment, vol.3, no.1-2, pp.385–396, 2010.
[15] Y. Matsubara, Y. Sakurai, and C. Faloutsos, “Autoplait:
Automatic mining of co-evolving time sequences,” Proceedings of the ACM SIGMOD International Conference on
Management of Data, pp.193–204, 2014.
[16] T. Murayama, S. Wakamiya, E. Aramaki, and R. Kobayashi,“Modeling the spread of fake news on twitter,” Plos one,
vol.16, no.4, p.e0250419, 2021.
[17] Y. Ogata, “Statistical models for earthquake occurrences
and residual analysis for point processes,” Journal of theAmerican Statistical association, vol.83, no.401, pp.9–27,
1988.
[18] M. Okawa, T. Iwata, Y. Tanaka, H. Toda, T. Kurashima,and H. Kashima, “Dynamic hawkes processes for discovering time-evolving communities’ states behind diﬀusion
processes,” Proceedings of the ACM SIGKDD Conferenceon Knowledge Discovery and Data Mining, pp.1276–1286,
2021.
[19] M.A. Rizoiu, Y. Lee, S. Mishra, and L. Xie, Hawkes processes for events in social media, Frontiers of multimedia
research, 2017.
[20] V. Tozzo, F. Ciech, D. Garbarino, and A. Verri, “Statisticalmodels coupling allows for complex local multivariate timeseries analysis,” Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.15931603, 2021.
[21] Y. Wang, N. Du, R. Trivedi, and L. Song, “Coevolutionary latent feature processes for continuous-time user-item
interactions,” Proceedings of the Advances in Neural Information Processing Systems, vol.29, 2016.
[22] Q. Zhao, M.A. Erdogdu, H.Y. He, A. Rajaraman, andJ. Leskovec, “Seismic: A self-exciting point process model
for predicting tweet popularity,” Proceedings of the ACM
SIGKDD Conference on Knowledge Discovery and Data
Mining, pp.1513–1522, 2015.
[23] 近江崇宏, 野村俊一, 点過程の時系列解析, 共立出版, 2019.