Outlier Detection

Object의 type에는 크게 네 가지가 있다.

첫 번째는 흔히 데이터라고 불리는 Normal Object,

두 번째는 Normal Object와 상당히 dissimilar한 Outlier,

세 번째는 micro-cluster 형태의 Outlier,

네 번째는 Normal Object이지만, Fringe Object로서 outlier와 구별이 힘든 데이터다.

 

이미 이전에 클러스터링에 대해 포스팅하면서, outlier를 다루는 것에 대해 언급한 적이 있었다.

여기서는 outlier를 잘 detection하는 여러 기법에 초점을 맞춰 포스팅할 예정이다.

---

 

Outlier Detection의 여러 종류

Outlier Detection은 여러 기반의 종류가 있고, 각 종류별로 장단점이 각기 다르다.

하나씩 살펴보며 각 종류의 특징을 익혀보자.

 

# Statistics 기반

모델이 '데이터 분포'를 내재하고 있다는 가정 하에 세워진 방식이다.

대표적으로 distribution parameter를 기준으로 outlier를 정의하는 것이 있다.

(mean, variance 등을 활용해 세운 기준 바깥의 데이터를 outlier로 처리하는 것.)

통계기반의 Outlier Detection은, 기준을 세우기 위해 분포를 구하는 것(특히 고차원일 때)이 매우 어렵다는 점에서 한계가 있음을 알아두자.

 

# Distance 기반

말 그대로 거리 기반의 outlier detection 방법이다.

object간 거리를 location feature로 삼고, 임계치를 못넘기면 outlier로 처리하는 방식이다.

이는 데이터, 클러스터들의 거리분포가 일정(uniform)하지 않으면 detection이 힘들다는 한계가 있다.

(Local Density Problem)

 

# Density 기반

이웃보다 밀도가 작으면 outlier로 처리하는 방식이다.

Distance 기반의 한계인 local density problem을 해결한다는 점이 장점이다.

하지만, outlier이지만 밀도가 높은 micro-cluster 형태의 outlier는 제대로 detect할 수 없다는 한계가 있다.

(Micro-Cluster Problem)

 

# RWR 기반

Graph Based Outlier Detection이라고 생각하면 되겠다.

데이터셋을 통합된 그래프로 모델링한 후, 그래프 node에 대해 global ranking을 수행하는 방식이다.

역시, fringe object와 outlier를 구별하는 것이 어렵다는 점에서 한계가 존재한다.

(Fringe Object Problem)

---

 

Centrality & Center-Proximity를 이용한 Outlier Detection

outlier detection을 위한 여러 접근법이 있지만, 각자 그 한계가 있었다.

여기서 설명할 접근법은, 이러한 한계를 모두 극복하면서 outlier를 잘 찾아내고자 개발된 방식이다.

구체적으로는 아래와 같은 조건을 모두 만족하는 방식이다.

- outlier를 정확히 detect해야 함. (micro cluster problem, local density problem, fringe object problem 등 모두 없어야.)

- outlier score를 제공해야 함.

- 데이터 타입에 관계없이 동작해야 함.

 

# Steps

대략적인 작동방식은 다음과 같다.

1) 주어진 dataset으로 "Weighted KNN Graph"를 그린다.

2) centrality & center-proximity score를 구해 outlierness score를 계산한다.

3) top-m 개의 object를 outlier로 선정한다.

 

 

# Step 1. KNN 그래프 그리기

여기서 knn 그래프를 그린다는 것은, k개의 directed edge로 각 object를 연결하는 것을 의미한다.

in-degree는 그래프 분포에 따라 다르지만, out-degree(노드로부터 나가는 edge의 수)는 k로 모두 동일하다.

k개의 edge를 연결하는 기준은 similarity이다.

(* Euclidean Similarity, Cosine Similarity 등이 쓰인다.)

 

 

# Step 2. Centrality & Center-Proximity 구하기

outlierness score를 계산하기 위해 centrality와 center-proximity를 구하는 단계가 다음이다.

이때, centrality와 center-proximity는 '이웃이 많은 것' 과 '이웃과의 거리가 가까운 것'이 outlier보다 center일 가능성이 높음에 기인하여 계산된다.

아래 각 score의 정의를 살펴보며 개념을 이해해보도록 하자.

 

[Centrality Score]

이전에 graph mining에서 다루었던 authority score와 유사하다고 생각하면 된다.

'얼마나 많은 다른 object가 점 p를 cluster의 center로 보는지'가 p의 점수 증가요인이다.

p를 neighbor로 지목하는 object가 많을 때,

p를 가까이에서 neighbor로 지목할 때,

p를 neighbor로 지목하는 object의 center-proximity score가 높을 때 centrality score가 높아진다.

$$Centrality_{i+1}(p) = \sum_{q∈IN(p)}w_{w_{q \to p}}×{Center-Proximity_{i}(q)\over Z_{out(q)}}$$

 

[Center-Proximity Score]

center-proximity score는 graph mining의 hub score와 유사한 면이 있다.

이번에는 'centrality score가 높은 객체와 p가 얼마나 가까운지' 가 점수 증가 요인이다.

p가 neighbor로 지목하는 object가 많을 때,

p가 neighbor로 지목하는 object와의 거리가 감소할수록,

p가 neighbor로 지목하는 object의 centrality score가 높을 때 center-proximity score가 높아진다.

$$Center-Proximity_{i+1}(p) = \sum_{q∈OUT(p)}w_{p\to q}×{Centrality_{i}(q)\over Z_{in}(q)}$$

 

두 score도 HITS와 유사하게 서로 mutual reinforcement relationship에 있으나,

weight가 클수록 (거리가 가까운 node일수록) neighbor에 영향을 많이 끼친다는 점에서는 HITS와 구별된다.

마찬가지로 score가 converge할 때까지 점수 업데이트를 반복한다.

 

 

# Step 3. Outlier 선정

계산하여 converge된 center-proximity score의 inverse의 기준으로, 큰 값들을 outlier로 선정한다.

이때, centrality score가 아닌 center-proximity score를 기준으로 outlier를 선정하는 이유는 centrality score는 fringe object와 outlier를 잘 구별하지 못하기 때문이다.