Isolation Forest

본 포스트는 2008년 IEEE에 억셉된 Isolation Forest 논문을 정리한 것입니다. 공부한 내용을 정리하는 것이기에 잘못된 점이 있을 수 있습니다. 해당 내용에 대한 교정, 첨언, 조언은 언제나 환영합니다.

기존의 방법론 세계

이상치 탐지(anomaly detection)를 수행하는 알고리즘은 크게 model-based, distance-based, density-based 방법론으로 나눌 수 있습니다. 그리고 model-based는 다시 statistical methods, classification-based, clustering-based로 나눌 수 있습니다. 각 범주에 속하는 알고리즘들은 나름의 이론과 우수성이 있지만 저자들은 기존의 방법론들이 다음과 같은 점에서 아쉬움이 있다고 주장합니다.

먼저 model-based 방법론의 정상 데이터의 범주(profile of normal instances)를 명확히 하는 방식에 의문을 제기합니다. 왜냐하면 정상 데이터 범주를 최적화시키는 것이 꼭 비정상 데이터를 잘 탐지한다는 것을 항상 보장하지 않기 때문입니다. 이는 다르게 표현하면 정상 데이터 영역이 너무 specialization되어 정상 데이터를 비정상으로 판단하는 false alarm(False Negative, FN)이 발생할 수 있다는 이야기입니다. 예시로 하나 보겠습니다.

사과를 정상 데이터로 보고 그 외 과일을 비정상데이터로 보았을 때, 빨간 사과에 너무 specialization되어 초록색 사과는 정상 범주에 들지 못하고 있습니다. 초록색 사과도 사과인 만큼 사실 이것도 정상 범주에 속해야합니다. 만약 모델이 잘 최적화되었다면 초록색 사과도 정상 범주에 있었겠지요. Model-based의 정상 데이터 범주를 정하는 문제는 어디까지를 범주로 정해 지나치게 specialization 되는 문제를 피할 수 있는지 고려해야 합니다.

다음으로 distance-based, density-based 방법론의 거리나 밀도를 구하는 계산량을 아쉬운 점으로 언급합니다. 계산량은 알고리즘의 동작 속도나 메모리 효율과 직결된 요소이기 때문에 매우 중요합니다. 또 계산량이 높다면 모델이 고차원 데이터(large & high dimenstional data)를 분석하기 쉽지 않습니다. 그렇기에 가급적 계산량은 작을수록 좋습니다. 그러나 거리나 밀도를 필요로 하는 모델들은 늘 이런 연산에 많은 컴퓨팅 자원을 소모하게 되어, 해당 모델을 이용하여 분석을 할 때 가용한 자원을 늘 고려해야 합니다.

기존 방법론들의 이러한 아쉬움과 비교하여 iForest는 어떤 장점을 가진 알고리즘이고 어떻게 이상치를 탐지해내는지 알아보겠습니다.

Isolation Forest는 어떤 알고리즘인가?

iForest는 model-based 방법론 영역에 속한 트리 계열 알고리즘으로 비정상 데이터를 고립(isolation)시키는 방법을 사용합니다. 트리 알고리즘은 데이터의 특정 변수값을 기준으로 데이터를 두 그룹으로 분리 시킵니다. 이 분기(partitioning)를 계속 진행하다보면 데이터들은 모두 분리되어 특정 노드에 담기게 되겠죠. 이것을 논문에서는 고립이라고 부르며 “한 데이터가 다른 데이터와 분리되는 것”으로 정의합니다. 트리 구조에서 데이터의 분기는 랜덤하게 선택된 변수의 최대값과 최소값 사이의 특정 값을 기준으로 하며 모든 데이터가 고립될 때 까지 이를 반복합니다. 그렇다면 비정상 데이터를 고립시킨다는 것은 어떤 의미인지 살펴보겠습니다.

