[Anomaly Detection] Isolation-based Anomaly Detection 논문 리뷰

💡 Index

 

1. Prerequisite

Anomaly Detection (이상탐지)는 주어진 sample data에 대해 해당 데이터가 normal인지 abnormal인지 분류하는 것을 의미한다.
"분류"한다고 해서 이 과정이 classification과 동일하지는 않다. 아래 그림을 통해 설명해 보자면,

classification의 경우 decision boundary가 빨간색 선이 그려진 것 처럼 두개의 class를 구분하는 것이라면 anomaly detection의 경우 이와 형태가 다르다. 빨간색 점인 new data가 들어왔을 때 classification은 이를 정상인 데이터로 구분하지만 anomaly detection의 경우 정상이 아닌것으로 구분짓게 된다.

anomaly detection은 학습시 abnoraml 데이터의 사용 여부와 label 유무에 따라 세가지 종류로 구분된다.

• supervised anomaly detection : 정상 + 비정상 sample 의 data, label 모두 있는 경우
• semi-supervised anomaly detection : 정상 sample만 이용해 학습하는 경우
• unsupervised anomaly detection : label 되지 않은 데이터를 이용하는 경우

2. Introduction

• Anomaly는 normal instances와는 다른 데이터 특징을 갖는 data pattern을 의미한다.
• 기존 anomaly detection의 방식 (Distance / Density measure)
  • 정상치(normal instance)에 대한 normal profile을 생성하고, normal profile에 맞지 않는 anomalies를 탐색하는 방식
  • 기존 방식의 한계 (저자의 주장)
    • 이상치를 감지하는 데 결론적으로 최적화되어있지 않다. -> 너무 많은 false alarms / 너무 적은 이상치 탐지
    • 기존 알고리즘의 특성으로 인해 low dimensional + small data의 형태를 띈다.
• 이 논문은 distance나 density measure에 의존하지 않고 instance를 isloating시킴으로써 이상치를 탐지하는 방식을 제안한다.
• Anomalies가 few and different (= Isolation) 하다는 특징에 주목하였다.
• 이 논문에서 제안하는 방식인 Isolation Forest (iForest) 는 주어진 데이터 셋에 대해 iTree들의 ensemble을 형성한다.
  • anomaly들은 iTree들에 대해 short average path length를 가지고 있다.
  • 두개의 training parameters + 하나의 evaluation parameter로 구성 된다.
    • training parameter : the number of trees to build + subsampling size
    • evaluation parameter : tree height limit
  • iForest는 높은 효율성으로 높은 탐지 정확도에 도달하는 데 small subsampling size만을 필요로 한다.

3. Isolation and Isolation Trees

• isolation ; instance를 나머지 instance들에서 부터 seperating 시키는 것.
• 일반적인 isolation based methods는 각 객체의 susceptibility(민감도)를 isolated 되었다고 측정한다. 이때 anomaly는 가장 높은 민감도를 가진 객체들로 분류된다.
• 즉 각 instance들이 isolated 되기위한 민감도를 측정한다. (=> Anomalies는 isolated 되기 쉬워 빨리 구분할 수 있다.)

위 그림에서 볼 수 있듯이 정상인 data를 isolate 시키기 위해서는 (a)와 같이 많은 스텝이 필요한 반면, (b)와 같이 anomaly data를 isolate 시키는 데는 몇번의 스텝만으로 가능하다.

위 그래프를 통해 $X_i$ 의 path 길이가 $X_O$보다 큼을 확인할 수 있다.

4. Anomaly Detection using IForest

• iForest를 이용한 이상탐지의 방식은 다음과 같다.
  • (1) Training Stage : 주어진 데이터 셋의 sub - samples를 활용하여 isolation tree들을 만든다.
  • (2) Evaluation Stage : 각 instance로 부터 anomaly score를 isolation tree로부터 얻기 위해 instance들을 테스트한다.

1) Training Stage

• 이 training stage에서는 모든 instance들이 isolated될 때 까지 sub sample $X\prime$를 recursively partitioning하여 iTree들을 만든다.
• 형성된 여러 개의 iTree들로 ensemble 을 통한 iForest를 구성한다.

(1) Algorithm 1

