When lookout sees crackle: Anomaly detection via kernel density estimation

1. 문제 정의 (Problem)

이상치 탐지는 신용카드 사기 탐지 등 다양한 분야에서 활용되지만, 기존 Lookout 알고리즘 (Kandanaarachchi & Hyndman, 2022) 은 몇 가지 이론적, 실용적 한계를 가지고 있었습니다.

• 대역폭 (Bandwidth) 선택의 일관성 부재: 기존 알고리즘은 Rips 지속 동형 (Persistent Homology) 의 '죽음 직경 (death diameters)' 중 가장 큰 간격의 하단 지점을 대역폭으로 사용했습니다. 이는 가우시안 분포에서는 작동할 수 있으나, 꼬리가 두꺼운 분포 (heavy-tailed distributions) 에서는 커널 밀도 추정기가 일관적 (consistent) 이라는 이론적 보장이 없었습니다.
• 민감한 스케일링: 기존 알고리즘의 최소 - 최대 (min-max) 스케일링은 이상치에 매우 민감하여 데이터의 왜곡을 초래할 수 있었습니다.
• 상관관계 무시: 대역폭 행렬이 대각 행렬로 가정되어 변수 간의 상관관계를 고려하지 못했습니다.
• GPD 피팅의 불안정성: 일반화 파레토 분포 (GPD) 의 모양 파라미터 (shape parameter, $\xi$) 에 대한 제약이 부족하여 피팅의 안정성이 떨어질 수 있었습니다.

2. 방법론 (Methodology)

저자들은 이상치 탐지를 위해 **커널 밀도 추정 (KDE)**과 **극값 이론 (Extreme Value Theory, EVT)**을 결합한 새로운 Lookout 알고리즘을 제안합니다. 주요 개선 사항은 다음과 같습니다.

A. 이론적 기반: 대역폭 선택과 일관성

• 크랙클 (Crackle) 개념 도입: Adler et al. (2014) 의 'crackle' 개념을 활용하여, 노이즈가 포함된 데이터의 지속 동형 특성을 분석했습니다.
• 양분수 (Quantile) 기반 대역폭: 기존에 사용하던 '최대 간격의 하단 지점' 대신, Rips 죽음 직경의 **상위 양분수 (upper quantile, $d_{\gamma(n-1)}$)**를 대역폭으로 선택합니다.
  • 이론적 증명: 가우시안 분포뿐만 아니라 꼬리가 두꺼운 분포 (Fat-tailed distributions) 에서도 $d_{\gamma(n-1)}$가 0 으로 수렴하며, $n(d_{\gamma(n-1)})^{m/2} \to \infty$를 만족함을 증명했습니다. 이는 커널 밀도 추정기가 **일관적 (consistent)**임을 보장합니다.
  • 기존 선택 ($d^*$) 은 두꺼운 꼬리 분포에서 일관성이 보장되지 않을 수 있음을 반례를 통해 보였습니다.

B. 수정된 Lookout 알고리즘 (Lookout v2) 의 3 가지 핵심 개선

1. 강건한 표준화 (Robust Standardization):
   • 기존 min-max 스케일링 대신 직교화된 Gnanadesikan-Kettenring 추정기를 사용하여 공분산 행렬을 추정합니다.
   • 데이터를 회전 및 스케일링하여 공분산 행렬이 단위 행렬에 가깝도록 만듭니다. 이는 이상치에 강건하며, 변수 간 상관관계를 제거하여 KDE 의 효율성을 높입니다.
2. 대역폭 행렬 선택:
   • Rips 죽음 직경의 $\gamma$-양분수 (예: 0.98) 를 대역폭 $H = d_{\gamma(n-1)}I_m$으로 사용합니다. 이는 이상치가 Rips 다이어그램의 최대 간격에 영향을 미치는 문제를 방지하고 일관성을 보장합니다.
3. GPD 피팅 제약:
   • 커널 밀도 추정값은 유한한 상한을 가지므로, 극값의 극한 분포는 Weibull 분포 ($\xi < 0$) 에 해당합니다.
   • 따라서 GPD 피팅 시 모양 파라미터 ($\xi$) 를 음수 (또는 0) 로 제한하여 피팅의 안정성을 높입니다.

C. 알고리즘 흐름

