異常検知問題における近傍法の機能

問題再設定:異常検知モデルの設計は如何にして可能になるのか

異常検知のモデル設計における主導的差異は「正常(Normally)」と「異常(Anomaly)」の区別によって構成されている。だがこの区別は極めて形式的に導入される傾向がある。単に「異常」と述べても、

  • 「疑わしい活動/出来事/行動(suspicious activity/event/behavior)」
  • 「不規則な活動/出来事/行動(irregular activity/event/behavior)」
  • 「珍しい活動/出来事/行動(uncommon activity/event/behavior)」
  • 「希少な活動/出来事/行動(unusual activity/event/behavior)」
  • あるいは望まない「ノイズ(nosie)」

などのように、この形式的な概念には様々な意味が代入される。いずれの定義においても、「正常」の概念との関連から記述されている。つまり「異常」という概念の定義が先にあるのではなく、「正常」との差異があって初めて「異常」の概念が記述されるのである。

「異常」と「正常」の意味論はまた、問題志向的に規定される場合もある。例えば「外れ値検知(outlier detection)」の問題設定では、観測データ点の外れ値となる異常標本が「異常」概念ということになる。一方、「変化点検知(change-point detection)」の場合は、時系列的な変異性が「異常」概念となる。

統計的機械学習問題の枠組みでは、データの性質に応じて確率分布を如何にして学習するのかという観点から、「異常度(anomaly score)」を如何にして確率分布と結び付けるのかを定式化することになる。正常なデータと異常なデータは、それぞれ異なる確率分布に基づいて生成されている。

教師ラベルが得られる場合には、この確率分布の比、すなわち「尤度比(likelihood ratio)」から異常度を計算することになる。だが教師ラベルが得られない場合には、情報理論的な計算が必要になる。この場合、異常データは希少であることが前提となる。つまり、正常データの学習時、出現確率が低い観測データ点ほど異常度が高いということである。逆に言えば、異常度の高いデータは情報量、あるいは情報エントロピーが高いと認識される。

問題解決策:近傍法

「近傍法(nearest neighbor)」に準拠した異常検知モデルは、正常データのインスタンスが密集地帯で発生する一方で、異常データのインスタンスはその最近傍から遠く離れて発生しているという想定から設計されている。

この技術においては、二つのデータインスタンスの間の距離を計算するために、予め規定された距離関数を導入しなければならない。典型的にはユークリッド距離として計算されるが、距離概念それ自体は偶発的な選択肢となる。ユークリッド距離のみならず、例えばマンハッタン距離やコサイン距離などの概念を用いても、計算は「可能」だ。だがこれらの概念で計算することは「必然」ではない。

大別するなら、近傍法に準拠した異常検知モデルは、「k近傍法(k-nearest neighbor)」での距離を異常度として利用する方法とデータインスタンスの相対密度を異常度として計算する方法とに区別することができる。k近傍法は最近傍探索問題を解くためのアルゴリズムの一種である。そのアルゴリズムは、特徴空間内で未知のデータを観測した際に、そこから最も距離が近い順に任意のk個のデータインスタンスを選択し、多数決でそのデータが属するクラスを推定する。k近傍法に基づいた異常検知モデルでは、小規模あるいは低密度なクラスに属するインスタンスが、「異常」なデータということになる。

一方、相対密度に基づいた異常検知モデルでは、k個の最近傍の平均局所密度とデータインスタンス自体の局所密度の比率を意味する「局所的外れ値要因(local outlier factor: LOF)」を前提に、各データインスタンスの近傍の密度を推定していく。そして密度の低い近傍にあるインスタンスが「異常」なデータであると形式的に定義される。

近傍法に準拠した異常検知モデルの利点は、教師なし学習として設計できるために、データの生成分布を仮定せずに済むということにある。それは純粋にデータ駆動型の探索アルゴリズムとなる。またこのアルゴリズムは他のアルゴリズムに容易に接続させることが可能である。例えば積層自己符号化器(Stacked Auto-Encoder)の隠れ層から得られた多様体の特徴量に対してK近傍法を導入すれば、原理的には次元削減(Dimensions reduction)の結果として得られた特徴写像に対して最近傍法の探索アルゴリズムを適用していることになるために、異常検知モデルの全体に「次元の呪い(Curse of dimension)」への耐性を持たせることも可能になる。

近傍法に準拠した異常検知モデルには、逆に不利な点もある。観測データ点に十分な近傍を有さない正常データが含まれている場合や、逆に十分な近傍を持つ異常データが含まれている場合には、その判定の難易度は増大することになる。加えて、計算複合性もまた大きな派生問題となる。最近傍法のアルゴリズムでは、全てのインスタンスのそれぞれにおいて、その最も距離が近いインスタンスを計算することになる。また、距離関数の偶発性も課題となる。データ・クラスタリングと同様に、異常検知モデル全体としての精度は距離関数の定義に依存することもある訳だ。

参考文献

  • Breunig, M. M., Kriegel, H. P., Ng, R. T., & Sander, J. (2000, May). LOF: identifying density-based local outliers. In ACM sigmod record (Vol. 29, No. 2, pp. 93-104). ACM.
  • Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7), 107-117.
  • Byers, S., & Raftery, A. E. (1998). Nearest-neighbor clutter removal for estimating features in spatial point processes. Journal of the American Statistical Association, 93(442), 577-584.
  • Eskin, E., Arnold, A., Prerau, M., Portnoy, L., & Stolfo, S. (2002). A geometric framework for unsupervised anomaly detection. In Applications of data mining in computer security (pp. 77-101). Springer, Boston, MA.
  • Ramaswamy, S., Rastogi, R., & Shim, K. (2000). Efficient algorithms for mining outliers from large data sets. In ACM Sigmod Record (Vol. 29, No. 2, pp. 427-438). ACM.
  • Salfner, F., Lenk, M., & Malek, M. (2010). A survey of online failure prediction methods. ACM Computing Surveys (CSUR), 42(3), 10.
  • Silver, N. (2012). The signal and the noise: why so many predictions fail–but some don’t. Penguin.

執筆者