[Anomaly Detection] Isolation Forest

이번 포스팅에서는 제가 얼마전부터 참여하고 있는 모두의 연구소 Anomaly detection - Isolation Forest 관련 내용을 정리하도록 하겠습니다. Isolation Forest는 이상탐지 기법 중 하나로서 트리 기반 알고리즘입니다. 

보시는 바와 같이 feature space에서 분할(Tree관점에서는 가지를 뻗어나기는 작업)을 해서 instance를 발라낸다고 할 때, 이상치의 경우(위 그림에서는 왼쪽 x0에 해당)에는 비교적 쉽게(Tree관점에서는 Root에 가까운 depth에서) 분리해낼수 있다는 데에 착안한 알고리즘입니다. 위 예시에서도 x0는 단 2번만에 분리가 된 것을 확인할 수 있지만 오른쪽에서는 수차례에 걸쳐 분기가 이루어져야만 분리해낼 수 있습니다. 

 

Isolation Forest는 iTree(Isolation Tree)의 앙상블로 볼 수 있습니다. 그럼 iTree는 어떻게 만들어진 트리일까요?

 

Given a sample of data X of n instances, the dataset X is recursively divided by randomly selected attribute q with a split value p, until either

▪ The tree reaches a height limit

▪ |X| = 1

▪ All instances in X have the same value

 

즉, 모든 말단(terminal) node에 각각 대응되는 데이터 포인트가 1개가 되는 상황이거나 미리 지정해준 특정 height에 도달할 때까지 분기를 시키는 것입니다. 

 

1. 먼저 비복원추출을 이용해서 데이터 일부를 sampling 합니다. 

2. Feature 중 무작위로 q를 선택하여 q값의 최대~최소 범위에서 uniform 한 확률로 분기기준값 p를 설정합니다.

3. 위에서 말씀드린 바와 같이 모든 관측치가 split되거나(이름이 Isolation인 이유를 이제 아시겠죠?) 미리 설정해둔 Tree의 height limit에 도달할 때까지 이 작업을 계속합니다. 

 

이 작업을 Ensemble로 반복하는 것이 Isolation Forest입니다. 

 

이렇게 Ensemble를 만들었으면 이제 이상치를 판별할 수 있는 score를 계산해야합니다. 처음에 Isolation Forest의 컨셉이 얼마나 root node에서 멀리떨어진 곳에서 분기해낼 수 있느냐 였죠? 그래서 Path length라는 개념이 들어옵니다. 

 

The path length h(x) of an instance x is measured by the number of edges x traverses an iTree from the root node to the terminal node in which the instance x is located

▪ h(x) is normalized by the average path length of h(x) given n

▪ c(n) = 2H(n-1)-(2(n-1)/n) (H(i) = ln(i) + 0.5772156649 (Euler’s constant))

 

그리고 path length의 개념을 이용해서 anomaly score도 계산할 수 있습니다: 

h(x)로 표기하는 path length는 iTree에서 모든 관측치가 split될 때의 split 횟수를 말합니다. iTree를 앙상블로 만든다고 했으므로 각 Tree 별로 path length로 다르겠죠? 그렇기 때문에 평균값으로 E(h(x))를 사용합니다. 그리고 c(n)은 h(x)를 normalization의 역할을 하고 있다고 보시면 됩니다. average path length of unsuccesful search in Binary Search Tree라는 개념에서 비롯됐다고 합니다. (아래 블로그를 참고하세요) 

https://woodyahn.tistory.com/60

[Anomaly Detection] Isolation Forest 설명

 

anomaly score 값의 구간에 따라 생각을 해보면

관측치 x의 평균경로 길이가 전체 경로 길이의 평균과 유사하다면 score값은 0.5에 가까워지게 됩니다. 관측치의 평균 경로길이가 0으로 수렴하게 되면 score값은 1에 가까워지게 됩니다. 즉, 이 score는 0~1 사이의 값을 갖고 1에 가까울 수록 이상치일 확률이 높다고 판단하게 되는 것입니다. 그럼 이번 포스팅은 여기서 마치겠습니다. (알고리즘의 세부사항이나 코드에 대한 부분은 https://donghwa-kim.github.io/iforest.html 를 참고하세요)

 

Reference)

Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation forest." 2008 eighth ieee international conference on data mining. IEEE, 2008.

Susto, Gian Antonio, Alessandro Beghi, and Seán McLoone. "Anomaly detection through on-line isolation forest: An application to plasma etching." 2017 28th Annual SEMI Advanced Semiconductor Manufacturing Conference (ASMC). IEEE, 2017.