[머신러닝] 이상치 탐지(anomaly detection) #03 Local Outlier Factor

이 포스트는 고려대학교 강필성 교수님의 강의 내용과, 따로 학습한 내용을 정리를 한 것입니다.

Motivation

Compute the novelty score of an instance by considering local density around it.
객체의 지역적인 밀집도를 고려해 이상치 점수를 계산하고 판단하자.

출처: A Review of Local Outlier Factor Algorithms for Outlier Detection in Big Data Streams

 그저 거리만 고려해 이상치를 판별 하게 된다면 회색 점에 대해서는 이상치라고 판별하지만, 빨간 점에 대해서는 이상치로 판별하기 어렵다. 즉 특정 집단에서는 매우 가까운 거리가, 다른 집단에서는 매우 먼 거리일 수 있으니 객체의 지역적인 밀집도를 고려해 이상치 점수를 계산하자.

LoF에서의 이상치

Defination 1: Hawkins-Outlier

 An outlier is an observation that deviates so much from other observations as to arouse suspicion that it was generated by a different mechanism.

• To simplify our notation, we use d(p, C) to denote the minimum distance between p and object q in C, i.e. d(p,C)=min{d(p,q) |q∈C}.
• C: sometimes with the intuition that C forms a cluster.

이상치는 다른 관측치에서 너무 많이 벗어나 다른 mechanism에 의해 생성됐다고 의심해볼만한 관측치이다.

Definition 2: (DB(pct, dmin)-Outlier)

An object p in a dataset D is a DB(pct, dmin)-outlier if at least percentage pct of the objects in D lies greater than distance dmin from p, i.e., the cardinality of the set {q∈D|d(p, q)≤dmin} is less than or equal to (100 pct)% of the size of D.

• If the dmin value is greater than the distance d(o2, C2), then it is easy to see that: o2 is a DB(pct,dmin)-outlier implies that there are many objects q in C1 such that q is also a DB(pct,dmin)-outlier.

데이터 세트 D의 객체 p는 D에 있는 객체의 최소 백분율이 p로부터의 거리 dmin보다 크면 DB(pct, dmin)-outlier이다. 즉, 집합 {q∈D|d(p, q)≤dmin} 의 카디널리티가 D 크기의 (100%)보다 작으면 DB(pct, dmin)-outlier이다.

Definition 3: (k-distance of an object p)

For any positive integer k, the k-distance of object p, denoted as k-distance(p), is defined as the distance d(p,o) between p and an object o∈D such that:
(i) for at least k objects o’∈D\{p} it holds that d(p,o’)≤d(p,o), and
(ii) for at most k-1 objects o’∈D\{p} it holds that d(p,o’)<d(p,o).

임의의 양의 정수 K에 대해서 K-distance는 다음 조건을 만족하는 d(p, o)로 정의된다.

1. 최소 k개의 개체 o’ 에 대해서 d(p,o’)≤d(p,o)  만족
2. 최대 k-1개의 개체 o’ 에 대해서 d(p,o’)<d(p,o)  만족

Definition 4: (k-distance neighborhood of an object p)

Definiation 1과 같은 점 p의 k-distance가 주어졌을 때 k-distance neighborhood of p는 p에서부터 k-distance 근처 거리에 있는 모든 개체들의 집합이다.

Given the k-distance of p, the k-distance neighborhood of p contains every object whose distance from p is not greater than the k-distance, i.e. N_k-distance(p)(p) = { q∈ D\{p} | d(p, q) ≤k-distance(p) }.
These objects q are called the k-nearest neighbors of p.

p의 k-distance가 주어졌을 때, p의 k-distance neighborhood은 p로부터의 거리가 k-distance보다 크지 않은 모든 객체를 포함한다. 이 객체 q들은 p의 k-nearest neighbors라고 불린다.

Definition 5: (reachability distance of an object p w.r.t. object o)

Let k be a natural number. The reachability distance of object p with respect to object o is defined as
reach-dist_k(p, o) = max { k-distance(o), d(p, o) }.

객체 p의 reachability distance는max{ k-distance(o), d(p, o) }로 정의된다. 즉 k-distance(o)와 d(p, o) 중 큰 값으로 정의.

Definition 6: (local reachability density of an object p)

The local reachability density of p is defined as

Nk는 k개의 이웃의 거리

객체 p를 기준으로 했을 때 local reachability density

• case 1: p is located in the the middle of a densor area: the denominator of lrd_k(p) becomes small, which results in a large  lrd_k(p)
  • p도 o의 관점에서 봤을 때 이웃, o의 관점으로 p를 봤을 때 이웃
