44. Isolation Forest에 대해서 알아보자.

---

이번 포스팅에서는 모델 기반 이상치 탐지 방법인 Isolation Forest에 대해서 알아보고자 한다.

 

- 목차 -

1. Isolation Forest이란 무엇인가?

2. Isolation Forest 알고리즘

3. 예제

3. 장단점

---

   1. Isolation Forest이란 무엇인가?

1) 정의

Isolation Forest는 이상치는 정상 데이터에 비하여 이진 탐색 나무(Binary Search Tree)로 고립이 잘될 것이라는 아이디어에 착안하여 개발된 알고리즘이다. Isolation Forest는 각 데이터에 대하여 이상치 점수를 계산하고 점수가 높을수록 이상치라고 판단한다.

---

2) 파헤치기

위 정의를 하나씩 파헤쳐보자.

a. Isolation Forest는 이상치는 정상 데이터에 비하여 이진 탐색 나무(Binary Search Tree)로 고립이 잘될 것이라는 아이디어에 착안하여 개발된 알고리즘이다.

Isolation Forest는 주어진 데이터를 고립시킬 때까지 의사결정나무로 영역을 분리한다. 아래 그림은 이상치(왼쪽 빨간 점)와 정상 데이터(오른쪽 빨간 점)를 고립시킨 것을 나타낸 것이다. 이때 왼쪽은 두 번만에 해당 데이터를 고립시켰고 오른쪽은 6번 만에 고립시킨 것이다.

Isolation Forest는 랜덤한 변수를 선택하고 그 변수가 가질 수 있는 최소값과 최대값사이에서 랜덤한 값으로 분리를 진행한다. 이때 이상치라면 정상 데이터들과 떨어져 있을 테고 그러면 랜덤하게 분리를 진행해도 비교적 적은 분리 횟수 안에 고립이 될 것이다(왼쪽 그림). 반대로 정상 데이터는 주변에 데이터가 많아서 분리하는 것이 쉽지 않기 때문에 고립시키기 위하여 많은 분리가 필요하다(오른쪽 그림).

 

이처럼 Isolation Forest는 이상치는 정상 데이터에 비하여 이진 탐색 나무로 (대충 분리해도) 비교적 적은 분리 횟수로 고립이 될 것이라는 아이디어를 적용하여 만들어진 알고리즘이다.

b. Isolation Forest는 각 데이터에 대하여 이상치 점수를 계산하고 점수가 높을수록 이상치라고 판단한다.

앞에서 이상치는 비교적 적은 분리 횟수로 고립시킬 수 있고 정상 데이터는 꽤 많은 분리 횟수로 고립시킬 수 있다고 했다. 그렇다면 주어진 데이터를 고립시키기 위한 분리 횟수를 이상치 점수로 활용할 수 있을 것이다. Isolation Forest는 분리가 랜덤하게 이루어지므로 고립시키기 위한 분리 횟수를 하나의 나무가 아니라 충분히 많은 나무에 대해서 고립 작업을 수행하게 된다.

 

아래 그림은 Isolation Forest가 데이터를 고립시킨 후 빨간 점에 대한 이상치 점수(Anamoly Score)를 계산하는 대략적인 과정을 나타낸 것이다.

이상치 점수(Anamoly Score)에 대한 구체적인 계산 방법은 아래에서 다루기로 한다.

---

   2. Isolation Forest 알고리즘

Isolation Forest 알고리즘 구성 요소 및 특징에 대해서 하나씩 알아보자.

---

1) 고립(Isolation)

Isolation Forest에서는 주어진 데이터를 고립시키게 된다. Isolation Forest는 아래의 세 가지 조건 중 어느 하나를 만족할 때까지 분리하게 된다.

---

(1) 영역 분리시 사전에 설정한 최대 깊이에 도달한 경우

(2) 분리했을 때 자식 노드(왼쪽 노드 또는 오른쪽 노드)에 데이터가 하나 포함되는 경우

(3) 분리 했을 때 자식 노드에 데이터 값이 모두 같은 경우

---

(2)는 고립의 관점에서 보면 너무나도 당연하며 (3)은 데이터는 여러 개이지만 사실 하나의 데이터와 다름없는 경우를 말한다. (1)에서 최대 깊이는 결국 분리 횟수를 의미하며 일정 분리 횟수를 넘어가면 더 이상 볼 필요 없이 정상으로 간주한다는 것으로 계산량을 아껴주는 역할을 한다.

---

2) 분리 방법

앞에서는 분리 종료 기준을 이야기했고 분리 방법에 대해서는 이야기하지 않았다. Isolation Forest는 매 분리시 변수와 분리 값을 랜덤하게 선택하여 영역을 분리한다.

 

