본 내용은 Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (December 2008). “Isolation Forest”. 2008 Eighth IEEE International Conference on Data Mining: 413–422. 논문을 정리한 내용입니다. 원문은 여기서 확인할 수 있습니다. 부족한 영어 실력으로 번역 및 정리한 내용이기 때문에 미흡한 부분이 존재할 수 있고 실제와 다르다면 피드백 부탁드립니다.

1. Introduction

이 논문은 이상 징후를 명시적으로 격리하는 방법을 제시합니다. 우리가 제안하는 방법은 두 가지 이상의 양적인 특성을 활용하여 제시합니다. 양적 특성은 다음과 같습니다.

1. 더 적은 인스턴스로 구성된 라벨인 경우
2. 속성 값이 일반적인 인스턴스 값과 매우 다른 경우

즉, 이상(Anomalies)은 일반적인 것보다 ‘적고 차이를 보인다’는 특징을 보입니다. 본 논문에서는 트리 구조가 모든 단일 인스턴스를 효과적으로 격리시키는 구조라는 것을 소개합니다. 트리 구조 상, 이상(Anomalies)은 트리의 뿌리에 더 가깝게 격리됩니다. 반면, 정상값은 뿌리로 부터 더 멀게 격리됩니다. 이러한 트리 모델에서 격리 특성은 이 논문의 근간을 이루고 있으며, 이 나무를 격리 트리 모델(Isolation Tree) 및 iTree라고 부릅니다.

Isolation Forest라고 불리는 방법은 주어진 데이터에 대한 iTree의 앙상블 기법 모델입니다. 여기에서는 두 개의 Hyper Parameter가 존재합니다.

• Number of Trees: 앙상블 기법을 적용할 iTree의 수
• Sub-Sampling Size: 서브 샘플링 크기

Isolation Forest의 특징은 다음과 같습니다.

• 이상 징후를 감지하기 위해 거리 또는 밀도 측정을 사용하지 않는다. 따라서 거리 및 밀도 측정 사용법보다 연산량이 적어 비교적 빠르다.
• 트리 모델 기반이기 때문에 데이터의 크기가 크거나 고차원 데이터에서도 효율적이다.

2. Isolation and Isolation Trees

본 논문에서 격리(isolation)란 ‘인스턴스를 나머지 인스턴스와 분리하는 것’을 의미합니다. 이상(Anomalies)의 정의는 ‘적고 차이를 보인다’이기 때문에 격리에 더 민감합니다. 데이터로 생성된 랜덤 트리 모델에서 모든 인스턴스가 격리 될 때까지 재귀적으로 분할 반복을 진행합니다. 다음과 같은 상황에서 분할이 눈에 띄게 짧아진다는 것을 확인할 수 있습니다.

1. 이상(Anomalies)는 일반적인 값보다 비교적 적기 때문에 트리 구조 내의 짧은 경로에서 분할된다.
2. 일반적인 값과 다르게 극단적으로 차이를 보이는(구별하기 쉬운) 값은 트리 모델의 초기 분할에서 분리될 가능성이 높다.

그림1. Anomalies의 트리 모델 분할 예시

그림1은 정상적인 값(x_i)과 이상(x_0)을 트리 모델을 기반으로 분할하는 모습을 보여준 예시입니다.(a)에서는 정상적인 값을 분할하는 과정을 수행하는 그림입니다. 트리 모델이 12 번의 분할을 수행했다는 것을 알 수 있습니다. 반면, (b)에서는 이상(Anomalies)를 분할하는 데에는 단 4개의 분할만 수행했다는 것을 확인할 수 있습니다.

그림2. 평균 경로 길이 수렴

그림2는 정상적인 값과 이상 인스턴스 모두 트리의 수가 증가하면 평균 경로 길이가 수렴한다는 것을 알 수 있습니다.

Definition: Isolation Tree

T를 iTree의 격리노드로 가정합니다. 여기서 T는 자식이 없는 하나의 외부 노드(T_l) 또는 테스트와 정확히 두 개의 자식 노드가 존재하는 내부 노드(T_r)입니다. 테스트는 속성 q와 분할값 p로 구성됩니다. 여기서 테스트가 q < p를 기준으로 데이터 포인트를 T_l 과 T_r로 나눕니다. 분할을 수행하기 위해 D차원의 다변량 분포에서 n개의 인스턴스의 데이터 샘플이 존재한다고 가정합니다. 수식은 다음과 같습니다.

