抄訳 LOF: Identifying Density-Based Local Outilers(2000)

November 28, 2022

局所外れ値因子法(LOF)は、あるインスタンスが外れ値かを、その周囲のインスタンスとの距離をもとに判定する。 異常検知の手法の中には異常か正常かの二値を出力するものがあるが、LOFは[0,1]区間の値を出力する。 L1に近いほど正常とみなす。 密度の高いクラスタと低いクラスタがあり、密度の高いクラスタの少し遠くに外れ値とみなすべきインスタンスがあるとする。 このとき、密度の低いクラスタのインスタンス間の距離を基準にすると、密度の高いクラスタのインスタンスと外れ値のインスタンス間の距離は大きいとみなせない。しかし、外れ値のインスタンスのそばの密度の高いクラスタの距離を基準にすれば、外れ値のインスタンスは周囲のインスタンスから遠いとみなせる。 このように、密度の違うクラスタがあるデータセットでも、インスタンスに近いサンプル間の距離を基準にすることで、他のクラスタの密度で測れば正常なインタンスと判定される外れ値を検出できる。

インスタンスの集合を\(D\), インタンス\(p\), \(o\)の距離を\(d(p, o)\)として、\(\textit{k-distance}(p)\)を\(p\)から\(k\)番目の近傍のインタンスの距離とする。 厳密に言えば、少なくとも\(k\)個の\(o'\in D \setminus \{p\}\)が\(d(p,o') \le d(p,o) \)であり、かつ、高々\(k-1\)個の\(o'\in D\setminus \{p\}\)が\(d(p, o') < d(p, o)\)である値である。

\(o\)への到達可能性距離\(\textit{reach-dist}_k(p,o)\)を\(\max \{\textit{k-distance}(o), d(p, o)\}\), \(N_k\)を\(p\)からの\(k\)近傍の要素の集合として、局所到達可能性密度\(\textit{lrd}_k(p)\)を

$$ lrd_{k}(p)=\frac{|N_k(p)|}{\sum_{o\in N_k(p)}\textit{reach-dist}_k(p,o)} $$ と定義したとき、\(p\)に対する出力\(\textit{LOF}_k(p)\)は

$$ \textit{LOF}_k(p)=\frac{\sum_{o\in N_k (p)} \frac{\textit{lrd}_k(o)}{\textit{lrd}_k(p)}}{|N_k(p)|} $$ となる。

論文へのリンク

雑記

到達可能性距離は対称性を満たさなそうなので、厳密には距離ではなさそう。 密度がほぼ同じクラスタが複数あり、1つのクラスタだけ他のクラスタから遠く離れている場合には、遠く離れたクラスタの要素を外れ値とみなすことはできないようだ。