0Local Outlier Factor (LOF)

明治大学 理⼯学部 応用化学科
データ化学⼯学研究室 ⾦⼦ 弘昌

Local Outlier Factor (LOF) とは︖
データ密度を推定する⼿法
k 最近傍法 (k-Nearest Neighbor, k-NN) による密度推定と⽐べて、データ分布における局所的なデータ密度の違いを考慮可能
LOF の結果から外れサンプル検出や (装置やプロセスなどの)異常検出が可能

1復習) k-NN によるデータ密度の指標例) k = 3x2

距離 : 小さい

データ密度 : 高い

距離 : 大きいx1
データ密度 : 低い

k 個の距離の平均をデータ密度の指標とする
指標の値が小さいほど、データ密度が高い

2

3k-NN で何が問題か︖
データがまんべんなく分布していればよいが、領域によってデータ分布に違いがあると、
x2

このあたりのサンプルのばらつきが大きく、「距離のしきい値を大きくしても」 いいのかな、となり、

x1サンプルが密に固まっている領域において、このような少し外れたところにあるサンプルを外れサンプル (データ密度が低い) として検出できない

LOF ではどうするか︖
最も近い k 個のサンプルとの距離だけでなく、その k 個のサンプルに最も近い k 個のサンプルとの距離も考慮する︕

区別できる︕

4あるサンプルの LOF をどう計算するか︖
あるサンプル A と最も距離の近い k 個のサンプル郡を Nk(A) とする
A とサンプル B との距離を d(A, B) とする
A に対して k 番目に近いサンプルと A との距離を k-distance(A) とする
A と B との間の reachability distance という距離 reach-distk(A,B) を以下のように定義する
reach-distk(A, B) = max(d(A, B), k-distance(B))

5あるサンプルの LOF をどう計算するか︖ 1/4
reach-distk(A, B) = max(k-distance(B), d(A, B))
A と B が離れていると (そして B の近くにサンプルがあると)、reach-distk(A, B) は単純に A と B の距離
A と B が十分近くにいると (そして B の近くにサンプルがあると)、reach-distk(A, B) は k-distance(B) に置き換わる
注) reach-distk(A, B) には対称性がないため、数学的には距離ではない6

あるサンプルの LOF をどう計算するか︖ 2/4
A と Nk(A) の間の reachability distance の平均を
mean-reach-distk(A, Nk(A)) とすると、
kmean-reach-dist k ( A, N k ( A ) ) = reach-dist ( A, C )kC∈N k ( A )kA の local reachability density (lrdk(A)) を以下のように定義する

1lrd k ( A ) =mean-reach-dist k ( A, N k ( A ) )距離 distance が小さいと、密度 density が大きい

7

あるサンプルの LOF をどう計算するか︖ 3/4
A と Nk(A) の間の reachability distance の平均を
mean-reach-distk(A, Nk(A)) とすると、
kmean-reach-dist k ( A, N k ( A ) ) = reach-dist ( A, C )k

C∈N k ( A )kA の local reachability density (lrdk(A)) を以下のように定義する

1
lrd k ( A ) =mean-reach-dist k ( A, N k ( A ) )距離 distance が小さいと、密度 density が大きい

8

あるサンプルの LOF をどう計算するか︖ 4/4LOF の値 (LOFk(A)) は以下のように計算されるk

LOFk ( A ) = lrd ( C )kC∈N k ( A )k1

lrd k ( A )Nk(A) の local reachability density を平均し、A の local reachability density で標準化している

9

実⾏例

10

左のようなサンプルにおいて、k-NN とLOF をそれぞれ実⾏し、外れサンプルの割合を 1% として、正常なサンプル (外れサンプルでないサンプル)の領域を⾚線で囲むと、以下の通り。
k-NN では右下のデータが密集した領域の正常領域が広くなっているが、LOF では適切な領域を正常としている

Python コード例
こちら https://github.com/hkaneko1985/dcekit にある
demo_lof.py で「実⾏例」と同じことができます11scikit-learn を使うときの注意点

12scikit-learn の sklearn.neighbors.LocalOutlierFactor が便利

https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LocalOutlierFactor.html

トレーニングデータから外れサンプルを探すときには (anomaly detection)、デフォルトの設定 (novelty=False) でよいが 、トレーニングデータが存在するときの、テストデータのデータ密度を計算するときは(novelty detection)、novelty=True とするcontamination で外れサンプルの割合を設定する必要があるk-NN, OCSVM との⽐較・注意点
k-NN• データ分布に違いがあると対応が難しい• 次元の呪いの影響を受ける
OCSVM (One-Class Support Vector Machine)• データ分布に違いがあると対応が難しい• 次元の呪いの影響を受けにくい
LOF• データ分布に違いがあっても対応できる• 次元の呪いの影響を受ける

13

参考文献

14 M. M. Breunig, H. P. Kriegel, R. T. Ng, J. Sander, LOF: identifying density-based
local outliers, Proceedings of the 2000 ACM SIGMOD international conference on
Management of data, 93-104, 2000. DOI: 10.1145/342009.335388
https://dl.acm.org/citation.cfm?id=335388
 https://en.wikipedia.org/wiki/Local_outlier_factor
 J. Lee, B. Kang, S. H. Kang, Integrating independent component analysis and local
outlier factor for plant-wide process monitoring, Journal of Process Control,21, 1011-1021, 2011. DOI: 10.1016/j.jprocont.2011.06.004
https://www.sciencedirect.com/science/article/pii/S0959152411001144