기술 요약: 비지도 이상치 감지를 위한 무작위 PCA 포레스트

문제 정의

이상치 감지는 데이터 마이닝 및 머신러닝의 근본적인 과제로, 침입 탐지, 고장 진단, 사기 탐지 등의 응용 분야에서 중요합니다. 새로운 알고리즘이 급증했음에도 불구하고, 포괄적인 평가에 따르면 K-최근접 이웃 (KNN) 및 로컬 이상치 인자 (LOF) 와 같은 고전적인 방법들이 여전히 최첨단 (state-of-the-art) 수준을 유지하고 있습니다. 이러한 방법들은 정상 데이터와 이상 데이터 간의 불명확한 경계와 노이즈 존재와 같은 문제를 효과적으로 해결하지만, 정확한 최근접 이웃 탐색이 필요하기 때문에 높은 계산 복잡성에 시달립니다. Isolation Forest(iForest) 와 같은 트리 기반 방법은 효율성을 제공하지만, 무작위 특징 선택에 의존하여 고차원 데이터의 근본적인 구조를 항상 효과적으로 포착하지는 못합니다. 따라서 차원 축소를 활용하면서도 전역 및 국부 이상치 모두를 감지하는 능력을 희생하지 않으면서 계산 효율성과 견고성 사이의 균형을 잡는 방법이 필요합니다.

방법론

저자들은 무작위 주성분 분석 (RPCA) 포레스트를 기반으로 한 새로운 비지도 이상치 감지 방법을 제안합니다. 이 접근법은 원래 근사 K-최근접 이웃 (KNN) 탐색을 위해 설계된 RPCA 포레스트를 포레스트의 고유한 속성에서 특정 이상치 점수를 유도함으로써 이상치 감지에 적용합니다.

핵심 구성 요소

1. RPCA 포레스트 구축:

   • 이 방법은 트리의 앙상블을 구축합니다. 무작위로 특징을 선택하는 iForest 와 달리, RPCA 포레스트는 각 노드에서 무작위 PCA(Halko et al., 2011) 를 활용합니다.
   • 루트 및 후속 노드에서 데이터 포인트는 소수의 주성분 ($p$) 을 사용하여 저차원 부분 공간으로 투영됩니다. 이는 차원을 축소하면서도 원래 특징 공간의 정보 가치를 보존합니다.
   • 분할 기준: 무작위 절단 대신, 알고리즘은 평균을 중심으로 한 라플라스 분포에서 각 주성분에 대한 분할 점을 샘플링합니다. 데이터 포인트는 $p$개 성분 전체의 다수결에 따라 왼쪽 또는 오른쪽 자식 노드에 할당됩니다.
   • 정지 기준: 트리 성장은 리프 노드에 포함된 포인트 수가 사전 정의된 이웃 크기 ($k$) 이하가 될 때까지 계속됩니다.

2. 이상치 점수 공식화:
   제안된 방법은 쿼리 포인트 $q$에 대해 두 가지 다른 기준을 결합하여 이상치 점수 ($RPCAForestScore$) 를 정의합니다.

   • 깊이 기반 이상성 ($P(q)$): 이상치는 종종 트리에서 더 일찍 (더 얕은 깊이로) 격리된다는 관찰에 기반합니다. 이는 포레스트 전체에 걸쳐 $q$를 포함하는 리프 노드의 정규화된 역깊이로 계산됩니다.
   • 거리 기반 이상성 ($\mu_{dist}(q)$): 원래 특징 공간에서 동일한 리프 노드 내의 모든 다른 포인트와 쿼리 포인트 $q$ 사이의 유클리드 거리의 평균으로 계산됩니다.
   • 최종 점수: 최종 점수는 이 두 구성 요소의 곱입니다:
     $$RPCAForestScore(q) = P(q) \times \mu_{dist}(q)$$
     이 결합은 투영으로 인해 리프에 정상 포인트와 함께 그룹화되더라도, 원래 공간의 클러스터 중심으로부터의 큰 거리가 높은 이상 점수를 초래하도록 보장합니다.

3. 분류:
   오염도 매개변수 ($\alpha$) 를 사용하여 이상치 임계값이 결정되며, 이는 예상되는 이상치의 백분율을 나타냅니다. 점수 분포의 $(1-\alpha)$-분위수를 초과하는 점수는 이상치로 레이블링됩니다.

주요 기여

