[ML] Isolation Forest

Anomaly Detection(이상 탐지)이란?

• Anomaly Detection(이상 탐지)이란 전체 데이터에서 다른 패턴을 보이는 데이터를 찾는 것을 말한다.
  • 다른 패턴을 보이는 데이터를 이상값(anomaly)라고 부르며,
  • 이상 탐지는 사기 탐지, 침입 탐지, 안전 관리를 포함한 다양한 분야에 널리 활용된다.
• Anomaly Detection 은 정답 label 이 주어졌냐, 안 주어졌냐에 따라 지도학습이나 비지도학습으로 진행된다.
• 비지도 학습을 통해 진행하는 Anomaly Detection 의 종류는 아래와 같다.
  • Isolation Forest
  • One Class SVM
  • Etc
• 따라서, 해당 포스트는 Anomaly Detection 의 비지도 학습 알고리즘 중 하나인, Isolation Forest에 대해 다룰 것이다.

Isolation Forest 란?

• Isolation Forest 는 기본적으로, 데이터셋을 의사결정나무(Decision Tree) 형태로 표현하며, Isolation Forest 의 기본 아이디어는 다음과 같다.
  • 정상 데이터는 분리하기 어렵기 때문에, 많은 재귀 이진분할을 통해 깊은 depth 를 가지지만,
  • 이상 데이터는 정상 데이터에 비해 분리하기 쉽기 때문에, 얕은 depth 를 가진다는 것이다.

• 위 그림을 보면, 왼쪽 그림의 정상 데이터 Xi 는, 오른쪽 그림의 이상 데이터 Xo 보다 더 많은 분할로 나눠진 것을 알 수가 있다.
• 따라서, 이 특성을 사용해, 데이터 분할 depth 를 기준으로 정상 데이터와 이상 데이터를 분리한다.

Isolation Forest의 특징

• Sub-sampling
  • 전수 데이터가 아닌 sampling한 데이터로 모델을 생성한다.
  • 기존의 군집화 이상탐지 방식은 전수데이터를 사용해야한다.
  • 따라서, 군집 기반 이상탐지 방식보다 계산량이 매우 적다.
• Swamping
  • 이상치가 정상치와 가까이 위치된 경우 잘못 분류되는 현상
  • 이를 해결하기 위해선, Sub-sampling 포인트를 줄여야한다.
• Masking
  • 이상치가 군집화 되어 있어, 정상치로 잘못 분류되는 현상
  • 이 또한, Sub-sampling으로 해결 가능하다.
• High Dimensional Data
  • 고차원의 데이터(feature가 매우 많은 경우)에서 잘 작동하지 않을 수 있다.
  • 고차원의 데이터로 넘어갈 때, 데이터간 sparse한 space가 많이 늘어나기 떄문에 split을 제대로 못한다.
  • 따라서, 차원을 줄이는 방법을 사용해야한다.
• Normal Instances Only
  • train 데이터에 이상치가 포함되어 있지 않아도 iForest는 잘 작동한다.
  • 이유는 score 판정 자체가 path length인 h(x)로 산정하기 때문이다.
  • 즉, iForest의 성능에는 이상치가 학습데이터에 있는지 없는지는 중요하지 않다.

참고

• https://dodonam.tistory.com/129
• https://john-analyst.medium.com/isolation-forest를-통한-이상탐지-모델-9b10b43eb4ac
• https://partrita.github.io/posts/isolation-forest/