머신러닝에서의 이상 탐지 종류(Anormaly Detection)

1. 이상탐지란?

이상탐지는 정상(Normal)/비정상(Anormal)을 구분하는 문제이다. 

대표적인 방법으로는 머신러닝에서 많이 해오던 이진 분류(Binary Classification)가 있다.

그러나 일반적인 분류문제로 풀기에 이상탐지 분야는 Class의 불균형(Class Unbalanced)이 너무 심각하다.

대부분의 이상탐지 문제는 아래 두가지 케이스에 해당된다.

• Case1 : 정상 데이터만 존재하는 경우
• Case2 : 대다수의 정상 데이터와 소수의 비정상 데이타가 있는 경우

빅데이터분석기사나 여타 데이터마이닝 분야에서 Class의 불균형 문제의 해답으로 Over/Under Sampling을 소개하고 있지만 실제로는 효과를 거두기 어렵다.

1.1 Over Sampling의 한계

Over sampling은 소수 Class의 측정된 샘플들의 분포를 기반으로 새로운 값을 생성한다.

측정된 샘플들의 분포가 실제 Class의 분포를 대변한다고 할 수 없으며,

측정된 분포 외의 값에 대해서는 결국 모델이 학습하지 못한다.

1.2 Under Sampling의 한계

소수 Class가 학습에 필요한 데이터가 충분이 존재하고 다수 Class의 데이터가 너무 많을 경우 의미가 있을 수 있다.

다수 Class의 개수를 줄이더라도 소수 Class에 대한 충분한 특징 학습이 이루어지지 않았기 때문에 근본적인 문제를 해결할 수 없다.

 

따라서 본 포스팅에서는 이진분류 기법이 아닌 One Class Classification 기법들을 소개한다.

• Density Based
  • Gaussian Model
  • KDE(Kernel Density Estimation)
  • LOF(Local Outlier Factor)
• Tree based
  • Isolation Forest
  • RRCF(Robust Random Cut Forest)
• AutoEncoder
  • AutoEncoder with Reconstruction Errors
  • PCA
  • LSTM AutoEncoder
  • AutoEncoder for Multivariate Time Series
• Generative
  • VAE
  • GAN
  • GAN + KDE

 

2. Density Based

2.1 Gaussian Model

기존 데이터로부터 Feature별로 평균과 분산을 구하고 새로운 데이터에 아래의 식을 적용해 값을 구한다.

구해진 값이 임계치보다 높다면 이상치로 분류한다.

(Feature 별로 독립적이라 가정한다.)

Feature의 분포가 정규분포임을 가정하므로, skew를 가지는 분포일경우 transform 기법을 적용한 후 사용한다.

\(C\) : Feature의 개수, c는 각 Feature를 의미한다.

\(\mu _{c} , \sigma_{c}  \) : c번째 Feature의 평균 및 분산

\( x \) : 이상탐지를 하고자하는 새로운 값

\( \epsilon \) : 이상치로 판별하기 위한 임계값(사용자 지정)

$$score = \prod_{c=1}^{C}[\frac{1}{\sqrt{2\pi \sigma_{c}^{2} }}e^{-\frac{1}{2\sigma_{c}^{2}(x_{c}-\mu _{c})^{2}}} ]$$

$$if \ score \ > \ \epsilon : Anormal$$

$$else \ : \ normal $$

2.2 KDE(Kernel Density Estimation)

수치 데이터에서만 동작 가능하다.

2.3 LOF(Local Outlier Factor)

 

K-distance는 k번째로 가까운 데이터와의 거리를 나타내며,

K-distance Neighborhood는 K-distance를 반지름으로하는 원안에 존재하는 데이터들을 의미한다.

Reachable distance는 아래의 식으로 계산된다.

$$max(k-distance(p),d(p,x))$$

점 P에 대해서 Reachable distance를 계산하면 아래와 같다.

대상이 x1이라면 x1과의 거리가 k-distance보다 짧기에 k-distance가 되고,

대상이 x2라면 x2와의 거리가 k-distance보다 길기에 d(p,x2)가 된다.

 

Local reachability density는 위의 값들을 통해서 계산되며 아래의 의미를 가진다.

$$Local \ reachability \ density = \frac{\left| N_{k}(p) \right|}{\sum_{o\in N_{k}(p)}reachability-distance_{k}(p,o)}$$

어떠한 점 p가 있을 때 주변에 다른 데이터가 밀집되어 있을수록 K-distance 및 Reachable distance이 작은 값을 가지게된다.(분모)

이때 분자는 같은 값을 가지게 되므로 밀집도가 높은 점P일수록  Local reachability density 값이 커지게 된다.

 

Non parametric 방법으로써 데이터가 커질수록 연산량이 증가한다는 특징을 가지고 있다.

또한 새로운 데이터가 추가되었을 경우 다시 계산하여야 한다.

 

3. Tree based

3.1 Isolation Forest

Isolation은 격리된다는 의미를 가지며, Tree에서 isolation은 특정 데이터가 leaf node에 들어갔음을 의미한다.

이때 몇번의 가지치기 끝에 leaf node에 들어갔는지를 Path length라고 하며,

여러개의 Tree를 생성(Forest)하여 특정값이 각 Tree에서 가지는 Path length를 평균내어 Average Path Length라고 한다.

여러개의  Tree는 Random으로 기준이 될 Feature 및 Split Point를 선택한다.

 

데이터의 개수가 늘어날 수록 Path Length의 평균 길이는 길어지게 되므로,

데이터 크기에 대한 영향을 줄이기 위해서 아래의 식을 통해 Anormaly score를 계산한다.

$$S(x,N) = 2^{-\frac{E[h(x)]}{c(N)}}$$

이상치(outlier)가 모여있는 경우에는 탐지가 힘들다는 점이 있다.

이러할 경우에는 전체 데이터를 쓰는것이 아닌 Sampling을 하여 Isolation을 수행함으로 보완 가능하다.

3.2 Robust Random Cut Forest(RRCF)

Isolation 기법이 Average Path Length 값 자제를 사용했다면,

RRCF는 Average Path Length의 변화량을 사용한다.

아래 그림을 통해서 예를 든다.

데이터 Z로 부터 x라는 값을 제거했을 때, Sub Tree a에 속하는 모든 데이터들은 Path Length가 1씩 감소할 것이다.

T(Z)와 T(Z-x)간의 Average Path Length의 변화량을 사용하여 Anormaly score를 구한다.

Isolation이 Uniform 분포에서 랜덤 선택을 수행했다면,

RRCF는 Feature의 범위(min~max)에 따라서 분포가 넓은 Feature를 높은 확률로 선택한다.

4. AutoEncoder

4.1

4.2

 

5. Generative

5.1 VAE

d

5.2 GAN

d

5.3 GAN + KDE

d

 

 

참고문헌

https://proceedings.mlr.press/v48/guha16.pdf (RRCF 논문)