• 내부 노드(Internal Node): 트리 모델에서 가장 끝에 있는 노드(Leaf Node)가 아닌 나머지 노드
• 외부 노드(External Node): 트리 모델에서 가장 끝에 있는 노드(Leaf Node)

\[X = \left \{ x1, ..., x_n \right \}\]

여기서 속성q와 분할값 p를 임의로 선택하여 다음과 같은 조건까지 X를 재귀적으로 분할합니다.

1. 트리가 제한 깊이(Depth)까지 도달했을 경우

2. X

   = 1 일 경우

3. X의 모든 데이터가 동일한 값을 가질 경우

iTree는 트리 모델의 각 노드가 정확히 0 또는 2개의 자식 노드를 갖는 적절한 이진 트리 모델이라는 것을 알 수 있습니다. 모든 인스턴스가 구분된다고 가정한다면, iTree 모델이 완전히 성장할 경우 각 인스턴스는 외부 노드로 격리되며, 이 경우 외부 노드 수는 n개, 내부 노드 수는 n - 1 개로 구성됩니다. 따라서 총 노드 수는 2n - 1이며 시스템 자원은 n과 선형적으로 증가한다는 것을 알 수 있습니다.

이상 징후 검출 문제는 이상 징후 정도를 반영하는 순위를 제공하는 것입니다. 따라서 이상 징후를 탐지하는 한 가지 방법은 데이터 포인트를 경로 길이(Path Length) 또는 이상 점수(Anomaly Score)에 따라 정렬하는 것입니다. 경로의 길이와 이상 점수를 다음과 같이 정의합니다.

Definition: Path Length, h(x)

h(x)는 iTree의 루트 노드부터 외부 노드까지 가로지르는 Edge의 수로 측정할 수 있습니다.

이상 점수(Anomaly Score)는 몇며 이상 징후 탐지 방법에서 필요한 방법입니다. h(x)에서 이러한 점수를 도출하는 데 어려움이 존재하는 이유는 iTree의 최대 깊이는 n 만큼 증가하는 반면, 평균 깊이(Isolation Forest)는 log n 만큼 증가한다는 점입니다. iTree는 이진 탐색 트리(BST, Binary Search Tree)와 동등한 구조를 가지므로, 외부 노드까지의 경로에 대한 평균 h(x)의 추정은 BST의 실패한 탐색(Unsuccessful Search)와 동일합니다.

• Unsuccessful Search: 더 이상 분할을 수행할 인스턴스가 남지 않아 탐색이 불가한 경우

그림2. 평균 경로 길이 수렴

iTree와 Binary Search Tree간 Path Length 비교

Column	iTree	BST
트리 구조	적절한 이진 트리(Proper Binary Trees)	적절한 이진 트리 (Proper Binary Trees)
평균 경로 길이	측정 외부 노드 도달 시 종료 (External Node Termination)	실패한 탐색 (Unsuccessful Search)
(?)	해당 없음 (Not applicable)	성공한 탐색 (Successful Search)

따라서 iTree의 평균 경로 길이를 추정하기 위해 이진 탐색 트리에서 아이디어를 가져오겠습니다. n개의 인스턴스에 대한 데이터 세트를 고려할 때, 이진 탐색 트리에서 실패한 검색의 평균 경로 길이를 다음과 같은 수식으로 표현합니다.

\[c(n)=2H(n-1)-(2(n-1)/n)\]

위 수식에서 H(i)는 조화수(Harmonic number)이며 조화수의 추정식은 다음과 같습니다. 0.5772156649는 Euler-Mascheroni Constant입니다.

\[H(i)=ln(i) + 0.5772156649\]

또한, c(n)은 h(x)의 평균이기 때문에 h(x)를 정규화하기 위해 사용합니다. 인스턴스 x의 이상 점수(Anomaly Score) s는 다음과 같이 정의됩니다.

\[s(x,n) = 2^\frac{-E(h(x))}{c(n)}\]

