Anomaly Detection

[데이터분석]/Python | AI | 머신러닝

Anomaly Detection

dowon 2024. 9. 17. 14:28

3-Sigma Rule & Box Plot

이상치 Outlier → Data Noise (O)

: 관측된 데이터의 범위에서 많이 벗어난 아주 작은 값이나 큰 값

: 분석하고자 하는 데이터에서 적은 확률로 나타나는 데이터

: 분석 결과 해석 시 오해를 발생시킬 수 있기 때문에 사전 제거 필요

: 분석 Domain에 따라 다르지만 대부분 분석 대상이 아님

이상 (Abnormal) → Data Noixe (X)

: 문제 해결의 관점으로 바라볼 수 있음

: 현업의 Domain의 관점에서 보았을 때, 문제 발생 가능성이 높은 데이터

: 정상적인 범주의 데이터라도 이상으로 정의할 수 있음

: 일반적으로 자주 발생하지 않는 패턴이 이상일 확률이 높음

: 따라서 데이터에 대해 Thread Hold가 존재함

Anomaly Detection

이상이라고 정의한 사건 및 패턴을 탐지하는 분야

eg 기업에서 이상 탐지를 하는 목적

1) [제조] 심각한 고장 발생 전 이상 탐지를 통해 효율에 대해 심각한 Risk 사전 방지

2) [금융] 비정상적 거래 및 사기 거래 방지를 통해 소비자 사후 보호 실행

3) [게임] 버그 유저 및 비정상 유저 탐지를 통해 게임 정상 운영

Data 유형에 따른 이상 탐지의 종류

1. Point Anomaly Detection

축적된 시간 동안 정적인 점 분포에 초점

특정 Point의 이상치를 감지

일반적으로 말하는 Data 내 Outlier

2. Contextual Anomaly Detection

시계열과 같은 동적인 특성에 초점 (※ 과거에 데이터가 현재의 값에 영향을 미칠 때, Sequential)

연속적인 변화 패턴을 읽어 이상치 감지, 맥락을 고려해서 예상 변화와 동떨어진 결과를 탐지함

민감하면 정상상황에서도 이상탐지가 되고, 둔감하게 만들면 비정상 상황에서 이상 탐지를 놓칠 수 있음

3. Collective Anomaly Detection

Contextual Anomaly Detection과 다르게 Global한 상황에서 변칙적인 이상치가 아닌 Local 한 이상치

개별 데이터가 아닌 집합 데이터 비교를 통해 이상을 확인함

4. Online Anomaly Detection

실시간 데이터 수집 체계가 구축되어 있는 환경에서 탐지

실시간은 몇 분 혹은 몇 초 마다 데이터가 수집되어야 실시간으로 볼 수 있는가? → Domain에 따라 다름

실시간 데이터를 어떻게 빠르게 처리하고 이상을 탐지할 지 설계하는 것이 매우 중요함

5. Distributed Anomaly Detection

관측치의 정상 분포에서 벗어나는 이상 데이터를 탐지

Anomaly Detection 종류 - Label

현재 보유하고 있는 데이터의 성격에 따라 이상 탐지의 종류 및 해결 방법론이 결정

1) Supervised Anomaly Detection

-모든 관측치에 대해서 이상 (abnormal) 과 정상 (normal) 라벨이 붙어있는 경우, 자주 발생하지 않는 이벤트인 이상 (abnormal)에 대해서 정의할 수 있는 상황이며, 충분히 학습할 만한 이상(abnormal) 데이터가 확보되어 있는 상황

-일반적인 이진분류 (Binary Classification) 문제로 해결할 수 있음

(※이상 abnormal의 종류가 다양하다면 Multi-Classification 문제로 해결)

-이상 abnormal 데이터 확보가 가능하나 적은 수의 데이터가 존재할 확률이 있으므로, 소수 클래스 문제, 불균형 문제를 해결해야 하는 상황을 고려할 수 있음

-성능 평가 시 ACC (Accuracy) 관점이 아닌, Recall 관점에서의 성능평가도 고려해야 함. 이상(abnormal) 데이터가 매우 적기 때문에 ACC는 높게 산출될 가능성이 큼

