순차 예외 기법(Sequential Exception Technique)이란?
순차 예외 기법은 인간이 겉보기에 유사한 객체들의 나열 속에서 비정상적인 집합을 직관적으로 구별해 내는 과정을 모방한 이상치(outlier) 탐지 기법입니다. 이 기법은 데이터에 내재된 암묵적 중복성을 활용하여 전체 데이터 집합에서 벗어나는 객체들, 즉 예외 집합을 효과적으로 찾아냅니다.
기본 원리
n개의 객체로 구성된 데이터 집합 D가 주어지면, 이 기법은 2 ≤ m ≤ n 조건을 만족하는 부분 집합들의 수열 {D₁, D₂, ..., Dₘ}을 구성합니다. 이때 각 부분 집합은 다음과 같은 포함 관계를 가집니다.
Dj−1 ⊂ Dj, 단 Dj ⊆ D
즉, 부분 집합들은 점차 커지면서 최종적으로 전체 데이터 집합에 도달하는 구조를 이룹니다. 이후 수열에 포함된 부분 집합들 사이의 상이도(dissimilarity)를 평가하여 예외 여부를 판단하게 되며, 이 과정에서 다음과 같은 핵심 용어들이 사용됩니다.
핵심 구성 요소
1. 예외 집합(Exception Set)
편차나 이상치에 해당하는 객체들의 집합입니다. 이 집합을 제거했을 때 나머지 집합의 상이도가 가장 크게 감소하는, 가장 작은 크기의 부분 집합으로 정의됩니다.
2. 상이도 함수(Dissimilarity Function)
객체 간의 거리 측도(metric distance)를 반드시 필요로 하지 않는 함수입니다. 객체들이 서로 유사하면 낮은 값을 반환하고, 객체 간 차이가 클수록 더 높은 값을 반환합니다.
부분 집합의 상이도는 수열에서 바로 앞에 위치한 부분 집합을 기준으로 점진적으로 계산됩니다. n개의 숫자로 이루어진 부분 집합 {x₁, ..., xₙ}이 주어졌을 때, 대표적인 상이도 함수로는 집합 내 숫자들의 분산을 들 수 있습니다.
(1/n) Σi=1n (xi − x′)²
여기서 x′는 집합에 포함된 n개 숫자의 평균값입니다. 문자열 데이터의 경우에는 지금까지 관찰된 모든 패턴을 포괄할 수 있는 패턴 문자열(예: 와일드카드 문자 포함)의 형태로 상이도 함수를 설계할 수 있습니다. Dj−1의 문자열들을 커버하던 패턴이 Dj−1에는 없는 Dj의 새로운 문자열을 커버하지 못하게 되면 상이도는 증가합니다.
3. 기수 함수(Cardinality Function)
주어진 집합에 포함된 객체의 개수를 세는 함수로, 일반적으로 집합의 크기를 나타냅니다.
4. 스무딩 계수(Smoothing Factor)
수열의 각 부분 집합마다 계산되는 값으로, 전체 객체 집합에서 해당 부분 집합을 제거했을 때 상이도가 얼마나 감소하는지를 평가합니다. 이 값은 집합의 기수(cardinality)로 나누어 정규화됩니다. 스무딩 계수가 가장 크게 나타나는 부분 집합이 곧 예외 집합이 됩니다.
계산 복잡도와 알고리즘의 동작 방식
예외 집합을 찾는 문제는 이론적으로 NP-난해(NP-hard), 즉 다루기 힘든(intractable) 문제가 될 수 있습니다. 그러나 순차적 방법은 계산적으로 실현 가능하며, 선형 시간 알고리즘으로 실행할 수 있다는 강력한 장점을 가집니다.
알고리즘은 현재 부분 집합과 그 여집합(complement set) 사이의 상이도를 직접 평가하는 대신, 분석 대상인 원래 집합으로부터 일련의 부분 집합들을 선택합니다. 그런 다음 각 부분 집합에 대해 수열에서 바로 앞의 부분 집합과 비교하여 상이도의 차이를 산출합니다. 이러한 상이도 차이를 통해 어떤 부분 집합이 전체 집합과 가장 크게 다른지를 파악할 수 있으며, 그 결과가 곧 예외 집합으로 식별됩니다.