비정상 데이터는 일반적으로 정상 데이터와 다른 특징을 가지고 있습니다. 위에서 봤던 그림을 다시 예로 든다면 보통 사과와 수박은 크기, 무게 등에서 큰 차이가 발생할 수 있습니다. 만약 과일 데이터를 분석한다면 비정상 데이터인 수박은 크기나 무게 변수에서 매우 큰 값을 가지게 되겠지요. 또 현재 그림에서 사과는 5개 수박은 1개 입니다. 항상 그런것은 아니지만 비정상 데이터는 정상 데이터보다 숫자가 적습니다. 분석하고자 하는 데이터 도메인에서 정상과 비정상이 무엇인지 정의하고 그 그룹의 특징을 미리 확인해본다면 대부분 이런 특징을 나타남을 확인할 수 있습니다. 이렇게 비정상 데이터가 가지는 특징을 논문에서는 ‘few & different’라고 이야기합니다. 비정상 데이터는 숫자가 적기 때문에(few) 분기에 필요한 수가 적고 분기되기 좋은 값으로 인해(different) 고립이 빠르게 될 가능성이 높습니다. 이는 논문의 그림에서도 확인이 가능합니다.

$x_i$는 정상 데이터이고 $x_0$는 비정상 데이터입니다. 그림 (a)에서 정상 데이터를 고립시키는 데는 11개 분기선이 필요한데 비해 (b) 그림에선 비정상 데이터를 고립시키는데 분기선이 4개만 필요함을 알 수 있습니다. 맨 오른쪽 그림 (c)는 여러 트리에서 분기에 필요한 평균 경로 갯수를 의미합니다. 이는 분기수를 어떤 수식을 통해 계산한 값이지만 쉽게 말하자면 비정상 데이터 고립에 필요한 분기선이 적다는 뜻힙니다. 결과적으로 비정상 데이터들이 담긴 노드는 트리의 루트 노드와 매우 가깝게 위치하게 됩니다. 반대로 정상 데이터들은 트리와 매우 멀리 떨어진 노드에 위치하게 됩니다.

iForest는 이런 특징을 가진 여러 트리들을 앙상블하여 구축한 모델입니다. 정상, 비정상 데이터의 평균 경로 길이가 다르다는 이 인사이트를 바탕으로 평균 경로가 작을수록 비정상 데이터일 가능성이 높다는 점수를 반환하게 됩니다.

iForest는 알고리즘의 특성으로 인해 완전 트리(full tree)를 구축할 필요성이 없고 sub-sampling를 유용하게 사용할 수 있습니다. 이 내용도 같이 살펴보겠습니다.

먼저 완전 트리를 구축할 필요가 없다는 내용을 살펴보겠습니다. 트리에서 데이터를 모두 고립시키려면 굉장히 깊은 트리가 필요합니다. 그러나 비정상 데이터를 탐지하는 것이 목적인 iForest는 모든 노드를 고립시킬 필요는 없습니다. 이미 앞에서 우린 정상 데이터의 평균 경로와 비정상 데이터의 평균 경로에 차이가 있음을 확인했습니다. 그렇다면 일정 깊이 이상으로 트리를 확장시킬 필요가 없을 것입니다. 그래서 iForest는 트리의 깊이에 제한을 두는 부분 모델(partial model)을 구축합니다. 이는 모델 구축 시간이 단축되며 알고리즘의 계산량, 속도 등에서도 효율을 얻을 수 있는 부분입니다.

다음은 sub-sampling을 사용하는 부분입니다. 앞의 과일 예시에서 비정상 데이터가 가지는 ‘few & different’ 성질을 이야기했습니다. 그러나 만약 분석하려는 데이터에서 비정상 데이터가 이런 속성을 가지고 있지 않다면 어떻게 될까요? 아래 그림을 보겠습니다.

빨간색이 비정상 데이터, 파란색이 정상 데이터입니다. 그림을 자세히 살펴보면 일부 파란색 정상 데이터가 빨간색과 유사한 위치에 있습니다. 이는 정상과 비정상 데이터의 변수값이 크게 다르지 않다는 것으로 비정상 데이터의 ‘different’ 성질을 만족하지 않습니다. 또 그림 (a)에서 빨간색이 작은 군집 2개를 형성하고 있는것도 보입니다. 이 안에있는 비정상데이터를 고립시키려면 많은 분기선이 필요하겠죠. 이는 비정상 데이터의 ‘few’ 성질을 만족하지 않습니다. 이상치 탐지의 분야에서 비정상 데이터가 정상 데이터와 차이가 크지 않는 문제를 swamping 문제라고 하며 비정상 데이터가 많고 밀도있게 구성된 문제를 masking 문제라고 합니다. 둘 다 이상치 탐지에서 항상 고려해야 하는 대표 고전적인 문제로 비정상 데이터의 ‘few & different’ 성질이 만족되지 못할 때 발생하는 문제이기도 합니다.