여기서 E(h(x))는 iTree들의 평균 h(x)입니다. 따라서 다음과 같은 조건이 성립합니다.

• E(h(x)) → c(n) 이라면, s → 0.5
• E(h(x)) → 0 이라면, s → 1
• E(h(x)) → n-1 이라면, s → 0

s 는 h(x)에 대해 단조입니다. 여기서 단조는 줄곧 상승하거나 하강하는 것을 의미합니다. 다음 그림은 0 < h(x) ≤ n-1에 대해 0 < s ≤ 1인 경우 E(h(x))와 s의 관계를 보여주고 있으며, 이상 점수 s를 사용하여 다음과 같이 평가할 수 있습니다.

기대 경로의 길이 E(h(x))와 이상 점수 s의 관계 그래프

그래프를 확인하면 알 수 있다시피, 예상 경로의 길이 E(h(x))가 평균 경로 길이 c(n)과 같다면 n의 값에 관계없이 0.5임을 알 수 있습니다.

아래 그림은 정규 분포를 따르는 64개의 인스턴스로 구성된 2차원 플롯입니다. s = 0.5, 0.6, 0.7에 대한 등고선들이 함께 그려져있습니다. 잠재적으로 이상 징후는 s ≥ 0.6 바깥에 위치한 점들로 식별할 수 있습니다.

정규 분포에 대한 iForest의 이상 점수 등고선

3. Characteristic of Isolation Trees

이 파트에서는 iTree의 특징과 마스킹 효과를 처리하는 방법에 대해 설명합니다. 앞에서 설명했다시피, Isolation Forest(iForest)는 iTree를 사용하는 트리 앙상블 모델로서 경로 길이가 짧은 포인트를 이상(Anomalies)으로 식별하는 여러 트리가 존재합니다. iForest는 모든 일반(Normal) 인스턴스를 격리할 필요 없기 때문에 샘플링을 이용해 모델을 구축할 수 있습니다.

일반적으로 샘플의 크기가 클수록 더 나은 결과를 보여주는 기존 방법과 달리, 격리 방법은 표본의 크기를 작계 유지할 때 가장 잘 작동한다는 특징이 존재합니다. 샘플링의 크기가 크면 iForest가 격리 프로세스를 방해하여 이상 징후를 격리할 수 있는 능력이 감소합니다. 본 논문에서는 샘플링을 무작위 인스턴스로 추출하여 과정을 수행합니다.

Swamping과 Masking 문제는 이상 징후 탐지에서 광범위하게 연구되어왔습니다. Swamping은 정상적인 경우를 이상 징후로 잘못 식별하는 것을 말합니다. 정상적인 인스턴스가 이상(Anomalies)와 근사하면 격리하기 위한 파티션의 수가 증가(트리의 분할 수 증가)하므로, 이상 징후를 일반 인스턴스와 구별하기 더 어려워집니다. Masking은 이상이라고 판단할 수 있는 인스턴스들이 너무 많이 존재하는 것입니다. 이상 징후 클러스터가 크고 밀도가 높은 경우 파티션의 수도 증가하는 문제가 발생합니다.

위 두 가지 상황에서 트리를 사용한 평가는 길어진 경로로 인하여 이상 징후를 탐지하기 더 어렵습니다. Swamping과 Masking이 발생하는 대표적인 이유는 이상 징후를 탐지하기 위해 너무 많은 데이터를 사용한 결과입니다.

iTree의 고유한 특성으로 인하여, iForest는 서브 샘플링을 이용해 Swamping과 Masking의 발생 위험을 완화하고 모델을 구축할 수 있습니다.

1. 서브 샘플링은 데이터의 크기를 제어하기 때문에 iForest가 이상 징후를 더 잘 격리할 수 있다.
2. 각 서브 샘플은 서로 다른 일련의 이상(Anomalies)를 포함하거나 오히려 이상이 없을 수도 있기 때문에, 각 iTree가 일련의 이상을 더욱 잘 찾는 스페셜한 트리가 될 수 있다.