장점: 양/불 판정 정확도가 높다

단점: Class-Imbalance 문제

2) Semi-Supervised Anomaly Detection

-이상(abnormal)에 대한 라벨이 없으며, 정상(normal) 데이터만 보유하고 있는 상황, 충분히 학습할 만한 이상(abnomal) 데이터가 없을 시 정상 (normal) 데이터만을 사용하여 이상 (abnormal)을 탐지

-정상(normal) 데이터의 패턴을 학습하여 이상(abnormal) 데이터가 들어올 시 정상(normal) 데이터와 차이점을 파악하여, 이상(abnormal) 데이터를 탐지

-정상 데이터를 둘러싸고 있는 discriminative boundary(구분선)를 설정하고, 이 boundary를 최대한 좁혀 밖에 있는 데이터들을 이상(abnormal)로 간주한느 것

-대표적인 방법으로는 One-Class SVM이 존재

장점: 연구가 활발하게 이뤄지고 있고, 정상(normal) 데이터만 있어도 학습이 가능

단점: Supervised Anomaly Detection 방법론 대비 양/불 판정 정확도가 떨어짐

3) Unsupervised Anomaly Detection

-정상(normal)과 이상(abnormal)에 대한 라벨이 모두 존재하지 않는 경우

-모든 데이터를 활용하여 학습

-일반적으로 딥러닝 알고리즘을 사용하여 정상 패턴을 학습하고, 학습된 모델을 통해 이상(abnormal) 데이터를 탐지함

장점: 라벨링 과정이 필요 없음

단점: 양/불 판정 정확도가 높지 않고 hyper parameter에 매우 민감함

3-Sigma Rule

SPC (Statistical Process Control, 통계적 공정 관리), 경험적 규칙 (Empirical Rule)

표준편차의 3배인 3-Sigma (σ)의 범위가 전체 Data의 99.73%를 포함

Data 전체의 산포를 파악하는 개념으로 많이 활용됨

UCL (Upper Control Limit) / LCL (Lower Control Limit)

6σ 수준: 불량률 & 불량 개수 0.00036% & 100만개 중 3.4개

3σ 수준: 불량률 & 불량 개수 6.7% & 100만개 중 66,807개

장점	단점
매우 구현하기 쉬움	정규분포가 가정되어야 함, 분포에 따라 σ의 크기 수준이 달라짐
명확한 기준을 설정할 수 있기 때문에 방법론에 재학습이 필요 없음	다차원 데이터에 적용하기 어려움
	단변량 데이터에 적용할 수 있으며, Feature간 상호관계를 파악하기 어려움

Box Plot

많은 데이터를 눈으로 확인하기 어려울 때 그림을 이용해 데이터 집합의 범위와 중앙 값을 빠르게 확인할 수 있음

데이터가 많은 경우 분포를 그리기 매우 힘들 수 있기 때문

Box plot은 최소 정상 값 (min), 1사분위수 (Q1), 중앙값, 3사분위수(Q3), 최대 정상 값(max)를 나타내는 시각화 방법

장점	단점
데이터를 눈으로 확인하기 어려울 때, 그림을 이용해 데이터의 범위를 빠르게 파악	위치정보에 기반하고 있기 때문에 분포를 확인하기는 어려움
통계적으로 이상치 Outlier가 있는지 확인 가능	가운데 선은 평균이 아니다. 오해의 소지가 있음
다양한 정보를 손쉽게 파악할 수 있음

LOF

Local Outlier Factor

대부분의 이상치 탐지 알고리즘은 전체 데이터와 비교하여 각각의 관측치가 이상인지 정상인지 판단함

아래 그림의 경우 O2에 대해 이상치로 판단하지 않음

C1은 밀도가 낮은 그룹, C2는 밀도가 높은 그룹

O1, O2는 이상치

C2와 O2 사이의 거리는 C1그룹 내 관측치 간의 거리와 유사하기 때문에 전체적인 데이터 관점에서 보면 O2는 이상치로 보기 어려움

