Skip to content
検索結果に戻る

局所外れ値因子 (LOF)

提唱者
Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
年
2000
種類
Density-based anomaly detection (unsupervised)

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

局所外れ値因子 (LOF) は、Breunig、Kriegel、Ng、Sander によって2000年に導入された、密度ベースの教師なし異常検知アルゴリズムです。各データ点に、その点が局所的な近傍と比較してどれだけ孤立しているかを定量化する連続的な外れ値スコアを割り当て、空間内の他の場所にある密なクラスターに紛れ込んでしまうためにグローバルな手法では見逃される異常の検出を可能にします。

手法の背後にある直感

ほとんどの人が密集した都市部に住んでいる都市の地図を想像してください。田舎にぽつんとある家は明らかに孤立しています。しかし、LOF はさらに進みます。すべての近隣住民がさらに密集したクラスターに詰め込まれている場合でも、適度に密集した郊外にある家をフラグ付けすることもできます。「この点はすべてから遠いか?」と問う代わりに、LOF は「この点の近傍は、その点自身の近傍の近傍よりもはるかに疎か?」と問います。近傍のすべてがその点自体よりも密接にまとまって住んでいる点は、高い LOF スコアを取得します。これは、空の領域にグローバルに存在しない場合でも、局所的な外れ値であることを示します。

歴史学

LOF は、Markus Breunig、Hans-Peter Kriegel、Raymond Ng、Jörg Sander によって ACM SIGMOD 2000 会議で導入されました。これは、既存の外れ値手法の認識されている制限に対処しました。それらはグローバルな距離しきい値に依存しており、そのため局所的な異常と、より密度の低い領域の通常の点を混同していました。この論文は、局所到達密度と LOF スコアの概念を導入し、これはすぐに異常検知の基盤となる参照となりました。その後、LoOP(局所外れ値確率)、LOCI、COF を含む多数のバリアントによって拡張され、主要な機械学習ライブラリに含まれています。ACM SIGMOD 2000 の論文は数千の引用を集め、密度ベースのデータマイニングにおける基礎的な研究の1つと見なされています。

使うべき場面

LOF は、異常がさまざまな密度のクラスターで発生することが予想され、グローバルな距離しきい値が疎な領域に隠れた外れ値を逃したり、空間内の正当に疎だが一貫したクラスター内の点を誤ってフラグ付けしたりする場合に適しています。意味のある距離尺度を持つ任意の連続特徴空間で機能し、ラベル付き異常例(完全に教師なし)を必要としません。不正検知、ネットワーク侵入検知、製造品質管理、医療異常スクリーニングなどのアプリケーションに適しています。主な仮定は、インライアが合理的にまとまった局所的な近傍を形成し、意味のあるペアワイズ距離を計算できることです。LOF は、n が少なくとも数十から数百の場合に最もパフォーマンスを発揮します。非常に高次元のデータ(次元の呪い)では、距離の識別力が低下するため、まず次元削減または特徴選択が推奨されます。

限界と注意点

  • ナイーブな実装における二次時間計算量は、近似最近傍インデックスなしでは大規模データセットで遅くなります。
  • k の選択に敏感です。k が小さすぎるとノイズの多いスコアになり、k が大きすぎると局所構造がぼやけます。
  • 次元の呪いにより、非常に高次元の空間ではパフォーマンスが低下します。
  • 再計算なしでは、ストリーミングまたはオンラインデータに自然にスケーリングしません。
  • トレーニングセットにアクセスせずに新しい点をスコアリングするために直接適用できるモデルを提供しません。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • さまざまな密度のクラスターを持つデータセットにおける局所的な外れ値を検出します。グローバルな手法では失敗します。
  • 柔軟なしきい値選択を可能にする、ハードな二値ラベルではなく、連続的で解釈可能なスコアを生成します。
  • 完全に教師なし:ラベル付き異常データは必要ありません。
  • 非ユークリッド距離を含む、計算可能な距離尺度を持つ任意のフィーチャ空間に適用可能です。
  • 距離が標準化されたデータで計算される場合、個々のフィーチャのスケールに対して堅牢です。

応用

  • 不正行為が局所的に疎なパターンを作成する金融取引における不正検知。
  • 周囲よりも局所的な近傍がはるかに疎なトラフィックレコードにフラグを付けることによるネットワーク侵入検知。
  • センサーが豊富な製造データにおける欠陥品を特定するための製造品質管理。
  • 類似した患者コホートと比較して異常な患者プロファイルを検出する医療異常スクリーニング。
  • 不均一な密度の地理的および環境データにおける空間異常検知。

