時系列異常検知SOTAサーベイ
3つの要点
✔️ 単変量時系列データの異常検知において機械学習、深層学習手法からSOTAサーベイ
✔️ 単発、連続異常には統計的手法が、コンテキストが絡んだ異常には、深層学習が優位
✔️ 多変量、マルチモーダルについては今後の調査を待つ
Anomaly Detection in Univariate Time-series: A Survey on the State-of-the-Art
written by Mohammad Braei, Sebastian Wagner
(Submitted on 1 Apr 2020)
Comments: Accepted by arXiv.
Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML)
code：
はじめに
時系列データの異状検知については、1979年の John Tukey以来研究し続けられています。統計的手法、機械学習に加えて、深層学習の手法も用いられるようになり、あまりに多くの手法の中で、場面に応じてどの手法を選ぶのがよいか指針が必要になっていると感じます。
このサーベイ論文では、単変量に限定してはいますが、統計的手法、古典的機械学習、深層学習から計20の手法を選び、異常検知の定義、データセット、評価指標を揃えたうえで、性能比較を行っています。
コンセプト定義
異常値と外れ値
異常値と外れ値は似通った概念ですが、それぞれにコンセンサスはありません。ここでは、異常値と外れ値は同じ意味を持つとし、次のようにしています。
異常値:一般的なデータ分布から顕著に乖離しており、異常値はデータ全体の中で、非常に小さい部分を形成している。
(学術的には、こういうスタンスしか取りえないでしょうが、実際には主要な分布の中で正常値／異常値を切り分ける必要もあります。例えば、複数の事象が因果関係を持ち、最終結果での正常／異常を中間事象での変動を見て判断しなければならない場合です。）
異常の種類
異常の種類を次のように分類しています。1) 単発異常(Point anomalies) : 1点のみトレンドからはずれても異常とみなす場合です。2) 連続異常(Collective anomalies):個々の値については異常ではないが、連続していると異常とみなせるケース。3) 状況依存異常(Contextual anomalies): 同じ値でも状況に応じて正常とされたり、異状とされたりします。
確率過程と時系列
確率過程は、Z(w, t)：wはサンプル空間、tは時点で表されるのに対し、時系列は時間にわたって継続的に測定された観測点の系列です。
時系列パターン
時系列データには次のようなパターンがあります。トレンドは時間経過により増加もしくは減少するパターンです。線形トレンド、非線形トレンドがあります。 季節性は周期的に行き来する変動です。サイクルは、周期が固定されず、1年以上のものをいいます。
レベルは系列の平均です。トレンドがある場合にはレベルが変動します。 定常性は時間間隔ごとに同じ特性（例えば平均値、分散、自己相関）を持ちます。 ホワイトノイズは確率過程です。時間とは相関がありません。
異常検知
時系列データの異常判定は、空間データの正常・異常判定とは異なり、あるデータ点は次のデータ点に影響を及ぼしていると考えます。従ってシーケンス上突然の変化は異常とみなされます。Aggarwalは、時系列予測に基づく異常検知、時系列の通常でない形状に基づく異常検知に分類しています。多くの統計的手法は前者、いくつかの機械学習は時系列のクラスタリング手法を用いています。
・教師あり、半教師あり、教師なし 異常検知
教師あり学習では、タイムスタンプに対して正常／異常のラベルを付けます。半教師あり学習では、正常値データのみを使って学習します。教師なし学習では、ラベルは使いません。広く使われている手法では、分布の3σを異常の基準にします。
選出した時系列データ異常検知手法
統計的手法での異常検知
Autoregressive Model (AR), Moving Average Model (MA), Autoregressive Moving Average Model (ARMA), ARIMA Modelは従来より時系列分析によく使われる手法です。（解説）
Simple Exponential Smoothing (SES)は1956年に提案されていますので古い手法ですが、あまり触れられていないので少し説明します。ここまでの手法が線形近似を行っているのに対して、SESでは指数関数重みを用いて非線形近似を行います。
$$X_{t+1} = \alpha X_t + \alpha (1 - \alpha )X_{t-1} + \alpha (1 - \alpha )^2 X_{t-2} + ... + \alpha (1 - \alpha )^N X_{t-N}$$
$$where \alpha \in [0, 1]$$
Double and Triple Exponential Smoothing (DES, TES)はSESの拡張版で、非定常性のモデリングを行います。DESはトレンドを平滑化するため、もう一つのパラメータβを追加し、TESはさらに季節性を制御するためパラメータγを追加します。
Time-series Outlier Detection using Prediction Confidence Interval (PCI)は２０１４年に発表された手法です。以前のデータに非線形の重み付けをします。$$ X_t = \frac{\sum_{j=1}^k \omega _ {t - j} X_{t - j}}{\sum_{j=1}^k X_{t - j}}$$
$$PCI=X_i \pm t_{\alpha , 2k-1} \times s \sqrt{1 + \frac{1}{2k}}$$
ここで、tはStudentのt分布係数、sは標準偏差、kはウィンドウサイズです。
古典的機械学習での異常検知
K-Means Clustering – Subsequence Time-Series Clustering (STSC)では、ウィンドウの長さwをγずつスライドさせながら、時系列データをベクトルの集合に変換したうえで、k-Meansを適用してクラスタリングしています。
Density-Based Spatial Clustering of Applications with Noise (DBSCAN)では、データ密度を考慮してクラスタリングしています。2011年、Celikらが時系列に適用しています。
Local Outlier Factor (LOF)は、k-nearesr neighborsと局所外れ値に着目したクラスタリングです。2015年、Oehmckeらが時系列に適用しました。
Isolation Forest(iForest)は、2008年にLiuらにより提案された、Isolation Treesのアセンブルで正常と異常の分離を図るものです。下図では、2回の分離で異常を検出しています。
One-Class Support Vector Machines (OC-SVM)はSVMをベースに1999年に提案された半教師あり学習です。学習には正常値のみを用います。時系列データは位相空間に投影、もしくはウィンドウで切り、ベクトル化したうえで2次元空間に投影するなどします。
Extreme Gradient boosting (XGBoost, XGB)はKaggleやKDDCupでよく用いられる手法です。主たる特徴は拡張性です。ツリー・ブースティングによる手法で、時系列データを回帰近似し誤差関数を求めます。誤差関数にユークリッド空間での最適化手法が適用できない関数が含まれているので、テイラー展開して、これを回避しています。
ニューラルネットワークでの異常検知
Multiple Layer Perceptron (MLP) をベースにしたNeural Network Autoregression Model(NNAR)では後れを持たせたデータ系列によりARIMAを模したモデルを作っています。入力のニューロン数がウィンドウサイズに対応します。
Convolutional Neural Networks (CNN)の時系列データへの適用の関心が近年高まっており、Munirらは下図のDeepAnTを提案しています。時系列のCNNにが1次元データを入力します。個々の例では、2セットのConvolution, Max poolingを使っていますが、この構造はデータセットの特徴に合わせて最適化します。比較評価では、バッチ正規化を挿入したものとも比較しています。
Residual Neural Network (Resnet)は、CNNにさらにResidual blockを持たせたもので、Wangらが2016年に時系列データに適用しています。データ数が少ないときには、オーバーフィットしてしまう問題があります。
WaveNetは少ない変数で、長い時間をモデル化できる特徴があります。Borovykhらは2017年に時系列データに適用しました。
Long Short Term Memory (LSTM) network, Gated Recurrent Unit (GRU)はもともと長期データ系列に適したモデルです。
Autoencoderについては、SakuradaとYairiが2014年に時系列データに適用しました。ウィンドウサイズwでベクトル化したうえでモデルに入力しています。半教師あり学習を行います。
実験
データセット
次の5種のデータセットを使用しています。UDはYahooサービスのネットワークトラフィックデータです。UD1が生データ。UD2はランダムに単発異常点を追加しています。UD3は季節性を含んだデータで、ランダムに異常点を追加しています。UD4は、変化点を持たせる加工を行っています。変化点でデータの平均が変動します。NYCTデータはニューヨーク市のタクシー利用のデータです。NYCマラソンなど5回の連続異常を含んでいます。
評価指標
AUCを主な評価指標としています。また、計算時間の比較も行っています。
結果
Yahooネットワークアクセスでーたについては、生データも、連続異常などを模した合成データについても統計的手法がおおむね優れた結果を出しています。LSTM, GRUがデータ形式の適正に反してそれほど結果がよくないと言えるでしょう。
タクシーの使用数のデータについては、長期に状況が変化するため、統計的手法では特徴をうまくとらえることができていません。K-means(STSC)を除くと機械学習でも芳しくなく、深層学習（特にLSTM, Wavenet)は良い結果を出しています。K-meansについては時系列データに適用することに対し、理論的な疑問が解決していないようで、条件によっては結果が異なることもあるかもしれません。
(Figure 18のタイトルが間違っているようです。グラフ上のタイトルが正しいです。)
一方、計算時間については、やはり統計的手法が有利です。リアルタイム性の高いシステム、エッジデバイスでの推論を行う場合には、このデータも参考にする必要があるでしょう。単位は秒です。Table 7は367モデルの総計とそれを割って１データ系列当たりの計算時間を示しています。
統計的手法の中でもARIMAは時間がかかっています。Wavenetでの推論は軽量です。
まとめ
単変数時系列異常検知について、統計的手法、古典的機械学習と深層学習にわたり２０の単変量解析手法について比較評価した論文を紹介しました。統計的手法まで含めた同一条件での比較は、この論文が初めてではないかということです。
実験の結果、統計的手法は機械学習や深層学習の手法に比べて、押しなべて良好なAUCを出し、学習、推論にかかる計算時間も短いことがわかりました。残念ながら、深層学習は時系列異常検知（点異常、集団異常）においては、まだ良い結果を叩き出せていません。一方、コンテキストによる異常については、いくつかの深層学習・機械学習手法が統計的手法よりは高いAUCを出しています。
このサーベイでは、単変量に限定されていましたが、実際の課題は多くの場合多変量データで構成されており、将来的には多変量異常検知あるいはオンライン異常検知、異種データ混合についての調査が期待されます。
この記事に関するカテゴリー
