.png&blockId=04a8d577-ace8-4bac-bec8-3da8a3f63bbd)
@Hyun Ahn
이진 트리 구조를 기반으로 다차원/대규모 데이터에 대해 계산 효율적으로
이상 탐지를 수행하는 알고리즘
•
Random Forest와 유사하게 무작위적으로 생성한 이진 트리들을 종합하여 결과를 출력하는 앙상블 기법이다.
Isolation Forest 알고리즘의 동작 과정(Medium)
•
Isolation Forest를 구성하는 각각의 이진 트리는 Isolation Tree(iTree 라고 지칭)이며 정 이진 트리(full binary tree)의 속성을 가진다.
•
iTree 의 각 노드에서는 무작위적으로 속성(attribute)과 분할 값(split value)을 선택하여 하나의 인스턴스와 나머지 인스턴스 그룹으로 분할하는 기능을 가진다. 이 과정에서 분할된 하나의 인스턴스는 자식이 없는 externel node가 되며, 이를 “고립되었다(isolated)” 라고 정의한다. 알고리즘은 모든 인스턴스가 고립될 때까지 노드를 생성한다.
•
따라서, 직관적으로 특징 공간에서 다른 인스턴스들과 동떨어진 이상치(outlier)는 iTree에서 상대적으로 쉽게 고립되는 것으로 이해할 수 있다.
◦
즉, Root node에서 이상치에 해당되는 인스턴스가 고립된 Externel node까지의 경로 길이(path length)가 보통 인스턴스와 비교하여 짧은 경향을 보인다.
정형적 정의
참고문헌
•
(Liu 08) Isolation Forest, In ICDM
•
