Isolation Forest

March 2, 2025

Isolation Forest 관련 논문을 읽고 알고리즘을 파악해보려고 합니다.

1 Isolation Forest Intro #

“Anomalies are data patterns that have different data characteristics from normal instances” (Liu et al., 2008)

이상치는 정상 instances 와 다른 데이터 특성을 가진 데이터 패턴이다 라고 제시하고 있고,

이상 탐지는 데이터에서 평소와 다른 비정상적인 패턴을 찾는 과정이라고 정의를 해 볼 수 있습니다.

기존의 이상 탐지 방법들은 정상적인 데이터의 패턴을 먼저 학습하고, 이를 벗어나는 데이터를 이상치로 간주하는 방식을 사용했습니다.

하지만, 정상 데이터를 학습하는 데 시간이 오래 걸리고,

고차원 데이터에서는 성능이 떨어지며,

훈련 데이터에 이상치가 포함되지 않으면 탐지하기 어렵습니다.

이런 문제를 해결하기 위해 Isolation Forest 방법이 제시되었습니다.

2 격리하는 새로운 방식 #

기존 방법과는 다르게 정상 데이터를 학습하지 않고, 대신 이상치를 빠르게 격리하는 방식을 사용하는 방법도 있습니다.

이는 정상 데이터보다 이상치들이 더 쉽게 분리된다는 원리를 활용한 것 입니다.

핵심 아이디어는

랜덤한 분할로 트리를 만들고,

이상치는 적은 분할 횟수로 격리되는 것입니다. 즉 이상치는 경로 길이가 짧고,

정상 데이터는 많이 나뉘어야 격리 되고, 경로 길이가 깁니다.

이 방식을 사용하면 데이터가 많아도 빠르게 이상치를 찾을 수 있고, 고차원 데이터에서도 성능이 유지됩니다.

3 동작 과정 #

여러 개의 트리들을 생성하고, 경로 길이를 분석하여 이상치를 탐지하는 방식으로 동작합니다.

3.1 여러 개의 isolation tree(itree) 생성 #

여러 개의 isolation tree를 생성해서 forest를 구성하도록 합니다.

여러 개의 트리를 만들기 위해서,

데이터에서 일부 샘플을 무작위로 선택합니다.

각 트리에서 데이터를 랜덤하게 분할하여 빠르게 이상치를 격리합니다.

트리의 깊이를 제한해서 과적합을 방지합니다.

알고리즘 1의 경우 forest를 초기화하고(여러 개의 트리를 저장할 빈 숲을 만들며)

최대 트리 깊이를 설정합니다. t번 정도 isolation tree 생성 반복을 해서 t개의 iTree를 생성하여 forest에 추가합니다.

각 트리는 데이터셋 X에서 랜덤하게 샘플링된 Psi (기호 적기 귀찮…) 개의 데이터를 사용해서 학습합니다.

생성된 t개의 isolation tree 를 반환합니다.

이 단계에선 여러 개의 iTree를 만들어 isolation Forest를 구성합니다.

3.2 경로 길이 측정 #

데이터 포인트는 isolation tree 에서 격리될 때까지의 path length를 계산합니다.

이상치는 경로 길이가 짧고

적은 분할 횟수로 쉽게 격리되며

정상 데이터는 경로 길이가 길며

많은 분할 횟수가 필요합니다.

측정한 경로 길이 값을 평균 내어 Anomaly Score, 이상 점수를 계산합니다.

좀 더 동작 과정을 설명하면 종료 조건을 확인하고 트리 깊이가 최대 깊이에 도달하거나 데이터 크기가 1이하면 종료 합니다. 이 때 외부 노드를 생성하고 데이터 크기를 저장합니다.

분할 속성 및 갚을 선택합니다 q, p

데이터 분할의 경우 분할 값 p 를 기준으로 데이터를 두 개의 그룹으로 나누는데 왼쪽 서브트리 오른쪽 서브트리로 나뉩니다.

재귀적으로 iTree를 생성하고,

데이터를 랜덤하게 분할하면서 트리를 생성하며, 이상치가 더 빠르게 격리되도록 합니다.

3.3 Anomaly Score 계산 #

외부 노드인지를 확인하고,

분할 속성 및 값을 확인합니다. 현재 노드에서 데이터를 분할한 속성 q와 분할 값 p를 가져옵니다.

경로 탐색이 시작하고 탐색할 때마다 경로 길이를 1 증가합니다.

특정 데이터 포인트 x의 경로 길이를 측정하여 이상치인지 판단하는 기준을 제공합니다

anomaly score가 1에 가까우면 이상치,

0.5에 가까우면 정상 데이터

장점 #

빠른 실행 속도… nlogn의 실행 속도를 가집니다.

고차원 데이터에 강하고 속성들이 많아도 성능을 유지할 수 있으며,

훈련 데이터에 이상치가 없어도 탐지를 가능하게 할 수 있습니다. 기존 방법보단 유연하고,

샘플링을 활용하여 연산 최적화를 할 수 있습니다. 일부 데이터만 사용해도 높은 정확도를 유지할 수 있습니다.

현업이라면 금융 사기 탐지나 네트워크 보안, 제조 결함 감지와 같이 빠르고 효율적인 탐지가 필요한 곳이면 적용해 볼 가능성이 있습니다.

해당 접근 방법이 중요한 이유는,

랜덤 분할로 이상치를 빠르게 찾아낼 수 있고, 기존의 거리나 밀도 기반 방법보다는 효율적이며, 대량 데이터와 고차원 데이터에서도 강력한 성능을 가질 수 있습니다.

정리 #

정리하면,

먼저, 여러 개의 isolation Tree를 생성해서 숲을 구성하고,

두 번재로, 데이터를 랜덤하게 분할하여 개별 트리를 구축,

세 번째, 새로운 데이터 포인트 x가 트리에서 얼마나 빠르게 격리되는지를 측정하고,

네 번째, 여러 트리에서 얻은 경로 길이를 기반으로 이상 점수를 결정하며,

마지막, 이상 점수가 특정 임계값 이상이면 이상치로 판단합니다.

끝.

Reference #

Liu, F. T., Ting, K. M., & Zhou, Z. (2008). Isolation forest. Proceedings of the 2008 IEEE International Conference on Data Mining (ICDM), 413-422. https://doi.org/10.1109/ICDM.2008.17