LOF (Local Outlier Factor)

LOF (Local Outlier Factor)

- 밀도 기반의 이상탐지 방법으로 local을 나누어 local의 밀도를 이용해 각 point 마다 factor를 부여하여 이상치를 탐지하는 방법

- LOF는 각각의 관측치가 데이터 안에서 얼마나 벗어나 있는가에 대한 정도(이상치 정도)를 나타냄

- LOF의 가장 중요한 특징은 모든 데이터를 전체적으로 고려하는 것이 아니라, 해당 관측치의 주변 데이터(neighbor)를 이용하여 국소적(local) 관점으로 이상치 정도를 파악

- 아래 그림의 O2와 O3가 가진 주변 point들과의 거리를 보면 당연히 O2가 O3보다 짧을 테지만, 국소적인 밀도관점에서 보면 abnormal score는 O2가 O3보다 크게 끔 만드려는 것이 LOF의 개념

- 즉, 데이터 안에서 밀도기반의 각 군집들을 생성하여 해당 군집에 얼마나 떨어져있는지를 확인하여 abnormal score를 만들어 outlier를 제거하는 개념

  > 이상탐지를 하기엔 이상탐지 집단의 규모가 크면 탐지하기 어려울 수 있지 않을까?

  > 이상탐지보다는 조금 다른 개념으로 noise 제거로 사용하는것이 어떨지

- LOF는 밀도기반의 이상치탐지이기 때문에 주변 데이터를 몇개까지 고려할 것인가를 나타내는 k라는 하이퍼-파라미터(hyper-parameter)만 결정하면 됨

 

주요개념

1. the distance between objects p and q

- d(p,q) : 관측치 p와 q의 거리

2. k-distance of an object p : 거리

- k-distance(p) : 관측치 p와 k번째로 가까운 이웃(포인트)의 거리

3. k-distance neighborhood of an object p : 개수 - Nk(p)

- Nk​(p) : 관측치 p의 k-distance(p)보다 가까운 이웃의 개수(집합(= k-distance(p)를 계산할 때 포함된 이웃의 집합))

- 관측치 p를 중심으로 k-distance로 원을 그릴대 원안에 들어와 있는 point 갯수

4. reachability distance of an object p w.r.t. object

- reach-distance는 O와 가까운 point는 3-distance(O)값을 가지고, O와 멀다면 distacne(실제거리)를 갖는다.

 

• 관측치 p가 o에서 멀다면 : 관측치 p와 o의 실제 거리
• 관측치 p가 o에서 가깝다면 : 관측치 o의 k-distance

5. local reachability density(lrd) of an object p

- 분모가 reachability-distance를 모두 더한 값이고, point의 카디널리티를 구함

- 수식을 해석하자면, 관측치 p에 대한 k-이웃의 reach-distk​(p,o) 평균의 역수입니다. 즉, 관측치 p주변에 이웃이 얼마나 밀도있게 있는가를 대변할 수 있음

- 정상일 경우(밀도가 높을 경우) => lrd가 커지고

- 이상치(outlier)일수록 => lrd는 작아질 것

- k=3 일때의 아래 예시

[예시1] : 관측치 p의 3-이웃이 가깝게 있고, 이웃 Oi​(i=1,2,3)의 reach-dist3​(p,oi​)도 작기 때문에 lrd3​(p)는 큰 값이 산출

[예시2] : 관측치 p의 3-이웃이 멀게 있고, 이웃 Oi​(i=1,2,3)의 reach-dist3​(p,oi​)이 크기 때문에 lrd3​(p)는 작은 값이 산출

 

6. local outlier factor(LOF) of an object p

- 이상치일수록 LOF는 크게됨 (lrd(O)를 이용하는 것은 주변 정보를 고려한 개념이라고 생각하면 됨)

- 밀도가 높은 군집의 경우, lrd(p)와 lrd(O)가 둘다 클 것이기 때문에 1에 가까운 숫자가됨

>> 즉, 정상일수록 1에 가까운 형태를 가짐

>> 밀도가 낮을면 1보다 큰 LOF값을 가질것

- 관측치 p의 이상치 정도를 나타내는 LOF는 아래와 같이 각 point별로 값을 나타낼수 있음

LOF < 1 : 밀도가 높은 분포

LOF ≒ 1 : 이웃 관측치와 비슷한 분포

LOF > 1 : 밀도가 낮은 분포, 크면 클수록 이상치 정도가 큼.

 

참조

Breunig, M. M., Kriegel, H. P., Ng, R. T., & Sander, J. (2000, May). LOF: identifying density-based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data (pp. 93-104).

https://www.youtube.com/watch?v=ODNAyt1h6Eg 

https://velog.io/@vvakki_/LOFLocal-Outlier-Factor

https://www.youtube.com/watch?v=wADcqMdpuv4