Isolation Forest

Isolation forest의 motive는 기본적으로 이상치 데이터는 소수의 데이터로 구성이 되어있다고 생각하고, 이 데이터들은 특정한 속성 값들이 정상 범주의 데이터보다는 매우 다른 속성 값들을 가질 것이라는 가정을 하고 있다.

따라서 input data에 대해 isolation을 할 수 있는 tree를 만들 수 있다면, 이상치 데이터는 isolation이 쉬울 것이고, 정상 데이터는 isolation을 시키는 것이 어려울 것이다.

위 plot에서 파란색 $x_{i}$는 정상 데이터이고, $x_{0}$는 이상치 데이터이다. 우리는 각 데이터를 고립시키는 트리를 만든다. 트리를 만드는 방법은 매우 간단하다.

Split point라는 위 plot에서 수직, 수평으로 그어진 선들을 랜덤으로 선택한다. Split point를 그었으면, 해당 데이터가 없는 부분을 버리게 된다. 이 과정을 계속 반복하다 보면 결국 데이터가 고립된다.

(a)의 경우는 총 11번의 split point를 통해 $x_{i}$를 고립시켰고, (b)의 경우에는 총 4번의 split point를 통해 $x_{0}$을 고립 시켰다.

정상 데이터의 경우에는 비슷한 특성을 갖고 있기 때문에, 서로 뭉쳐 있는 모습을 볼 수 있고, 비정상 데이터는 이와 반대로 멀리 떨어져 있는 것을 볼 수 있다. 따라서 정상 데이터일수록 고립시키기 힘든 반면, 비정상 데이터일 수록 고립을 시키기 쉬워 진다. 이렇게 split을 몇 번 했는지가 isolation forest에서는 abnomal score가 된다.

위 plot은 log scale이고, Isolation tree를 1000개 생성하였을 때 결과를 보여준다.

정상 데이터의 경우 평균 path length가 13, 비정상 데이터의 경우에는 4 정도로 수렴하는 모습을 보인다.

Path length는 split을 몇 번 했는지와 같다.

이를 그래프로 표현하면 다음과 같다.

정상 데이터일 수록 더 깊은 depth에 위치하게 되고, 사용자는 왼쪽과 같이 threshold를 통해 최종적으로 해당 데이터에 대해 normal, abnormal을 결정할 수 있다.

Isolation tree의 종료 조건은 다음과 같다.

Tree의 맨 마지막 depth까지 도달하였을 때 (맨 마지막 depth는 사용자 지정)
우연히 데이터 포인트 2개가 같은 설명 변수를 가지고 있을 때
모든 데이터 포인트의 instance가 같은 값을 가지고 있을 때

충분히 많은 tree를 만들고 나면 path length를 구한다. 여기서 path length는 tree edge의 개수이다. 그리고 오일러 상수를 통해 평균 path length를 구할 수 있다.

여기서 구한 평균 path length를 $c(n)$이라 하고, $h(x)$를 1개의 tree에 대해 $x$를 고립시키기 위한 path length라고 할 때 아래 수식을 사용하여 최종적인 anomaly score를 정의한다.

$$ Anomaly \ score=s(x,n)=2^{-\frac{E(h(x))}{c(n)}} $$

Anomaly score가 1에 가까워지면 비정상일 가능성이 높고, 0에 가까워지면 정상일 가능성이 높아진다.

트리의 특성상 복잡도가 높은 알고리즘에 속해, 데이터가 많을수록 속도가 느려진다.

위 plot은 각 4096, 128개의 instance를 통해 isolation tree를 사용한 결과이다. 정상 데이터와 비정상 데이터의 area를 보면 거의 차이가 없는 모습을 보인다.

논문에 따르면 대략 256개의 instance만 사용해도 전체 데이터를 사용했을 때랑 성능 차이가 없다고 한다.

결과를 보면 다른 알고리즘에 비해 AUC가 매우 높은 모습을 볼 수 있다.

성능과 계산 복잡도를 생각하면 활용의 가치가 매우 높고, 해당 논문이 나온지는 시간이 14년 정도가 지났지만, 아직까지도 현업에서 활용이 되고 있는 anomaly detection 방법론이다.

Extended Isolation Forests

Exteneded isolation forest는 2018년에 나온 비교적 최근의 논문이다. 위 plot에서 흰색에 가까울수록 정상이라고 판별할 가능성이 높다. 이전 standard isolation forest의 경우 왼쪽 plot과 같은 데이터에 대해서는 이상치를 잘 판별한다. 하지만 오른쪽 plot과 같이 data의 분포가 2개로 몰려있을 때는 오른쪽 위, 왼쪽 아래도 anomaly score가 작은 것을 확인할 수 있다.

이 단점을 보완하고자 extended isolation forest는 논문의 이름과 같이 기존 isolation forest를 살짝 수정하였다.

개념은 비교적 간단하다. 위 그림에서 빨간 rect 부분까지 정상이라고 판단하는 이유는 가로, 세로 선들을 통해 isolation을 시키기 때문이다. 빨간색 영역도 보면 고립시키기에 힘든 영역이다. 따라서 해당 영역도 정상 데이터 영역으로 보는 것이다.

기존 isolation forest는 데이터에 대한 설명력이 별로 없다. 이 이야기는 중요도, 영향도를 파악을 하지 않는다는 말이다. 따라서 우리가 굳이 split을 수직으로 할 필요가 없어진다. Extended isolation forest는 split을 기울기가 있는 선분으로 진행한다.

같은 데이터 셋이지만 split line이 확연히 차이나는 모습을 볼 수 있다.