局所外れ値因子法

異常検知における局所外れ値因子法（きょくしょはずれちいんしほう、）は Markus M. Breunig、、Raymond T. Ng、Jörg Sander によって2000年に提案されたアルゴリズムで、任意のデータ点での、近傍点に対する局所的な変動を測ることによって異常を発見するものである。
局所外れ値因子法は、コア距離
（core distance）や到達可能性距離
（reachability distance）等の概念をDBSCANやといったアルゴリズムと共有しており、これらは局所密度の推定に用いられる。
基本的なアイディア.
局所外れ値因子法は局所密度の概念に基づいている。ここでの「局所（locality）」は formula_1 個の最近傍で与えられ、それらの距離によって密度が推定される。あるオブジェクトの局所密度をその近傍群の局所密度と比較することで、密度が同程度であるような領域と、周囲と比べて密度が有意に低い点を特定することができる。こうした点が外れ値だと考えられる。
局所密度は、その近傍から「到達（reach）」するのにかかる標準的距離を使って推定される。局所外れ値因子法での「到達可能性距離（reachability distance）」は、クラスタ内でより安定的な値が生じるよう追加的に定義された尺度である。
正式な定式化.
formula_2 を、オブジェクト formula_3 の "k" 番目の近傍までの距離とする。ここで "k" 個の最近傍とはこの距離以下の全てのオブジェクトの集合で、「タイ」が存在する場合は個数が "k" より大きくなり得ることに注意する。"k" 最近傍オブジェクトの集合を formula_4 と書く。
この距離は、到達可能性距離（reachability distance）と呼ばれる値を定義するのに用いられる：
formula_5
つまり、オブジェクト formula_3 の formula_7 からの「到達可能性距離」は、それが formula_7 の formula_9 以上である限りは、2オブジェクト間の真の距離と一致する。formula_7 の "k" 最近傍集合（formula_7 のコア（core）。DBSCANクラスタ解析を参照）は全て等距離だと見なせる。このような距離を考えるのは、結果をより安定的なものにするためである。これは対称的でないので、数学的定義上の距離にはなっていないことに注意する。 （常に formula_9 の方を使うのはよくある誤りで、そのような場合は Simplified-LOF と呼ばれるわずかに異なる手法になる。）
オブジェクト formula_3 の局所到達可能性密度（local reachability density）は
formula_14
と定義される。これはオブジェクト formula_3 の、その近傍群からの到達可能性距離の平均の逆数をとったものである。formula_3 から近傍へ到達する距離の平均ではなく（これは定義上 formula_2 に等しい）、近傍から formula_3 へ到達する距離の平均であることに注意する。オブジェクトが重なっている点ではこの値は無限大になり得る。
次に以下のようにして、近傍群と局所到達可能性密度が比較される。
formula_19
これは「近傍群の局所到達可能性密度の平均」を「オブジェクト自身の局所到達可能性密度」で割ったものである。これが formula_20 に近い値であるとき、オブジェクトはその近傍と同程度（similar）である（よって外れ値ではない）。formula_20 を下回るとき、その点は密度が高い領域（内部点（inlier））に位置する。formula_20 を有意に上回るとき、外れ値である。
LOF(k) ~ 1 は、近傍と同程度の密度であることを意味する。 
LOF(k) < 1 は、近傍よりも高密度であることを意味する。
LOF(k) > 1 は、近傍よりも低密度であることを意味する。
利点.
局所外れ値因子法は局所的なアプローチであるため、データセットの別の領域に位置していれば外れ値とはなっていないであろう点も、外れ値として検知できる。例えば、かなり密度の高いクラスタまでの距離が「小さい」点は、（まばらなクラスタ内の点も近傍までの距離は同程度かもしれないが）外れ値になる。
局所外れ値因子法を幾何学的な直観で捉えられるのは低次元ベクトル空間の場合に限られるが、このアルゴリズムは非類似度関数（dissimilarity function）が定義できるような任意の状況に対し適用できる。この手法は経験的に、数多くの設定下で非常に上手く働くことが示されており、例えば侵入検知システムや加工（processed）分類ベンチマークデータに関して、しばしば競合する手法より優れた結果を出す。
局所外れ値因子法や類似する手法群は、他の様々な問題、例えば地理データ、動画ストリーミング、著者ネットワーク（authorship network）における外れ値の検知に対しても容易に一般化できる。
欠点および拡張.
出力値が分数であるため、解釈が難しい。値が 1 またはそれ以下であれば明確に外れ値でないと判断できるが、外れ値であるかどうかに対する明確な規則は存在しない。あるデータセットでは値が 1.1 であれば外れ値とされる一方で、別のデータセットあるいは別の（局所的な変動の激しい）パラメータの下では値が 2 であってもなお、外れ値とされないかもしれない。手法の局所性のために、こうした相違は一つのデータセットの中でも発生し得る。これらの特質の改善を試みる、局所外れ値因子法の拡張が存在している。