統計的変化点検出の手法

ログデータの異常検知を行う必要が発生したので、変化点検出の統計的な手法をざっくりと調べてみた。

偏差の累積和による方法

各データ点に対して標本平均との偏差の累積和を求め、これが最も大きくなる点を変化点とする方法。

手順は下記の通り。

1. 系列全体の平均値(標本平均)を計算して、各点について平均値との差を求める
2. 平均値との差の累積和を計算し、絶対値が最大になる点を変化点とする。
3. 変化点によって区切られた各区間について、1,2を再帰的に繰り返す。

平均値でなく分散を使うバージョンもある。

特徴

• 1次元のデータ列に適用可能。
• 変化していない部分のデータは同一の確率分布に従い、かつ観測値はすべて互いに独立であることを仮定。
• 上記を満たしていれば、データが特定の分布に従うことを仮定しない。
• もちろんデータの独立性が仮定できなければ使えないので、ログのような時間相関のありがちなデータにおいて使える場面は限定的。

参考/実装

• Change-Point Analysis:A Powerful New Tool For Detecting Changes
• Change Point Analysis Rによる実装1
• CPAN - Package changepoint Rによる実装2

統計的検定に基づく手法

自己回帰モデル、多項式回帰モデルといった自己相関を表すデータ生成モデルを使い、「全てのデータ」に対してまとめてフィッティングを行った場合と、「ある点より前のデータ」と「ある点より後のデータ」に対して別々にフィッティングを行った場合とで、得られる予測値と観測値との誤差が変化しているかどうかを検定し、有意に変化している場合、この点を変化点とする手法。

特徴

• AR過程などに基づいてデータが生成されていることを仮定
• ARモデルを使う場合、事前に次数を決定する必要がある。
• データNに対する処理時間は$O(N^2)$

「データマイニングによる異常検知」でも言及されている手法だが、全ての候補点に対していちいち統計的検定を行うため計算量が大きくなり、オンライン処理に対して実用的でない。
(これをそのまま実装している例も見つけらなかった・・・。)

参考

• Rで計量時系列分析：AR, MA, ARMA, ARIMAモデル, 予測

ChangeFinder

• 統計的検定に基づく手法の応用。ARモデルを用いた時系列モデルの2段階学習。
• ARモデルのパラメータ推定にオンライン忘却アルゴリズムであるSDARを使うことで、計算量をデータ数に対して線形オーダーに抑える。
• 第1段階学習では観測値の外れ値スコアを計算し、これを平滑化してから第2段階学習に入力する。
  • これによってノイズによる変動を除去することができる。

特徴

• SDARを使った場合、データ数に対して線形時間で処理可能
• SDARの次数、忘却係数に加えてスムージングの期間を決める必要があり、こいつらのチューニングが結構センシティブ。

応用

SDARを別のモデルに置き換えたバージョンも提案されている。

• ARIMAモデル (参考リンク参照)
  • SDARに比べてパラメータにセンシティブでないが、オンラインアルゴリズムでなく毎回フィッティングを行うため計算量が大きい。
• カルマンフィルタ: shima_xさんによる記事 カルマンフィルタで変化点検知

参考/実装

• yokkunsの日記 異常検知（変化点検出）のパッケージを作ってみた SDARでなくARIMAモデルを使った実装
• @yokkuns:時系列分析による異常検知入門 http://www.slideshare.net/yokkuns/ss-8425312
• 変化点検出 ChangeFinder NTTデータ数理システムによるレポート
• http://argmax.jp/index.php?changefinder Python実装。SDARを使ったChangeFinderと、ARIMAを使ったChangeFinderARIMAが利用可能。
• fluent-plugin-anomalydetect 作りました Fluentdプラグインとしての実装。SDARを使用。