Isolation Forest

지난 포스트의 전통적인 이상탐지 기법 LOF (Local Outlier Factor) 에 이어, 이번 포스트에서 다룰 이상탐지 기법은 2008년에 발표된 Isolation Forest 입니다. Isolation Forest는 여러 개의 의사결정나무 (decision tree)를 종합한 앙상블 기반의 이상탐지 기법으로 의사결정나무를 지속적으로 분기시키면서 모든 데이터 관측치의 고립 정도 여부에 따라 이상치를 판별하는 방법입니다.

직관적으로 비정상 데이터라면 의사결정나무의 루트에서 가까운 깊이에서 고립될 것이고 정상 데이터라면 루트에서 먼 깊이에서 고립될 것입니다. 즉, 특정한 샘플이 고립되는 leaf 노드 (의사결정나무의 끝) 까지의 거리를 outlier score로 정의하고 루트 노드까지의 평균 거리가 짧을 수록 outlier score가 높아지는 원리입니다.

Isolation Forest

Algorithm

먼저 forest 를 구성하는 여러 의사결정나무를 정의합니다. 이때 의사결정나무가 각각 서로 다른 데이터를 볼 수 있게 각 의사결정나무마다 매번 전체 데이터에서 일부분을 샘플링한 데이터를 이용합니다. Algorithm 1에서 처럼 각 나무를 구성할 때 전체 데이터에서 $\Phi$ 비율만큼 샘플링해서 사용하게 됩니다.

각 나무에서는 분기에 사용할 변수 $q$를 랜덤하게 선택합니다. 선택된 변수들의 값을 랜덤하게 분기하기 위해 해당 변수의 최소/최대 값 사이에 정의된 uniform 분포에서 샘플링하여 분기하게 됩니다. 사용하는 데이터의 크기만큼 나무의 최대 깊이가 $log_2 n$ 만큼 정해지므로 (데이터가 256개라면 최대 깊이는 7이 됩니다.) 최대 깊이에 도달할 때까지 지속적으로 분기하게 됩니다.

https://donghwa-kim.github.io/iforest.html

다음으로 이상치 여부를 판단하기 위한 각 나무 별 데이터가 고립되기까지의 평균 길이 (루트 노드로부터의 거리, depth)를 계산합니다. 특히 최대 깊이에 의해서 분기가 중단되어 고려되지 못한 실질적인 depth를 반영하기 위해 Algorithm 3의 두번째 줄에 정의한 각 데이터 별 $c$값을 더해줍니다.

---

정리하면 샘플링된 데이터와 선택된 변수를 활용하여 다양한 나무를 생성해서 분기합니다. 분기 후에는 각 나무별로 각 데이터의 leaf node 를 알 수 있습니다. 만약 leaf node 에 포함된 데이터가 1이라면 고립이 된 것이고 1보다 크다면 최대 깊이로 한정되어 더 이상 분기하지 못한 것이겠죠. 또한, 각 관측치마다 각 나무 별 이동 경로 (depth 길이)를 모든 나무에 대해서 계산합니다.

Algorithm 3의 데이터 별 $c$는 어떻게 계산할까요? 각 데이터 별 leaf node에 포함된 데이터가 1개라면 $c=1$로 두고 1개보다 큰 $n$이라 한다면 다음과 같이 정의합니다. 최종적으로 각 데이터 별로 구한 $c$를 각 데이터 별 leaf node의 depth에 더해주어 각 데이터 별 평균 길이를 각 나무 별로 보정합니다. (0.5772는 오일러 계수입니다.) (데이터 개수 $\times$ 나무 개수 의 행렬을 만들어 [각 데이터 (행), 각 나무 (열)] 별 depth, $c$를 정의합니다.)

$H(i) = ln(i) + 0.5772$

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

Novelty score

최종적으로 이상치 여부를 판단하기 위한 score는 다음과 같이 계산합니다.

$score = 2^{-\frac{E(h)}{c}}$

위 수식에서의 $c$는 평균경로길이를 보정해 주기 위한 각 데이터 별로 정의된 위의 $c$와 다른 상수값으로 각 나무 별 사용된 데이터 개수 $n$에 (밑의 max samples) 대한 $2H(n-1)-\frac{2(n-1)}{n}$ 로 정의됩니다. (각 데이터 별 평균경로길이를 정규화하기 위한 상수 값입니다) $E(h)$는 기존 leaf node 깊이에 $c$를 더해 (Algorithm 3의 2번째 줄) 보정한 이후의 전체 나무에 대한 평균 길이입니다. 따라서 수식을 생각해봤을때 $E(h)$가 높으면 score가 낮고 반대이면 score가 높습니다.

$E(h)$가 높다는 것은 데이터가 고립되기까지의 길이가 많이 소요된다는 것이므로 정상데이터일 확률이 높고 $E(h)$가 낮으면 데이터가 이른 depth에서 고립되기에 이상치일 확률이 높습니다. 따라서 score가 높으면 이상치, 낮으면 정상이라 판단합니다. 일반적으로 이상여부를 판단하기 위한 score는 score가 높을수록 정상이라고 판단하기에 최종적으로는 0.5 - score 값을 최종 score로 사용하게 됩니다.

In python

파이썬에서는 sklearn.ensemble 모듈의 IsolationForest 함수가 Isolation Forest 알고리즘을 지원합니다.

Parameters	Description
n_estimators	나무의 개수로 디폴트는 100 입니다.
max_samples	Algorithm 1의 $\Phi$로 정수일 경우 지정한 정수 개수만큼 각 나무 별로 데이터를 샘플링합니다. 0과 1사이의 실수일 경우 전체 데이터 개수에 실수를 곱한 만큼의 데이터를 사용하며, 따로 지정하지 않았을 경우 전체 데이터 개수와 256 중 작은 수를 사용합니다.
contamination	전체 데이터에서 이상치의 비율입니다. 이 비율에 따라서 이상치로 판단하기 위한 score의  threshold를 정의합니다.
max_features	각 나무를 훈련할 때, 사용할 feature의 개수로 디폴트는 1로 선언되어 있습니다.

Isolation Forest example

일반적인 sklearn의 다른 함수와 마찬가지로 데이터에 "fit()", "predict()" 를 통해 결과를 알 수 있으며, "predict()"의 결과는 정상 (1), 이상 (-1) 로 표현합니다.

 

참조

• donghwa-kim.github.io/iforest.html
• scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html