k近傍法による時系列データの異常検知

こんにちは、エンジニアのtetsuです。

k近傍法は主に分類問題で機械学習・パターン認識の領域で使われている手法です（回帰でも使えますが、あまり見ない気がします）。
今回はこのk近傍法を時系列データの異常検知に適用する方法をご紹介します。

また、k近傍法を動画の異常検知に適用した事例が記事になっておりますので、こちらもあわせてご覧いただければ幸いです。
リンク：IoT・AIのお悩み 動画データを使った異常検知を行いたい

k近傍法による異常検知

最初にk近傍法とは何かという話をしていきます。ただし、ここではまだ時系列データには限定せずに考えていくことにします。
まず、正常データの集まり が与えられているとします。各はある次元のベクトルとします。この状況下で未知のデータが正常であるか、異常であるかを判定することを考えます。
k近傍法のコンセプトは”が正常データの集まりであることから、がのいずれかのデータの近くにあればは正常であると考え、そうでなければ異常であると考える”というものです。これをもう少し細かく説明していきます。
を中心とする球を考えます。この球の半径はのデータを個含めるように決めます。このようにして決定した半径をの異常度と言うことにします。このように異常度を定義すると、が正常なデータの集まりであるから外れたところに存在すれば、異常度は大きくなります。逆にに含まれるデータとあまり変わらないのであれば、異常度は小さくなります。こうして計算された異常度に対してしきい値を決めることで、異常度がしきい値を超えたときには異常が起きたと判定することができます。以上の説明を図にしたものを次に示します。

時系列データへのk近傍法の適用

次に、前述したk近傍法を時系列データに適用することを考えていきます。
下図のようにというような時系列データが得られているとします。k近傍法に適用することを考えると、この時系列データをどうにかしてベクトルの集まりにする必要があります。このために、適当な窓幅を決め、窓内の点を並べて1つのベクトルにしてしまいます。例えば、窓幅を4にしたときは

や

といった形でベクトルを作ります。こうして作られたベクトルをk近傍法で用います。

心電図データでのk近傍法の実験

実験の内容・設定

ここまでで説明した方法を用いて、http://www.cs.ucr.edu/~eamonn/discords/にある心電図データに対する異常検知をおこなってみます。心電図データは次のような波形となっており、横軸が285の値の付近で異常が起きています。

この波形は全部で3751個の点からできており、このうちの先頭の1000個の点をを生成するために使用し、残りの2751個の点をテストするために用いました。また、各点に対して前処理としてBox-Cox変換という方法を適用して、少しデータの変化をなだらかにしています。窓幅とk近傍法のを決めておく必要がありますが、窓幅は50、は1としています。

k近傍法の適用結果

次の2つのグラフのうち、上が後半2751個の点からなる波形をあらわし、下がそれに対応するk近傍法で計算された異常度になります（異常度に対するしきい値は今回は特に決めていません）。


異常箇所付近で異常度が大きくなっており、k近傍法のような簡単なロジックでも異常検知が可能であることがわかります。

まとめ

今回はk近傍法による時系列データの異常検知の紹介をおこないました。k近傍法の中身は単純でわかりやすいですが、問題によってはこれで上手くいきます。
ここでいうに含まれるデータの数が多くなったときには、計算時間がかかるようになるため注意が必要です。