• Input parameters
  • Subsampling size (ψ) ; training data size
    • 해당 논문에서는 ψ = 256으로 사이즈를 고정해둠.
      • small subsampling(256)이 충분한 이유 ; desired value까지 ψ 값을 증가시키면, iForest가 신뢰성있게 탐지하기에 더 이상 값을 증가시킬 필요가 없다. (여기서 더 증가시킬 경우 이득없이 메모리 사이즈와 처리 시간만 늘어나게 됨)
  • Number of trees (t) ; ensemble size
    • path 길이가 보통 t = 100 이전에 잘 전환됨을 확인하였기에 해당 논문에서는 t = 100으로 값을 고정해둠.

 

1. iForest를 저장할 빈 instance 생성

2. for loop ( subsampling 갯수 t회 반복)

   3. sub sampling ( size ; ψ )

   4. iTree construction과 iForest 저장

5. for loop end

6. return iForest

 

 

(2) Algorithm 2

1. sampling된 $X\prime$가 더이상 분할되지 않는다면

( = isolated 되었다면)

     2. external Node로 리턴

3. isolated 되지 않는다면

     4. $X\prime$의 변수들을 Q에 list로 저장

     5. list Q의 원소 중 랜덤하게 q 하나를 선택

     6. split point에 사용될 원소 p를 랜덤하게 선택

     7. q < p 를 만족하는 x들을 $X_l$로 할당

     8. q >= p 를 만족하는 x들을 $X_r$로 할당

모든 데이터 포인트가 isolated될 때 까지 반복

=> Algorithm 2를 통해 binary한 iTree가 만들어지게 됨.

 

2) Evaluation Stage

• 만들어진 iTree에 data point 하나인 $x$를 흘려 보낸다.

1. x에 있는 노드가 external node (terminal node) 일 경우
2. e+c(T.size)를 리턴.
   • e : 현재 path length
   • c(T.size) : 현재 노드에 있는 data point 갯수 (계속 split 했을 때 기대되는 path length)
     • 이를 더해주는 이유는 height limit 값을 통해서 anomaly의 민감도를 조정할 수 있기 때문. (이전 training stage에서 height limit에 의해 split이 멈춘 경우 그 노드를 external node로 리턴하는데, 그 노드 안에 1개가 아닌 여러개의 데이터 포인트가 존재할 수 있다. 따라서 split을 멈추지 않고 계속 했을 때 사전에 기대되는 path length를 계산해 더해주는 것)

4. 현재 노드 T에 저장되어 있는 split attribute를 a로 선언한다.

5. 데이터 포인트 x의 a 변수 값을 노드 T에 저장되어 있는 split value q와 비교 (x가 external node가 아니거나 Height limit을 초과하지 않을 때)

6. 경계 선상의 왼쪽이냐 오른쪽이냐에 따라 다음 노드를 지나게 됨.

=> Algorithm 3을 통해 모든 데이터의 path length를 구할 수 있음. 이를 t개의 iTree에 적용하여 평균을 구하면 모든 데이터 포인트에 대해 average path length인 $E(h(x))$를 얻을 수 있는데, 이를 활용해 최종적으로 Anomaly score인 $s(x,n)$을 얻는다.

5. Anomaly Score

• h(x)로부터 도출한 score를 바로 사용할 수 없는 이유 : subsampling 갯수가 증가할 수록 path length 또한 log로 증가하게 됨. 따라서 이에 대한 normalized anomaly score가 필요함.

anomaly score

• iForest는 여러개의 sub sample 모델을 사용하는 방식으로 swamping과 masking의 영향을 감소시킬 수 있다.
  • swamping : the phenomenon of labeling normal events as anomalies. (정상치가 이상치에 가까운 경우 이상치로 오분류하게 되는 현상)
  • masking : outlier cluster merged to a cluster with normal data points -> outlier are not detected. (이상치가 군집화되어 있으면 정상치로 오분류하게 되는 현상)
• small size로 subsampling한 iTree가 전체 데이터셋을 돌린 것보다 성능이 좋은 데 그 이유는 subsampling이 정상치가 이상치에 간섭하는 포인트가 적기 때문이다. (더 쉽게 이상치 구분 가능)

6. Conclusion

• 기존 Distance, Density 방식에서 벗어난 새로운 시각으로 접근함.
• anomaly의 'few & different' 특징에 착안하여 구상된 decision tree 기반 알고리즘
• 고차원, 많은 데이터에서 성능을 보존하며 빠른 속도로 학습 진행
• Labeled 데이터 없이 학습 가능