Takeuchi, J., and Yamanishi, K.: A Unifying Framework for Detecting Outliers and Change Points from Time Series, IEEE Trans. on Knowledge and Data Eng

Size: px

Start display at page:

Download "Takeuchi, J., and Yamanishi, K.: A Unifying Framework for Detecting Outliers and Change Points from Time Series, IEEE Trans. on Knowledge and Data Eng"

ゆめじひろなが
4 years ago
Views:

1 Takeuchi, J., and Yamanishi, K.: A Unifying Framework for Detecting Outliers and Change Points from Time Series, IEEE Trans. on Knowledge and Data Engineering, 18(4), pp , 年度論文ゼミ # 中西航東京大学大学院工学系研究科社会基盤学専攻

2 論文全体の構成 2 1. Introduction 2. Problem Setting :: 本論文の主題 Change Point Detection の位置づけ 3. Two-Stage Learning for Change Point Detection ::Change Point Detection の定式化 4. Other Methods :: 以下での比較用に別の手法を紹介 5. Simulation :: 人工データに対する適用と分析 6. Experiment with Real Data :: 実データに対する適用 7. Concluding Remarks

3 1. 時系列データからの検出 3 時系列データの変化には外れ値の検出変化点の検出の 2 種類がありともに興味を引く問題となってきている何かの値外れ値変化点? 時刻

4 1. 時系列データからの検出 4 時系列データの変化には外れ値の検出変化点の検出の 2 種類がありともに興味を引く問題となってきている例 ) ネットワークのアクセスログ通常状態をデータから学習し新たに入ってくるデータがそこからどの程度はずれているか = 外れ値 = 異常検出一方で膨大な外れ値データが入ってきた場合は統計的に通常状態自体が変化しているととらえたいこれまで外れ値検出と変化点検出は別個に行われてきたこれを統一した枠組みで記述したい

5 1. 著者らの既往研究との関係 5 従来 : 統計的な外れ値検出手法 ( 時系列データに未対応 ) これに対し時系列データに対応変化点の検出にも対応の 2 点が本研究の手法具体的には Auto Regression モデルを従来手法に導入する外れ値検出と変化点検出を 2 段階の検出ステップに分離し逐次同時に処理するより具体的にはデータ単体の外れ度合いの計算とデータの移動平均の外れ度合いの計算を行うこの手法を ChangeFinder と命名する

6 1. 関連する研究 ( の課題 ) 6 外れ値検出は時系列データへの対応が不完全時系列を考慮した AR モデルはデータの定常性を仮定非定常な時系列データを扱う方法として AR モデルの ( 共 ) 分散に時間変化を持たせる方法割引率の導入による一種の最尤推定 ( 本研究のアプローチ ) 事前に変化点の個数が分かっていることを前提変化後のデータがある程度蓄積されてから変化点が検出より一般化した適用可能性の高い手法の構築

7 2.Change Point Detection では何を行うか 7 Change Point とはデータの属性が急激に変化する時間軸上の点 ( 時刻 ) のことで緩やかな変化は対象としないこの時刻 t=a を検出するのが Change Point Detection ( 中西注 : 緩やかな変化に対しては動的パラメータの逐次推定やファジィシステムの適用が行われているように思われる ) 何かの値 Change Point? a 時刻

8 2.Change Point Detection では何を行うか 8 ある確率過程 p に基づいて d 次元の実数ベクトル x t が t=1 から順次得られる p(x t x t-1 ) は x 1 から x t-1 が得られたもとでの x t の分布このときある時刻 t=aがchange Pointならば pがある時刻 t=aを境にp (1) とp (2) という2つの ( 異なる ) 確率密度関数に分離されるという想定が出来る x p1 Change Point? p2 a 時刻

9 2.Change Point Detection では何を行うか 9 このときカルバックライブラー情報量 p D p p lim E 2 ln n p n p 2 1 x x n n E p :p の期待値たとえば有意な Change Point である t=a では D の値がとても大きいというような想定もし p (1) と p (2) が i.i.d. を満たす確率密度関数ならば p (1) のもとで x a+1 から x a+m までの一連の x が得られる確率は p (2) のもとで得られる確率の exp(-md) 倍に比例するところで上記の方法では唯一の変化点 t=a の存在とその前後での p (1) と p (2) の定常性を仮定しているこれに対し本研究は複数の変化点に対応し変化点を出来る限りリアルタイムで検出することを目的としている

10 2.Change Point Detection では何を行うか 10 具体的には以下の 2 つを扱う Jumping mean( 平均の変動 ) p (i) が i.i.d. の 1 次元正規分布で平均 μ (i) 分散ともに σ 2 のとき D p p μ (1) -μ (2) が大きいとき Jumping mean 型の変化点 Jumping variance( 分散の変動 ) p (i) がi.i.d. の1 次元正規分布で平均ともに0 分散がσ (i)2 のとき 1 ln p 2 D p σ (1)2 と σ (2) 2 が大きく異なるとき Jumping variance 型の変化点

