거리 기반 이상값(DB Outlier)의 정의
데이터 집합 S에 속한 객체 o가 매개변수 p와 d를 갖는 거리 기반(distance-based, DB) 이상값, 즉 DB(p, d)가 되려면, S 내 객체들 중 최소 비율 p만큼의 객체들이 o로부터 거리 d보다 먼 위치에 있어야 합니다.
다시 말해, 통계적 검정에 의존하는 대신 충분한 이웃을 확보하지 못한 객체를 이상값으로 간주하는 방식입니다. 여기서 이웃(neighbors)은 해당 객체로부터의 거리를 기준으로 정의됩니다.
통계 기반 방법과의 관계
통계 기반 방법과 비교했을 때, 거리 기반 이상값 탐지는 표준 분포에 대한 비일관성 검정(discordancy test)의 핵심 아이디어를 일반화하고 통합합니다. 이러한 특성 때문에 거리 기반 이상값은 통합 이상값(unified outlier), 즉 UO-이상값이라고도 불립니다.
또한 거리 기반 접근법은 관측된 분포를 특정 표준 분포에 맞추고 비일관성 검정을 선택하는 과정에서 발생할 수 있는 과도한 계산 부담을 줄여줍니다. 실제로 일부 비일관성 검정에서는, 객체 o가 주어진 검정 기준에 따라 이상값이라면 적절히 설정된 p와 d에 대해 o 역시 DB(p, d) 이상값임을 증명할 수 있습니다.
예를 들어, 정규 분포를 가정할 때 평균으로부터 3표준편차 이상 떨어진 객체를 이상값으로 보는 규칙은 DB(0.9988, 0.13σ) 이상값의 형태로 '통합'될 수 있습니다.
거리 기반 이상값 탐지 알고리즘
거리 기반 이상값을 효율적으로 찾아내기 위해 여러 알고리즘이 개발되었으며, 대표적으로 다음 세 가지가 있습니다.
1. 인덱스 기반 알고리즘(Index-based Algorithm)
주어진 데이터 집합에 대해 R-트리나 k-d 트리와 같은 다차원 인덱싱 구조를 활용하여 각 객체 o 주변 반경 d 이내의 이웃을 검색합니다. M을 이상값의 d-이웃 내 최대 객체 수라고 할 때, 객체 o의 이웃이 M+1개 발견되는 순간 o는 이상값이 아니라고 판단할 수 있습니다.
이 알고리즘의 최악의 경우 시간 복잡도는 O(k × n²)입니다. 여기서 k는 차원 수, n은 데이터 집합의 객체 수를 의미합니다.
2. 중첩 루프 알고리즘(Nested-loop Algorithm)
중첩 루프 알고리즘은 인덱스 기반 알고리즘과 동일한 계산 복잡도를 가지지만, 인덱스 구조를 별도로 구축하지 않고 I/O 횟수를 최소화하는 데 초점을 둡니다. 메모리 버퍼 영역을 두 부분으로 나누고, 데이터를 여러 개의 논리 블록으로 구성하여 처리합니다.
3. 셀 기반 알고리즘(Cell-based Algorithm)
O(n²)의 계산 복잡도를 회피하기 위해 메모리 상주(memory-resident) 데이터 집합을 대상으로 개발된 알고리즘입니다. 시간 복잡도는 O(cᵏ + n)이며, 여기서 c는 셀 개수에 기반한 상수, k는 차원 수입니다.
이 방법에서는 데이터 공간을 한 변의 길이가 d/√k인 셀(cell)로 분할하며, 각 셀은 두 개의 층(layer)으로 둘러싸입니다.
- 첫 번째 층: 두께가 1개 셀
- 두 번째 층: 두께가 √k개 셀(가장 가까운 정수로 올림)
이 알고리즘은 객체 하나씩이 아닌 셀 단위로 이상값을 계산합니다. 주어진 셀에 대해 다음 세 가지 카운트를 누적합니다.
- 해당 셀 내부의 객체 수
- 해당 셀과 첫 번째 층을 합친 객체 수
- 해당 셀과 두 층 전체를 합친 객체 수
이러한 셀 단위 집계 방식을 통해 전체 데이터 공간을 스캔하는 비용을 크게 줄일 수 있어, 대규모 데이터 집합에서도 효율적인 이상값 탐지가 가능합니다.