[Anormaly Detection] Isolation Forest 분류트리를 거꾸로 생각하면 이상치를 찾을때 사용할 수 있다!

Isolation Forest : 트리알고리즘을 이용한 비지도 이상탐지

장점과 단점

장점

• 군집기반 알고리즘에 비해 계산량이 적다 (누적 평균치를 계산한 이후 서브셋을 만들어 계산량을 줄일 수 있다)
• Robust한 모델이다 → 계속 실행해도 같은 결과가 나온다
• Train 데이터에 이상치가 포함되어 있어도 잘 작동한다
• 트리계열 알고리즘이기 때문에 데이터에 대한 가정이 없어도 잘 동작하고 전처리가 거의 필요없다

단점

• 어떤 값이 이상치인지는 하이퍼파라미터를 조정해 threshold를 정의해야한다
• 특정 데이터 분포의 경우 Isolation Forest로 분류가 어렵다 (Extended Isolation Forest로 개선한 모델 사용)

이상치에 대한 가정

1. 이상치는 적은 데이터로 구성되어 있을 것이다
2. 이상치는 특정한 속성값이 정상치와 비교해서 매우 다른 값을 가질 것이다

이상치는 정상값에 비해 동떨어져 있으므로 이상치는 쉽게 고립시킬 수 있을 것이다

→ isolation 을 통해 이상치를 정상값에서 분리시킨다는 개념!

특정한 기준이 없이 임의 변수와 임의의 값으로 이상치를 splite 시킨다

 

 

아무의미없이 트리를 만드는데 분류트리와는 반대로 엔트로피가 낮은쪽으로 선택한다

하나의 값을 고립(isolation)시키는데 있어서 얼마나 많은 split 가 필요한지를 계산한다.

이상치가 평균적으로 몇번의 split이 필요한지를 계산 (정상값에 비해 매우 적은 횟수로 분류될 것이다)

 

 

평균을 취하기 위해 100개 이상의 forest를 구성해서 이상치인 x0를 구별할 수 있었다.

• 계산자원을 무한정 사용하는 상황을 방지하기 위해 split 최대치를 지정한다
• 우연히 동일한 값이 존재할 수 있으므로 그런 경우 split을 중단한다

이상치를 계산하는 score

 

 

하나의 트리에서 어떤 값을 고립시키는 path length의 기대값 E(h(x))과 평균 path length를 이용해 이상치를 계산하는 스코어를 계산한다.

기댓값이 클 수록 (정상값이어서 분류하는데 많은 split 이 필요한 경우) score는 0에 가까워지고 기대값이 작을 수록 (이상치여서 쉽게 Isolation 될 수록) score는 1에 가까워진다.

 

 

데이터 셋과는 상관없이 항상 0 ~ 1 사이의 이상치 score 가 계산된다 → 비지도 학습으로 데이터에 대한 이해가 적어도 바로 사용할 수 있다.

알고리즘이 작동하지 않는 경우와 이를 위한 Extended Isolation Forest

트리를 만들 때 수직 수평으로만 분류를 하므로 2번 3번의 경우 노란영역이 정상영역으로 분류되지만 실제로는 데이터가 있으면 안되는 이상치의 영역을 포함하고 있다. 축이라는 건 feature를 의미하는데 알고리즘은 feature가 어떤 중요도나 의미를 가지는지는 상관하지 않고 그냥 수직한 선을 그어서 isolation을 진행하는 것이 이런 문제를 야기함.

 

 

선이 많이 겹쳐질 수록 정상치로 분류하는데 2번 3번의 경우 이상치 데이터에도 선이 꽤 그어져있으므로 이상치인데 정상값에 가깝게 분류됨

 

 

Feature의 특성을 고려하지 않는 알고리즘 (랜덤하게 선을 그을 뿐임) 이므로 Isolation forests를 개선한Extended Isolation Forests는 선을 직선이 아닌 사선으로 그어서 이상치를 isolation 시킨다.