- the distance between objects p and q : d(p,q) 관측치 p와 q의 거리

- k-distance of an object p: k-distance(p) 관측치 p와 k번째로 가까운 이웃의 거리

- k-distance neighborhood of an object p: Nk(p) 관측치 p의 k-distance(p)보다 가까운 이웃의 집합, 관측치 p를 중심으로 k-distance로 원을 그릴 때 원 안에 있는 point 수

- Reachbility distance of an object p w.r.t object o

B는 3-distance와 같으니 A와 B의 Distance는 똑같음

C는 3-distance보다 작으니 3-distance 값으로 함

D는 3-distance보다 크니 A와 D의 Distance 값으로 함

- Local reachability density of an object p

관측치 p에 대한 k-이웃의 RD(p,o) 평균의 역수

관측치 p 주변에 이웃이 얼마나 밀도 있게 있는가를 대변하는 값

- Local outlier factor (LOF) of an object p

관측치 p의 이상치 정도를 나타내는 LOF는 p의 밀도와 이웃 o의 밀도의 비율을 평균한 것

p의 밀도가 작을 수록, o보다 클수록 LOF 값은 커지며, 이상치라고 판단할 수 있음

LOF < 1: 밀도가 높은 분포

LOF = 1: 이웃 관측치와 비슷한 분포

LOF > 1: 밀도가 낮은 분포, 크면 클수록 이상치 확률이 높음

Isolation Forest

기본적으로 의사결정나무 (Decision Tree) 형태로 표현해 정상 값을 분리하기 위해서는 의사결정나무를 깊숙하게 타고 내려 가야 하고, 반대로 이상치인 경우 의사결정나무 상단부에서 분리할 수 있다는 것을 이용한 기법

Random Forest처럼 Decision Tree를 앙상블 하듯, Isolation Forest도 마찬가지로 Decision Tree를 앙상블함

Sub-sampling: 비복원 추출하여 Tree에 들어갈 Dataset을 준비함

Random Forest의 경우 복원 추출을 함 (약 37% 데이터가 뽑히지 않기 때문에 Data Noise에 강건해질 수 있음)

Feature Randomly Selection: 변수를 랜덤하게 선택함

Split point 설정

: 선택된 변수들의 값을 랜덤하게 분기하기 위해 해당 변수의 최소/최대 값 사이에 정의된 Uniform 분포에서 샘플링 진행

: 사용하는 데이터의 크기 만큼 나무의 최대 깊이가 log2(n) 만큼 정해지므로 (데이터가 256개라면 최대 깊이 7)

: 최대 깊이에 도달할 때까지 지속적으로 Split 진행 (모든 데이터 고립 → Fully overfitting)

각 데이터 마다의 Scoring 계산

Robust Random Cut Forest - Made by AMAZON

Isolation Forest와 거의 차이가 없음

실시간 환경에서 분석이 가능하게 했음

사소한 부분만을 바꾸어 (Feature Randomly Selection과 Score 계산) 크게 개선함

IF: 왼쪽

RRCF: 오른쪽 (이상치가 시작되는 점부터 Score가 뜀)

Isolation Forest 가정은 이상치는 수가 적으며, 정상 데이터와는 다른 Feature 값을 갖음

Robust Random Cut Forest 가정은 이상치는 학습하는 Model의 복잡성을 증가시킴: 다른 데이터들의 Depth가 증가할 것임

Robust Random Cut Forest에서 그림의 Data[x]를 제거하면 subtree c 안에 있는 노드들의 depth가 모두 1씩 감소함

