近傍グラフの異常検知
論文
Anomaly detection with score functions based on nearest neighbor graphsという論文を読む。
kNNグラフを用いた異常検知で理論的にしっかり解析されている。
理論面はわからなかったのでイントロだけなんとなくメモ。
アブスト
n個の正常データに対して構築される近傍グラフを元にしたスコア関数に基づき、高次元データに対するノンパラメトリックな適応的以上検知アルゴリズムを提案する。
望まれた誤検知率に基づき異常は検知される。
結果として導出されて異常検出器はuniformly most powefulという意味において漸近的に最適になる。
この事は異常分布は正常分布と既知なある密度との混合で表されるという仮定のもとで成立つ。
私達のアルゴリズムは計算コストも低く、次元数に対して線形、データ数に対して二次的なオーダーである。
このアルゴリズムは複雑なパラメータ設定や関数近似を要求せず局所的な次元数変化などの局所的構造に適応可能である。
イントロ
異常検知は正常分布からの注目すべき偏差を検出する問題である。
典型的には、正常分布は未知であり、高次元であったりデータ数が制限される事から正常分布を正しく予測する事は難しい。
データを[0,1]なスコア関数へ写像する事により、異常検知のための適応的なノンパラメトリック手法を私達は提案する。
n個正常データに対して構築されるK近傍グラフにより私達のスコア関数は導出される。
設定された誤検出率α以下にスコア関数が値を持てばそれは異常として検出される。
多変量p値に近い形で私達の検定法は効率的である。
統計的検定においては、正常データに対して[0,1]で一様分布を持つような特徴空間写像を行ったものをp値と呼ぶ。
もしテストデータのp値がαがより小さく、異常として検知されたなら、その誤検出はαよりも小さくなる。
尤度比関数に基づくlevel setの測度に基づき新たなp値を私達は開発する。
もし異常分布が正常分布と既知の分布の混合として表されるとした時、設定された誤検出率におけるuniformly most powerful testとなる最適な異常検出指標として新たに開発したp値は作成される。
このスコアはデータ数が無限大に近づくと多変量p値に収束するため漸近的に一貫している。
異常検知は良く研究されている分野である。
これは新規性検知、外れ値検知、１クラス分類など文脈によって呼ばれる。
これらのアプローチはいくつかのカテゴリーに別れる。
パラメトリック手法では、正常分布はパラメトリックな族によりモデル化され、一般化尤度比検定における偏差を用いて検知を行う。
しかし分布が未知であったり、データが制限されている場合この手法は難しい。
K近傍異常検知手法も提案されている。
これはテストサンプルのK近傍がしきい値の外側にある場合に検知を行う。
対して私達の手法は、KNNグラフに基づき全体的な構造も考慮する事が出来る。
加えて、最適性条件も証明した。
正常なデータと外れ値を分類するような決定境界を学習理論的に考察している。
マージン最大化に基づく分類をカーネル空間へ訓練データを写像して行うone class SVMもこれに含まれている。
他にもsupport vector data description, 線形計画法、single class minimax probability machine等がこの研究領域に含まれている。
その計算効率の良さにも関わらず、望んだ誤検出率に沿ったパラメータ設定を行う事はそれら従来手法に関しては一般的に難しい。
タイプ１，２エラーを制御する手法としてminimum vokume(MV) setsに基づく決定境界も提案されている。
訓練データから未知の正常多変数密度のlevel setsをその手法では予測する。
関連して、テストサンプルを訓練データにおける最も凝集した部分集合と比較する事で外れ値検出を行うgeometric entropic minimization(GEM)がある。
この最も凝集した部分集合はK-point minimum spanning tree(MST)と呼ばれ、漸近的に最小エントロピー集合へ収束する（これは同時にMV setでもある）。
それにも関わらず、それらの計算はintractableである。
この問題を解決するために、leave one out KNNグラフに基づくヒューリスティックな貪欲法が提案された。
しかしこの手法はもはや最適性が証明出来ない。
MV setsやGEMに私達の手法は関連している。
テストデータを含んだMV setsの経験的な推定としてKNNGによるスコア関数を私達は構築する。
最適性を保証するための十分統計量としてその実数体積は利用出来る。
高次元のlevel set推定を明示的にこの手法で回避する事が可能である。
かつ、誤検出を制御しながら統計的な最適解を導く事が私達のアルゴリズムでは出来る。
以下に私の手法の主な特徴をまとめる。
１．次元に対し線形、データ数に対し２次オーダーで計算コストがかかるので高次元データに強い。
２．異常分布が正常分布と任意の分布の混合で表される場合において、与えられた誤検出率αに関してuniformly most powerfulであるような最適性が証明されている。
３．level setsに対し、線形性、スムーズ性、連続性、凸性を仮定しない。
さらに、正常分布が持つ局所的次元や隠れた多様体構造に適応する。
４．他の学習理論的手法と違い、私達は複雑なパラメータ設定や近似関数クラスを要求しない。
所感
十分計算コスト重い気がする。しかし理論面の貢献がすごい。
