Local Outlier Factor (LOF)

이번 포스트에서 다룰 내용은 딥러닝 기반 이상탐지 말고 2000년에 발표된 전통적인 이상탐지 방법, Local Outlier Factor (LOF) 입니다. LOF 의 기본 아이디어는 전체 데이터 분포에서 지역적인 밀집도를 (density) 고려하겠다는 것에서부터 출발합니다. 일반적인 density based 방법은 특정 거리 안에 들어오는 데이터의 개수로 밀집도를 정의하나 밑의 그림의 C1/C2 처럼 밀집된 정도가 각각 다르다면 밀집도를 정의하는 특정 임계치를 정하는 것이 어렵습니다. 밑의 경우에 대해 기존 density based 방법은 o1은 이상치로 잘 탐지하겠지만 o2는 탐지를 못할 가능성이 높겠죠. 따라서 LOF는 지역적인 밀집도를 고려하여 이상치를 판단합니다. 

https://godongyoung.github.io/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D/2019/03/11/Local-Outlier-Factor(LOF).html

LOF

LOF에서는 먼저 특정 데이터 $x$에서 $k$번째 가까운 k-nearest-neighbor 까지의 거리인 $k-distance(x)$를 정의합니다. 예를 들어 $3-distance(x)$라면 $x$에서 3번째로 가까운 이웃점까지의 거리가 되겠죠. $k-distance(x)$가 같은 점이 여러개 있을 수 있으므로 $k-distance(x)$ 안에 있는 자기자신을 제외한 모든 점의 집합을 $N_k (x)$로 정의합니다. k-NN 알고리즘처럼 명확한 개수의 $k$를 정하는 것은 상황마다 다르겠으나 일반적으로 $k$가 작으면 더욱 지역적으로 포커싱하고 $k$가 크면 위 그림의 o2와 같은 지역적인 이상치를 놓칠 수 있습니다.

Reachability distance

정의한 $k-distance(x)$를 가지고 reachability distance $reach-dist(x, n)$을 계산합니다. 이것은 $x$ 기준에서 다른 데이터 $n$의 $k-distance(n)$을 고려한 거리로 다음과 같이 정의됩니다.

$reach-dist(x, n)=max(k-distance(n), dist(x, n))$

이를 해석하면 $x$가 $k-distance(n)$ 안에 존재하면 $k-distance(n)$이 되고 밖에 존재할 경우 $x, n$의 거리가 됩니다. 여기서 $x, n$이 매우 가까이 있을때에는 $dist(x,n)$이 아니라 $k-distance(n)$이 되게 되는데, 이는 LOF가 추후 지역 별 밀도를 고려하여 이상치를 판단하는데 지나치게 밀집되어 있는 구간이 고평가 되지 않도록 하는 최소한의 버퍼로 작동합니다.

Local reachability density

$reach-dist(x, n)$을 이용하여 local reachability density (lrd)를 계산합니다. $x$에 대한 lrd, $lrd(x)$를 계산하기 위해서 $x$와 $N_k (x)$의 모든 점에 대한 $reach-dist$의 평균을 계산하고 역수를 취합니다. 역수를 취하는 이유는 LOF는 지역 별 밀도를 고려하고 거리가 가까울수록 (작을수록) 밀도가 높기 떄문입니다.

$lrd(x) = [\frac{\sum_{n\in N_k (x)}reach-dist(x, n)}{N_k (x)}]^{-1}$

lrd가 크면 그만큼 밀도가 낮다는 것이므로 $x$가 주변 점들과 어느 정도 멀리 떨어져 있다는 것이고 반대의 경우 주변 점들과 어느 정도 가까이 존재한다고 생각할 수 있습니다. Figure 1에서의 case 1의 파란색 점의 경우 평균거리가 작아 lrd가 높을 것이나 case 2의 파란색 점은 주변 초록색 점과 멀리 떨어져 있으므로 lrd가 낮을 것입니다.

Figure 1

Local Outlier Factor

데이터 $x$에 대해 구한 $lrd(x)$와 $N_k (x)$에 속한 점들의 lrd의 비율을 통해 $lof(x)$를 계산합니다. 즉, $lof(x)$는 $lrd(x)$와 $x$의 이웃점들의 $lrd$의 비율의 평균으로 밀도를 고려하여 $x$의 이웃과의 평균거리와 $N_k (x)$의 이웃간의 평균거리를 비교하곘다는 것으로 다음과 같이 정의할 수 있습니다.

$lof(x) = \frac{\sum_{n\in N_k (x)}\frac{lrd(n)}{lrd(x)}}{N_k (x)}$

$x$의 이웃과의 평균거리와 $N_k (x)$의 이웃간의 평균거리가 비슷하다면 $lof(x)$는 1에 매우 근접할 것이고 $x$의 이웃과의 평균거리가 $N_k (x)$의 이웃간의 평균거리보다 크다면 $lof(x)$가 1보다 매우 커져 이상치로 판단될 확률이 높아집니다. $x$가 이상치일때 $x$의 최근접 이웃들 자체의 최근접 이웃점들에 $x$가 포함되지 않을 것이기 때문이죠. 

또한, $reach-dist(x,n)$에서 $k-nearest(n)$으로 하방을 정해주었기 때문에 엄청나게 밀집된 지역에서의 $lrd, lof$가 미세한 차이로 인해 민감해지는 것을 robust 하게 방지한 것을 알 수 있습니다. 따라서 각 지역별로 밀도를 고려하여 평균거리를 계산하기 때문에 밀집된 지역/덜 밀집된 지역에 대하여 기존 방법대비 상당히 공평하게 이상치를 판단할 수 있습니다.

In python

파이썬에서는 sklearn.neighbors 모듈의 LocalOutlierFactor 함수가 LOF를 정의합니다. 주 파라미터는 "num_neighbors"와 "contamination" 으로 "num_neighbors" 는 $k$로 디폴트는 20으로 지정되어 있습니다. "contamination" 파라미터는 데이터에 포함된 이상치의 비율로 이 값에 따라 $lof$ 값에 따른 이상치를 판단하기 위한 임계치를 결정합니다. fitting 이후의 각 데이터의 이상치 여부는 "negative_outlier_factor_" 속성으로 파악할 수 있으며 $lof$에 마이너스 부호를 붙여 높을 수록 정상 데이터라 판단합니다.

LocalOutlierFactor Example

 

참조

• godongyoung.github.io/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D/2019/03/11/Local-Outlier-Factor(LOF).html
• towardsdatascience.com/local-outlier-factor-for-anomaly-detection-cc0c770d2ebe
• scikit-learn.org/stable/modules/generated/sklearn.neighbors.LocalOutlierFactor.html