使い方

使い方

1

各点 p について、アルゴリズムはまず k 距離を計算します。これは、p の k 番目に近い近傍までの距離です。これにより、p の局所的な近傍の到達範囲が定義されます。その距離内にあるすべての点が k 近傍 N_k(p) を形成します。k の選択は、局所性が評価されるスケールを制御します。小さい k は細かい局所構造を捉え、大きい k はそれを平滑化します。

数式
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } p
2

p から近傍 o への到達距離は、o の k 距離と p と o の間の実際のユークリッド距離(または他の距離尺度)の最大値として定義されます。この平滑化は、2 点が非常に近接している場合の不安定性を防ぎます。これは、o 自身の近傍のより広い範囲で小さな距離を置き換えることで、密度推定値をより堅牢にします。

数式
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}
3

p の局所到達密度 (lrd) は、p からその k 近傍すべてへの平均到達距離の逆数です。密に詰め込まれた近傍に囲まれた点は、平均到達距離が小さいため、lrd が高くなります。疎な領域にある点は、平均到達距離が大きく、lrd が低くなります。

数式
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}
4

p の LOF スコアは、その近傍の lrd 値とその p 自身の lrd 値との比率の平均です。p の近傍がすべて p 自体よりも大幅に高い lrd を持つ場合(つまり、それらがより密なサブ領域に存在する場合)、比率は 1 を超え、p が局所的な外れ値であることを示します。1 に近いスコアは、p が周囲とほぼ同じ密度を持っていることを示します。1 をはるかに超えるスコアは、ますます異常な点をフラグ付けします。この局所性を考慮した比較が、LOF を距離のみの手法と区別するものです。

数式
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}

よくある落とし穴

  • 距離計算前にフィーチャを標準化または正規化することを忘れると、分散が大きいフィーチャが支配的になります。
  • 感度分析なしで k の単一値を使用します。ベストプラクティスは、いくつかの k 値を評価することです。
  • LOF スコアを確率として扱うこと。これは、固定された確率的解釈を持たない相対的な尺度です。
  • 高次元データにおける次元の呪いを無視し、事前の次元削減なしで LOF が機能することを期待すること。
  • 特定のデータセットのスコア分布を検査せずに、任意の LOF しきい値(例:スコア > 1.5)を設定すること。

よくある質問

適切な k の値を選択するにはどうすればよいですか?

普遍的に最適な k はありません。一般的な実践は、値の範囲(通常は 5 から 50)を評価し、スコア分布とフラグ付けされた外れ値がどのように変化するかを調べることです。k 値全体にわたる感度分析により、検出された異常が選択に対して堅牢であることを確認できます。最小の予想クラスターサイズに関するドメイン知識も下限をガイドできます。

LOF スコアが 1 と 3 の場合、どのような意味がありますか?

1 に近いスコアは、その点が近傍とほぼ同じ局所密度を持ち、インライアと見なされることを意味します。1 より大幅に大きいスコア(データセットによっては 1.5 または 2 以上と解釈されることが多い)は、その点の近傍が近傍の近傍よりもはるかに疎であることを示します。普遍的なカットオフはありません。しきい値は、特定のデータセットの LOF スコアの分布を検査することによって選択する必要があります。

LOF は、トレーニングなしで新しい、未知の点をスコアリングできますか?

LOF は帰納的な手法です。新しい点の近傍と密度を計算するためにトレーニングセットが存在する必要があります。新しい観測値をスコアリングするには、トレーニングセットを保持し、各新しい点を挿入して、保存されたトレーニングポイントに対してその k 近傍を再計算する必要があります。一部の実装ではこの機能を提供していますが、これは、コンパクトなスコアリング関数を学習するパラメトリックモデルとは根本的に異なります。

LOF は異常検知において Isolation Forest とどのように比較されますか?

LOF は局所的な近傍に基づいた密度推定を使用し、異常が不均一な空間の局所的に疎な領域にクラスター化する場合に強力です。Isolation Forest はランダムなパーティショニングを使用し、大規模データセットに対してより高速でスケーラブルな傾向があります。高次元または非常に大規模なデータセットの場合、Isolation Forest が好まれることがよくあります。密度の変動がある中程度の次元のデータの場合、LOF はしばしばより細かい識別を提供します。

関連する手法

参考文献

  1. Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.

    DOI 文献を開く
    コピーしました。
  2. Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.

    ISBN:978-3-319-47577-6
    コピーしました。
  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.

    ISBN:978-0-387-84857-0
    コピーしました。