[ML] iForest / Extended iForest 정리

이상치 탐지 Task를 참여하면.. 한번쯤 들어보는 알고리즘인 iForest...
Forest계열은 언제나 옳다는 마음가짐으로 이상치 탐지 테스크를 할때마다 사용하고 한다. ( 할때마다 성능은 그닥...?)
 
그래서, 이번 기회에 iForest를 정리하고 확장된 개념인 Extended iForest 또한 정리하고자 한다.
iForest는 ExtraTree기반을 사용하기 때문에 혹시 ExtraTree에 대해 잘 알고있으면 훨씬 수월할 것이다.
Decision Tree가 어떻게 작동하는지 정도는 알고 해당 글을 봐야 어느정도 이해가 될것이라 생각한다.
ExtraTree는 해당 글을 참고하길 바란다.
https://sims-solve.tistory.com/93

[ML] Extra Tree (Extremely Randomized Trees)- 정리

 
iForest의 핵심은 '해당 데이터가 얼마나 일찍 분류되는가(혼자가 되는가)?' 이다.
즉, 특정 데이터를 몇번의 split만에 구분할 수 있는가? 이다.
왜 이러한 개념이 나왔는가 하면.. 이상치 일수록 무리(군집)에서 벗어난 데이터일 확률이 높다.
즉, normal한 데이터 분포에서 벗어나다보니, 일반적인 normal한 데이터보다 훨씬 적은 split으로 해당 데이터를 구분해 낼 수 있다는 아이디어다. ( normal한건 서로 근접해있기때문에, 해당 데이터를 고유하게 isolate하려면 많은 split이 필요함)
 
시각적으로 보면 단숨에 이해가 가능할 것이다. 밑의 이미지를 보자.

좌측은 normal한 데이터를 isolate 시켰다. 우측은 abnormal한 데이터를 isolate 시키는 경우다.
직관적으로 abnormal한 데이터는 무리(군집)에서 벗어나 있기 때문에, 상대적으로 적은 split을 통해 가려낼 수 있다.
 
이와같이 iForest는 split한 횟수를 가지고 anomaly_score을 구하여 abnormal 데이터를 판별한다.
 
그럼 이제 코드적으로 살펴보자.

해당 코드는 iForest의 init이며, 여기서 보면 base estimator가 ET(ExtraTreeRegressor)인점을 알 수 있다. 즉, base는 Extra Tree라는 것...
 
ET의 특징을 한번 다시 상기시켜보고 가자.
1. random feature select
2. random split
Extra Tree는 best split 구간을 찾는것이 아닌, 랜덤으로 feature를 선택하여 랜덤하게 구간도 split한다. iForest도 이 방식을 사용하여 진행한다.
 
다음 iForest의 특징으로는 sample수를 모두 사용하지 않는다는 점이다.
정확히 말하자면, 최대 256개의 sample수만 사용한다.
 

이처럼 코드에서 볼 수 있다. 왜 최대 샘플수를 최대 256개만 사용하는 것일까?
이유는 간단하다. 시간이 너무 오래걸리게 된다. iForest는 이름에서도 나타나 있듯, isolation, 데이터를 고립시켜 해당 데이터의 depth를 구하게된다. 즉, leaf노드에 해당하는 sample 수는 1이라는 소리다. 유일하게 구분될 때까지 진행을 해야한다.
그런데, 데이터 수가 많이지면 많아질수록.. depth는 높아져가고 연산량은 엄청나게 늘어난다.
이러한 이유로 최대 256개의 데이터만 사용한다. 여기서 기존 'Forest'의 장점이 다시한번 나타난다.
 
이러한 sampling은 약분류기를 만들 수 밖에없지만, 수많은 estimator를 통해 학습하여 하나의 결과값을 내보낸다면 파워풀한 분류기가 된다는 사실을 우리는 RandomForest를 사용하고 공부하며 경험하였다.
이와 마찬가지로, 256개의 데이터만 사용하더라도 다수의 estimator를 사용하여 최종결과를 도출할 것이기 때문에, 어느정도 모집단과 유사해질 것이다. (통계의 중심 극한의 법칙~?)
 
단, tree의 최대 depth는 조절하여 연산량을 줄인다고 한다.
 
그럼, 이제 iForest가 어떻게 Score을 연산하는지 살펴보자.

depths += ( np.ravel(node_indicator.sum(axis=1)) 
            + _average_path_length(n_samples_leaf)
            - 1.0 )

 

_average_path_length는 평균 depth 근사치를 알 수 있다. 위의 공식을 이용하여 구한다고 한다.
 
이렇게 n개의 ExtraTree에서 해당 데이터가 몇번의 split만에 구분할 수 있는지 누적합을 구한다.

그 후 위와같은 anomaly-score를 구하는 방식을 통해 각 데이터의 score을 구하게 된다.
 
그 후 score - offset 을 통하여 0보다 작으면 이상치라 판단한다.
(여기서 contamination이 auto면 -0.5 / 지정해 줬다면, 퍼센티지로 offset 결정)
 
Tree를 베이스로 두고있다보니 어렵지않게 해당 개념을 이해할 수 있다.
 
그런데, iForest의 문제점이 존재한다. 아래 이미지를 보자.

위 이미지 오른쪽 이미지는 Anomaly Score Map이다. 밝을수록 '정상' 이라는 뜻인데.. 어느정도는 잘 해주는 것 같다..? 라고 생각하기엔 뭔가 아쉽다. 12, 3 , 6 ,9 시 방향은 귀퉁이보다 Anomaly Score가 낮은 것(밝은 것)을 볼 수 있다.
다음 이미지를 보면 문제점이 뚜렷하게 보일것이다.

위 오른쪽 이미지를 보자. 그럼, 데이터가 존재하지 않는 공간인 1,3사분면에 Anomlay Score가 낮은 지점을 볼 수 있을것이다.
이는 Anomaly를 잘못 판단할 수 있는 구간이 될 수 있으므로 문제가 될 수 있다.
그럼 왜 이런 현상이 나타날까?
바로 Tree의 특성때문이다.
Tree의 특성은 바로 split !! 즉, 수직,수평으로 split을 진행한다는 문제점이 존재한다.

이처럼, 데이터가 존재하지 않는 곳(이상치)도 상당히 많은 선들이 지나가다 보니 자연스럽게 Anomaly Score가 낮아질 수 밖에 없는 것이다.
 
이러한 문제점을 해결하고자 나온 것이 Extended iForest이다.
 
Extened iForest는 iForest의 문제점인 수직,수평으로 분할하는 방식을 random slope(기울기)를 이용하여 해결한다.
 

즉, 위 사진에서 볼 수 있듯이 분기선이 수직,수평이 아닌 것을 볼 수 있다. 이러한 방식을 통해 위에 iForest에서 나타난 'Ghost Cluster' 를 방지 할 수 있다.

 

위 두가지를 살펴보면, 중간은 iforest, 오른쪽은 eif이다.
확실히 eif가 iforest에 비하면 실제로 데이터 분포에 따라 anomaly - score가 분포되어 있는 것을 볼 수 있다.
특히 두개의 집합이 존재하는 두번째 사진에서, Gost Cluster가 존재하지 않는 다는 점이 눈에 띈다.
 
이처럼, Extended iForest는 iforest의 단점인 Gost Cluster의 문제를 random slope를 이용하여 방지하였다.