• 혁신적인 통합: 이 논문은 근사 최근접 이웃 탐색과 이상치 감지 간의 간극을 연결하며, RPCA 포레스트를 비지도 이상치 감지에 최초로 적용했습니다.
• 하이브리드 점수 메커니즘: 구조적 격리 깊이 (iForest 와 유사) 와 원래 특징 공간의 국부 밀도/거리 (KNN/LOF 와 유사) 를 모두 활용하는 복합 이상치 점수를 제안하여, 단일 지표만 사용하는 것의 한계를 극복하고자 합니다.
• 무작위 PCA 를 통한 효율성: 무작위 SVD 를 채용함으로써, 복잡성이 전체 데이터 차원성이 아닌 주성분 수에 의존하므로 특히 고차원 데이터에서 높은 계산 효율성을 달성합니다.
• 견고성: 이 방법은 트리 수, 주성분 수 ($p$), 그리고 리프 크기 ($k$) 선택만 요구하며, 하이퍼파라미터 튜닝에 대해 견고하도록 설계되었습니다.

실험 결과

저자들은 KNN, KNNW, LOF, SLOF, ODIN, DAO, iForest 를 포함한 고전적이고 최첨단인 방법들과 비교하여 표준 벤치마크 저장소의 22 개의 다양한 데이터셋에서 이 방법을 평가했습니다. 성능은 수신자 운영 특성 곡선 아래 면적 (AUC) 을 사용하여 측정되었습니다.

• 성능: RPCA 포레스트는 많은 데이터셋에서 최상이거나 두 번째로 좋은 성능을 보였으며, 다른 데이터셋에서도 경쟁력을 유지했습니다. 무작위 특징 선택을 사용하는 iForest 가 어려움을 겪었던 고차원 데이터셋에서 특히 강력한 성능을 보였습니다.
• 견고성: 이 방법은 주성분 수에 대한 두 가지 설정 ($p=1$ 및 $p=5$) 만 사용하여 경쟁적인 성능을 유지한 반면, 경쟁 방법들은 100 가지 다른 하이퍼파라미터 구성으로 테스트되었습니다. 이는 제안된 방법이 하이퍼파라미터 튜닝에 덜 민감함을 시사합니다.
• 절단 연구 (Ablation Study): 깊이 기반 구성 요소와 거리 기반 구성 요소를 분리한 실험 결과, 결합된 점수가 깊이 기반 구성 요소보다 훨씬 우수했으며, 일반적으로 거리 기반 구성 요소 단독과 경쟁하거나 더 우세한 것으로 나타났습니다.
• 효율성: iForest 가 여전히 가장 빠른 방법이었지만, RPCA 포레스트는 데이터셋 크기가 증가함에 따라 KNN 기반 방법보다 훨씬 더 나은 확장성을 보여주었으며 빅데이터에 적합한 효율적인 실행 시간을 유지했습니다.
• 관찰된 한계: 이 방법은 특정 데이터셋 (예: ALOI, InternetAds, Annthyroid, Wilt) 에서 낮은 성능을 보였습니다. 저자들은 이를 다음과 같이 귀인합니다:
  • 소수의 주성분 ($p=1, 5$) 이 이상치를 격리하기에 충분하지 않은 고차원성 (InternetAds).
  • 이상치가 정상 포인트와 매우 유사하여 선택된 $p$가 제공할 수 있는 것보다 더 많은 정보를 필요로 함 (Annthyroid, Wilt).
  • 특정 특징 추출이 있는 데이터셋의 국부 대 전역 이상치의 성격 (ALOI) 으로, 국부 구조 방법 (LOF) 이 전역 투영 접근법보다 우세한 경우.

중요성 및 주장

이 논문은 RPCA 포레스트가 비지도 이상치 감지를 위한 견고하고 계산적으로 효율적인 대안을 제공한다고 주장합니다. 그 중요성은 다음과 같은 능력에 있습니다:

1. 효율성과 정확성의 균형: 검색을 블랙박스로 취급하는 대신 (PCA 투영을 통한) 트리의 내부 구조를 활용하는 "화이트박스" 접근 방식을 통해 근사 이웃 탐색을 제공합니다.
2. 우수한 일반화: 이 방법은 광범위한 데이터셋에서 포괄적인 하이퍼파라미터 최적화 없이도 경쟁력 있는 성능을 발휘하며, 많은 새로운 방법들이 특정 문제 인스턴스에서만 우수하다는 문제를 해결합니다.
3. 전역 및 국부 이상치 모두 감지: 이론적으로 이 방법은 트리에서의 초기 격리를 통해 전역 이상치를 그리고 더 깊은 노드에서의 거리 지표를 통해 국부 이상치를 감지하도록 설계되었으나, 저자들은 군집형 이상치에 대한 한계를 인정합니다.

저자들은 이 방법이 모든 이상치 유형 (특히 군집형 이상치) 에 대한 만능 해결책은 아니지만, 트리 기반 방법의 계산 속도와 거리 기반 방법의 정확성 사이의 유리한 균형을 제공하여 범용 이상치 감지에 대한 강력한 선택지라고 결론지었습니다.