예제를 살펴보자. 아래와 같은 데이터가 있다고 할 때 Isolation Forest를 만드는 방법을 알아보자.

이때 변수는 $x_1, x_2$ 그리고 데이터 상에서 $x_1$의 최소값과 최대값은 각각 1, 5이고 마찬가지로 $x_2$의 최소값과 최대값은 각각 1, 5이다. 또한 최대 깊이(원 논문에서는 Path Length라 한다)를 3이라 해보자.

 

첫 번째 분리를 해보자. $x_1, x_2$ 중에서 랜덤하게 선택된 것이 $x_1$이라 해보자. 그리고 분리값은 $x_1$의 최소값과 최대값 사이 즉, 1과 5 사이의 값 중 랜덤하게 선택한다. 선택된 값이 2.3이라 해보자.

이때 $x_1<2.3$이면 왼쪽 노드로 $x_1\geq 2.3$이면 오른쪽 노드로 가게 된다. 이때 왼쪽 노드에 포함되는 데이터는 하나이므로 더 이상 분리가 되지 않는다. 

 

두 번째 분리를 해보자. 이번에도 $x_1$이 랜덤하게 선택됐고 $x_1$의 최소값 최대값이 각각 2.5와 5라고 할 때 그 사이에서 4.9를 랜덤하게 선택되었다고 해보자.

이때 $x_1<4.9$인 경우 왼쪽 노드로 $x_1\geq 4.9$이면 오른쪽 노드로 가게 된다. 이때 오른쪽 노드에 포함되는 데이터는 하나이므로 더 이상 분리가 되지 않는다. 이제 분리를 진행하면 최대 깊이가 3이 되므로 사실상 분리는 더 진행되지 않는다. 이때 노란색 점은 Path Length가 2이고 파란색 점들은 3이 된다는 점을 유의하자.

---

3) 이상치 점수

하나의 이진 탐색 나무가 모든 데이터를 다 고립시켰다고 하면 각 데이터에 대해서 이상치 점수를 계산하게 된다. 이상치 점수를 계산할 때에는 주어진 데이터 $x$와 이진 탐색 나무를 이용한다. 이진 탐색 나무를 통해 $x$가 지나간 경로의 길이(Path Length)를 $h(x)$라 하자.

 

아래 그림은 앞선 예제에서 각 데이터들의 Path Length를 계산한 것이다.

$h(x)$를 바로 이상치 점수로 활용할 수 있지만 Isolation Forest는 하나의 나무가 아닌 여러 개 나무를 이용하고 각 나무의 사이즈(터미널 노드의 개수)가 각 나무마다 다를 것이다. 따라서 나무의 사이즈의 관계없이 이상치 점수를 계산하기 위하여 $h(x)$를 정규화(Normalization)를 해주어야 한다.

 

만약 데이터 $n$개가 모두 다른 값이라고 가정하고 (사전에 설정한 최대 깊이 이전에) 모든 데이터를 분리했다면 터미널 노드는 $n$개가 생긴다. 그렇다면 데이터들의 Path Length 평균은 터미널 노드 Path Length의 평균과 같다. 이때 주어진 이진 탐색 나무의 사이즈(터미널 노드의 개수)가 $n$개인 경우 터미널 노드의 평균 Path Length $c(n)$은 다음과 같다는 사실이 알려져 있다.

$$c(n) = 2H_{n-1}-\frac{2(n-1)}{n} \tag{1}$$

여기서

$$H_n = 1+\frac{1}{2}+\cdots +\frac{1}{n}$$이다.

 

이제 $h(x)$를 $c(n)$으로 나누어 정규화를 하게 된다. Isolation Forest의 나무가 $t$개 있을 때 데이터 $x$의 정규화된 평균 Path Length $h'(x)$는 다음과 같이 계산한다.

$$h'(x) = \frac{1}{t}\sum_{i=1}^th_i(x)/c(n) \tag{2}$$

여기서 $h_i(x)$는 $i$ 번째 이진 탐색 나무에서 계산된 $x$의 Path Length이다. 

 

이제 데이터 개수 $n$에 대하여 $x$의 이상치 점수 $s(x, n)$을 다음과 같이 정의한다.

$$s(x, n) = 2^{-h'(x)}\tag{3}$$

2의 지수를 취한 것은 이상치 점수가 0과 1 사이에 있게 하기 위함이다. 

 

이때 $h'(x) \rightarrow 0$이면 $s \rightarrow 1$이고 이는 주어진 $x$가 이상치일 가능성이 높다고 판단한다. 만약 $h'(x)$가 커지면 $s$는 작아지고 $x$는 정상일 가능성이 높다고 판단한다.

---

4) Sub-sampling

