Rapid Distance-Based Outlier Detection via Sampling (NIPS 2013) に基づく外れ値検知手法をPyODフォーマットで実装した

はじめに

"Rapid Distance-Based Outlier Detection via Sampling" という論文の中で提案された手法を、外れ値検知のためのPythonライブラリ PyOD のフォーマットに落とし込んで、手軽に使えるように実装したということ。併せてベンチマークデータを用いて性能を評価した。

論文

論文は以下から読むことができる。

Sugiyama, M., Borgwardt, K. M., "Rapid Distance-Based Outlier Detection via Sampling," Advances in Neural Information Processing Systems (NIPS 2013), 467-475, 2013.

論文著者のSugiyama氏による解説資料(PDF)はこちらから。

Sugiyama氏によるR および C 言語による実装例はこちらから。

手法の概要

データセット全体から一度だけサンプリングしてサブセットを作り、保持する(再サンプリングは行わない)。 新規入力データの異常スコアは、サブセット上の最近傍サンプルとの距離を求めることで計算される。

サブセットのサイズを十分に小さくしても、 データセット全体を用いる他の外れ値検知手法と匹敵する検知精度を得ることができる。 かつ計算時間を大きく減らせるのでハッピー。

実装したコード

PyODのBaseDetectorクラスを継承し、Samplingクラスを実装した。

コードを表示する gist.github.com

引数の意味は以下の通りである。

引数 説明
subset_size サンプリングするサブセットのサイズを指定する。int型ならばサブセットのサンプル数、float型ならば全体に対するサブセットの比率
metric 距離を指定する。sklearn準拠。
metric_params metricのキーワード引数
random_state 乱数の種 (int) or RandomState インスタンス
contamination 外れ値の(想定)比率

デモンストレーション

準備

PyODはpipコマンドでインストールできる。

pip install pyod

上記リンクにあるコードをsampling.pyなど適当な名前で保存する。

ノートブックその1

実行例を以下のnotebookに示す。サブセットのサイズは20にした。

gist.github.com

ノートブックその2

PyOD付属のベンチマーク用のスクリプトを少し改変する。件の論文にも比較手法として掲載されている外れ値検知の各手法と比較する。

  • Angle-based Outlier Detector (ABOD)
  • k-Nearest Neighbors Detector (kNN); k = 5
  • Isolation Forest (IForest)
  • Local Outlier Factor (LOF); k=10
  • One-Class SVM (OCSVM)
  • Sampling (今回の手法)

データセットの種類は16種類である。サンプリングにおけるサブセットのサイズは50で固定した(デモンストレーションなので50という数字に特に意味はない)。 ベンチマークデータは以下のgithubリポジトリからダウンロードして使う。

https://github.com/yzhao062/pyod/tree/master/notebooks

gist.github.com

"Sampling"の実行時間はとても短いが、外れ値検知の性能は他の手法と匹敵していることが分かる。

おわりに

本記事では"Rapid Distance-Based Outlier Detection via Sampling"において提案された外れ値検知手法を実装し、その検知性能を評価した。

学習データ全体からサブセットを一度だけサンプリングして保持し、以降はサブセット上で最近傍距離を求めるというシンプルな手法である。 PyOD付属のベンチマークデータを用いた外れ値検知実験の結果から、サンプリングにより検知精度を大きく落とすことなく、実行時間を大幅に減らせることを確かめた。

学習データ量が十分にあり、かつ外れ値がある程度含まれている場合には有望な手法のひとつだろう。何より実装が簡単である。学習データに外れ値がまったく含まれていない場合にも、ある程度は動くのではと考える(実験していないので推測)。