이를 설명하기 위해 그림 4를 확인해 보겠습니다. 데이터셋에는 중앙에 정상값들이 존재하는 하나의 큰 클러스터와 그에 가까운 이상 클러스터가 존재합니다. 이상 징후 클러스터는 근방에 정상값들이 존재하며, 전체 샘플 4096개 인스턴스 중 정상 지점보다 밀도가 높다는 것을 알 수 있습니다. 서브 샘플링을 수행한 데이터는 128개의 인스턴스로 구성된 데이터입니다.

이상 징후 클러스터는 서브 샘플에서 명확하게 식별할 수 있다는 것을 알 수 있습니다. 두 이상 징후 군집 근방에 위치한 정상값들이 제거되었고, 이상 징후 클러스터의 밀도가 작아져서 식별하기 쉬워졌습니다. 실제로 전체 샘플을 사용할 때 iForest는 AUC 0.67을 보였고, 128개의 서브 샘플링 데이터를 사용할 때 iForest는 AUC 0.91을 보였습니다. 결과적으로, iForest는 전체 샘플에서 서브 샘플링으로 축소된 데이터를 통해 Swamping과 Masking을 처리하는 데 있어 탁월한 이상 징후 탐지 능력을 보여줍니다.

4. Anomaly Detection Using iForest

이번 파트에서는 iForest를 이용한 이상 징후 검출을 수행합니다. 이상 징후 검출은 크게 2단계 과정으로 수행합니다.

1. 훈련 단계. 훈련 데이터를 서브 샘플링하여 iTree들을 구축
2. 테스트 단계. 구축한 iTree들을 이용하여 테스트 인스턴스를 통과시켜 각 인스턴스에 대한 이상 점수 산출

4.1 Training Stage

훈련 단계에서 iTree는 인스턴스가 격리되거나 특정 트리 깊이(Depth)에 도달할 때까지 훈련 데이터를 반복적으로 분할하여 구성됩니다. 이렇게 구성된 iTree는 iForest의 부분 모델이 됩니다. 트리 깊이 제한(l)은 서브 샘플링의 크기(ψ)에 의해 자동으로 설정되며 대략적으로 평균 트리 깊이입니다. 수식은 다음과 같습니다.

\[ψ: l = ceiling(log2 ψ)\]

평균 나무 깊이까지 트리 모델을 성장시키는 이유는 이상 탐지에서 관심있는 것은 평균 경로 길이가 더 짧은 데이터 포인트에만 관심이 있기 때문입니다. 앞에서 설명했다시피, 그 포인트들은 이상일 가능성이 더 높습니다.

iForest 알고리즘에는 두 가지 입력 파라미터가 존재합니다.

• Sub-sampling Size(ψ)
• Number of trees(t)

Sub-sampling Size

Sub-sampling Size(ψ)는 훈련 데이터의 크기를 관리합니다. 적절한 값으로 파라미터를 결정한다면 iForest가 이상을 보다 안정적으로 탐지합니다. 그러나, 파라미터를 너무 키운다면 모델의 이상 탐지 성능과 관계없이 처리 시간과 메모리 크기를 증가시키기 때문에 이를 고려하여 파라미터를 선택해야 합니다. 본 논문의 저자들의 경험상, 일반적으로 ψ를 28또는 256으로 설정하면 광범위한 데이터에 걸쳐 이상 징후 탐지를 수행할 수 있는 충분한 샘플링 데이터 수를 만족한다고 말합니다. 따로 값이 명시되지 않는 한, 논문 실험의 기본값은 256을 사용합니다.

Number of trees

Number of trees(t)는 앙상블의 크기를 제어합니다. 보통 경로의 길이가 t = 100보다 훨씬 전에 수렴된다는 것을 확인했습니다. 따로 값이 명시되지 않는 한, 논문 실험의 기본값은 100을 기본값으로 사용합니다.

4.2 Evaluating Stage

평가 단계에서 이상 점수 s는 각 테스트 인스턴스의 평균 예상 경로 길이 E(h(x))에서 도출됩니다. E(h(x))는 iForest에서 각 iTree를 통해 테스트 인스턴스를 전달하여 도출합니다. Path Length 함수를 사용하면 테스트 인스턴스 x가 iTree를 통과할 때 루트 노드에서 외부 노드로 가는 엣지 수(e)를 세어 단일 경로 길이 h(x)를 얻습니다. 테스트 인스턴스 x가 외부 노드에 도달할 때, Size > 1인 경우, 반환 값은 e + c(Size)로 조정합니다. 각 트리의 앙상블 모델에 대한 h(x)를 구하면 s(x, ψ)를 계산하여 이상 점수를 산출합니다.