Isolation Forest는 이진 탐색 나무로 (비록 최대 깊이 제한이 있다 하더라도) 모든 데이터를 고립시킬 때까지 하나의 나무를 성장시키기 때문에 데이터가 많다면 그만큼 계산량도 많아진다. 이러한 계산량 문제를 극복하고자 Isolation Forest는 원 데이터를 샘플링하여 나무를 성장시킨다(성장시킨다는 것은 데이터를 고립해 나간다는 뜻). 아래 그림은 이러한 샘플링 과정을 나타낸 것이다.

샘플링을 하는 또 다른 이유는 Swamping이라고 부르는 현상(아래 그림 왼쪽)인데 이는 정상 데이터와 이상치 데이터가 매우 가깝게 붙어있어서 정상을 이상치로 잘못 판별하는 것을 말한다(정상 데이터가 이상치 데이터라는 늪에 빠진 상황이라 하여 Swamping이라고 부르는 것 같다). 이러한 현상은 데이터가 많기 때문에 발생할 수 있으며 샘플링을 하면 이러한 Swamping 문제를 해결할 수 있다.

 

또한 이상치 데이터가 한 곳에 조밀하게 많이 모여있어서 이상치 하나를 고립시키는 데 많은 분리가 필요할 수 있다. 이는 이상치 점수가 낮아지는 결과로 이어지며 이상치를 정상으로 잘못판단하는 Masking 문제가 발생할 수 있다. 이 문제 또한 샘플링으로 해결할 수 있다.

---

5) 알고리즘

Isolation Forest의 알고리즘은 다음과 같다.

---

Algorithm

1 단계) 나무 개수 $t$와 샘플링 사이즈 $\psi$를 설정한다. 이때 최대 깊이는 자동적으로 $\log_2\psi$을 올림한 정수값으로 설정된다(평균 나무 깊이의 근사값이라고 한다). 그리고 $F = \phi$로 설정한다.

 

$i=1, 2, \ldots, t$에 대하여 2~3 단계)를 반복한다.

2 단계) 데이터 X를 $\psi$개만큼 비복원 추출한다. 이를 $X'_i$라 하자. $X'_i$를 이용하여 데이터를 고립시킬 때까지 이진 탐색 나무 $T_i$를 성장시킨다.

 

3 단계) $F= F \cup T_i$로 설정한다.

---

---

6) 알고리즘 고찰

여기서는 두 가지 질문에 대한 내용을 생각해 보자.

 

튜닝 파라미터는 어떻게 설정하는가?

 

Isolation Forest의 튜닝 파라미터는 샘플링 사이즈 $\psi$와 나무 개수 $t$이다. 이건 뭐 실험을 통해서 선택할 수밖에 없는 듯하다. 논문에서는 $\psi=256$ 정도면 모든 데이터를 다 커버할 수 있다고 한다. 그리고 나무 개수는 Isolation Forest 논문에서 $t=100$을 넘지 않아도 평균 Path Length가 수렴이 잘 되었다고 한다.

 

정말 이상치의 평균 Path Length가 작을까?

 

Isolation Forest의 아이디어는 이해했지만 랜덤 요소가 많아서 이상치의 평균 Path Length가 정상에 비하여 정말 작은지 궁금할 수 있다. 이에 대한 답이 Isolation Forest 논문에서 발췌한 그림에 있다.

위 그림은 정상 데이터 $x_i$와 이상치 $x_o$에 대한 평균 Path Length를 나무의 개수에 따라 어떻게 변하는지 나타낸 것이다. 그래프에서 나무의 개수가 50일 때부터 어느 정도 수렴성이 확보되는 것을 알 수 있으며 확실히 이상치의 평균 Path Length가 정상치보다 작다는 것을 알 수 있다. 즉, 나무의 개수가 50개 이상 정도된다면 이상치와 정상치가 평균 Path Length로 잘 구분이 된다는 것을 알 수 있다.

---

   3. 예제

예제를 통해 Isolation Forest를 구성하는 방법과 이상치 점수 계산 방법을 알아보자. 아래 그림과 같이 5개의 데이터가 있다. 왼쪽은 테이블로 나타낸 것이고 오른쪽은 이를 좌표축에 나타낸 것이다.

편의상 나무의 개수는 2, 샘플링 사이즈는 4로 정하고 최대 깊이는 제한하지 않겠다. 이제 위 데이터에서 4개를 샘플링한다.

이제 랜덤하게 변수 $x_1, x_2$와 분리 기준을 선택하여 모든 데이터를 고립시킨다. 먼저 랜덤하게 변수 $x_1$을 선택했다고 해보자. 이때 $x_1$의 최소값과 최대값은 1과 5이므로 1과 5 사이의 랜덤한 (연속형) 숫자를 하나 랜덤하게 선택한다. 이를 1.5라고 해보자. $x_1 < 1.5$이면 왼쪽 노드에 $x_1\geq 1.5$이면 오른쪽 노드로 데이터를 보낸다. 아래 그림은 이 과정을 나타낸 것이다.

