Machine Learning/Algorithm

Local Outlier Factors (LOF)

고슴군 2019. 10. 7. 14:58

Local Outlier Factors (LOF)

: 거리 기반의 outlier 탐지 기법.
거리 기반이지만, (내 관심대상 A의 k개 neighbor과의 평균거리)와 (그 neighbor들의 k개 neighbor 평균거리)를 비교하여, 주변과 비교했을 때 밀집해있는지 '밀도'를 측정한다. 

위 그림에서 O1은 이상치라는걸 바로 알 수 있지만 O2는 이상치라고 말할 수 있을까요? 얼핏 보기엔 아닌 것 같지만 근처에 빡빡하게 밀집해 있는 데이터가 있으므로 이상치라고 볼 수도 있을 것입니다. LOF(Local outlier factors)관점에서는 O2도 이상치입니다. 밀집 지역에서 밀도 관점으로 봤을 때 급격한 감소가 이루어지기 때문입니다. 즉, LOF는 데이터가 가지는 상대적인 밀도까지 고려한 이상치 탐지 기법입니다.

 

수식 살펴보기

k-distance

그래서 LOF에서는 $k-distance$라는 개념을 사용합니다. $k-distance$ A로부터 k번째 근접 이웃까지의 거리를 뜻합니다. 그리고 $k-distance$안에 들어오는 오브젝트의 집합을 $N_k(A)$라고 정의합니다. 쉽게 얘기하면 $k-distance$보다 작거나 같은 거리를 가지는 수 입니다.

 

Reachability distance

$$ reachability-distance_k(A,B) = max \left \{ k-distance(B), dist(A,B) \right \} $$

다음은 reachability distance입니다. 막상 수식을 보면 복잡하게 보이지만 간단히 말해서 A와 B까지의 거리 그리고 k-distance중 큰 값을 사용하면 됩니다. k-distance 안에 들어오는 object들은 전부 원 위로 밀어내고 원 밖은 그대로 거리 값을 사용하는게 reachability distance입니다. 만약 항상 k-distance를 사용한다면, LOF가 아닌 Simplified-LOF가 됩니다.

 

위 그림에서도 A를 기준으로 봤을 때, B와 C까지의 reachability-distance는 원 밖으로 밀어내서 3-distance(A)와 같아집니다. 그리고 D의 경우는 원 밖에 있으니까 그대로 거리값을 사용하게 됩니다.

 

Local reachability density

오브젝트 A에 대한 local reachability density는 다음과 같이 구할 수 있습니다.

 

분자는 k-distance 안의 개체 수이고 분모는 A에서 다른 오브젝트들까지의 reachability-distance의 입니다. A로부터 다른 오브젝트들 까지의 reachability distance들의 평균 식을 거꾸로 뒤집은 것과 같습니다.

 

  • Case 1 : 만약 A가 밀도가 높은(dense area) 지역에 위치한다면 분모가 작아질 것이고 이에 따라 $lrd_k(A)$값이 커지게 됩니다.
  • Case 2 : 반대로 A가 밀도가 높지 않은(sparse area) 지역에 위치한다면 분모가 커지게 되고 이에 따라 $lrd_k(A)$값도 작아지게 됩니다.

 

Local Outlier Factor

위 식에서 분자를 보면 A에 속한 B의 local reachability density의 평균을 $|N_k|$로 나눴다는것을 확인할 수 있습니다. 여기서 산출된 LOF score는 결국 A가 얼마나 이상치인가를 나타내는 정도라고 볼 수 있습니다.

쉽게 이해하기 위해서 아래 그림을 예시로 들어보겠습니다. 파란색 점이 A이고 초록색 점이 B입니다. $LOF(A)$값이 크다는 것은, 초록색 점들의 $lrd(B)$가 높고 파란색 점의 $lrd(A)$가 낮다는 말과 같습니다. 즉, 초록색 점들이 밀도가 높은 지역에, 파란색 점은 밀도가 낮은 지역에 위치한다는 말입니다.

정리해보자면 파란색 점이 밀도가 낮은 지역에 있을수록, 초록색 점들이 밀도가 높은 지역에 위치할수록 파란색 점의 LOF값은 커지게 됩니다. 쉬운 이해를 위해 표도 같이 첨부하겠습니다.

 

 

 

Conclusion

LOF의 장점으로는, 굉장히 밀집된 클러스터에서 조금만 떨어져 있어도 이상치로 탐지해준다는 점입니다. 아래 그림에서 숫자들이 LOF 스코어를 나타내고 있습니다. 굉장히 뺵빽한 곳에 가까운 이상치들은 확실히 더 높은 LOF값을 가지는 것을 확인할 수 있습니다.

 

 

단점이라면 이상치라고 판단하는 기준을 어디에 잡아야할지 정해줘야 한다는 것입니다. 위 그림의 경우 2차원 데이터라서 쉽게 시각적인 도움을 받을 수 있지만 차원이 늘어나면 판단하기 골치아프게 됩니다. 어떤 데이터셋에서는 1.1이라는 값이 이상치이지만 어떤 데이터셋에서는 2라는 값을 가지고 있어도 정상 데이터일 수 있습니다.

 

LOF score

  • Score가 Nan인 경우 (분자가 0/0인 경우)
    - 해당 point가 같은 위치에 neighbor가 매우 많은 경우. 이 경우는 outlier가 아니다.
  • Score가 Inf인 경우 (분자가 n/0인 경우)
    - 해당 point를 제외하고, neighbor들이 같은 위치에 있을 경우. 해당 point는 그 무리에 해당하지 않기 때문에 outlier이다.

Hyper-parameter (k 값) 지정하는 방법

저자의 논문(https://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf) 에 따르면, 여러 k값을 이용해 anomaly score를 계산하고, 각 데이터의 score 중 최댓값을 사용하는 방법을 제시한다. 

그럼에도 불구하고, k 값의 range를 결정해줘야 한다. k 값에 매우 민감하게 성능이 변한다.

 

 

 

[참조]

https://jayhey.github.io/novelty%20detection/2017/11/10/Novelty_detection_LOF/ 를 가져온 것입니다.

https://turi.com/learn/userguide/anomaly_detection/local_outlier_factor.html (score 값)

반응형