728x90
- Introduction
- 기존 이상치 탐지 모델의 한계
- 노말 인스턴스 프로파일을 먼저 만든 후에 그를 기준으로 이상치 여부를 탐지하기 때문에 많은 연산량
- 일단 노말 인스턴스 프로파일을 제대로 구축하는 것이 목표이기 때문에 이상치 탐지에 최적화된 알고리즘이 아님 (cause too many false alarms)
- low dimension, small data size에 한함.
- Isolation Forest
- 트리모델의 분기법에 착안
- 이상치는 루트 노드에 가까운 지점에서 일찍이 분기된다는 특징 활용
- subsampling을 활용해 데이터셋을 여러 개로 분리하고, 각 데이터셋별로 트리를 만들어 평균적인 depth가 짧은 관측치를 이상치로 정의
- high dimension, big data size에도 적용 가능
- linear time complexity, low memory requirement
- 기존 이상치 탐지 모델의 한계
- Isolation and Isolation Trees
- 트리모델에서 이상치는 고립(분기 완료시점)까지의 path length가 정상 데이터에 비해 짧다.
- 트리의 개수가 증가함에 따라 평균적인 path length가 수렴하는데, 수렴하기까지 필요한 트리 개수가 적음 (효율적 알고리즘)
- path length; h(x) - x가 한 번 순회하기까지 거친 노드 수
- anomaly score; s(x,n) - n개로 분할된 데이터셋에서 h(x)의 평균
- anomaly score가 1에 가까울 수록 이상치라고 볼 수 있다.
- 윤곽 그림 첨부
- 여러 윤곽을 보고 적절한 threshold를 설정 가능
- Characteristics of Isolation Trees
- 기존 이상치 탐지 알고리즘의 한계 극복
- Swamping: 정상 인스턴스를 이상치로 잘못 분류
- Masking: 이상치가 한 곳에 너무 많이 모여있어 구분이 어려움
- 위 문제들은 sample size가 커서 발생하나, 기존 이상치 탐지 알고리즘은 정상 인스턴스로 프로파일을 구축했기 때문에 이를 한계로 가지고 있었음.
- iTree는 모든 데이터를 한꺼번에 활용하지 않고 sub-sampling을 활용해 인스턴스를 분산시키기 때문에 swamping & masking 문제가 완화됨
- i.e. 성능비교표
entire sample sub-sample AUC 0.67 0.91
- 기존 이상치 탐지 알고리즘의 한계 극복
- Anomaly Detection Using iForest
- training stage
- terms
- ψ : sub-sampling size
- t : number of trees
- Algorithms
- iForest(X, t, ψ)
- output: a set of t iTrees
- ψ controls the training data size: when fulfilled the desired value, there is no need to increse ψ further.
- empirically ψ = 256 is generally used
- t controls ensemble size: usually converges before t = 100
- 시간복잡도 = O(tψlogψ)
- iTree(X, e, l)
- output: an iTree
- e : current tree height
- l : height limit
- iForest(X, t, ψ)
- terms
- evaluating stage
- in this stage, an anomaly score s is derived fromo the E(h(x)) for each test instance.
- iTree를 순회하는 동안의 path length
- s(x, ψ) 시간복잡도 = O(ntlogψ)
- training stage
- Empirical Evaluation (4 experiments (a) - (d))
-
- ORCA: KNN 기반 최신 이상치 탐지 기법 (거리 계산에 많은 리소스 필요한 KNN 알고리즘을 pruning해 시간복잡도를 리니어 타임 수준으로 낮춘 알고리즘)
- LOF: 밀도 기반 알고리즘
- RF: 트리 앙상블 기법이라는 공통점
- 성능비교표 - iForest outperformsComparison with ORCA, LOF, and RF
- Efficiency analysis (Examine the impact on the different sub-sampling size)
- adjusted ψ = 2, 4, 8, 16, …, 32768
- a small ψ provides high AUC and low processing time, and a further increase of ψ is not necessary.
- High dimensional data handling
- Curse of demension: need more data to use the distance-based method with high demension.
- Added 506 irrelevant attributes → good performance yet best at the original number of attributes
- Training using only normal instances
- AUC decreases
- Using a larger sub-sampling size can help to restore the detection performance
-
- Discussion
- small sub-sample size → available with online anomaly detection system with minimal memory footprint
728x90
'99_DS' 카테고리의 다른 글
[paper review] MLOps: Overview, Definition, and Architecture (6) | 2025.05.25 |
---|---|
전이학습과 파인튜닝 (4) | 2025.05.24 |
[paper review] Attention Is All You Need (2017) (1) | 2025.05.18 |
[딥러닝] 경사하강법의 응용 (0) | 2025.05.08 |
[딥러닝] 역전파 (1) | 2025.05.08 |