Anomaly Detection

Anomaly Detection

비정상적인 데이터를 찾는 문제이다.

응용분야는

신용카드 사기, 전화 사기, 네트웍 침입, Fault Detection 등이 있다.

Challenge

얼마나 많은 outlier를 찾을 것인가?

unsupervised이므로 찾기가 어렵다.

가정

정상저인 데이터가 비정상보다 확연하게 더 많다.

Types of anomaly detection schemes

- model based or statistical approaches

- distance based

- Density based

1) model based or statistical approaches

일단 모델을 생성하던가 어떤 잘 알려진 분포를 따라야 한다.

normal distribution과 같이 특정 파라메터로 분포를 설명 할 수 있어야 한다.

이럴때 outlier란 결국 probability가 낮은 분포에 속하는 데이터가 된다.

아래와 같은 분포인 Gaussian distribution이 많이 사용된다.

파라메터는 mean과 standard deviation이다.

위는 PDF로

N(0,1)의 값을 나타낸다.

2차원 PDF를 나타내므로, 결국 원래 값은 1차원 분포인 것이다. 변수가 x 하나이다.

Statistical 접근법의 한계점

Attribute가 1개이다. 대부분

데이터 분포가 잘알려진 분포를 따르기가 쉽지 않다.

고차원 데이터 분포에서는 적용하기가 쉽지 않다.

2) Distance based approach

멀리 떨어지면 아웃라이어

k-nearest neighbor를 쓸 수 있다.

장점: 간단

단점:

복잡도 O(m^2)

m by m matrix를 생성 해야 내기 때문이다.

k와 같은 파라메터에 너무 민감함

하나의 분포에서 밀도가 매우 다양하게 분포되어 있다면 잘 동작하지 않는다.

즉, 같은 데이터 분포안에서 특정 점들음 엄청 밀도가 높고 특정 점들은 밀도는 낮지만 어쨋든 모여있다면 명백히 두 점들의 분포는 각각의 클러스터를 생성할 수 있게 되어야 한다. 이렇게 같은 분포 안에서 밀도가 서로 다르게 나타나지면 밀도가 낮은쪽은 몽땅다 아웃라이러로 처리 되어 진다.

5개로 설정하면 일단 C는 아웃라이어 처럼 보인다.

하지만 문제는 1개로 줄여 버리면 c가 아웃라이러로 판별되지 않는다.

즉, K에 너무 민감하다.

k를 너무 높여도 문제가 발생 한다.

밀도가 서로 다를때가 문제가 심하다.

C는 아웃라이어다.

하지만 D와 A는 아웃라이로 검출하지 못한다.

전체적인 거리만 따질것이 아니라, 자신 주위의 밀도도 같이 고려 해야 한다.

- Density based approach

neighbor 안에 드는 모든 node들에 대한 distance의 평균을 구한 다음

그것의 역수를 취해서 density를 계산하여 outlier를 판별 한다.

한계점은 역시나 서로다른 밀도로 섞여 있는 경우 적합하지 않다.

- Improved density based approach

주변의 이웃들도 같이 밀도를 고려 하는 방법이다.

relative density에 역수를 취해서 outlier를 검출 하는데 사용 한다.

위 식의 의미는 아래와 같다.

N = 3이라고하면

나와 내 이웃 3개와의 Density의 평균 / 나의 이웃 3개 들의 Density 평균

이렇게 되면 이 값이 크다는 의미는  나의 덴시티가 내 이웃들의 덴시티 보다 크기 때문에 나는 더더욱 아웃라이어이지 않을 확률이 높다는 것이다.

작다는 의미는 내 덴시티보다 이웃들의 덴시티가 더 크니 위에서 발견못한 D같은 point를 아웃라이어로 판별 할수 있다.

따라서 저 값을 역수로써 사용하면 anomaly detection의 지표로 사용 할 수 있다.

3) Density based LOF Approach 

Local Outlier Factor (LOF)

Outliers in Lower Dimensional Projection

고차원에서는 빈공간도 너무 많고, proximity의 개념 자체가 잘동작 하지 않는다.

따라서 대부분의 point들이 outlier로 판별되는 문제가 존재 한다.

이것을 방지하기 위해서 Lower dimensional projection을 수행 해야 한다.