한편 subtree b의 depth는 바뀌지 않음. 즉 [x[를 제거하면 subtree c에 있는 data들의 depth가 1씩 감소

따라서 [x]의 자매 조드에 있는 data 개수가 depth 변화의 총합이 됨

[x] data가 추가 될 경우, 어떤 data들은 path length가 증가함: 이것을 Score로 사용 → Displacement (Disp)

Disp Score의 경우 masking 문제에 취약함

이상 Data끼리 서로 뭉쳐 있으면 그 이상 데이터를 제거하더라도 Disp는 1정도 밖에 되지 않을 것

따라서 colluder(공모자)들까지 고려하는 이상스코어 Collusive Displacement (CoDisp) 제안

[x]의 공모자들의 집합을 C라고 가정 (C는 우리가 알 수 없는 것이고, x를 포함하는 가능한 모든 부분 집합을 고려함)

: CoDisp 값이 크면 클수록 이상치로 간주함

**Robust Random Cut Forest (RRCF)**는 주로 **이상치 탐지(anomaly detection)**를 위한 **앙상블 알고리즘**입니다. RRCF는 Amazon에서 개발한 알고리즘으로, 고차원 데이터에서 이상치를 효율적으로 탐지하기 위해 설계되었습니다. RRCF는 랜덤하게 데이터를 분할하여 이상치와 정상 데이터를 구분하며, 특히 **스트리밍 데이터**나 **대규모 데이터**에서 이상치를 탐지하는 데 매우 유용합니다.

이 알고리즘은 일반적인 **Random Forest**와 유사하지만, **데이터 분할(cutting)** 방식을 다르게 사용하여 **이상치** 탐지에 특화된 구조로 만들어졌습니다. 기본적으로 **데이터의 밀도**나 **분포**에 기반해 이상치와 정상 데이터를 구분하며, **고차원**에서도 잘 동작하는 특성이 있습니다.

### RRCF의 주요 개념:

#### 1. **랜덤 컷(RC, Random Cut)**:
- RRCF에서 **랜덤 컷**은 랜덤한 방식으로 데이터 공간을 나누는 과정입니다. 각 데이터 포인트를 포함하는 **최소 경계 상자(bounding box)**를 만들고, 이 상자 내부에서 무작위로 차원을 선택한 후, 그 차원 내에서 **임의의 위치**에서 데이터 공간을 나눕니다.
- 이렇게 만들어진 **랜덤 컷 트리(Random Cut Tree)**는 데이터가 어떻게 분포되어 있는지 반영하며, 이상치 탐지에 활용됩니다.

#### 2. **랜덤 컷 트리(Random Cut Tree)**:
- RRCF는 여러 개의 랜덤 컷 트리를 구성합니다. 이 트리는 데이터 포인트들을 랜덤하게 분할한 후, 이를 **트리 구조**로 표현합니다.
- 데이터 포인트들이 트리의 어느 위치에 놓이는지, 그리고 그들이 분할된 방법을 통해 **이상치 점수**를 계산할 수 있습니다. **깊이(depth)**가 깊을수록 포인트가 일반적이지 않으며, 이는 이상치일 가능성이 높다는 의미입니다.

#### 3. **코덱스 점수 (CoDisplacement or CoDex Score)**:
- **코덱스 점수**는 RRCF에서 이상치 탐지를 위해 계산하는 점수입니다. 이 점수는 특정 포인트가 **트리에서 얼마나 쉽게 분리**되는지를 측정합니다.
- 랜덤 컷 트리에서, 어떤 데이터 포인트가 빠르게 분리되면 (즉, 트리의 상위 레벨에서 분리되면) 이는 해당 데이터가 다른 데이터와 **상대적으로 다르거나 이상치**일 가능성이 높다는 것을 의미합니다.
- 코덱스 점수는 여러 트리에서의 결과를 결합하여 계산되며, 이 값이 높을수록 이상치일 가능성이 큽니다.

#### 4. **스트리밍 데이터에서의 사용**:
- RRCF는 **스트리밍 데이터**에도 잘 맞는 알고리즘입니다. 이는 새로운 데이터 포인트가 들어왔을 때, 해당 포인트를 랜덤 컷 트리에 추가하고, 오래된 데이터를 제거하는 방식으로 트리를 계속 업데이트할 수 있기 때문입니다.
- 새로운 데이터가 지속적으로 유입되는 환경에서도, RRCF는 효율적으로 이상치 탐지를 수행할 수 있습니다.

### RRCF의 작동 원리:

1. **트리 생성**: RRCF는 랜덤하게 데이터를 분할하는 **랜덤 컷 트리**를 여러 개 생성합니다. 각 트리는 주어진 데이터 포인트들을 랜덤하게 분할하며, 분할된 데이터 포인트들을 트리 구조로 배치합니다.

2. **이상치 탐지**: 각 트리에서, 데이터 포인트가 어떻게 분리되는지에 따라 **이상치 점수**를 계산합니다. 트리의 상위 레벨에서 빠르게 분리되는 데이터는 **다른 포인트와 밀도가 다르거나 고립**되어 있다고 판단되어 이상치로 간주됩니다.

3. **앙상블 기법**: 여러 개의 랜덤 컷 트리에서 계산된 이상치 점수를 결합하여 최종적으로 특정 데이터 포인트가 이상치일 가능성을 평가합니다. 앙상블을 통해 단일 트리에서 발생할 수 있는 오류를 줄이고, 더욱 정확하게 이상치를 탐지할 수 있습니다.

### RRCF의 장점:

1. **비모수적(non-parametric)**:
   - RRCF는 데이터의 분포에 대해 가정하지 않기 때문에, **비모수적** 방식으로 이상치를 탐지할 수 있습니다. 즉, 데이터가 어떤 분포를 따르지 않아도 잘 작동합니다.

2. **고차원 데이터 처리**:
   - RRCF는 고차원 데이터에서 이상치를 탐지하는 데 매우 적합합니다. 다른 방법들이 고차원에서 성능이 떨어질 수 있지만, RRCF는 공간을 랜덤하게 분할함으로써 고차원에서도 이상치 탐지가 가능합니다.

3. **스트리밍 데이터에 적합**:
   - RRCF는 **스트리밍 데이터**에서 잘 동작합니다. 새로운 데이터가 들어올 때마다 트리를 업데이트하고, 오래된 데이터를 제거하는 방식으로 실시간으로 이상치를 탐지할 수 있습니다.

4. **잡음에 강함**:
   - RRCF는 여러 트리를 사용한 앙상블 기법을 사용하기 때문에, 일부 노이즈가 존재하는 데이터에서도 상대적으로 안정적인 이상치 탐지가 가능합니다.

### RRCF의 단점:

1. **해석의 어려움**:
   - RRCF는 랜덤한 분할을 기반으로 작동하므로, 특정 이상치 점수가 왜 그렇게 계산되었는지에 대한 **해석이 어려울 수** 있습니다.

2. **매개변수 설정 필요**:
   - RRCF에서는 몇 가지 매개변수(예: 트리의 개수, 최대 깊이 등)를 설정해야 하며, 이 설정에 따라 성능이 달라질 수 있습니다.

### RRCF의 활용 예시:

1. **이상 거래 탐지**: 금융 분야에서 RRCF는 신용카드 거래나 금융 기록에서 **이상 거래**를 탐지하는 데 사용할 수 있습니다. 정상적인 패턴을 따르지 않는 거래를 이상치로 탐지합니다.
2. **기계 상태 모니터링**: 제조업에서 기계의 센서 데이터를 스트리밍 방식으로 모니터링하며, 비정상적인 상태 변화를 이상치로 감지하여 기계 고장을 사전에 예측할 수 있습니다.
3. **네트워크 이상 탐지**: 네트워크 트래픽 데이터를 분석하여, 정상적이지 않은 데이터 흐름을 이상치로 탐지하여 잠재적인 보안 위협을 파악하는 데 사용할 수 있습니다.

### 정리:

**Robust Random Cut Forest (RRCF)**는 **이상치 탐지**에 특화된 알고리즘으로, 고차원 데이터와 스트리밍 데이터에서 매우 효과적입니다. 랜덤하게 공간을 분할하고 트리 구조를 형성한 뒤, 이상치 점수를 계산하여 데이터를 평가합니다. RRCF는 다양한 환경에서 실시간으로 이상치를 탐지할 수 있으며, 데이터의 분포를 가정하지 않아 매우 유연하게 적용될 수 있는 알고리즘입니다.