Random Projection Outlyingness（RPO）に基づく外れ値検知をPyODフォーマットで実装した

機械学習 異常検知 python

はじめに

データ分布に対する各サンプル点の外れ度合いを測る指標として、Random Projection Outlyingness（RPO）が存在する。今回はRPOに基づく外れ値検知をPythonで実装したので、紹介する。

Random Projection Outlyingnessとはなにか？

depthについて

David Donoho先生らによる、以下の論文を参考にする。

David L. Donoho and Miriam Gasko, "Breakdown Properties of Location Estimates Based on Halfspace Depth and Projected Outlyingness," vol.20, no.4, pp.1803-1827, The Annals of Statistics, 1992.

projecteuclid.org

論文タイトルにも含まれている「depth」という量は、Tukeyらによって提案された（ちなみTukeyはFFTアルゴリズムの開発者の一人としても有名）。ある1つのデータ点（一般には多次元ベクトル）が、手元のデータセット（同次元のベクトル集合）の「分布的な意味でどのあたりに位置しているか」を記述する量がdepthである。以下にdepthの定義を示す。1次元のdepthの定義は

\displaystyle \mathrm{depth}_{1} = \mathop{\rm min} (\; \# \{ i \mid X_i \leq x\}, \; \# \{ i \mid X_i \geq x\})

である。ここで、$X$はデータセット $X =\{X_1, X_2, \ldots, X_n\}$である。入力データ$x$の左側と右側にくるデータの数を数えて、小さいほうをとる。これを$d$次元データに拡張するには、データを1次元空間に射影し、スカラーの集合に変換して比較可能にすることで、depthが計算できる。定義は

\displaystyle \mathrm{depth}_{d} = \mathop{\rm min}\limits_{\| u \|=1} \; \# \{i \mid u^{T}X_i \geq u^{T} x \}

とする。ここで$u$が射影軸を表すベクトルであり、$u^{T}X_i$は$i$番目のデータサンプルを$u$に射影した成分（内積を取っているのでスカラー）である。$u^{T} x$が当該サンプル$x$を射影したときの成分であり、成分が$u^{T} x$より大きくなるサンプルの数は大小関係を比較しながらカウントすることができる（有限集合なので比較は有限回で終わる！）。そして$\mathrm{min} $は正規化された射影軸$u$に渡って取る（暗黙的にそのような$u$の集合は有限濃度を考えている）。$d$次元版の観点から1次元版の定義を眺めると、数直線の右向きの軸および左向きの軸への射影を考えているわけである。

上記の論文で紹介されているが、1次元空間で考えるとsample maximumとsample minimumはdepthが1である。また上位/下位四分位数に対応するのは、depthとしてほぼn/4であり、メディアンに対応するのはdepthとしてn/2である（nはサンプルサイズ）。sample maximum/minimumは分布の際（きわ）に位置しているので「一番浅く」、depth的には最小値を取る。メディアンは分布のほぼ真ん中に位置しているので「一番深く」、depth的には最大値を取る。1次元のヒストグラム（山が一つ）をイメージすると分かりやすいかもしれない。上記のdepthを使うと、ロバスト統計にとって色々と興味深い議論ができる。

outlyingnessについて

さてDonoho先生らは、多次元データであってもdepthのように1次元空間に射影して統計的な性質を議論できることに目をつけ、多次元データにおける外れ度合い（outlyingness）の議論も同様にあてはまるだろうとした。1次元空間において、中心（平均）からのデータの乖離を測るために以下の量を考えるのは素朴である（1次元のホテリング$T^{2}$法において定義される異常度の平方根に相当する）。

\displaystyle \frac{|x - \mathrm{mean}(X) |}{\mathrm{std}(X)}

ここで$\mathrm{mean}(X)$と$\mathrm{std}(X)$はそれぞれ、$X$上で計算した標本平均と標本標準偏差である。しかしながら、この量は外れ値の影響を受けやすい。そこで標本平均をメディアン（median; MED）、標本標準偏差を中央絶対偏差（mean absolute deviation; MAD）に置き換えた

\displaystyle r_1(x; X) = \frac{|x - \mathrm{MED}(X) |}{\mathrm{MAD}(X)}

を外れ値にロバストなoutlyingessとして考えることができる。MEDとMADは外れ値の影響を受けにくいことが知られている。

Random Projection Outlyingness (RPO)

depthと1次元射影のことを踏まえて、$d$次元のoutlyingnessへと拡張するには

\displaystyle r_d(x; X) = \mathop{\rm max}\limits_{\| u \|=1} \; \; r_1 \left( u^{T}x ; \{u^{T}X\} \right)

とすればよい。ここで$u^{T}X$は$u$上に射影したデータセットを表し、$u^{T}x$は$x$を$u$上に射影したデータ点（スカラー値）を表す。$\max$を取る$u$の集合は有限であり、したがって単位超球面$S^{d-1}$上から有限個をランダムサンプリングしたうえで計算する。以上がRandom Projection Outlyingness (RPO)である。文献によっては、Stahel-Donoho outlyingnessとも呼ばれる。これを外れ値検知における異常度スコアとして利用することができるというわけである。

実装

PyODのインストール

pip install pyod

RPOクラス

PyODフォーマットに従って、RPOクラスを実装した。以下を適当なファイル名（rpo.pyなど）で保存する。

ここをクリックしてコードを表示する gist.github.com

実装はとても簡単。ちなみに中央絶対偏差の計算にはscipy.statsのmedian_abs_deviation関数を使うことができる。

Toy example

PyODのexampleを実行した。 gist.github.com

ベンチマーク

PyOD付属のベンチマーク用のスクリプトを少し改変する。15のデータセット上で評価した。 外れ値検知の代表的な手法たちと比較する。

  • 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)
  • Random Projection Outlyingness (RPO) (今回の手法; 射影次元は500 つまり射影軸を500本保持する） gist.github.com RPOは外れ値検知性能と省計算量とを両立していることがわかる。射影次元を大きくすれば計算時間とメモリ消費量は大きくなる（射影軸の集合をたくさん保持しないといけないので）。

参考文献

  • Donoho, D. L., Gasko, M., et al. Breakdown properties of location estimates based on halfspace depth and projected outlyingness. The Annals of Statistics, 20(4):1803–1827, 1992. Link

  • Zuo, Y. et al. Projection-based depth functions and associated medians. The Annals of Statistics, 31(5):1460–1490, 2003. Link