局所外れ値因子法

機械学習および データマイニング
問題 分類 クラスタリング 回帰 異常検知 相関ルール（英語版） 強化学習 構造化予測（英語版） 特徴量設計（英語版） 表現学習（英語版） オンライン学習（英語版） 半教師あり学習（英語版） 教師なし学習 ランキング学習（英語版） 文法獲得（英語版）
教師あり学習（分類 • 回帰） 決定木（英語版） アンサンブル （バギング、ブースティング、 ランダムフォレスト） k-NN 線形回帰 単純ベイズ ニューラルネットワーク ロジスティック回帰 パーセプトロン 関連ベクトルマシン (RVM)（英語版） サポートベクトルマシン (SVM)
クラスタリング BIRCH（英語版） 階層的（英語版） k平均法 期待値最大化法 (EM) DBSCAN OPTICS（英語版） 平均値シフト（英語版）
次元削減 因子分析 CCA ICA LDA（英語版） NMF（英語版） PCA t-SNE
構造化予測（英語版） グラフィカルモデル ベイジアンネットワーク CRF HMM
異常検知 k-NN 局所外れ値因子法
ニューラルネットワーク オートエンコーダ ディープラーニング DeepDream 多層パーセプトロン RNN LSTM GRU 制約ボルツマンマシン（英語版） SOM CNN U-Net
強化学習 TD学習 Q学習 SARSA
理論 偏りと分散のトレードオフ 計算論的学習理論（英語版） 経験損失最小化（英語版） オッカム学習（英語版） PAC学習 統計的学習（英語版） VC理論（英語版）
学会・論文誌等 NIPS（英語版） ICML（英語版） ML（英語版） JMLR（英語版） ArXiv:cs.LG
全般 統計学および機械学習の評価指標
Category:機械学習 Category:データマイニング
表 話 編 歴

異常検知における局所外れ値因子法（きょくしょはずれちいんしほう、英: local outlier factor, LOF）は Markus M. Breunig、Hans-Peter Kriegel（英語版）、Raymond T. Ng、Jörg Sander によって2000年に提案されたアルゴリズムで、任意のデータ点での、近傍点に対する局所的な変動を測ることによって異常を発見するものである^[1]。

局所外れ値因子法は、コア距離 （core distance）や到達可能性距離 （reachability distance）等の概念をDBSCANやOPTICS（英語版）といったアルゴリズムと共有しており、これらは局所密度の推定に用いられる^[2]。

基本的なアイディア[編集]

局所外れ値因子法は局所密度の概念に基づいている。ここでの「局所（locality）」は ${\displaystyle k}$ 個の最近傍で与えられ、それらの距離によって密度が推定される。あるオブジェクトの局所密度をその近傍群の局所密度と比較することで、密度が同程度であるような領域と、周囲と比べて密度が有意に低い点を特定することができる。こうした点が外れ値だと考えられる。

局所密度は、その近傍から「到達（reach）」するのにかかる標準的距離を使って推定される。局所外れ値因子法での「到達可能性距離（reachability distance）」は、クラスタ内でより安定的な値が生じるよう追加的に定義された尺度である。

正式な定式化[編集]

${\displaystyle {\mbox{k-distance}}(A)}$ を、オブジェクト ${\displaystyle A}$ の k 番目の近傍までの距離とする。ここで k 個の最近傍とはこの距離以下の全てのオブジェクトの集合で、「タイ」が存在する場合は個数が k より大きくなり得ることに注意する。k 最近傍オブジェクトの集合を ${\displaystyle N_{k}(A)}$ と書く。

この距離は、到達可能性距離（reachability distance）と呼ばれる値を定義するのに用いられる：

${\displaystyle {\mbox{reachability-distance}}_{k}(A,B)=\max\{{\mbox{k-distance}}(B),d(A,B)\}}$

つまり、オブジェクト ${\displaystyle A}$ の ${\displaystyle B}$ からの「到達可能性距離」は、それが ${\displaystyle B}$ の ${\displaystyle {\mbox{k-distance}}}$ 以上である限りは、2オブジェクト間の真の距離と一致する。${\displaystyle B}$ の k 最近傍集合（${\displaystyle B}$ のコア（core）。DBSCANクラスタ解析を参照）は全て等距離だと見なせる。このような距離を考えるのは、結果をより安定的なものにするためである。これは対称的でないので、数学的定義上の距離にはなっていないことに注意する。 （常に ${\displaystyle {\mbox{k-distance}}}$ の方を使うのはよくある誤りで^[3]、そのような場合は Simplified-LOF と呼ばれるわずかに異なる手法になる^[3]。）

