[Anomaly Detection] Local Outlier Factor

모두의 연구소에서 스터디 참여중인 이상탐지 관련 포스팅입니다. Local Outlier Factor라는 고전적인 방법론이라고 보시면 됩니다. 저희 스터디가 고려대 강필성 교수님의 커리큘럼을 기반으로 이루어지고 있어서 더 궁금하신 분들은 https://github.com/pilsung-kang/Business-Analytics-IME654-/tree/master/03 을 참고하시기 바랍니다. 그림 자료도 해당 강의에서 퍼왔습니다. (페이지에 다른 이상탐지 관련 강의도 업로드해두셨습니다)

 

일단 어떤 식으로 이상탐지를 진행할 것인가에 대한 고민을 먼저 보시죠.

이 그림에서 outlier라고 판단할 수 있는 관측치는 o1, o2 두 개 입니다. 사실 o1의 경우에는 사람이든 모델이든 쉽게 이상치로 추출할 수 있는 관측치인데, 관건은 o2입니다. C1 그룹의 관측치들에 비하면 C2 그룹과 떨어진 거리가 그렇게 멀진 않습니다만, C2 그룹은 워낙에 뭉쳐있는 특성을 보이므로 C2 그룹 간 거리를 감안하면 o2는 이상치로 판단할 수 있어야할 것입니다. 단순 '거리'의 개념 외에 추가적인 다른 개념을 살펴보아야 한다는 것입니다. 

 

그래서 논문에서는 5 step에 걸쳐 metric을 정의합니다. 

1) k-distance : p라는 instance 입장에서 생각했을 때, 동률(무승부)를 고려했을 때 k번째로 멀리 떨어진 instance까지의 거리를 말합니다. 아래 예시에서 p의 3-distance를 구해보면 1.5라는 것을 알 수 있습니다. 

2) k-distance neighborhood : k-distance 보다 작거나 같은 거리에 떨어져있는 (자신을 제외한) instance들의 집합입니다.

3) reachability-distance : o의 k-distance 내에 있는 것들은 k-distance로 치환해주고 그 바깥에 있는 것들은 o로부터의 거리가 됩니다. 

4) local reachability density : '밀도'이니 관측치가 밀집해 있는 곳에서는 높은 값이 나오도록 정의해줍니다. 즉, p의 local reachability density를 구한다고 하면 일단 분자에는 p의 k-distance neighborhood 집합의 크기가 들어갑니다. 분모에는 이 집합 원소들 각각에 대해서 p까지의 reachability-distance를 구하여 합해줍니다. (주의할 점은 지금 우리가 보고자 하는 관심 instance p가 아니라 neighborhood 집합의 원소 o입장에서 위의 reachability-distance를 따져줍니다) 

예를 들어서 Case 1 같은 경우에는, o가 p의 k-distance 내에 있기도 하지만(neighborhood) p 역시 o의 k-distance 내에 있습니다. 즉, 분모에 들어가는 reachability distance 대부분이 k-distance로 치환된다는 이야기이죠. 하지만 Case 2의 경우는 그렇지 않습니다. o는 p의 k-distance 안에 들어가지면 거꾸로는 그렇지 않아서 분모의 reachability distnace 대부분은 o와 p 사이의 거리 자체가 됩니다. 

 

드디어 우리가 궁극적으로 정의하고자 했던 metric이 나옵니다.

5) Local Outlier Factor: 관심 대상 instance p의 local reachability density가 분모로, 그 neighborhood의 local reachability density 합계가 분자로 들어갑니다. 그런데, Case 1같은 경우에는 살펴봤던 것처럼 분모에 들어가는 p의 밀도도 높고, 분자로 들어가는 o의 밀도도 높습니다. Case 3는 분자, 분모가 둘다 밀도가 낮죠. 그런데, Case 2는 분모는 작지만 분자의 항들은 큰 값을 가집니다. 따라서 우리가 처음 궁극적으로 원했던 주변 녀석과는 다른 "outlier"를 올바르게 측정할 수 있다는 논리입니다. 

 

Local Outlier Factor는 연산량이 많다는 점, 그리고 측정된 metric이 타 데이터셋과 비교가 불가능하다는 점(측정한 local outlier factor는 해당 데이터셋 내부에서만 instance끼리 비교가 가능하다는 것입니다)이 단점이라고 합니다. 그럼 이것으로 포스팅을 마치겠습니다.