1. 데이터의 강건한 표준화 수행.
2. 표준화된 데이터에 대한 0 차 Rips 지속 동형 바코드 계산.
3. 죽음 직경의 상위 양분수 ($d_{\gamma(n-1)}$) 를 대역폭으로 설정하여 KDE 수행.
4. leave-one-out KDE 값을 구하고, 이를 음의 로그 변환 (Surprisal) 하여 극값 분포 (GPD) 에 피팅.
5. 피팅된 분포를 통해 각 관측치의 이상 확률 ($p_i$) 을 계산하고, 임계값 ($\alpha$) 보다 작으면 이상치로 판정.

3. 주요 기여 (Key Contributions)

• 이론적 엄밀성: Rips 죽음 직경 기반 대역폭 선택이 다양한 분포 (가우시안 및 두꺼운 꼬리 분포) 에서 커널 밀도 추정기의 일관성을 보장함을 수학적으로 증명했습니다.
• 강건한 알고리즘 설계: 이상치에 민감한 스케일링 방식을 대체하고, GPD 피팅의 안정성을 높이는 제약을 도입하여 알고리즘의 전반적인 신뢰성을 높였습니다.
• 성능 향상: 다양한 시뮬레이션 및 실제 데이터셋에서 기존 Lookout 및 다른 이상치 탐지 방법 (HDoutliers, Stray, KDEOS, RDOS 등) 보다 우수한 성능을 입증했습니다.

4. 실험 결과 (Results)

저자는 7 가지 실험을 통해 알고리즘을 평가했습니다.

• 시뮬레이션 실험:
  • 감도 분석: 이상치가 비정상 분포에서 멀어질수록 (Experiment 1, 2), 새로운 Lookout 은 기존 버전보다 일관되게 더 높은 True Positive Rate 를 보였습니다. 특히 Gamma 분포에서 이상치와 정상치의 구분이 모호할 때 성능 차이가 두드러졌습니다.
  • 샘플 크기 영향: 데이터 크기가 증가할 때 (Experiment 3, 4), 새로운 Lookout 은 더 낮은 False Negative Rate 를 유지하며 성능이 향상되었습니다.
  • 다변량 및 고차원: 6 차원, 20 차원 데이터 (Experiment 5, 6, 7) 에서도 새로운 Lookout 은 F-measure 와 G-mean 측면에서 기존 버전 및 다른 경쟁 알고리즘 (HDoutliers, Stray 등) 보다 우수하거나 동등한 성능을 보였습니다. 특히 고차원 데이터에서 이상치가 단일 차원이나 2 차원 평면에서는 구별되지 않을 때 (Experiment 7), 새로운 Lookout 이 효과적으로 탐지했습니다.
• 실제 데이터 적용:
  • Old Faithful (간헐천) 데이터: 새로운 Lookout 은 밀도가 낮은 영역의 이상치를 더 잘 식별하고, 기존 버전이 잘못 탐지했던 주요 군집 근처의 점들을 정상으로 분류했습니다.
  • Wine Reviews (와인 리뷰) 데이터: 새로운 Lookout 은 기존 버전이 과도하게 탐지했던 극단값이나 주요 군집 내 점들을 정상으로 분류하여, 훨씬 더 정교한 이상치 탐지를 보여주었습니다.

5. 의의 및 결론 (Significance and Conclusion)

• 이론과 실전의 결합: 지속 동형 (Topological Data Analysis) 과 극값 이론을 결합하여, 단순한 경험적 알고리즘을 넘어 이론적 보장을 갖춘 이상치 탐지 프레임워크를 제시했습니다.
• 범용성: 연속적인 다변량 데이터에 적용 가능하며, 이미지나 함수형 데이터와 같이 특징 추출을 통해 다변량 문제로 변환 가능한 문제에도 적용 가능합니다.
• 한계 및 향후 과제: 계산 복잡도가 $O(n \log n)$으로, 매우 큰 데이터셋에서는 계산 비용이 높을 수 있습니다. 또한, 차원의 저주로 인해 매우 고차원 데이터에서는 차원 축소 기법 (PCA, dobin 등) 과의 결합이 필요합니다.

결론적으로, 이 논문은 Lookout 알고리즘을 이론적으로 정립하고, 대역폭 선택과 스케일링 방식을 개선함으로써 이상치 탐지의 정확성과 강건성을 크게 향상시킨 중요한 연구입니다. 업데이트된 알고리즘은 lookout R 패키지를 통해 공개되어 있습니다.