オブジェクト ${\displaystyle A}$ の局所到達可能性密度（local reachability density）は

${\displaystyle {\mbox{lrd}}_{k}(A):=1/\left({\frac {\sum _{B\in N_{k}(A)}{\mbox{reachability-distance}}_{k}(A,B)}{|N_{k}(A)|}}\right)}$

と定義される。これはオブジェクト ${\displaystyle A}$ の、その近傍群からの到達可能性距離の平均の逆数をとったものである。${\displaystyle A}$ から近傍へ到達する距離の平均ではなく（これは定義上 ${\displaystyle {\mbox{k-distance}}(A)}$ に等しい）、近傍から ${\displaystyle A}$ へ到達する距離の平均であることに注意する。オブジェクトが重なっている点ではこの値は無限大になり得る。

次に以下のようにして、近傍群と局所到達可能性密度が比較される。

${\displaystyle {\mbox{LOF}}_{k}(A):={\frac {\sum _{B\in N_{k}(A)}{\frac {{\mbox{lrd}}(B)}{{\mbox{lrd}}(A)}}}{|N_{k}(A)|}}={\frac {\sum _{B\in N_{k}(A)}{\mbox{lrd}}(B)}{|N_{k}(A)|}}/{\mbox{lrd}}(A)}$

これは「近傍群の局所到達可能性密度の平均」を「オブジェクト自身の局所到達可能性密度」で割ったものである。これが ${\displaystyle 1}$ に近い値であるとき、オブジェクトはその近傍と同程度（similar）である（よって外れ値ではない）。${\displaystyle 1}$ を下回るとき、その点は密度が高い領域（内部点（inlier））に位置する。${\displaystyle 1}$ を有意に上回るとき、外れ値である。

LOF(k) ~ 1 は、近傍と同程度の密度であることを意味する。

LOF(k) < 1 は、近傍よりも高密度であることを意味する。

LOF(k) > 1 は、近傍よりも低密度であることを意味する。

利点[編集]

局所外れ値因子法は局所的なアプローチであるため、データセットの別の領域に位置していれば外れ値とはなっていないであろう点も、外れ値として検知できる。例えば、かなり密度の高いクラスタまでの距離が「小さい」点は、（まばらなクラスタ内の点も近傍までの距離は同程度かもしれないが）外れ値になる。

局所外れ値因子法を幾何学的な直観で捉えられるのは低次元ベクトル空間の場合に限られるが、このアルゴリズムは非類似度関数（dissimilarity function）が定義できるような任意の状況に対し適用できる。この手法は経験的に、数多くの設定下で非常に上手く働くことが示されており、例えば侵入検知システム^[4]や加工（processed）分類ベンチマークデータ^[5]に関して、しばしば競合する手法より優れた結果を出す。

局所外れ値因子法や類似する手法群は、他の様々な問題、例えば地理データ、動画ストリーミング、著者ネットワーク（authorship network）における外れ値の検知に対しても容易に一般化できる^[3]。

欠点および拡張[編集]

出力値が分数であるため、解釈が難しい。値が 1 またはそれ以下であれば明確に外れ値でないと判断できるが、外れ値であるかどうかに対する明確な規則は存在しない。あるデータセットでは値が 1.1 であれば外れ値とされる一方で、別のデータセットあるいは別の（局所的な変動の激しい）パラメータの下では値が 2 であってもなお、外れ値とされないかもしれない。手法の局所性のために、こうした相違は一つのデータセットの中でも発生し得る。これらの特質の改善を試みる、局所外れ値因子法の拡張が存在している。

