こんにちは！インフラエンジニア見習いつるべーです。
今回は、mrubyという組込ソフトウェア向けの軽量なRuby言語を使って、k近傍法による異常検知を行うスクリプトを書いてみたので、そちらの紹介です！
目次
- なぜ作ったのか
- 作ったもの
- mrubyに入門するには
- Changefinderとの比較から見るKNNの特徴
- 今後やりたいこと
- オマケ：k近傍法(K-Nearest Neighbor :KNN)に基づく異常検知の理論
なぜ作ったのか
今回は、「何かの問題を解決したい」というよりは、「Rubyの勉強がてらに何か作ってみよう」という動機で作りました。
ただ、一般的なRuby（CRuby）ではなくmrubyを選択したのには理由があります。
私が勤めているGMOペパボでは、mrubyを利用してミドルウェアの振る舞いを設定・制御する仕組み（これを"Middleware Configuration as Code"と呼んでいる）を積極的に導入しており、そこに非常に興味を持ったからです。
下の二つのスライドには、"Middleware Configuration as Code"の概要や事例がまとめられています。
Middleware Configuration as Code - Speaker Deck
作ったもの
ソースコード
k近傍法に基づく異常検知の理論は最後に書いておくので興味のある方はぜひ！
使い方
mrubyで自分が書いたコードを動かすには、mrubyのコンパイル時に書いたコードを組み込んでコンパイルする必要があります。
したがって、まずはmrubyをコンパイルする環境を用意する必要があります。QiitaにCentOS7上でmrubyをコンパイルして動かすまでの手順を書きましたので、ご参考までに。
mrubyをビルドする前にbuild_config.rbに以下の記述を追加してやると、mruby-knn-detectorを組み込んだmrubyができます。
MRuby::Build.new do |conf| # ... (snip) ... conf.gem :github => 'tsurubee/mruby-knn-detector' end
それでは、mirbというCRubyにおけるirbに相当する対話型インタープリタを使って動かしてみます。
※ mruby-knn-detectorは一次元の時系列データの異常検知を行うもので、入力データは一次元配列になります。
$ mruby/bin/mirb mirb - Embeddable Interactive Ruby Shell > knn = KNN.new(2, 1) #(Window size, Number of neighbors) => #<KNN:0xdc0fa0 @k=1, @w=2> > data = [1, 2, 10, 2, 1] => [1, 2, 10, 2, 1] > knn.score(data) => [0, 1.4142135623731, 8.0622577482985, 8.0622577482985, 1.4142135623731]
KNNクラスの引数にはスライド窓の幅と近傍数を渡してやり、一次元配列をscore関数に投げ込むと、投げ込んだ配列と同サイズの異常度配列が返ってきます。
（スライド窓や近傍数については最後に解説しています）
返ってきたら異常度配列のうち要素の値が大きいものほど異常度が高いと判断できます。
mrubyに入門するには
mrubyを書き始めるのはCRubyやPythonなどを始めるより少しハードルが高く感じました。それはなぜかというと、コンパイルということに馴染みがなかったからです。私自身ほぼPythonしか書いたことがなかったため、今回初めて自分の書いたコードをコンパイルしました。
それでは、私と同じように「mrubyってちょっと取っつきづらいよ」と感じる方がどうやってmrubyに入門すると良いかということについてですが、私の場合、最初に「WEB+DB PRESS Vol.101」の中で@pyama86さんが執筆された「mrubyを活用したインフラ運用の最前線」を読みました。mrubyの部分は本の中の7ページだけですが、実際にmrubyを利用して開発を行うときに必要な手順がわかりやすく解説されていました。
具体的には、@matsumotoryさんが開発しているmruby-mrbgem-templateを用いたmrbgem開発の基本的な流れが書かれていました。
mruby-mrbgem-templateを用いると、たった数コマンドでmrbgemのひな形が生成されるため、大変便利でした。
mruby-mrbgem-templateの使い方は下の記事に解説がありました。
mrbgemのひな形までできると、あとは普通にRubyを書いていくだけでした。
やりたいことによっては、Linuxのシステムコールを利用するような処理をC言語で実装し、C言語のメソッドをRubyから呼び出したりできるようです。
今回私は50行くらいのRubyを書いただけです。
Changefinderとの比較から見るKNNの特徴
mrubyによる異常検知の実装には@matsumotoryさんのmruby-changefinderがあります。今回これとKNNの比較をしてみたいと思います。
用いるデータは、あんちぽさんがmruby-changefinderを使った異常検知例を以前のブログに書いていたので、それを真似てみようと思います。
データの元ネタは「異常検知でGo！」のデータを使っています。
ハイパーパラメータは以下のような値を用いました。（ハイパーパラメータとは人が決定しなければならないパラメータのこと）
# ChangeFinder cf = ChangeFinder.new(5, 0.01, 10, 0.01, 5) # KNN knn = KNN.new(5, 5)
異常検知の結果が以下のグラフになります。比較しやすくするために縦軸は調整しています。
KNNもなかなかいい形してますね！
ここで両者の違いをいくつか議論します。（アルゴリズム的にどちらが優れているとかいう話ではない）
まず、ハイパーパラメータについてですが、ChangeFinderが5つに対して、KNNは2つしかありません。したがって、ChangeFinderの方が柔軟な設定が可能であり、確率分布がバチっとハマった時は強そうですが、ハイパーパラメータのチューニングが大変だとも言えます。
明示的に確率分布を仮定しない、KNNや特異スペクトル変換などのアルゴリズムは、ハイパーパラメータも少ないですし、様々なデータに頑強な印象です。
ChangeFinderのメリットの一つは逐次的な学習アルゴリズムであるため、初期学習をしておけば、新しい観測点に対して、一つの異常度を返します。そのため、計算も比較的軽量ですし、異常度のデータを受け取る側の実装もシンプルに組めそうです。
一方、KNNは、今の実装だとデータ配列を受け取って、それと同じサイズの異常度配列を返すので、オンラインで異常検知してやるには実装側でインプットのデータ配列をいい感じにずらしながらデータを投げ込んでやる必要があるし、計算もそこそこ重いです。
今後やりたいこと
Ruby・mruby周りで今後やりたいこと。
テストを書く
今回はなるべく早く動かしたかったのでテストの実装をサボりました。Travis CIで自動テストするとこまではちゃんとやりたい。言語仕様を学ぶ
下の本をちら見したらmrb_stateとかmrb_valueとか知らないことがいっぱい解説してあったので、ちゃんと読むと言語仕様を学ぶのに良さげな感じ。
オマケ：k近傍法(K-Nearest Neighbor :KNN)に基づく異常検知の理論
k近傍法とは一般的には多クラス分類のアルゴリズムですが、ちょっとした工夫で時系列データの異常検知にも応用することができます。
k近傍法を言葉で簡単に説明すると、「各点から最も近いデータへの距離を計算することで異常度を算出する手法」です。
もう少し詳しく解説していきます。
まず、1次元の時系列データを時間的に隣接したまとまりとして取り出します。これはスライド窓とも呼ばれ、下のようなイメージです。
この長さwの窓を左から右にずらしていくことで、1次元の時系列データをスライド窓の幅の次元数の列ベクトルの集合に変換することができます。
ここで列ベクトルとは空間上の点のようなものだとイメージして下さい。（正確には、ユークリッド空間の原点から空間内のどこか一点を結ぶ有向線分）列ベクトル同士には近い/遠い、すなわち距離の概念を考えることができます。k近傍法では、ある列ベクトルから距離が近いベクトルをk個取り出して、その距離の大きさをもとに異常度を算出します。
ここで、ベクトル間の「距離」の求め方と、「異常度」の算出方法には任意性があります。
今回の実装では、距離は典型的にはユークリッド距離を用いています。（マハラノビス距離などを使うこともできる）
異常度の計算には、k個の近傍距離の平均を用いました。