5. Empirical Evaluation

이 파트에서는 iForest를 평가하기 위해 설계된 네 가지 실험에 대한 상세한 결과를 제시합니다. 첫 번째 실험에서는 iForest와 ORCA, LOF, RF를 비교합니다. ORCA와 LOF는 추후에 다루도록 하겠습니다. LOF는 밀도 기반 방식으로 잘 알려져 있으며 RF는 트리 앙상블이기 때문에 선택되었습니다. 두 번째 실험에서는 두 개의 큰 데이터를 이용하여 서로 다른 서브 샘플링의 영향을 확인합니다. 서브 샘플링이 이상 탐지 성능에 미치는 영향을 알 수 있습니다. 세 번째는 고차원 데이터에서 iForest를 적용합니다. 서브 샘플링에 대해 간단한 단변량 검정을 적용하여 차원을 축소합니다. 세 번째 실험의 목적은 고차원 데이터에서 iForest의 이상 탐지 성능을 향상시킬 수 있는지 여부를 알아내는 것을 목표로 합니다. 마지막으로 대부분의 경우 이상 징후 데이터를 얻기 어렵기 때문에, 정상적인 인스턴스만 훈련했을 때 iForest의 성능을 확인합니다. 이 실험의 성능 지표는 Area Under Curve (AUC)입니다.

5.1 Comparison with ORCA, LOF, Random Forest

이 실험의 목적은 AUC를 이용한 모델 성능 및 처리 시간 측면에서 iForest를 ORCA, LOF 및 RF와 비교하는 것입니다.

다음 표는 네 가지 방법에 대한 AUC 점수와 실제 실행 시간을 나타냅니다. 표에서 iForest가 ORCA에 비해 좋은 성능을 보인다는 것을 확인했습니다. 즉, 모델 기반 방법으로서의 iForest가 거리 기반 방법인 ORCA에 비해 성능과 처리 시간 면에서 우수하다는 것을 확인할 수 있습니다. 특히 iForest는 1,000개 이상의 관측값을 가진 데이터에서 더 정확하고 빠릅니다.

대규모 데이터의 처리 시간 면에서 iForest가 ORCA보다 우수한 이유는 관측값간의 쌍방향 거리를 계산할 필요가 없기 때문입니다. iForest는 사용된 8개의 데이터 중 7개의 데이터에서 LOF에 비해 우수하다고 나왔으며, iForest는 AUC 측면에서 테스트된 4개 데이터에서 RF보다 나은 모습을 보여주고 있습니다. 처리 시간에서 iForest는 LOF, RF와 비교했을 때 모든 데이터에서 우수한 결과를 보여 줍니다.

NA는 매우 높은 연산 복잡도와 시스템 자원으로 인하여 수행하지 않음 \

Http와 Mulcross 데이터의 경우, 이상 징후의 클러스터 크기와 밀도가 정상 인스턴스와 동일하거나 더 높기 때문에(Masking Effect) ORCA는 낮은 성능 결과를 보입니다.

또한 iForest는 t(Number of trees)의 변화에 안정적입니다. 다음 그림은 AUC가 비교적 작은 t에서 수렴되는 것을 보여줍니다. 따라서 t를 증가시키면 처리 시간도 증가하기 때문에, 데이터에 따라 수렴에 가까워지는 최소 t를 결정한다면 처리 시간을 더욱 단축시킬 수 있습니다.

5.2 Efficiency Analysis