11 3.ChangeFinder 11 2 段階学習を行う x t : 時系列データ p:x の時系列変化を表す ( 条件付き ) 確率密度関数 y t :p t-1 のもとでの x t の合致度の移動平均 q:y の時系列変化を表す ( 条件付き ) 確率密度関数データ x t が入る確率密度関数 p t を学習 ( 更新 ) p t-1 の x t についての表現力を計算 Outlier Detection p はどんな関数でも良いここでは AR モデルを導入 ( 後述 ) スコアリング方法として 2 種類提案 ( 後述 ) 幅 T の窓でスコアの移動平均を算出この時系列を y t とする y t を表現する確率密度関数 q t を学習 ( 更新 ) q t-1 の y t についての表現力を計算 Change Point Detection

12 3.Outlier Detection 12 Scoringの方法 Score t1 1. 対数損失 xt log pt 1 xt x 情報理論の立場では p t-1 に従って生成されるバイナリデータをもとにx t をエンコードするのに必要な記述長 2. 二次損失データ x t が入る確率密度関数 p t を学習 ( 更新 ) p t-1 の x t についての表現力を計算 Outlier Detection p はどんな関数でも良いここでは AR モデルを導入 ( 後述 ) スコアリング方法として 2 種類提案 2 t1 ˆ, ˆ t t t t = t1 t Score x x x x xp x x dx Score(x) が大きいとき外れ値の可能性が高いということ

13 3.Outlier Detection 13 データ x t が入る確率密度関数 p t を学習 ( 更新 ) p t-1 の x t についての表現力を計算 p はどんな関数でも良いここでは AR モデルを導入スコアリング方法として 2 種類提案 ( 前述 ) pにarモデルを導入初期値の平均が0であるようなd 次元ベクトルz t が k 次のARモデルに従う k z A z ε, ε N 0, Σ t i ti i1 x z μ t t t1 x t-k からx t-1 までの系列データを xt kと表記すれば p t xt xtk : θ exp k /2 1/2 xt w Σ xt w 2 Σ 2 k i1,,...,,, w A x μ μ θ A A μ Σ i ti 1 k T Outlier Detection

14 3.Outlier Detection 14 さきほどの式展開 x z μ t k t i1... w A x μ μ A x μ A x μ A x μ μ i ti 1 t1 2 t2 k tk xt w zt A1zt 1 A2zt2... Akztk ε N 0, Σ z t についての回帰式 p t xt xtk : θ exp k /2 1/2 xt w Σ xt w 2 Σ 2 T Sequential Discounting AR learning による θ の推定 : 割引率 r を導入した以下の式を最大化する θ t x x θ i1 ti i 1 r log p 1 i,

15 3.Outlier Detection 15 Sequential Discounting AR learning による θ の推定量 := は代入 ( 更新 ) であり逐次推定を行うという意味 μ の推定量 C: 計算上設定する変数自己共分散関数と呼ばれる Yule-Walker の方程式これを解くと A の推定量が得られる A の推定量を代入すると x と Σ の推定量が得られる

16 3.Change Point Detection 16 幅 T の窓でスコアの移動平均を算出この時系列を y t とする y t を表現する確率密度関数 q t を学習 ( 更新 ) q t-1 の y t についての表現力を計算 Score(x) を元に新たな時系列データ y を生成いわゆる移動平均外れ値 x の前後での y の値の変化は小さく変化点 t の前後での y の値の変化は大きいことが想定される x t p t と同じ要領で y t から q t を生成する p t と同じ要領で q t について Scoring し Score(t) とする T: 小変化点検出高速外れ値との峻別能力低い T: 大変化点検出低速検出精度高い Change Point Detection y t t 1 Score( x ) T i t T 1 i

17 4. 比較手法 17 GS: Guralnik and Srivastava(1999) に基づく手法誤差 ( 残差 ) の平方和の最小化 GS では多項式による近似も行っているが今回は線形近似 SC: GS に AR モデルを導入した手法確率的コンプレキシティ (Stochastic Complexity) 最小化 t 確率密度関数 t tk と系列データが与えられたとき確率的コンプレキシティ t1 p x x, θ は与えられた x( 時刻 u から t-1 まで ) のもとでの最尤推定量変化点 t=a のあと毎時刻 t=b でを計算し閾値以上となれば t=i を変化点として検出変化点が検出されたら i を a として繰り返す t=i で区間を分割し異なる θ による p を用いた方が確率的コンプレキシティが低下するとき表現力が高いモデルだということ x u t t t1 t1 u log t tk, u I x p x x x iu t b 1 t a 1 tb i tb t min t i1 I x I x I x a i: t a i t b a

