変化点検出 ChangeFinder

はじめに

今回は、 『データマイニングによる異常検知 (山西健司著)』で解説されている ChangeFinder を紹介します。

ChangeFinder は、時系列データにおける値の急激な変化を、リアルタイムに検出することができる手法です。 この手法を用いることにより、例えば、トラフィック量の急激な増加や減少を、自動で検出することができます。

このレポートでは、ChangeFinder の特徴を紹介し、これを用いた変化点の検出例を示します。

ChangeFinder のスコアリング

アルゴリズム

ChangeFinder は、時系列データの各時点におけるスコアを算出し、 このスコアが高いほど、変化の度合が高いと判断します。

スコアは、AR モデルを使用した 2段階学習 (two-stage learning of time series models) に基づくアルゴリズムによって求められます。 図1 のデータを例に説明します。

../image/changefinder-original-data.png

図1: 時系列データ

まず第1段階の学習で、各時点における外れ値スコアを求めます (図2)。 外れ値スコアは、AR モデルで予測される値と実際の値とが、 どれくらい異なるかによって決まります。

次に、この外れ値スコアを平滑化 (smoothing) します (図3)。 平滑化は、直近の数時点1 の外れ値スコアを平均することによって行われます。 この平滑化により、ノイズに反応した外れ値スコアが除去されます。

次に、この平滑化したスコアの時系列データに対して2段階目の学習を行い、平滑化後の外れ値スコアを求めます (図4)。

そして最後に、平滑化後の外れ値スコアを再度平滑化して、最終的な各時点におけるスコアを求めます(図5)。

このように、平滑化を行ってノイズを除去する事により、本質的な変動のみを検出できるアルゴリズムになっています。

../image/changefinder-score1.png

図2: 1段階目の学習を行った後のスコア

../image/changefinder-score2.png

図3: 1回目の平滑化後のスコア

../image/changefinder-score3.png

図4: 2段階目の学習を行った後のスコア

../image/changefinder-score.png

図5: 最終的なスコア(2回目の平滑化後のスコア)

ChangeFinder の特徴

ChangeFinder では、時系列データに対し AR モデルを用いてモデル化し、 これに忘却型学習アルゴリズム2 を適用して学習します。 一般に AR モデルは、時系列データの定常性を仮定していますが、 ChangeFinder では、忘却効果を取り入れたアルゴリズムを用いることによって、 非定常な時系列データを扱えるようにしています。

このアルゴリズムの計算量はデータ数に対して線形オーダーに抑えられるため、 オンライン処理に向いていることが特徴としてあげられます。

ChangeFinder による検出例

統計・機械学習パッケージ CLML の ChangeFinder パッケージを使用して、変化点検出の実行例を示します。

データの準備

ここでは、的確に値の変化を検出できるか確認するため、人工的に時系列データを作成しました。

作成したデータでは、急激に値が変動したあと、しばらくその状態が継続するようにしています。 また、局所的に値が変動した時のスコアを確認するために、要素の値が前後の要素と大きく異なる時点を、3箇所に入れました。

作成した時系列データは、ファイル cf-sample.sexp に保存しました。 この時系列データをプロットしたものが、図6 のグラフの青線です。

では、CLML の ChangeFinder を実行するために、ファイル cf-sample.sexp を読み込んで CLML の時系列データ構造を作成します。

CHANGEFINDER(74): (setf ts
                    (time-series-data (read-data-from-file "cf-sample.sexp")))
#<TIME-SERIES-DATASET >
DIMENSIONS: Value
TYPES:      NUMERIC
NUMBER OF DIMENSIONS: 1
FREQUENCY:  1
START:      (1 1)
END:        (2503 1)
POINTS:     2503
CHANGEFINDER(75):

ChangeFinder の実行

この例では、時系列データの最初50個の要素を学習用データとして使用することにします。 最初の50個の要素で学習をした後、51個目以降の各要素に対するスコアを求めます。

CHANGEFINDER(75): (setf changefinder (init-changefinder (sub-ts ts :start 0 :end 50)))
#<CHANGEFINDER @ #x1002874f42>
CHANGEFINDER(76): (loop for p across (ts-points (sub-ts ts :start 50))
                      as new-vec = (ts-p-pos p)
                      collect (update-changefinder changefinder new-vec))
(-0.299051997082095 -0.3197614532381655 -0.1952868796385583
 -0.0827827102777017 -0.12042998715609494 -0.11938193791679175
 -0.12702316232642122 -0.3292904833094793 -0.34410638727875353
 -0.32248944257279855 ...)
CHANGEFINDER(77): 

検証

得られたスコアを、時系列データの各要素と合わせて、以下のグラフの赤線で示します。 また、これらの値を保存した cf-sample-result.csv も参照ください。2段階学習の各過程で得られたスコアは、 Appendix A を参照ください。

../image/cf-sample.png

図6: 実行結果

値の大きな変化に対してスコアは高くなっており、 急激に値が変化した時点を検出できていることがわかります。

その後、この状態が継続すると、スコアは低くなります。 これは、この状態が定常状態であると、学習したためです。

局所的に値が変動した点については、 その変動が小さい場合には (図中(1))、高いスコアは出ていません。 一方、変動が大きい場合には (図中(2),(3))、高いスコアが得られています。 この局所的な変動を「ノイズ」と判断すべきか「変化点」と判断すべきかは、 ChangeFinder を適用する場面によって異なります。

まとめ

このレポートでは、ChangeFinder の特徴と検出例を示しました。

ChangeFinder は、文字どおり、急激に値が変化した点を検出する手法であり、 Kleinberg のバースト検知 のように、 バーストが継続している期間を得ることができる手法ではありません。 しかし、例えばディスクの使用量のように、 一旦値が増えた後は、それが定常状態になるシステムもあります。 ChangeFinder は、こういった、あらかじめ定常状態を設定できないシステムに対して、 適した手法と言えます。

このことに加え、ChangeFinder はリアルタイムに値の変化を検出することができるため、 「スコアが高くなったことをトリガーに、オペレータに異常を通知する」 という機能を実現することができます。 このような即時性が求められる監視システムに対して、有効な手法であると言えるでしょう。

Appendix A

ChangeFinder による検出例 の実行の際に、 2段階学習の各過程で得られたスコアを示します。

../image/cf-sample-original-data.png

図7: cf-sample の時系列データ

../image/cf-sample-score1.png

図8: 1段階目の学習を行った後のスコア

../image/cf-sample-score2.png

図9: 1回目の平滑化後のスコア

../image/cf-sample-score3.png

図10: 2段階目の学習を行った後のスコア

../image/cf-sample-score.png

図11: 最終的なスコア(2回目の平滑化後のスコア)

Reference

  • 山西健司, "データマイニングによる異常検知", 共立出版, 2009年, ISBN 9784320018822

Footnotes:

1 文献 では、直近の 5 から 10 時点の間の外れ値スコアを用いて平滑化することが多いが、 ChangeFinder を適用する場面に応じてチューニングすべきであると、記されています。 この値が小さい場合は、局所的な変動に反応しやすくなります。 一方、大きい場合には、スコアが高くなるまでに時間を要するため、遅れが生じます。

2 文献では、SDAR (Sequentially Discounting AR model learning) アルゴリズムと呼んでいます。

Author: 数理システム知識工学部

Date: 2013-07-02T15:02+0900

Generated by Org version 7.9.2 with Emacs version 24

© Mathematical Systems Inc. 2013