Sub-sampling은 이 문제를 해결하는 좋은 대안 중 하나입니다. 학습에 사용되는 데이터의 일부를 샘플링하면 그림 (b)처럼 나타날 수 있습니다. 샘플링을 통해서 애매한 곳에 위치해 정상과 비정상을 구분하기 어려운 데이터들이 상당히 감소했고 비정상 데이터 군집 자체의 밀도도 낮아졌습니다. 이렇게 된다면 트리의 분기수도 적어지고 swamping과 masking에도 잘 대처할 수 있겠죠. 결과적으로 sub-sampling을 통해 이상치를 탐지하는 효과적인 모델 구축이 가능하면서 동시에 계산량에서도 이득을 얻을 수 있습니다.

수식으로 살펴본 Isolation Forest

(논문에서 n개 instance, n개 externel-node 등 n이 가리키는 것이 무엇인지 혼란스러울 수 있으니 주의!!)

iForest를 구성하는 기본적인 요소는 트리(이하 iTree)입니다. iTree는 먼저 완전이진트리(proper binary tree, full binary tree)를 기본으로 합니다. iTree는 주어진 데이터 셋을 특정 기준에 따라 반복적으로 분기하며 다음 3가지 조건 중 하나를 충족시킬 때 멈추게 됩니다.

• 제한 높이(height limit)에 도달한 경우
• 노드의 데이터가 1개인 경우(|X|=1)
• 노드에 들어있는 데이터의 값이 모두 동일한 경우

n개 데이터 샘플이 주어진 데이터 셋 $X={x_1, x_2, …, x_n}$는 iTree에서 분기되어 최종 노드에 담기게 됩니다. BST(binary search tree)에는 search의 결과물이 내부 노드(internal node)에 있는지 혹은 외부 노드(external)에 있는지에 따라 successful search와 unsuccessful search로 나눠지는 개념이 있습니다. iTree는 이 중 unsuccessful search의 구조와 유사하며 이 개념에서 두가지 정보를 얻을 수 있습니다. 첫번째는 트리가 얼마나 깊어질 수 있는지 입니다. 논문에서 path length라고 부르는 $h(x)$는 앞으로 비정상 점수(anomaly score)를 계산하는데 매우 중요한 요소인데 unsuccessful search tree에서 $h(x)$가 가질 수 있는 범위는 $0 < h(x) \leq n-1$입니다. 두번째는 트리의 평균깊이(average path length)입니다. 아래와 같은 수식으로 정의되며 유도 과정은 이곳을 참고하시기 바랍니다.

비정상 점수는 $h(x)$와 $c(n)$을 활용해 다음과 같이 정의됩니다.

$h(x)$의 기대값을 구하는 이유는 알고리즘이 forest이기 때문에 여러 트리에서 나온 결과를 평균내야 하기 때문입니다. 위에서 $h(x)$의 범위를 알았고 이 값이 0에 가까워지면 s는 1에 근접합니다. 반대로 n-1에 가까워지면 s는 0에 근접하게 됩니다.

우리는 비정상 데이터가 ‘few & different’ 성질로 인해 루트 노드에 가깝게 분기될 것이라고 했습니다. 이를 수식에 대입하면 $h(x)$값이 0에 가까워진다는 것을 의미하고 s는 1에 가까워 질 것입니다. 즉, 비정상 점수 s가 커질수록 데이터가 비정상이라고 할 수 있습니다.

pseudocode 내용

iForest는 forest를 만드는 training 과정과 비정상 점수를 계산하는 inference 단계로 나눠집니다. 먼저 training 과정부터 살펴보겠습니다.

iForest를 생성하기 위해 필요한 하이퍼파라미터와 학습 데이터가 inputs 부분에 나타나 있습니다. 앙상블을 수행할 트리 숫자와 sub-sampling 사이즈를 미리 알려줘야합니다. Sub-sampling 사이즈가 정해지면 평균 트리 높이의 근사값으로 트리 높이의 제한값이 정해집니다. 수식은 다음과 같습니다.