이 실험의 목적은 서브 샘플링 크기 ψ와 관련하여 iForest의 효율을 확인합니다. 가장 크기가 큰 데이터인 Http와 ForestCover를 사용하여 서브 샘플링 크기가 이상 검출 정확도와 처리 시간에 미치는 영향을 검토합니다. 이 실험은 서브 샘플링 크기 ψ = 2, 4, 8, …, 32768로 조정하며 진행됐습니다. 결과는 다음 그림과 같습니다. 작은 ψ에서 AUC가 매우 빠르게 수렴된다는 것을 알 수 있습니다. ψ = Http의 경우 128, ψ = ForestCover의 경우 512일 때 가장 최적으로 나타났습니다. 이는 Http의 전체 데이터의 크기와 비교해서 0.045%, ForestCover의 경우 0.18%에 불과합니다.

5.3 High Dimensional Data

이상 징후 탐지의 중요한 과제 중 하나는 ‘고차원 데이터를 어떻게 처리할 것인가?’ 입니다. 거리 기반 방법의 경우 모든 점은 고차원 공간 내에서 매우 희박(Sparsity)합니다. iForest도 ‘차원의 저주’를 고려해야합니다. 이 실험의 목적은 높은 차원의 데이터에 대해 iForest가 처리 시간에 대하여 좋은 성능을 보임을 확인하는 것입니다.

각 데이터에 대해 Uniform Distribution를 따르는 임의의 변수 506개를 추가로 생성합니다. 따라서 각 데이터에는 총 512개의 변수가 존재합니다. 각 iTree를 구축하기 전에 서브 샘플링에서 변수의 하위 공간(subspace)를 선택하기 위해 Kurtosis test를 이용합니다. Kurtosis test는 일변량 분포의 첨도(Peakness)를 측정합니다. Kurtosis가 각 변수에 대한 순위를 제공한 후, 각 트리를 구성하기 위해 이 순위에 따라 하위 공간(subspace)를 선택합니다.

결과는 하위 공간의 크기가 원래 변수 수에 근접하면 이상 탐지 성능이 향상된다는 것을 보여줍니다. 다음 그림을 통하여 AUC(좌측 y축, 실선)는 서브 스페이스 크기(x축)가 원래 변수의 수(6개)에 근접할 때 좋은 성능을 보이고 있다는 것을 알 수 있습니다. 또한 서브스페이스 크기가 증가함에 따라 처리 시간(우측 y축, 점선, 초 단위)이 미약하게 증가한다는 것을 알 수 있습니다. 원자료를 사용하여 훈련된 iForest의 AUC는 상단 점선으로 표기됩니다.

5.4 Training using Normal instance only

그렇다면, “훈련 데이터가 정상적인 인스턴스만 포함할 때에도 iForest를 적용할 수 있는가?”라는 궁금증이 생길 수 있습니다. 이 질문에 답하기 위해 실험에서 가장 큰 두 데이터를 이용하여 간단한 실험을 수행했습니다.

각 데이터를 무작위로 이등분하여, 하나는 훈련 데이터 또 다른 하나는 테스트 데이터로 구성합니다. 이 데이터를 이용하여 iForest를 구축하고 AUC를 측정하는 과정을 10번 반복합니다. 이상 징후와 정상 데이터를 사용하여 모델링할 경우 Http는 AUC=0.99997을 보였습니다. 그러나 이상 징후 없이 훈련할 경우 AUC=0.9919로 감소했습니다. ForestCover의 경우 AUC는 0.8817에서 0.8802로 감소합니다. AUC가 전체적으로 감소했지만, 더 큰 서브 샘플링 크기를 사용하면 이상 징후 감지 성능을 회복하는데 도움이 될 수 있습니다. 서브 샘플링의 크기를 Http의 경우 ψ = 256에서 ψ = 8,192 ForestCover의 경우 ψ = 256에서 ψ = 512로 증가시키면 AUC는 0.99997과 0.884까지 상승합니다.

6. Discussion

지금까지 iForest에 대해 살펴봤습니다. iForest의 가장 큰 특징은 서브 샘플링을 이용하여 주어진 원자료에 비해 상당히 작은 샘플 크기만 요구한다는 것입니다. 이상 탐지 영역은 다른 도메인과 비교하여 상대적으로 빠른 대처가 필요한 영역입니다. 따라서 작은 샘플의 크기를 이용하여 처리 시간을 단축한 iForest는 이상 징후 탐지 영역에서 매우 뛰어난 모델 기반 알고리즘이라고 할 수 있습니다.