격리림

이 기사의 주요 기고자는 그 주제와 밀접한 관련이 있는 것으로 보인다.Wikipedia의 콘텐츠 정책, 특히 중립적인 관점을 준수하기 위해 청소가 필요할 수 있습니다.토크 페이지에서 더 자세히 논의해 주세요. (2022년 7월)(이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

격리 포레스트는 이상 검출 알고리즘입니다.정상점을 모델링하는 대신 격리(데이터 지점이 나머지 데이터 지점까지 얼마나 떨어져 있는지)를 사용하여 이상을 감지합니다.2007년, Fei Tony Liu에 의해 박사학위 연구의 독창적인 아이디어 중 하나로 처음 개발되었습니다.이 연구의 중요성은 당시 대부분의 기존 이상 검출기를 뒷받침하는 주류 철학에서 벗어난다는 데 있다. 여기서 모든 정상 인스턴스는 이상이 정규 인스턴스의 분포에 부합하지 않는 인스턴스로 식별되기 전에 프로파일링된다.격리 포레스트는 바이너리 트리를 사용하여 이상 징후를 명시적으로 격리하는 다른 방법을 도입하여 모든 정상 인스턴스를 프로파일링하지 않고 이상 징후를 직접 대상으로 하는 보다 빠른 이상 검출기의 새로운 가능성을 보여준다.이 알고리즘은 낮은 상수와 낮은 메모리 요구 사항으로 선형 시간 복잡성을 가지며, 대용량 데이터에 ^[1][2]적합합니다.

분리 포레스트는 원점과 직교하는 선을 사용하여 데이터 공간을 분할하고 분리할 필요가 거의 없는 데이터 점에 더 높은 이상 점수를 할당합니다.그림 1에서 고립숲은 옐로스톤 국립공원의 Old Faile 간헐온천 분출 간격에 적용되었다.빨간색의 어두운 색조는 추정된 이상 점수가 더 높다는 것을 나타냅니다.

빅 데이터 집합의 이상 징후는 매우 복잡한 패턴을 따를 수 있으며, 이는 대부분의 경우 시각적으로 감지하기 어렵습니다.이것이 이상검출 분야가 기계학습기법의 적용에 적합한 이유이다.

이상검출에사용되는가장일반적인기법은정상적인프로파일의구성을기반으로합니다.^[2]이상검출은일반프로파일에준거하지않는데이터셋의인스턴스로보고됩니다.Isolation Forest는 다른 접근 방식을 사용합니다. 즉, 일반 인스턴스의 모델을 구축하는 대신 데이터 집합의 비정상적인 지점을 명시적으로 분리합니다.이 접근방식의 주요 장점은 프로파일 기반 메서드에 허용되지 않는 범위까지 샘플링 기술을 이용할 수 있다는 것입니다.이것에 의해, 메모리 요구가 ^[1][3][4]낮은 매우 고속의 알고리즘이 작성됩니다.

역사

Isolation Forest(iForest) 알고리즘은 ^[1]Fei Tony Liu, Kai Ming Ting 및 Zhi-Hua Zhou에 의해 2008년에 처음 제안되었습니다.저자들은 표본에서 비정상적인 데이터 포인트의 두 가지 정량적 특성을 이용했다.

1. 소수 - 적은 수의 인스턴스로 구성된 소수입니다.
2. Different - 일반 인스턴스와 매우 다른 속성 값을 가집니다.

이상 징후는 "소수 및 차이"이므로 일반 점에 비해 "분리"하기가 더 쉽습니다.Isolation Forest는 데이터 세트에 대해 "Isolation Tree"(iTree)의 앙상블을 구축하며, 이상 징후는 iTree의 평균 경로 길이가 짧은 지점입니다.

2010년에는 클러스터 이상 문제를 해결하고 랜덤 하이퍼플레인을 활용하여 축 병렬 이상 검출 알고리즘 능력을 향상시키기 위해 알고리즘 SCIForest의 확장판이 발행되었다.이러한 능력은 당초의 실장에서는 결여되어 있습니다.

2012년에^[2] 발행된 최신 논문에서 동일한 저자들은 iForest가 다음과 같은 것을 증명하는 일련의 실험에 대해 설명했습니다.

• 선형 시간 복잡도가 낮고 메모리 요건이 작습니다.
• 관련 없는 속성으로 고차원 데이터를 처리할 수 있습니다.
• 트레이닝 세트의 이상 유무에 관계없이 트레이닝할 수 있습니다.
• 재훈련 없이 다양한 수준의 정밀도로 검출 결과를 제공할 수 있다

2013년 Zhiguo Ding과 Minrui Fei는 스트리밍 ^[6]데이터의 이상 검출 문제를 해결하기 위해 iForest 기반의 프레임워크를 제안했습니다.스트리밍 데이터에 대한 iForest의 더 많은 적용은 ^[4]Tan 등, ^[7]Susto 등 및 Weng ^[8]등의 논문에 설명되어 있다.

이상 검출에 iForest를 적용하는 주요 문제 중 하나는 모델 자체의 문제가 아니라 "이상 점수"를 계산하는 방식에 있었다.이 문제는 2018년 ^[9]논문에서 강조되었으며, EIF(Extended Isolation Forest)라는 이름의 개선된 iForest 모델이 제안되었습니다.이 백서에서는 원래 모델 iForest에 대한 개선 사항과 특정 데이터 포인트에 대해 생성된 이상 점수의 일관성과 신뢰성을 어떻게 향상시킬 수 있는지에 대해 설명합니다.2010년 SCiForest에서 유사한 구조인 "랜덤 초평면"이 제안되었기 때문에 EIF에서 제안된 무작위 경사 강화가 새로운 것인지 확실하지 않다. 이는 iForest에서 동일한 축-평행 편향을 완화한다.

알고리즘.

Isolation Forest 알고리즘에 따르면 데이터 집합의 비정상적인 인스턴스는 일반 지점에 비해 샘플의 나머지 부분으로부터 분리(분리)하기 쉬운 경향이 있습니다.데이터 포인트를 분리하기 위해 알고리즘은 해당 속성에 허용되는 최소값과 최대값 사이에서 속성의 분할값을 랜덤으로 선택하고 해당 속성의 분할값을 랜덤하게 선택함으로써 샘플에 파티션을 재귀적으로 생성합니다.

정규 분포 지점의 2D 데이터 집합에서 랜덤 파티셔닝의 예는 그림 2에 나와 있으며, 그림 3에 이상일 가능성이 높은 점이 나와 있습니다.그림에서 이상 징후가 일반 지점에 비해 격리해야 하는 랜덤 파티션이 얼마나 적은지 알 수 있습니다.

수학적 관점에서 재귀 파티셔닝은 Isolation Tree라는 이름의 트리 구조로 나타낼 수 있지만, 점을 분리하는 데 필요한 파티션의 수는 루트로부터 종단 노드에 도달하는 경로의 길이로 해석할 수 있습니다.예를 들어 그림 2의 $포인트{\displaystyle {}_{}}$ $i$의 패스길이는 그림 ${\displaystyle 3_{}}$의$$x$j$의$패스길이$보다 크다$.$

${\displaystyle {}_{}}$ 더 형식적으로 X${\displaystyle }$= { ${\displaystyle {x\mathrm{}}_{}{1}_{}}$, ...${\displaystyle }$, x n $}$ { $displaystyle$ X $=$ \ { $x _$ {1} , \ $dots$, x _ { n$$} ${\displaystyle \}}$ ${\displaystyle \mathrm{x<img\; alt="\{\backslash displaystyle\; X=\backslash \{x\_\{1\},\backslash dots\; ,x\_\{n\}\backslash \}\}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/100345e63f9659382d5a93de3bb0f87719a4ab07"\; style="vertical-align:\; -0.838ex;\; width:17.514ex;\; height:2.843ex;">}}$ x x$$X { $displaystyle$ X' \ $subset$ X$\}$ an an $an{\displaystyle }$ an 。격리 트리(iolation Tree)는 구조 데이터에 따라 정의됩니다.

1. 트리의 각 $노드{\displaystyle }$T(\$displaystyle$ T$)$에 대해 T$(\displaystyle$ T$)$는 하위 노드가 없는 외부 노드이거나 "테스트"가 1개이고 도터 노드가 ${\displaystyle {정확히}_{}}$ 2개 있는 내부 노드(${\displaystyle {}_{}}$ ${\displaystyle l_{}}${$displaystyle T_{r$입니다.
2. $노드$$T$에서의 테스트는 $(\displaystyle$q)와$$ $분할값{\displaystyle }$p(\$displaystyle$ p$)$로 구성됩니다.이것에 의해 $(\displaystyle$q<$p})$는, $(\$$displaystyle$ $T_$${l$}) $또는$ T(\$displaystyle$ ${\displaystyle {T\_r}_{}}\})$에의 데이터 포인트의 통과를 결정합니다.

iTree를 구축하기 위해 알고리즘은 $속성q와$$$$분할값$$p$를 랜덤하게 선택함으로써$X$를 $재귀적$으로 분할합니다$.$

1. 노드에 인스턴스가 1개밖에 없습니다.
2. 노드의 모든 데이터는 동일한 값을 가집니다.

iTree가 완전히 성장하면 X$(\displaystyle$ X$)$의 각 포인트는 외부 노드 중 하나로 격리됩니다.직관적으로 비정상 포인트는 트리 내의 패스 길이가 작은 (따라서 분리하기 쉬운) ${\displaystyle {포인트x}_{}}$ i$X$의 패스 $길이h{\displaystyle }$ ${\displaystyle (}$ x i ) \ $displaystyle$ h ( $x$_ {$i$ )$$\ $displaystyle$ x$_$ { $i$}\ $in$X )는$$$$ 루트에서 노드까지 ${\displaystyle {통과}_{}}$하는 $엣지{\displaystyle {}_{}}$ x i ( ${\displaystyle x_{}}$ i ) \ $displaystyle$ x _ { i$$} \ displaystyle x_${i$}외부 노드

iTree에 대한 확률론적 설명은 iForest 원본 ^[1]문서에 나와 있습니다.

격리 포리스트 속성

• 서브샘플링: iForest는 모든 일반 인스턴스를 분리할 필요가 없기 때문에 트레이닝 샘플의 대부분을 무시할 수 있습니다.따라서 iForest는 샘플링 크기를 작게 유지하면 매우 잘 작동합니다. 이는 일반적으로 큰 샘플링 크기가 ^[1][2]바람직한 기존 방법의 대부분과 대조적인 특성입니다.
• 늪: 일반 인스턴스가 이상에 너무 가까우면 이상 현상을 분리하는 데 필요한 파티션 수가 증가합니다. 이 현상은 iForest가 이상과 정상 지점을 구별하는 것을 더 어렵게 만듭니다.습지의 주요 원인 중 하나는 이상 검출을 위해 너무 많은 데이터가 존재하기 때문에 문제에 대한 가능한 해결책 중 하나가 서브샘플링임을 의미합니다.iForest는 성능 측면에서 서브샘플링에 매우 잘 반응하기 때문에 샘플의 포인트 수를 줄이는 것도 ^[1]늪의 영향을 줄이는 좋은 방법입니다.
• 마스킹: 이상 징후 수가 많으면 일부 이상 징후가 고밀도 및 대규모 클러스터로 집계되어 단일 이상 징후를 구분하는 것이 더 어려워지고 이상 징후를 감지하는 것이 더 어려워질 수 있습니다.흡수와 마찬가지로 이 현상('마스킹'이라고 함)도 표본의 점 수가 클 때 더 가능성이 높으며 하위 표본을 통해 ^[1]완화될 수 있습니다.
• 고차원 데이터: 표준 거리 기반 방법의 주요 제한 중 하나는 고차원 데이터 세트를 처리하는 데 있어 비효율적이라는 것입니다.^[10]그 주된 이유는 고차원 공간에서는 모든 점이 똑같이 희박하기 때문에 거리 기반 분리 측정을 사용하는 것은 매우 효과적이지 않기 때문입니다.안타깝게도 고차원 데이터는 iForest의 검출 성능에도 영향을 미치지만 Kurtosis와 같은 특징 선택 테스트를 추가하여 샘플 공간의 ^[1][5]치수를 줄임으로써 성능을 크게 향상시킬 수 있다.
• 일반 인스턴스만: iForest는 트레이닝 세트에 비정상적인 ^[5]포인트가 포함되어 있지 않은 경우에도 양호한 성능을 발휘합니다.그 이유는 iForest는 패스 $길이h{\displaystyle }$ ${\displaystyle (}$ x${\displaystyle {}_{}}$i$$) \ $displaystyle$ h$(x_{i})$의 높은 값이 데이터 포인트의 존재에 대응하도록 데이터 분포를 기술하기 때문입니다.따라서 이상 유무는 iForest의 검출 퍼포먼스와는 무관합니다.

격리 포리스트에서의 이상 검출

Isolation Forest에서의 이상 검출은 다음 두 가지 주요 ^[5]단계로 구성됩니다.

1. 첫 번째 단계에서는 이전 섹션에서 설명한 대로 교육 데이터 세트를 사용하여 iTree를 구축합니다.
2. 두 번째 단계에서 테스트 세트의 각 인스턴스는 이전 단계에서 iTree 빌드를 통해 전달되며, 아래에 설명된 알고리즘을 사용하여 적절한 "이상 점수"가 인스턴스에 할당됩니다.

테스트 세트의 모든 인스턴스에 이상 점수가 할당되면 분석이 적용되는 도메인에 따라 점수가 미리 정의된 임계값보다 큰 모든 점을 "이상"으로 표시할 수 있습니다.

이상 점수

데이터 포인트의 이상 점수를 계산하는 알고리즘은 iTree 구조가 BST(Binary Search Tree)의 구조와 동등하다는 관찰에 기초하고 있습니다.즉, iTree의 외부 노드에 대한 끝은 BST에서 ^[5]실패한 검색에 해당합니다.그 결과 외부 노드 종료에 대한 $평균h{\displaystyle }$(${\displaystyle x}$ $)\displaystyle$ h$(x)$의 추정치는 BST에서 실패한 검색의 추정치와 동일합니다^[11].

${\displaystyle c(m)=begin{cases}2H(m-1)-{\frac {2(m-1)}{n}}&{\text{m}}m=2\0&{\text{cases}}}}$

$여기$서 n$${$displaystyle$ n$}$은 테스트 데이터 크기,$m{\displaystyle }$ {\$displaystyle$ m$}$은 샘플 세트의 크기,$H{\displaystyle }$ {\$displaystyle$ H$}$는 H${\displaystyle (i)}$ $= ln(i)$ + $（$ \$displaystyle$ H$(i$)+\$gamma$로 추정할 수 있습니다. 여기서 ${\displaystyle \mathrm{\gamma }}$ $= 0572156\displaystyle$아셰로니 상수

위의 c(m) 값은${\displaystyle }$m$${$displaystyle$ h$($$x)}$의 $평균$을 나타내므로 h($x)${$displaystyle$ h$(x)}$를 $정규화$하고 특정 인스턴스 x의 이상 점수를 추정할 수 있습니다.

${\displaystyle s(x,m)=2^{\frac {-E(h(x)}}}}}$

$여기$서${\displaystyle }$E ( ${\displaystyle h}$(${\displaystyle x}$) { $display style$E ($h$ ($x$ ) } is$$ 、 iTree 컬렉션의${\displaystyle }$h (${\displaystyle x}$) { $display style$h ($x$ ) }의 평균값입니다.특정 $인스턴스{\displaystyle }$x(\$displaystyle$ x$)$에 대해 다음과 같은 점에 유의하십시오.

• $s(\displaystyle$s$$$)$가 1(\$displaystyle$1)에 $가까울{\displaystyle }$ $경우{\displaystyle }$x(\$displaystyle$ x$)$는 매우 이상적입니다.
• $s(\displaystyle$s)가$$ ${\displaystyle 0}$.5$(\displaystyle$0.5$)$보다 작을 $경우{\displaystyle }$ x$(\displaystyle$ x$)$는 정상값이 될 수 있습니다.
• 주어진 샘플에 대해 모든 인스턴스에 약${\displaystyle 0}$.5$(\displaystyle$0.5$)$의 이상 점수가 할당되어 있는 경우 샘플에는 이상이 없다고 가정해도 무방합니다.

오픈 소스 구현

최초 구현:

• Isolation Forest는 R로 작성된 이진 트리를 사용하여 데이터 이상 징후를 감지하는 알고리즘입니다.이 신문의 첫 번째 작가인 류페이 토니에 의해 2009년에 발표되었습니다.

기타 구현(알파벳 순서):

• Isolation Forest - LinkedIn Anti-Ause AI 팀의 James Verbus가 만든 Spark/Scala 구현입니다.
• H2O-3에 의한 Isolation Forest - H2O-3에 의한 이상 검출을 위한 Isolation Forest 구현.
• Srikanth Komala Sheshachala에 의한 R에서의 패키지 고독 구현.
• skikit-learn의 예제를 사용한 Python 구현.
• Spark iForest - Apache Spark에서 실행되는 Scala 및 Python의 분산 구현입니다.팡저우 양 지음.

「 」를 참조해 주세요.

• 이상 검출
• 랜덤 포레스트

레퍼런스