Outlier Discovery

Outlier Discovery

다른 object와 특성이 상당히 다른(dissimilar한) object를 outlier라 한다.

 

Outlier discovery는 large dataset에서 outlier를 찾는 것을 목표로 한다.

신용카드 사용 내역, 비정상 통신망 사용자, 돈을 많이 쓰는 고객, 의료 정보 등에 활용할 수 있다.

 

Statistical Approach

데이터셋이 정규분포를 따른다고 가정하고 평균으로부터 일정 이상 떨어지는 objects들을 outlier로 간주한다.

 

Multi attribute에서 활용하기 어렵다.

또한 정규분포를 가정으로 하지만 실제 데이터에서는 distribution을 알기 힘들다는 문제가 있다.

 

Distance-based Approach

일정 거리(d) 내에 일정 수(n) 이상의 object가 없으면 outlier로 간주한다.

반대로 일정 거리 밖에 일정 수 이상의 object가 있으면 outlier로 간주하기도 한다.(예 : 범위 밖에 99%의 데이터가 존재)

 

이를 위해 거리와 수를 결정하는 2개의 파라미터가 필요하다.

그러나 사전에 distribution을 몰라도 되고 multi-attribute data에도 적용 가능하다.

 

Algorithm

d distance 이내의 object 수를 빠르게 찾는 것이 중요하다.

• index-based algorithm : indexing을 하여 outlier를 mining
• nested-loop algorithm : DB JOIN을 응용
• cell-based algorithm : 전체 공간을 cell로 나눠서 찾음

 

문제점

Distance-based approach는 global distance distribution 기반으로 outlier를 찾는다.

즉 모든 outlier에 대해 동일한 distance를 적용하게 된다.

 

이 경우 cluster에 따라 적절한 distance가 다르기 때문에 outlier를 정확하게 찾기 힘들다.

즉, uniform하게 분포되지 않은 데이터에 대해 outlier를 찾기 힘들다.

 

아래 그림과 같이 $o_2$는 $C_2$에 대해서 outlier이기 때문에 distance를 작게 설정하면 $C_1$에 속하는 모든 점들이 outlier가 되버리는 문제가 발생한다.

 

Density-based Approach

Local outlier의 개념을 적용한다.

주변에 비해 상대적인 차이를 본다.