[Anomaly Detection] Local Outlier Factor (LOF)

9e0na·2023년 9월 13일

Anomaly Detection

[이상치탐지]

목록 보기

4/6

출처: DSBA 연구실 유튜브 와 DSBA 연구실 강의자료 를 참고하면서 스터디를 진행하였습니다.

주제: Anomaly Detection: Local Outlier Factor (LOF)

1. Local Outlier Factors (LOF)

밀도 기반 이상치 탐지의 연장선에 있음.

어떤 객체가 주어졌을 때, local density를 고려해서 정의를 하자!

데이터 포인트의 지역적 밀도와 그 주벼 데이터 포인트의 밀도를 비교함으로써 이상치를 탐지함.

LOF는 데이터 포인트의 극소적 밀도 변동을 감지하여 클러스터 내부의 밀도가 높은 지역과 낮은 지역을 구별 할 수 있음.

📊 알고리즘의 단계

1. 거리 계산

2. Reachability Distance 계산

3. Local Reachability Density (LRD) 계산

4. LOF 계산

📌 장점

1. 비모수적

데이터의 분포에 대한 가정 필요X

2. 국소적 특성

데이터 포인트의 국소적 밀도를 기반으로 이상치 탐지하기 때문에 다양한 밀도를 갖는 클러스터에서도 잘 작동함.

*국소적 밀도
: 데이터의 특정 지역 or 부분에서의 데이터 포인트의 밀도
=> (바뀐점) 특정 데이터 포인트 주변의 데이터 포인트의 수와 그 밀도를 기반
=> (기존) 전역적인 밀도 기반 이상치 탐지 방법은 데이터셋 전체의 밀도를 기반으로 함.

📌 단점

1. 계산 복잡도

2. 하이퍼파라미터 선택

선택한 이웃의 수 k에 따라 크게 달라질 수 있음.

3. score가 normalization 되어 있지 않음.

=> 같은 dataset에서는 LOF score가 크면 클수록 이상치일 확률 up
=> dataset이 달라지면, 단순히 이상치 score의 절대값을 가지고 이상치의 정도를 비교하는 건 위험함.

1.1. Definition

1. k-distance of an object p

거리에 대한 정의

여기서 $d(p,o)$ 란 $p$ 와 $o$ 의 거리를 의미함.

$d(p,o') <= d(p,0)$ 를 만족하는 최소한 k개의 o'이 있어야 됨.

최대로 k-1개에 대해서는 $d(p,o') < d(p,o)$ 를 만족해야 함.

"Simply it is the distance to the k-th nearest neighbor considering ties."
📌 동률이 존재했을 때, 그 동률을 고려해서 거리를 정렬시켰을 때 k번째 해당하는 거리를 의미함.

0.5 (1)
1.0 (2)
1.5 (3) 📌
1.5 (4)
1.5 (5)

5개 >= k(3)

2개 < k(3)

2. k-distance neighborhood of an object p

객체들의 집합에 대한 정의

$q$ : 현재 데이터셋에서 $P$ 를 제외한 집합 &
$d(p,q) <= k-distance(p)$

각 데이터 포인트에 대해 최근접 이웃을 찾기 위해 모든 데이터 포인트 간의 거리를 계산함.

p의 3-distance는 3번째로 가까운 이웃과의 거리인 1.5임.

조건1 $d(p,o')$ <= $d(p,o)$ : 5개 >= k:3 ⭕️
조건2 $d(p,o')$ < $d(p,o)$ : 2개 < k:3 ⭕️

p의 3-distance는 3번째로 가까운 이웃과의 거리인 1.0임.

조건1 $d(p,o')$ <= $d(p,o)$ : 4개 >= k:3 ⭕️
조건2 $d(p,o')$ < $d(p,o)$ : 1개 < k:3 ⭕️

p의 3-distance는 3번째로 가까운 이웃과의 거리인 1.0임.

조건1 $d(p,o')$ <= $d(p,o)$ : 4개 >= k:3 ⭕️
조건2 $d(p,o')$ < $d(p,o)$ : 0개 < k:3 ⭕️

3. reachability distance

도달 가능거리라는 의미임.

여기서 $distance(o)$ 에서 $p$ 가 아니라 $o$ 라는 점이 매우 중요함.

데이터 포인트 $A$ 와 $B$ 간의 reachability distance는 $A$ 와 $B$ 사이의 거리와 $B$ 의 k-번째 최근접 이웃까지의 거리 중 더 큰 값임.
📌 이는 $A$ 가 $B$ 의 밀도가 높은 지역에 있을 때 그 거리를 과대 평가하는 것을 방지하기 위한 것임.