이 제한값이 iTree의 최대 높이이면서 부분 모델의 기준점입니다. 평균 트리 높이보다 짧은 경로에 있는 데이터들은 아마 비정상 데이터일 가능성이 높을 것입니다. 매번 데이터를 복원 샘플링하여 $X’$을 만들고 이 데이터로 t개 iTree를 만듭니다. iTree는 다음과 같은 과정으로 만들어집니다.

iTree는 샘플링된 데이터 X, 현재 트리 높이, 트리 높이의 제한을 파라미터로 받습니다. 인스턴스가 분리되어 노드가 |X|=1이 되거나 제한 트리 높이에 도달할 때까지 재귀적으로 분기를 수행합니다. X는 여러가지 변수를 가지고 있을텐데 이 변수 집합을 Q라고 합니다. 이 중 선택된 특정 변수가 q이며 q의 최대값과 최소값 사이의 특정 값을 p로 놓습니다. p값을 기준으로 작은 값은 왼쪽 자식 노드로 큰 값은 오른쪽 자식 노드로 나누어 재귀적으로 분할을 시도하는 트리가 iTree입니다. 분할되어 종료 조건에 해당하면 external node를 반환하고 종료 조건에 해당되지 않으면 internal node를 재귀적으로 계속 반환합니다. 최종적으로 이 iTree의 앙상블이 iForest가 됩니다.

모델 iForest가 완성되면 학습은 종료가 됩니다. 이제 새로운 데이터가 들어왔을 때 이것이 비정상인지 정상인지를 판단하기 위한 점수를 반환하는 알고리즘을 보겠습니다. 우선 알고리즘의 pseudocode는 다음과 같습니다.

비정상 점수 s를 계산하는데 필요한 $h(x)$는 첫 노드에서 external node에 도착할 때 까지의 경로 길이와 terminal node에 있는 학습셋의 데이터 수(=c(T.size))의 합으로 구합니다. 우선 external node에 도착할때까지 경로를 보면 노드가 internal node인 경우 분할할 변수 q와 그 값 p를 기준으로 자식노드로 내려가면서 경로 길이 변수 e를 1씩 더해나갑니다. 경로를 기준으로 세기 때문에 초기 e값은 0으로 지정됩니다. 만약 루트노드에서 마지막 노드까지 중간에 8개 노드를 거쳐 총 10개 노드가 존재한다면 경로는 9가 됩니다. 이 경로 길이에 더해 $c(T.size)$를 더하게 되는데 이는 트리 높이 제한을 초과하여 생성되지 않은 트리의 평균 경로길이입니다. T.size는 알고리즘2에서 external 노드에 들어가는 X의 갯수인데 즉 아직 분기되지 않은 데이터수를 의미합니다. 여기서 c(n)의 의미를 좀 더 살펴보고 T.size가 1, 2, 2 이상인 경우에 대해 잠시 살펴보겠습니다.

iForest에서 c(n) 수식은 n-1개 internal node가 있을 때 external node n개의 평균 길이를 나타내는 수식입니다. 즉, iTree의 terminal node가 external node가 되고 나머지 노드들이 internal node가 되는 구조입니다. 이 말은 T.size가 1인 경우 0개 internal node가 있는(=아예 노드가 없는) 경우이므로 c(1)=0이 됩니다. T.size가 2인 경우 루트 노드만 존재하는 경우이므로 c(2)=1이 됩니다. 루트 노드만 존재할 경우 BST에서 external node는 2개가 존재하고 이 경우 평균 external node 경로는 $ \frac{1}{2}(1+1) $이기 때문입니다. 2개 이상인 경우는 평균 external node 경로는 수식을 따라 approximate한 값을 이용합니다.

이렇게 각 iTree에서 얻은 새로운 x에 대한 $h(x)$값을 총 t개 구하여 평균을 낸 값으로 비정상 점수 s를 구합니다. 비정상 점수는 $ s(x,n) = 2^{-\frac{E(h(x))}{c(n)}} $ 이런 수식으로 얻어집니다. 마지막으로 지수에 있는 c(n)은 모든 iTree가 생성될 때 들어가는 $X’$의 크기가 됩니다. 모든 iTree는 샘플의 종류는 다르지만 크기는 동일한 $X’$을 쓰기 때문입니다.

의견

본 알고리즘은 학습 셋에 normal과 abnormal이 있는 경우에만 잘 동작하는 듯 하다. 만약 normal만으로 학습할 경우 abnormal을 잘 탐지하는 것은 불가능해 보인다.