18 5. Simulation データ作成 18 x t :2 次の AR モデルに従って生成 y t :3 次の AR モデルに従って生成 Score(x): 対数損失で計算 Score(y): 二次損失で計算移動平均の幅 T=5 x a x a x t 1 t1 2 t2 t 2 a 0.6, a 0.5, N 0, 1 2 割引率 r=0.02 変化点は t=1000x(x=1,2,,9) に設ける 3 種類のパターンで試行

19 5. Simulation: Jumping mean with constant variance 19 t=1000x(x=1,2, 9) の 9 回平均を Δx=10-x 変化 ( 加算 ) Δx を change size と呼ぶ σ 2 =1( 一定 ) x 回目の変化前後での KL 情報量は 2 x 2 t=6000 まで検出できているこのとき K(x) a K x x x 2 2 i1 i 2 2 元データ Score

20 5. Simulation: Jumping mean with varying variance 20 t=1000x(x=1,2, 9) の9 回平均をΔx=1 変化 ( 加算 ) t /10000 時間経過とともにに増加 x 回目の変化前後での KL 情報量は x 2 K x t=6000 まで検出できているこのとき K(x) 6.4 元データ Score

21 5. Simulation: Jumping variance with constant mean 21 平均は 0 で一定 t=1000x(x=1,2, 9) の 9 回 σ 2 を 1.0 と 9.0 とで行き来させる元データのときの KL 情報量のときの KL 情報量 0.65 分散が増大するときは変化点が検出できているが減少するときは検出できていない Score

22 5. Simulation: Quantitative Evaluation 22 Activity Monitoring[Fawcett and Provost, 1999] に基づき検出力を検出速度と誤検出率の観点から評価 Score に対して設ける閾値によって検出力が変動する Effective Alarm と False Alarm Rate とを軸とした ROC 曲線のようなことを考える Effective Alarm: 変化点から20タイムステップ以内に検出 * t* を真の変化時刻 tを検出時刻としたとき benefit t t t Alarm Policy: 最新の Alarm から 20 タイムステップ以内の Alarm は無視 1 / 20 SCやGSの場合はt* より前の時点で検出することがあるので benefit t 1 t t /10 とする * False Alarm Rate:False Alarm/ 全 Alarm

23 benefit(t) の平均 5. Simulation: Quantitative Evaluation 23 Jumping mean with constant variance データセットは前出同様ただし change size は 5 で固定している CF の性能が高い誤検出率

24 benefit(t) の平均 5. Simulation: Quantitative Evaluation 24 Jumping mean with varying variance データセットは前出同様誤検出率 CF よりも GS の性能が高いただし分散が徐々に縮小していくパターンを試すと CF のみが変化点を検出できた ( と書いてあるがグラフは無い )

25 benefit(t) の平均 5. Simulation: Quantitative Evaluation 25 Jumping variance with constant mean データセットは前出同様誤検出率 CF の性能が高いただし分散が小さくなる (KL 情報量が小さい ) 変化点を検出できていないので benefit が低いそもそも KL 情報量に依存する手法であることの課題

26 5. Simulation 26 考察定性的には CF は SC や GS よりも変化点検出に遅れの出にくい方法といえる SC や GS で False Alarm Rate をあげても Benefit が低下することがあるこれは Alarm の発生が真の変化点よりも早すぎることが多くなるため CF は SC や GS に匹敵する検出力を持っている特に 3 番目のデータセットと 2 番目のデータセットの分散を小さくしていくパターンでは相対的に高性能といえる計算のオーダーは SC や GS が O(n 2 ) であるのに対し CF は O(n) であるためリアルタイム分析には CF が適している

27 6. 実データへの適用 27 DoS 攻撃の実例に適用パラメータ設定は Simulation と同様 Scoring は対数損失 CF により変化点を正しく検出できた 8 月 11 日の Alarm は現実のトレンドマイクロの発表より 1 時間 44 分早く 8/18 の Alarm も約 1 日の遅れに留まっている SC や GS でも変化点は検出できるが CF より検出時刻が遅い

28 7. まとめ 28 成果 2 段階の学習プロセスからなるChangeFinderの開発 ChangeFinderへのARモデルとSDARモデルの適用外れ値検出と変化点検出の統合的な枠組みの構築いくつかのデータによる挙動の検証課題 Tの最適化データセットからのT 自体の学習分散が減少する変化点の検出法 ARIMAモデルや状態空間モデルへの拡張隠れマルコフモデル等との統合

様々なミクロ計量モデル†

様々なミクロ計量モデル† 担当 : 長倉大輔 ( ながくらだいすけ ) この資料は私の講義において使用するために作成した資料です WEB ページ上で公開しており自由に参照して頂いて構いませんただし内容について一応検証してありますがもし間違いがあった場合でもそれによって生じるいかなる損害不利益について責任を負いかねますのでご了承ください間違いは発見次第継続的に直していますがまだ存在する可能性があります 1 カウントデータモデル