📖 이번 포스팅은 고려대학교 김성범 교수님의 강의영상을 참고하여 밀도기반 이상치 탐지 알고리즘 중 LOF에 대해 다루고자 합니다.
우선 Anomaly Detection이 무엇인지에 대해 알아봅시다.

Anomaly Detection (이상치 탐지)

Notion

• 쉽게 말해, 데이터 안에서 Normal(정상) sample과 Abnormal(비정상, 이상치, 특이치) sample을 구별해내는 문제를 의미합니다. 즉, 매우 많은 정상 데이터에서 극소수의 비정상 데이터를 구별하는 것이 목적입니다.
• 주로 이벤트 사건이 정상 데이터에 비해 적은 데이터를 다루는 분야에서 많이 사용합니다.
• Anomaly Detection은 학습 데이터 셋에 비정상적인 sample이 포함되는지, 각 sample의 label이 존재하는지, 비정상적인 sample의 성격이 정상 sample과 어떻게 다른지, 정상 sample의 class가 단일 class 인지 Multi-class 인지 등에 따라 다른 용어를 사용합니다.
  예를 들어, Novelty Detection라는 용어도 존재하나 이는 지금까지 등장하지 않았지만 충분히 등장할 수 있는 sample을 찾아내는 연구, 즉 데이터가 오염이 되지 않은 상황을 가정하는 연구와 관련된 용어라고 할 수 있고, Outlier Detection은 등장할 가능성이 거의 없는, 데이터에 오염이 발생했을 가능성이 있는 sample을 찾아 내는 연구와 관련된 용어 정도로 구분하여 정리할 수 있습니다.

Local Outlier Factor (LOF)

Notion

• 각각의 관측치가 데이터 안에서 얼마나 벗어나 있는가에 대한 정도(이상치 정도)를 나타냅니다. LOF의 가장 중요한 특징은 모든 데이터를 전체적으로 고려하는 것이 아니라, 해당 관측치의 주변 데이터(neighbor)를 이용하여 국소적(local) 관점으로 이상치 정도를 파악하는 것입니다.
• 정상객체는 주로 주변에 데이터가 많이 존재하며, 불량 객체는 주로 단독으로 존재함을 가정합니다.
• 주변 데이터를 몇개까지 고려할 것인가를 나타내는 k라는 하이퍼-파라미터(hyper-parameter)만 결정하면 되는 장점이 있습니다.
• 데이터가 많아질수록 계산복잡도가 올라가는 알고리즘입니다.
• 데이터가 고차원인 경우, 저차원으로 차원 축소하여 시행하는 것이 좋습니다.

Motivation

• 집단 C1 과 집단 C2의 density가 다르며, 데이터 o1은 눈에 띄게 다른 데이터와의 거리가 멀기에 걸러내기 쉽지만 데이터 o2는 걸러내기가 어렵습니다.
  일정 거리로 기준을 삼을 경우, C1혹은 C2에만 특화된 outlier detction을 하게 됩니다.
  이러한 문제의식에서, local의 상대적인 dense를 비교하여 outlier를 정하자는 lof가 등장했습니다.
  큰 틀은, neighbor들의 dense를 고려하여 비교한다는 것입니다.

Algorithm

1. K-distance of object p

• 자기 자신($p$)를 제외하고 k번째로 가까운 이웃과의 거리

  

• 예시 : 4-distance of object p : 자기 자신을 제외한 4번째로 가까운 이웃과의 거리 = 2.0

• 주의사항 : distance가 continuous라면 3-distance내에 정확히 3개의 neighbor가 들어있겠지만, 거리가 1,2,3,3,3,3같이 discrete해서 겹치는 경우라면 3-distance내에 5개든 10개든 neighbor로 들어있을 수는 있습니다. 이를 따로 나타내주기 위해 k-distance(p)안에 들어온 데이터갯수를 $N_k,(p)$라고 부른다.

2. K-distance neighborhood of object p ($(N_k,(p))$)

• k번째로 가까운 이웃과의 거리를 원으로 표현할 때, 원 안에 포함되는 모든 객체들의 개수

• 예시 : k = 4일 때, $N_4(p)$ = 4개 포함

3. Reachabillity Distance ($Reachabillity\;distance_k(p,o)$)

• 주변 데이터 o를 기준으로 k번째 가까운 이웃과의 거리(k-distance of o)와 o와 p사이 거리 간의 최대값
  • $Reachabillity\;distance_k(p,o) = max(k-distance\;of\;o\;, d(p,o))$