위 그림에서 초록점은 고립되었으므로 이제 나머지 3개의 데이터를 고립시켜야 한다. 이때 랜덤하게 선택된 변수가 $x_2$라고 한다면 $x_2$의 최소값과 최대값이 각각 1.5와 2.5이므로 이 사이에서 하나의 숫자를 랜덤하게 선택한다. 이를 1.75라 하자. $x_2<1.75$인 경우 왼쪽 노드 $x_2\geq 1.75$인 경우 오른쪽 노드로 분리한다. 여기서 파란점이 고립되는 것을 알 수 있다.

마지막으로 랜덤하게 선택된 변수가 $x_1$이라 하면 남아 있는 데이터에서 $x_1$의 최소값과 최대값은 각각 2와 2.5가 된다. 이 사이에서 랜덤하게 선택된 값이 2.3이라 하자. $x_1 <2.3$이면 왼쪽 노드 $x_2\geq 2.3$이면 오른쪽 노드로 분리된다. 이제 모든 데이터가 고립되었으므로 첫 번째 이진 탐색 나무가 완성된 것이다.

 

나무 개수는 2개이므로 앞에서의 절차와 같은 방법으로 나무를 하나 더 만들어야 한다. 아래 그림과 같이 첫 번째, 두 번째 이진 탐색 나무가 만들어졌다고 해보자. 즉, 두 개의 이진 탐색 나무로 이루어진 숲(Forest)이 만들어진 것이다.

 

그렇다면 이상치 점수는 어떻게 구할까? $x=(1, 1)$이 주어졌다고 해보자. 이제 각 이진 탐색 나무에서 $x$가 포함되는 터미널 노드를 찾는다. 그러고 나서 해당 노드에 대한 Path Length를 계산한다. 주어진 데이터는 첫 번째 나무에서 Path Length는 1이고 두 번째 나무에서는 2인 것을 알 수 있다.

이때 $n=5$이고

$$c(5)=2H_4 - \frac{8}{5} = 2\cdot \frac{25}{12}-\frac{8}{5} = 2.57$$

이므로

$$h'(x) = \frac{1}{2}\left (\frac{1}{2.57} + \frac{2}{2.57} \right )=0.58$$

이다.

따라서 $x$의 이상치 점수 $s(x, 5) = 2^{-0.58} = 0.67$이 된다.

---

   4. 장단점

Isolation Forest의 장단점은 다음과 같다.

- 장점 -

a. 샘플링을 이용하기 때문에 계산량이 줄고 다른 이상치 탐지 알고리즘(LOF, 1-SVM, SVDD)에 비하여 속도가 빠르다.

 

b. 샘플링을 통해 이상치 탐지에서 골칫거리인 Swamping과 Masking 문제를 해결할 수 있다.

 

c. 라벨이 없어도 데이터의 이상치 점수를 계산하여 이상치 여부를 판단할 수 있다.

 

d. 특별한 데이터 분포 가정이 필요 없다.

---

- 단점 -

a. Isolation Forest는 샘플링과 나무 개수에 따른 불안정성이 있다.

따라서 충분한 수의 샘플링과 나무 개수를 설정하는 것이 중요하다.

 

b. Isolation Forest는 이상치를 잘 판별 못하는 데이터 구조가 있다.

 

왼쪽 그림에서 정상 데이터는 좌상단 우하단에 모여있다. 따라서 우상단 좌하단에 있는 데이터(빨간 점)는 이상치로 간주해야 하나 특정 축에 투영시키면 이상치가 정상 데이터 분포에 포함되어 고립시키는 것이 어렵다. 따라서 Isolation Forest는 이를 이상치로 잘 판단하지 못하게 된다. 또한 오른쪽 그림과 같이 변수 간 주기성 관계를 가질 때에도 한 축으로 데이터를 투영시켰을 때 이상치가 정상 데이터에 포함된다. 이러한 구조를 갖고 있는 데이터에 대해서 Isolation Forest는 이상치를 잘 잡아내지 못한다. 이러한 단점을 극복한 Extended Isolation Forest라는 것이 있는데 이는 다음 포스팅에서 다루려고 한다.

그림 출처 : Extended Isolation Forest 논문

---

 

- 참고 자료 - 

F. T, Liu, K.M, Ting, Z.H, Zhou - Isolation Forest

강필성 - 03-7: Anomaly Detection - Isolation Forest (이상치 탐지 - Isolation Forest)

---