[paper review] Isolation Forest (2009)

1. Introduction
   1. 기존 이상치 탐지 모델의 한계
      1. 노말 인스턴스 프로파일을 먼저 만든 후에 그를 기준으로 이상치 여부를 탐지하기 때문에 많은 연산량
      2. 일단 노말 인스턴스 프로파일을 제대로 구축하는 것이 목표이기 때문에 이상치 탐지에 최적화된 알고리즘이 아님 (cause too many false alarms)
      3. low dimension, small data size에 한함.
   2. Isolation Forest
      1. 트리모델의 분기법에 착안
      2. 이상치는 루트 노드에 가까운 지점에서 일찍이 분기된다는 특징 활용
      3. subsampling을 활용해 데이터셋을 여러 개로 분리하고, 각 데이터셋별로 트리를 만들어 평균적인 depth가 짧은 관측치를 이상치로 정의
      4. high dimension, big data size에도 적용 가능
      5. linear time complexity, low memory requirement
2. Isolation and Isolation Trees
   1. 트리모델에서 이상치는 고립(분기 완료시점)까지의 path length가 정상 데이터에 비해 짧다.
   2. 트리의 개수가 증가함에 따라 평균적인 path length가 수렴하는데, 수렴하기까지 필요한 트리 개수가 적음 (효율적 알고리즘)
   3. path length; h(x) - x가 한 번 순회하기까지 거친 노드 수
   4. anomaly score; s(x,n) - n개로 분할된 데이터셋에서 h(x)의 평균
   5. anomaly score가 1에 가까울 수록 이상치라고 볼 수 있다.
   6. 윤곽 그림 첨부
      1. 여러 윤곽을 보고 적절한 threshold를 설정 가능
3. Characteristics of Isolation Trees
   1. 기존 이상치 탐지 알고리즘의 한계 극복
      1. Swamping: 정상 인스턴스를 이상치로 잘못 분류
      2. Masking: 이상치가 한 곳에 너무 많이 모여있어 구분이 어려움
      3. 위 문제들은 sample size가 커서 발생하나, 기존 이상치 탐지 알고리즘은 정상 인스턴스로 프로파일을 구축했기 때문에 이를 한계로 가지고 있었음.
      4. iTree는 모든 데이터를 한꺼번에 활용하지 않고 sub-sampling을 활용해 인스턴스를 분산시키기 때문에 swamping & masking 문제가 완화됨
      5. i.e. 성능비교표
      
      

      	entire sample	sub-sample
      AUC	0.67	0.91

4. Anomaly Detection Using iForest
   1. training stage
      1. terms
         1. ψ : sub-sampling size
         2. t : number of trees
      2. Algorithms
         1. iForest(X, t, ψ)
            1. output: a set of t iTrees
            2. ψ controls the training data size: when fulfilled the desired value, there is no need to increse ψ further.
            3. empirically ψ = 256 is generally used
            4. t controls ensemble size: usually converges before t = 100
            5. 시간복잡도 = O(tψlogψ)
         2. iTree(X, e, l)
            1. output: an iTree
            2. e : current tree height
            3. l : height limit
   2. evaluating stage
      1. in this stage, an anomaly score s is derived fromo the E(h(x)) for each test instance.
      2. iTree를 순회하는 동안의 path length
      3. s(x, ψ) 시간복잡도 = O(ntlogψ)
5. Empirical Evaluation (4 experiments (a) - (d))
   1. 1. ORCA: KNN 기반 최신 이상치 탐지 기법 (거리 계산에 많은 리소스 필요한 KNN 알고리즘을 pruning해 시간복잡도를 리니어 타임 수준으로 낮춘 알고리즘)
      2. LOF: 밀도 기반 알고리즘
      3. RF: 트리 앙상블 기법이라는 공통점
      4. 성능비교표 - iForest outperformsComparison with ORCA, LOF, and RF
      
      
   2. Efficiency analysis (Examine the impact on the different sub-sampling size)
      1. adjusted ψ = 2, 4, 8, 16, …, 32768
      2. a small ψ provides high AUC and low processing time, and a further increase of ψ is not necessary.
   3. High dimensional data handling
      1. Curse of demension: need more data to use the distance-based method with high demension.
      2. Added 506 irrelevant attributes → good performance yet best at the original number of attributes
   4. Training using only normal instances
      1. AUC decreases
      2. Using a larger sub-sampling size can help to restore the detection performance
6. Discussion
   1. small sub-sample size → available with online anomaly detection system with minimal memory footprint