• 예시 : k = 5일 때, k-distance of o는 1.2, $d(p,o)$는 2.0이다.
  $Reachabillity\;distance_5(p,o) = max(1.2,2.0) = 2.0$

4. Local reachabillity density of object p ($lrd_k(p)$)

• p주변의 k_neighbor들과의 reach_dist의 평균을 inverse(역수)취한 것입니다.
  주변의 dense를 고려한 p점에서의 ‘neighbor들과의 적당한 거리’를 나타낼 수 있습니다.

• lrd는 inverse입니다.

  • $lrd_k(p) = \frac{\vert N_k(p) \vert}{\displaystyle\sum_{o \in N_k(p)}^{}{Reachabillity\;distance_k(p,o)}}$

• 자기 자신(p) 주변의 밀도가 높은 경우, 위 식의 분모가 작아지게 되어 $lrd_k(p)$값이 커지게 됩니다. = 정상

• 반대로 자기 자신(p) 주변의 밀도가 낮은 경우, 위 식의 분모가 커지게 되어 $lrd_k(p)$값이 작아지게 됩니다. = 비정상

5. Local Outlier Factor of object p ($LOF_k(p)$)

• 자기 자신(p)의 최종 Local Outlier Factor값을 계산

  • $LOF_k(p) = \frac{\displaystyle\sum_{o \in N_k(p)}^{}{lrd_k(o)/lrd_k(p)}}{\vert N_k(p) \vert}$ = $lrd_k(o)$와 $lrd_k(p)$의 비율의 평균
    
    
  

• 자기 자신(p) 주변의 밀도가 높은 경우, 큰 $lrd_k(o)$, 큰 $lrd_k(p)$ = 1근방의 $LOF_k(p)$값을 갖습니다.

  

• 자기 자신(p) 주변의 밀도가 낮은 경우, 큰 $lrd_k(o)$, 작은 $lrd_k(p)$ = 1보다 큰 $LOF_k(p)$값을 갖습니다.
• 하지만 자기 자신(p) 주변의 밀도가 낮지만 전체적으로 밀도가 낮은 경우, 작은 $lrd_k(o)$, 작은 $lrd_k(p)$ = 1근방의 $LOF_k(p)$값을 갖게됩니다.

• 결론적으로, 1근방의 값을 가진다면, 오밀조밀한 군집이든 크게 펼쳐진 군집이든 데이터가 그 안에 포함되어 있다고 간주하여 정상이라고 할 수 있다.

Code

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import LocalOutlierFactor
from matplotlib.pyplot import figure
figure(num=None, figsize=(8, 6), dpi=80, facecolor='w', edgecolor='k')


np.random.seed(123)

# Generate train data
X_inliers = 0.3 * np.random.randn(100, 2) ## 정규분포에서 100*2만들고
X_inliers = np.r_[X_inliers + 2, 2*X_inliers - 2] ## 각각 2,2 혹은 -2,-2만큼 평행이동한거를 vstack. 즉 cluster 2개

# Generate some outliers
X_outliers = np.random.uniform(low=-4, high=4, size=(20, 2))
X = np.r_[X_inliers, X_outliers] ##-4,4에서 뽑은 outlier와 inlier를 vstack

n_outliers = len(X_outliers)
ground_truth = np.ones(len(X), dtype=int)
ground_truth[-n_outliers:] = -1

# fit the model for outlier detection (default)
clf = LocalOutlierFactor(n_neighbors=20, contamination=0.1)
## use fit_predict to compute the predicted labels of the training samples
## (when LOF is used for outlier detection, the estimator has no predict, decision_function and score_samples methods).
y_pred = clf.fit_predict(X) # 1,-1로 나온다.
n_errors = (y_pred != ground_truth).sum()
X_scores = clf.negative_outlier_factor_ ## 음수 LOF scsore

plt.title("Local Outlier Factor (LOF)")
plt.scatter(X[:, 0], X[:, 1], color='black', s=3., label='Data points')
# plot circles with radius proportional to the outlier scores
radius = (X_scores.max() - X_scores) / (X_scores.max() - X_scores.min())
plt.scatter(X[:, 0], X[:, 1], s=500 * radius, edgecolors='g',
            facecolors='none', label='Outlier scores')
n = np.copy(X_scores)
n[n>-2] = np.nan ## LOF scsore(음수)의 threshold는 2
n = np.round(n,2)
n = -1 * n ## 양수변환

# LOF만 txt표기
for i, txt in enumerate(n):
    if np.isnan(txt):continue
    plt.annotate(txt, (X[i,0], X[i,1]))
legend = plt.legend(loc='upper left')
plt.show()