# Anomaly Detection in Streams with Extreme Value Theory 論文情報: KDD 2017 (2017年8月13-17日、カナダ・ハリファックス)。DOI: https://doi.org/10.1145/3097983.3098144 著者: [[Alban Siffer]]([[Amossys]], [[IRISA]], [[Inria]]) / [[Pierre-Alain Fouque]]([[Univ. Rennes 1]], IUF, [[IRISA]]) / [[Alexandre Termier]]([[Univ. Rennes 1]], [[Inria]], [[IRISA]]) / [[Christine Largouet]]([[AgroCampus]], [[Inria]], [[IRISA]]) 実装リポジトリ: https://github.com/Amossys-team/SPOT ## 概要 時系列の異常値(外れ値)検知において、従来手法は「分布の仮定」か「手動閾値設定」を必要としていた。本論文は**極値理論(Extreme Value Theory, EVT)** の Peaks-Over-Threshold(POT)アプローチを高スループット・ストリーミング環境に適用し、これらの制約を取り除く2アルゴリズム SPOT と DSPOT を提案する。主要パラメータは偽陽性率の上界を制御するリスクパラメータ q のみである。 ## 問題設定 ストリーミング時系列 $(X_t)_{t \geq 0}$ に対し、「任意の $t$ で $P(X_t > z_q) < q$ となる閾値 $z_q$」を自動的かつ継続的に求めたい。制約: - データを複数回スキャンできない(ストリーミング制約) - 分布を事前に仮定できない(オープン環境) - 新しい概念(コンセプトドリフト)が生じる可能性がある 従来の距離ベース手法(STORM, CORM, DBOD-DS)は多次元・カテゴリ特徴に対応するが手動閾値を要求する。分布仮定を置く手法(ガウスモデル等)は未知分布には適用困難だった。 ## EVT と POT アプローチ ### 極値分布理論の核心 Fisher-Tippett-Gnedenko の定理: 弱い条件のもとで、分布 $F$ から得られる極値の分布は原分布の形状にかかわらず**一般化極値分布(GEV)** $G_\gamma$ に収束する。テールの形状を決める極値指数 $\gamma$ は: | テール形状 | $\gamma$ の値 | 典型例 | |---|---|---| | 重テール($P(X>x) \sim x^{-1/\gamma}$) | $\gamma > 0$ | フレシェ分布 | | 指数テール($P(X>x) \sim e^{-x}$) | $\gamma = 0$ | ガンマ分布 | | 有界テール($P(X>x) = 0, x \geq \tau$) | $\gamma < 0$ | 一様分布 | ### Peaks-Over-Threshold(POT) Pickands-Balkema-de Haan の定理: 閾値 $t$ を超える超過量 $X - t$ の分布は、$t$ が十分大きければ**一般化パレート分布(GPD)** $\mathrm{GPD}(\gamma, \sigma)$ に収束する。これにより $z_q$ を: $z_q \approx t + \frac{\hat\sigma}{\hat\gamma}\left(\left(\frac{qn}{N_t}\right)^{-\hat\gamma} - 1\right)$ で推定できる($N_t$: 閾値 $t$ を超えたピーク数, $n$: 総観測数)。 パラメータ推定は**最尤推定(MLE)**を Grimshaw のトリックで効率化する。2変数最適化問題を1変数のスカラー方程式 $u(x)v(x) = 1$ に帰着し、さらに命題 4.1 によって解探索区間を縮小することで計算コストを削減する。 ## 提案アルゴリズム ### SPOT(定常ストリーム向け) 1. **初期化**: 最初の $n \approx 1000$ 件で POT 推定を実行し、初期閾値 $z_q$ と内部閾値 $t$(98パーセンタイル)を取得。 2. **ストリーム処理**: 新規観測 $X_i$ ごとに: - $X_i > z_q$: 異常として記録(モデル更新しない) - $t < X_i \leq z_q$: ピークとして峰集合 $Y_t$ に追加し、$z_q$ を再計算 - $X_i \leq t$: 正常として観測数 $k$ を増加 3. **メモリ効率**: ピーク集合のみ保持(全系列不要) ### DSPOT(ドリフト対応版) 局所移動平均 $M_i = \frac{1}{d}\sum_{k=1}^{d} X^*_{i-k}$($X^*$ は最近 $d$ 件の正常値)を算出し、差分 $X'_i = X_i - M_i$ に SPOT を適用する。追加パラメータはウィンドウサイズ $d$ のみ。異常値はウィンドウ更新から除外するため、異常が局所モデルを汚染しない。 ## 実験結果 ### 合成データ(信頼性検証) $n = 300 \sim 5000$、$q = 10^{-3}$ のガウスホワイトノイズ 15000 件で 100 回試行。誤差率は $n$ の増加とともに収束し、$n \approx 1000$ で十分な精度を達成。$n$ はさほど重要なパラメータではない。 ### MAWI データセット(侵入検知) ネットワークキャプチャ(NetFlow 変換済み、50 ms ウィンドウ)で SYN フラッド攻撃を検知。真陽性率 86%、偽陽性率 4% 未満。ROC 曲線から $q \in [10^{-3}, 10^{-5}]$ の範囲で高い TPr と低い FPr の両立を確認。 ### 宇宙物理データ(ACE 衛星磁場) DSPOT を $q = 10^{-3}$, $d = 450$ で適用。ノイズの多い非定常信号でも局所ドリフトを追跡しつつ異常峰を検知。 ### 株価データ(EDF) 2017年2月9日のフラマンビル原子力発電所爆発事故による株価急落を DSPOT が検知($q = 10^{-3}$, $d = 10$)。リアルタイムアラート用途に有効。 ### 計算性能 Python3 実装、Intel i5-5300U / 8GB RAM のノートPCで平均 350〜590 µs/反復(1000 件/秒超)。メモリ使用量はピーク集合のみで全観測の約 2〜4% 程度。 ## 技術的貢献 1. **EVT のストリーミング初適用**: EVT を高スループットストリームの外れ値検知に初めて適用(著者らの主張)。 2. **Grimshaw トリック改良**: 解探索区間の理論的縮小(命題 4.1)と L-BFGS-B を用いた数値根探索の安定化。 3. **DSPOT のドリフト吸収**: 非連続ウィンドウ $W^*$(異常値を含まない)により汚染なしに局所挙動をモデル化。 4. **単一パラメータ設計**: $q$ のみで偽陽性率を制御でき、閾値の手動設定が不要。 ## 他のソースとの関連 - [[@ 2020__ICSE-SEIP__Understanding and Handling Alert Storm for Online Service Systems|Zhao+ (ICSE-SEIP 2020) — アラートストーム]] は EVT ベースの異常検知器として SPOT/DSPOT の枠組みを採用している。本論文がアラートストーム分野における EVT 閾値学習の根拠論文となっている。 - 提案アルゴリズムは「アラートストーム検知」文脈では、発報量の急増を無設定で検知する基盤として機能する。 ## 未解決・今後の方向 著者自身が指摘する拡張課題: - 多変量ケースへの拡張(現在は単変量のみ) - 独立同分布(iid)でない観測への適用(自己相関を持つ時系列等) - 自動閾値設定のビルディングブロックとしての活用(複合システムへの組み込み) ## 出典 - PDF: `[[.raw/papers/kdd17p1067.pdf]]` - DOI: https://doi.org/10.1145/3097983.3098144 - 実装: https://github.com/Amossys-team/SPOT