HIF(Hybrid Isolation Forest)
Motivation(TL;DR)
요즘 데이터에서 Feature Extraction을(Dimension Reduction)한 후, Clustering하는 일을 하고 있다. 아직 데이터의 물리적인 특성을 완벽하게 이해하지 못해서 그 원인이 무엇인지는 모르겠지만, abnormal하게 보이는 데이터들이 가끔씩 눈에 띈다.
당연하게도, 이런 outlier들이 clustering의 결과를 심각하게 왜곡시킬 수 있는 가능성이 있어서 제거를 해야 되는데...... 학부때 배운 알고리즘은 너무 Naive한 것들인 것 같아 여러가지 outlier detection 방법론을 공부하는 중이다.
내가 분석하고 있는 데이터는 Non-Gaussian, High Dimensional, Assumed to be Multi-class Data이다. 이 데이터에 Model-based Outlier Detection 방법론을 적용한 알고리즘을 썼더니 결과가 썩 마음에 들지 않아 대안을 찾아다니다가 IF를 발견하게 되었는데, 꽤나 괜찮은 결과를 얻었다. 공부도 할겸, 인터넷을 돌아다니다가 논문말고는 적당한 글이 없어서 공부 겸해서 나름대로 다른 알고리즘과의 분석도 곁들여봤다.
IF(Isolation Forest)
* 논문에서는 'anomalies'를 썼지만, 더 범용적으로 쓰이는 'outlier'를 쓰도록 하겠다.
IF는 꽤나(...) 최근인 2008년에 제안되었다. 현재 널리 쓰이고 있는 model based outlier detection에서는 normal sample에 대한 모델을 만들고(profiling), 그에 따라 분류를 한다. IF에서는 기존과는 다른 방법으로 outlier를 찾는데, outlier를 말 그대로 "isolation" 시키는 방법이다. 논문[Ref 1] 에서는 outlier가 "few and different"한 특성을 지닌 것이라고 가정하고, 데이터를 random 하게 재귀적으로 partitioning하는 tree structure를 이용하여 "few and different"한 outlier를 효과적으로 찾아내어 isolate 할 수 있음을 보이고 있다. fewness는 outlier의 수가 '굉장히' 적을 것이라는 가정이고 따라서 작은 수의 partition만으로도 isolation될 것이라고 생각할 수 있다. 그리고 differentness는 outlier의 feature값이 normal sample과 '확연히' 차이날 것이라는 가정인데, 따라서 partition 과정이 일찍 끝날 것이라고 생각할 수 있다.
그렇다면 어떻게 outlier들을 normal sample들로부터 효과적으로 "isolation"시킬 수 있을까? 논문에 소개된 아이디어와 pseudo-code는 굉장히 간단하다. Decision Tree와 ensemble류 알고리즘에 대해서 공부해 본 사람이라면 아마 단번에 이해할 수 있을 것이다.
IF Algorithm
IF는 ITree(Isolation Tree)의 집합으로 구성되며, 각 ITree는 proper binary tree, 즉 자식이 없거나 두개여야만 한다(이 조건은 알고리즘 3번 때문에 자동적으로 충족된다......). ITree를 만드는 알고리즘은 다음과 같다.
IF를 실전에 적용하기 전에 먼저 Naive한 데이터에 적용해보자. 일단 scikit-learn의 well-made plot을 가져와 봤다(http://bit.ly/1F9l8vs). Multivariate Gaussian distributed 데이터에서 IF와 RC(Robust covariance)가 One-Class SVM보다는 Out-perform한 결과를 보인다.
그렇다면, Non-Gaussian에서도 비슷할까? Fig.2에서 볼 수 있듯이, Multivariate Non-Gaussian distributed 데이터에서는 Isolation Forest가 다른 두 알고리즘에 비해서 훨씬 월등한 성능을 보였다. 어떻게 보면, Multi-cluster 형태의 데이터에서 잘 동작한다고 생각해도 되겠다. 물론, 이 예제들(Fig.1, Fig. 2)은 굉장히 한정적인 상황에서, 일부의 알고리즘만을 가지고 비교한 것이기 때문에 실전에 바로 적용하기에는 문제가 있다.
예를 들어, Feature의 갯수가 조금만 더 늘어나도, IF를 비롯한 대부분의 Outlier detection algorithm들은 Poor한 성능을 보인다. 왜 그런지는 'Concentration of Distances' Theorem 을 참고하면 되겠다. Curse of Dimensionality가
이를 단순히 실험적으로
(1)
(2) Isolation Forest Implementation(python, parallelized) : http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html
HIF(Hybrid Isolation Forest)
Implementation(python, not paralleized) : https://github.com/pfmarteau/HIF
2017/7/29, 현재 적당한 Implementation이 딱 한개(...) 존재하는데 parallelized하지 않아서 구현중이다.
Reference
[1] Liu, Fei Tony, Ting, Kai Ming and Zhou, Zhi-Hua. “Isolation forest.” Data Mining, 2008. ICDM‘08. Eighth IEEE International Conference (https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf)
[2] Pierre-Françcois Marteau, Saeid Soheily-Khah, and Nicolas Béchet. 2017. Hybrid Isolation Forest - Application to Intrusion Detection.
(https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0ahUKEwjZpKHb-a3VAhVCkZQKHYkYCqAQFggqMAA&url=https%3A%2F%2Farxiv.org%2Fabs%2F1705.03800&usg=AFQjCNFryx8ZH4owQBU4s_DWjPzXN42_6w)
요즘 데이터에서 Feature Extraction을(Dimension Reduction)한 후, Clustering하는 일을 하고 있다. 아직 데이터의 물리적인 특성을 완벽하게 이해하지 못해서 그 원인이 무엇인지는 모르겠지만, abnormal하게 보이는 데이터들이 가끔씩 눈에 띈다.
당연하게도, 이런 outlier들이 clustering의 결과를 심각하게 왜곡시킬 수 있는 가능성이 있어서 제거를 해야 되는데...... 학부때 배운 알고리즘은 너무 Naive한 것들인 것 같아 여러가지 outlier detection 방법론을 공부하는 중이다.
내가 분석하고 있는 데이터는 Non-Gaussian, High Dimensional, Assumed to be Multi-class Data이다. 이 데이터에 Model-based Outlier Detection 방법론을 적용한 알고리즘을 썼더니 결과가 썩 마음에 들지 않아 대안을 찾아다니다가 IF를 발견하게 되었는데, 꽤나 괜찮은 결과를 얻었다. 공부도 할겸, 인터넷을 돌아다니다가 논문말고는 적당한 글이 없어서 공부 겸해서 나름대로 다른 알고리즘과의 분석도 곁들여봤다.
IF(Isolation Forest)
* 논문에서는 'anomalies'를 썼지만, 더 범용적으로 쓰이는 'outlier'를 쓰도록 하겠다.
IF는 꽤나(...) 최근인 2008년에 제안되었다. 현재 널리 쓰이고 있는 model based outlier detection에서는 normal sample에 대한 모델을 만들고(profiling), 그에 따라 분류를 한다. IF에서는 기존과는 다른 방법으로 outlier를 찾는데, outlier를 말 그대로 "isolation" 시키는 방법이다. 논문[Ref 1] 에서는 outlier가 "few and different"한 특성을 지닌 것이라고 가정하고, 데이터를 random 하게 재귀적으로 partitioning하는 tree structure를 이용하여 "few and different"한 outlier를 효과적으로 찾아내어 isolate 할 수 있음을 보이고 있다. fewness는 outlier의 수가 '굉장히' 적을 것이라는 가정이고 따라서 작은 수의 partition만으로도 isolation될 것이라고 생각할 수 있다. 그리고 differentness는 outlier의 feature값이 normal sample과 '확연히' 차이날 것이라는 가정인데, 따라서 partition 과정이 일찍 끝날 것이라고 생각할 수 있다.
그렇다면 어떻게 outlier들을 normal sample들로부터 효과적으로 "isolation"시킬 수 있을까? 논문에 소개된 아이디어와 pseudo-code는 굉장히 간단하다. Decision Tree와 ensemble류 알고리즘에 대해서 공부해 본 사람이라면 아마 단번에 이해할 수 있을 것이다.
IF Algorithm
IF는 ITree(Isolation Tree)의 집합으로 구성되며, 각 ITree는 proper binary tree, 즉 자식이 없거나 두개여야만 한다(이 조건은 알고리즘 3번 때문에 자동적으로 충족된다......). ITree를 만드는 알고리즘은 다음과 같다.
- Feature를 랜덤하게 선택한다.
- Feature value range중에서 split value를 랜덤하게 선택한다
- 선택된 Feature의 Split value로 현재 노드의 데이터를 양분하고, 현재 노드의 Left child, Right child에 추가한다.
- 만약 아래 조건을 만족하면 알고리즘을 끝내고, 그렇지 않으면 1번으로 돌아간다.
- Tree height limit(hyper parameter)에 도달했을 경우
- 현재 노드에 속한 데이터 갯수가 1개일 경우
IF를 실전에 적용하기 전에 먼저 Naive한 데이터에 적용해보자. 일단 scikit-learn의 well-made plot을 가져와 봤다(http://bit.ly/1F9l8vs). Multivariate Gaussian distributed 데이터에서 IF와 RC(Robust covariance)가 One-Class SVM보다는 Out-perform한 결과를 보인다.
[Figure 1] Outlier detection in Gaussian-distributed data
from scikit-learn
그렇다면, Non-Gaussian에서도 비슷할까? Fig.2에서 볼 수 있듯이, Multivariate Non-Gaussian distributed 데이터에서는 Isolation Forest가 다른 두 알고리즘에 비해서 훨씬 월등한 성능을 보였다. 어떻게 보면, Multi-cluster 형태의 데이터에서 잘 동작한다고 생각해도 되겠다. 물론, 이 예제들(Fig.1, Fig. 2)은 굉장히 한정적인 상황에서, 일부의 알고리즘만을 가지고 비교한 것이기 때문에 실전에 바로 적용하기에는 문제가 있다.
[Figure 2] Outlier detection in Non Gaussian-distributed data
from scikit-learn
예를 들어, Feature의 갯수가 조금만 더 늘어나도, IF를 비롯한 대부분의 Outlier detection algorithm들은 Poor한 성능을 보인다. 왜 그런지는 'Concentration of Distances' Theorem 을 참고하면 되겠다. Curse of Dimensionality가
이를 단순히 실험적으로
(2) Isolation Forest Implementation(python, parallelized) : http://scikit-learn.org/stable/modules/generated/sklearn.ensemble.IsolationForest.html
Implementation(python, not paralleized) : https://github.com/pfmarteau/HIF
2017/7/29, 현재 적당한 Implementation이 딱 한개(...) 존재하는데 parallelized하지 않아서 구현중이다.
Reference
[1] Liu, Fei Tony, Ting, Kai Ming and Zhou, Zhi-Hua. “Isolation forest.” Data Mining, 2008. ICDM‘08. Eighth IEEE International Conference (https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/icdm08b.pdf)
[2] Pierre-Françcois Marteau, Saeid Soheily-Khah, and Nicolas Béchet. 2017. Hybrid Isolation Forest - Application to Intrusion Detection.
(https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0ahUKEwjZpKHb-a3VAhVCkZQKHYkYCqAQFggqMAA&url=https%3A%2F%2Farxiv.org%2Fabs%2F1705.03800&usg=AFQjCNFryx8ZH4owQBU4s_DWjPzXN42_6w)
댓글
댓글 쓰기