• Feature Bagging for Outlier Detection（外れ値に対する特徴バギング） ^[6]は、データの複数の射影に対して局所外れ値因子法を実行し、結果を結合することで、高次元での検知の質を高める。これは異常検知に対するアンサンブル学習アプローチの最初の例であり、他の変種については脚注^[7]を参照。
• Local Outlier Probability (LoOP)^[8]（局所外れ値確率）は局所外れ値因子法から派生した手法だが、あまり込み入っていない（inexpensive）局所的統計量を用いることで、結果がパラメータ k の選択に鋭敏に左右されないようにしている。また出力値は ${\displaystyle [0:1]}$ 区間の値に規格化されている。
• Interpreting and Unifying Outlier Scores ^[9]（外れ値スコアの解釈および統合）は、ユーザビリティ向上のために統計的スケーリングを用いてLOFの外れ値スコアを区間 ${\displaystyle [0:1]}$ の値へ規格化することを提案するもので、LoOPの改善案とみることができる。
• On Evaluation of Outlier Rankings and Outlier Scores ^[10]（外れ値ランキングと外れ値スコアの評価）は、LOFの変種や別のアルゴリズムを用いた、高度な異常検知アンサンブル構築法同士の類似度および相違度を測る手法を提案する。上述の Feature Bagging for Outlier Detection を改善したものである。
• Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection^[3]（局所外れ値検知再考：空間・映像・ネットワークでの外れ値検知を用いた局所性への一般的視点）は、様々な局所外れ値検知手法（例えば、LOF, simplified version of LOF, LoOP）における一般的なパターンを議論し、一般的なフレームワークを抽象している。このフレームワークは続いて、地理データ、動画ストリーミング、著者ネットワーク等における外れ値検知に応用される。

脚注[編集]

1. ^ Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J. (2000). LOF: Identifying Density-based Local Outliers (PDF). Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. SIGMOD. pp. 93–104. doi:10.1145/335191.335388. ISBN 1-58113-217-4。
2. ^ Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J. R. (1999). “OPTICS-OF: Identifying Local Outliers”. Principles of Data Mining and Knowledge Discovery. Lecture Notes in Computer Science. 1704. pp. 262. doi:10.1007/978-3-540-48247-5_28. ISBN 978-3-540-66490-1. http://www.dbs.ifi.lmu.de/Publikationen/Papers/PKDD99-Outlier.pdf 
3. ^ ^{a b c d} Schubert, E.; Zimek, A.; Kriegel, H. -P. (2012). “Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection”. Data Mining and Knowledge Discovery. doi:10.1007/s10618-012-0300-z. 
4. ^ Lazarevic, A.; Ozgur, A.; Ertoz, L.; Srivastava, J.; Kumar, V.; (2003). “A comparative study of anomaly detection schemes in network intrusion detection”. Proc. 3rd SIAM International Conference on Data Mining: 25–36. http://www.siam.org/proceedings/datamining/2003/dm03_03LazarevicA.pdf. 
5. ^ Campos, Guilherme O.; Zimek, Arthur; Sander, Jörg; Campello, Ricardo J. G. B.; Micenková, Barbora; Schubert, Erich; Assent, Ira; Houle, Michael E. (2016). “On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study”. Data Mining and Knowledge Discovery. doi:10.1007/s10618-015-0444-8. ISSN 1384-5810. 
6. ^ Lazarevic, A.; Kumar, V. (2005). “Feature bagging for outlier detection”. Proc. 11th ACM SIGKDD international conference on Knowledge Discovery in Data Mining: 157–166. doi:10.1145/1081870.1081891. 
7. ^ Zimek, A.; Campello, R. J. G. B.; Sander, J. R. (2014). “Ensembles for unsupervised outlier detection”. ACM SIGKDD Explorations Newsletter 15: 11. doi:10.1145/2594473.2594476. 
8. ^ Kriegel, H.-P.; Kröger, P.; Schubert, E.; Zimek, A. (2009). LoOP: Local Outlier Probabilities (PDF). Proceedings of the 18th ACM conference on Information and knowledge management. CIKM '09. pp. 1649–1652. doi:10.1145/1645953.1646195. ISBN 978-1-60558-512-3。
9. ^ Kriegel, H. P.; Kröger, P.; Schubert, E.; Zimek, A. (2011). Interpreting and Unifying Outlier Scores (PDF). Proceedings of the 2011 SIAM International Conference on Data Mining. pp. 13–24. doi:10.1137/1.9781611972818.2. ISBN 978-0-89871-992-5。
10. ^ Schubert, E.; Wojdanowski, R.; Zimek, A.; Kriegel, H. P. (2012). On Evaluation of Outlier Rankings and Outlier Scores (PDF). Proceedings of the 2012 SIAM International Conference on Data Mining. pp. 1047–1058. CiteSeerX 10.1.1.300.7205. doi:10.1137/1.9781611972825.90. ISBN 978-1-61197-232-0。