# Event Detection from Time Series Data > [!abstract] 概要 > 近年、時間的に変化する現象を監視するセンサが生成する時系列データから、興味深いパターンを抽出するためにデータマイニング技術を用いることへの関心が高まっている。ほとんどの研究は、生のデータが何らかの方法で処理されてイベント列が生成され、そのイベント列から興味深いエピソードが採掘されると仮定してきた。センサの読み取り値がいつイベントを生成すべきかを決める規則が既知である場合もある。しかし、現象がよく理解されていない場合、そのような規則を述べるのは難しい。本論文の焦点は、そのような環境でのイベントの検知である。振る舞いが時間とともに変化し、質的に有意な変化とみなせる動的な現象を考える。我々が調べる問題は、振る舞いの変化が起こる時点を特定することである。統計学の文献では、これは変化点検知問題と呼ばれてきた。標準的な手法は、(a)発見すべき変化点の個数をあらかじめ決め、(b)連続する変化点の間の区間で曲線当てはめに用いる関数を決めるというものだった。本論文ではこの両方の次元について一般化を行う。時間区間にモデルを当てはめ、その区間をさらに分割すべきか、すなわち新たな変化点を含むかどうかを尤度基準で判定する反復アルゴリズムを提案する。本論文では、バッチ版とインクリメンタル版の両方の問題に対するアルゴリズムを示し、合成データと実データでその振る舞いを評価する。最後に、バッチアルゴリズムが検知した変化点を、視覚検査により人間が検知した変化点と比較した初期結果を示す。 ## 論文情報 - 題名: Event Detection from Time Series Data(PDF 上の題名。書誌上は "Event Detection for Time Series Data") - 著者: Valery Guralnik, Jaideep Srivastava(University of Minnesota, Department of Computer Science) - 会議: KDD-99(ACM、San Diego、1999 年 8 月)。DOI・arXiv ID は PDF から確認できない。 - 資金: NSF EHR-9554517、ARL DAKF11-98-P-0359 ## 概要 センサ監視で得た実数値の時系列から、現象の質的な変化点(イベント)を検知する手法を提案する論文である。従来の変化点検知は、変化点数と区間ごとの関数形(通常は線形などの定常なモデル)を事前に仮定していた。本論文は基底関数の集合(実験では 1, t, t², t³)から区間ごとにモデルを選び、尤度基準 −2 log L を最小化する分割を階層的に探索することで、この 2 つの仮定を外す。全データを使うバッチ版と、データ到着ごとに変化を判定するインクリメンタル版を示し、ミネアポリス周辺の高速道路ループ検知器データで人間の視覚検査と比較する。 ## 問題設定 - 時系列 y(t), t = 1..n を、k 個の区間に分けた区分モデル $y = f_i(t, w_i) + \epsilon_i(t)$ で表す。$f_i$ は区間 i の関数(パラメータ $w_i$)、$\theta_i$ が変化点、$\epsilon_i$ が誤差項である。関数形に制約は置かない。 - 変化点を事前指定した場合の尤度 L から、変化点が未知のときは −2 log L を最小化して最尤推定(MLE)する。不均一分散誤差なら $\sum m_i \log \sigma_i^2$、均一分散誤差なら $n \log(\sum \sigma_i^2)$ に相当する量を尤度基準 C とする。著者らは既知の事実がなければ均一分散を仮定する。 - 従来手法(Hawkins らの区分回帰)は、(a)定常で既知のモデルで現象を記述でき、(b)変化点数が既知である、という 2 つの仮定を置いていた。本論文はこの両方を外す。 - 動機の例は、高速道路の交通が軽い・重い・渋滞へ移る変化と、ボイラの通常・過熱の変化である。閾値規則が定めにくい現象では、生データからイベント列を導く系統的な手法が必要になる。 ## 提案手法 ### バッチアルゴリズム - 各区間について、基底関数集合から最良のモデルを選ぶ。モデル選択は線形回帰の leave-one-out 交差検証によるリスク推定を解析的に計算する方法を使い、再標本化の計算コストを避ける(基底クラスの上限次数は p−1)。 - 階層的な分割: まず全区間で $C(1,j) + C(j+1,n)$ を最小にする j\* を最初の変化点とする(各区間には最低 p 点が必要)。以後は各反復で、既存の各区間について最良の分割候補を求め、候補の中から尤度基準を最も下げる 1 点を採用する。この手順を停止基準まで繰り返す。 - 停止基準: 変化点を増やすと尤度基準は最初は大きく下がり、その後は安定し、偽の変化点が増えると再び上がる(図4)。反復 k と k+1 の値 $L_k, L_{k+1}$ について、$(L_k - L_{k+1})/L_k < s$ となったら停止する。s はユーザが決める安定閾値であり、s = 0% なら尤度基準が増え始めたときだけ停止する。 - 著者らは Hawkins らの階層的解法を、他の解法(Hawkins-Merriam、Guthery)より計算効率が高いために選び、その仮定を外した。手順の擬似コードは論文の Figure 1, 2, 3(階層手順、Find-Candidate、Find-Likelihood-Criteria)にある。 ### インクリメンタルアルゴリズム - 最後の変化点が $t_{k-1}$ のとき、$t_k$ から時点 $t_j$ までの新データで、分割した場合の最小尤度基準と分割しない場合の尤度基準を比べる。差が閾値 δ(尤度増加閾値)を超えたら変化点を報告して系列を空にする。差が小さいだけなら雑音による見かけの変化の可能性があるため報告しない。 - 過去の区間の尤度は前回の反復で計算済みなので、新しい点が加わる区間の分だけ再計算する。ただし変化点が長く出ないと計算が増えるため、直近 w 点のスライディングウィンドウを提案する。擬似コードは Figure 14, 15 である。 ## 新規性 - 変化点数と区間ごとの関数形の両方を事前に固定しない、変化点検知とモデル選択の同時解決。 - 回帰法とモデル選択法に依存しない枠組みである(基底クラスも多項式以外に、放射基底・ウェーブレット・フーリエなどが使えるとする)。 - バッチ版とインクリメンタル版の両方を示し、人間の視覚検査に対する定量比較(尤度比)を行った点。 - 事前モデルを要するベイズ的手法(Raftery、Carlin ら)と異なり、非ベイズで事前分布が不要である。 ## 実験設定 - 合成データ: 40 点のノコギリ波(高さ h が信号雑音比を決める。雑音は平均 0・分散 1 のガウス)。基底関数は 1, t, t², t³。正解区間は [1,9], [10,19], [20,29], [30,39] だが、境界点は前後どちらの区間に含めてもよい。 - 実データ: ミネアポリス・セントポール都市圏の高速道路ループ検知器の交通量(5 分間隔・24 時間・288 点)。V274, V287, V1101, V315 の 4 系列を使う。 - 人間との比較: V274 について 4 人の被験者に視覚検査で変化点を挙げさせる(指示は「現象が有意に変化した点」のみ)。S1・S2 は移動平均で平滑化したデータ、S3・S4 は元データを見た。アルゴリズムは平滑化なしの元データを使った。 - インクリメンタル版の評価: 80 点の 2 区間の直線 $f(t)$(変化点は 40、h は 10〜70)で、変化点の位置精度と検知までの遅れを見た。 ## 実験結果 - 合成データ(表1): s = 0% では h が 8 以上のとき偽陽性・偽陰性なしで全変化点を検知する。h = 5 では区間 [30,39] を [30,35], [36,39] に偽分割し、s = 5% に上げると偽分割が止まる。h = 2 では雑音が支配的になり、s = 5% でも正しい分割は得られない。s は雑音が小さいデータでは結果に影響しない。 ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig-table1-synthetic-results.png]] (Table 1. 合成データでの検知区間。左が s = 0%、右が s = 5%。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig05-sawtooth.png]] (Figure 5. 合成データのノコギリ波(雑音なし、h = 10)。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig04-likelihood-vs-changepoints.png]] (Figure 4. 変化点の個数に対する尤度基準。初期に急減し、安定したのち偽の変化点で増加に転じる。停止基準の根拠である。) - 交通量データ: 4 系列すべてで s = 0% の停止基準を満たした変化点を報告する。V274(図6)は変化点が直観と一致する。V287(図7)の区間 A は目視では変化点がありそうだが、尤度計算では変動が雑音と区別できないため 1 区間とされる。V1101(図8)の区間 B も同様に、見かけ上有意な局所極小が 1 区間に含まれる。逆に V315(図9)では C と D が別区間になるが、目視では 1 区間に見える。人間は直線的な区間に注目しがちであるためとする。 ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig06-v274.png]] (Figure 6. V274。検知した変化点が直観に一致する例。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig07-v287.png]] (Figure 7. V287。区間 A は目視では変化点がありそうだが 1 区間とされた。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig08-v1101.png]] (Figure 8. V1101。区間 B は局所極小を含むが 1 区間とされた。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig09-v315.png]] (Figure 9. V315。C と D は目視では 1 区間に見えるが別区間とされた。) - 人間との比較(Figure 10〜13、Table 2): S1 の分割はアルゴリズムに最も近い。S2 は 2 次、S3 は 3 次、S4 は線形のモデルで分割しているように見える。被験者間の食い違いが大きく、真の変化点を決めること自体が自明でないと著者らは結論する。各被験者の分割の尤度基準をアルゴリズムの値で割った比は 1.79, 2.04, 2.58, 1.77 で、アルゴリズムはいずれの被験者より統計的に良い。 ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig10-subject-s1.png]] (Figure 10. 被験者 S1(平滑化データ)の変化点。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig11-subject-s2.png]] (Figure 11. 被験者 S2(平滑化データ)の変化点。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig12-subject-s3.png]] (Figure 12. 被験者 S3(元データ)の変化点。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig13-subject-s4.png]] (Figure 13. 被験者 S4(元データ)の変化点。) ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig-table2-likelihood-ratio.png]] (Table 2. V274 での尤度基準の比。アルゴリズムを 1.0 とし、値が大きいほど悪い。) - インクリメンタル版(表3、正解の変化点は 40): h が大きいと検知位置は 37〜40 で、検知までの遅れは 2〜5 点と小さい。h が 20 以下になると位置が不正確になり、遅れも増える。δ = 35% では偽の変化点が出る。δ を 45% に上げても偽の変化点は消えず、h = 10 では真の変化点が消えた。バッチ版(s = 5%)は h = 10 でも 40 を検知し、雑音への耐性が高い。 ![[_attachments/1999__KDD__Event-Detection-for-Time-Series-Data/fig-table3-incremental-vs-batch.png]] (Table 3. インクリメンタル版(δ = 35%・45%)とバッチ版(s = 5%)の比較。) ## 考察 - バッチ版がインクリメンタル版より頑健なのは、全データに対して尤度を大域最適化できるためである。インクリメンタル版は将来のデータを持たないため局所最適化にとどまる。 - 尤度基準による検知は、(1)滑らかな曲線を折れ線に分割したがる人間の傾向に影響されない、(2)雑音が大きくても(信号を圧倒しない限り)扱える、という点で目視より頑健である、と著者らは主張する。ただし比較は被験者 4 人・系列 1 本に基づく初期結果である。 - ベイズ的手法との比較は今後の課題とする(事前モデルの設計と、事後分布計算の可解性が障壁)。 ## 強み / 弱点・課題 - 強み: 変化点数と関数形の事前指定が不要。基底関数・回帰法・モデル選択法を差し替えられる。尤度基準に基づく定量的な停止基準を持つ。 - 弱点・課題(本文より): 雑音が大きいと偽の変化点や見逃しが出る(h = 2 のバッチ、h ≤ 20 のインクリメンタル)。安定閾値 s と尤度増加閾値 δ をユーザが決める必要があり、決め方の指針が示されない。インクリメンタル版は変化点が出ない間の計算量が増える。 - 弱点・課題(評価の範囲、読み取り): 実データは交通量 4 系列で、人間との比較は V274 のみ・被験者 4 人である。正解が不明な実データでは尤度基準の良さが評価の唯一の指標になり、事象としての意味的な正しさは検証されていない。 ## 出典 - [[.raw/papers/1999__KDD__Event-Detection-for-Time-Series-Data.pdf]](§2 定式化、§3 バッチ、§4 評価、§5-6 インクリメンタル、§7 結論)