Local Outlier Factor (LOF) の算出方法、スクラッチでの実装

Local Outlier Factor (LOF)の概要

異常検知に用いられる手法の一つです。
各点それぞれのk 個の近傍点との距離から局所密度を推定し、自身と近傍群の局所密度を比較したとき、自身の局所密度が極めて低い場合は異常値と判断するというのが基本的なアイディアです。

詳しくは下記のページも参考にしましょう。
[ Local Outlier Factor (LOF) による外れ値検知についてまとめた]
(https://hktech.hatenablog.com/entry/2018/09/04/002034)
[[デモのプログラムあり] Local Outlier Factor (LOF) によるデータ密度の推定・外れサンプル(外れ値)の検出・異常検出]
(https://datachemeng.com/local_outlier_factor/)

LOFの算出方法

LOFを計算するためには、
・reachability distance（到達可能性距離）を計算
・lrd（local reachability density：局所到達可能性密度）を計算
・LOFを計算
というステップを踏みます。

reachability distance（到達可能性距離）を計算

点Aとその近傍点Bにおいて、下記の2つの距離の大きい方をAB間のreachability distanceとして定義し、reachability-distance$^{}_{k}$(A,B)と表します。
・AとBとの距離
・Bのk番目の近傍点との距離

具体例として、k=2、下記の点A～点Eを考えます。
k=2の時、Aの近傍点はBとEです。AとB、AとE、それぞれについて上記の2つの距離を計算し、それぞれのreachability-distance$^{}_{k}$を算出します。

lrd（local reachability density：局所到達可能性密度）を計算

lrdは、ある点におけるk個の近傍点とのreachability-distanceの平均の逆数です。
上記の例の場合、lrd$^{}_{k}$(A)は下記の通り計算します。

LOFを計算

最後にLOFを計算します。ある点におけるk個の近傍点のlrdをそれぞれ自身のlrdで割った値を平均したものがLOFとなります。

上記の例の場合、LOF$^{}_{k}$(A)は下記の通り算出されます。

実装

sklearnのLocalOutlierFactorを使用した実装

sklearnのパッケージを使用すれば数行で実装できます。

import numpy as np
from sklearn.neighbors import LocalOutlierFactor

X = [[-1.1], [0.2], [101.1], [0.3]]

clf = LocalOutlierFactor(n_neighbors=2)

# -1が異常値
print(clf.fit_predict(X))
# > [ 1  1 -1  1]

# LOFの値（仕様上負の値に変換されている）
print(clf.negative_outlier_factor_)
# > [ -0.9821...,  -1.0370..., -73.3697...,  -0.9821...]

スクラッチでの実装

最後に理解を深めるためにスクラッチでも実装しました。(sklearnは使っているけど）

from sklearn.neighbors import NearestNeighbors

k = 2

# 各点の近傍点とその距離を計算
# 最も近い点は自身が選ばれてしまうので（距離0）、予めk+1分計算
knn = NearestNeighbors(n_neighbors=k+1)
knn.fit(X)
distances, neighbors_index = knn.kneighbors(X)

# 自身を除外
distances = distances[:,1:] # 近傍点との距離
neighbors_index = neighbors_index[:,1:] # 近傍点のindex

###### reachability distance ###### 

# 各点の近傍点における、k番目に近い点との距離
dist_k = distances[neighbors_index, k - 1] # indexは0始まりなので-1する

# 最大値を取得
reach_dist_array = np.maximum(distances, dist_k)

###### lrd  ###### 

# 値が0となることを防ぐために+ 1e-10
lrd = 1.0 / (np.mean(reach_dist_array, axis=1) + 1e-10)

###### LOF  ###### 

# sklearnのLocalOutlierFactorに合わせてLOFは負にする
lrd_ratios_array = lrd[neighbors_index] / lrd[:, np.newaxis]
negative_outlier_factor_scratch = -np.mean(lrd_ratios_array, axis=1)

# スクラッチの結果がsklearnと一致しているかを確認
clf.negative_outlier_factor_  == negative_outlier_factor_scratch
# > array([ True,  True,  True,  True])

参考

[局所外れ値因子法 - Wikipedia]
(https://ja.wikipedia.org/wiki/%E5%B1%80%E6%89%80%E5%A4%96%E3%82%8C%E5%80%A4%E5%9B%A0%E5%AD%90%E6%B3%95)
[ Local Outlier Factor (LOF) による外れ値検知についてまとめた]
(https://hktech.hatenablog.com/entry/2018/09/04/002034)
[[デモのプログラムあり] Local Outlier Factor (LOF) によるデータ密度の推定・外れサンプル(外れ値)の検出・異常検出]
(https://datachemeng.com/local_outlier_factor/)