• case 2: p is located in a spare are between two dense clusters: the denominator of lrd_k(p) becomes large, which results in a small lrd_k(p)
  • o의 관점으로 봤을 때 p가 이웃하지 않는다.

Definition 7: ((local) outlier factor of an object p)

The (local) outlier factor of p is defined as

 

LoF 구현

python sklearn 패키지의 LocalOutlierFactor를 이용해서 구현 가능하다.

LocalOutlierFactor(n_neighbors=20, *, algorithm='auto', leaf_size=30, metric='minkowski', p=2, metric_params=None, contamination='auto', novelty=False, n_jobs=None)

1. n_neighbors: Number of neighbors. 디폴트는 20으로 설정되어있다. 
2. algorithm: nearest neighbors 계산 방법을 결정하는 파라미터.
3. leaf_size: 알고리즘에서 BallTree or KDTree를 선택할 경우 leaf size를 정하는 파라미터
4. metric: 이웃한 거리를 계산할 때 어떤 알고리즘을 사용할 것인지 정하는 파라미터. 디폴트는 “minkowski”거리를 이용한다.
5. p: Parameter for the Minkowski metric. 1이면 L1, 2이면 L2를 이용. 디폴트는 2로 설정되어있다.
6. contamination: The amount of contamination of the data set. 데이터셋의 이상치 비율을 설정. 이상치 스코어의 threshold를 설정할 때 사용된다.
7. novelty: LoF는 원래는 Outlier detection에 사용되지만(novelty=False), novelty detection(novelty=True)에서도 사용 가능하다. 하지만 novelty=True로 사용할 경우 training set이 아닌 새로운 unseen data에 대해서만 predict, decision_function, score_samples만 사용할 수 있으며, 표준 LoF 결과와 다를 수 있다.
   1. outlier detection: The training data contains outliers which are defined as observations that are far from the others. 트레이닝 데이터에 이상치가 포함되어 있음.
   2. novelty detection: The training data is not polluted by outliers and we are interested in detecting whether a new observation is an outlier. 트레이닝 데이터에 이상치가 불포함됨.

* Novelty detection vs Outlier detection

Method	Outlier detection	Novelty detection
fit_predict	OK	Not available
predict	Not available	Use only on new data
decision_function	Not available	Use only on new data
score_samples	Use negative_outlier_factor_	Use only on new data
negative_outlier_factor_	OK	OK

OutlierDetection으로 이용할때 LoF score를 구하려면 LocalOutlierFactor.negative_outlier_factor_를 이용한다.
The standard LOF scores for the training data is available via the negative_outlier_factor_ attribute.

LoF의 이상치 탐지 결과는 1(정상), -1(비정상)으로 나온다.

코드

# 1. 트레이닝 데이터 생성

from pyod.utils.data import generate_data
import numpy as np

X_train, Y_train = generate_data(   
                                    n_train=150, 
                                    n_features=2,
                                    train_only=True,
                                    contamination=0.1,
                                    random_state=42
                                 )
                                 
x1, x2 = X_train[:,0], X_train[:,1]

Y_train = np.where(Y_train == 1, -1, Y_train)
Y_train = np.where(Y_train == 0, 1, Y_train)

# 생성한 데이터 시각화

import matplotlib.pyplot as plt
%matplotlib inline

for idx, i in enumerate(Y_train):
  if i==1: 
    color='blue'
  else: 
    color='red'
  plt.scatter(x1[idx], x2[idx], c=color)
  
  
# LoF 모델 생성 및 학습
from sklearn.neighbors import LocalOutlierFactor

LoF_model = LocalOutlierFactor(n_neighbors=20, contamination=0.1)
LoF_model.fit(X_train)

pred = LoF_model.fit_predict(X_train)

error = (pred != Y_train).sum()
print (f'Error % = {(error/len(pred))*100}')


# 예측한 값 plot
import matplotlib.pyplot as plt
%matplotlib inline

for idx, i in enumerate(pred):
  if i==1: 
    color='purple'
  else: 
    color='orange'
  plt.scatter(x1[idx], x2[idx], c=color)

참고

• Breunig, Markus M., et al. "LOF: identifying density-based local outliers." Proceedings of the 2000 ACM SIGMOD international conference on Management of data. 2000.
• https://www.youtube.com/watch?v=ODNAyt1h6Eg
• https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LocalOutlierFactor.html
• https://scikit-learn.org/stable/modules/outlier_detection.html 
• 예시코드 참고
• https://blog.paperspace.com/outlier-detection-with-abod/