STING(Statistical Information Grid)란?
STING은 Statistical Information Grid(통계 정보 그리드)의 약자로, 공간 데이터 마이닝에서 활용되는 그리드 기반 다중 해상도(multiresolution) 군집화 기법입니다. STING은 공간 영역을 사각형 셀(rectangular cell) 단위로 분할하며, 서로 다른 해상도에 해당하는 여러 종류의 셀이 계층 구조(hierarchical structure)를 이룹니다. 즉, 상위 레벨의 각 셀은 다음 하위 레벨의 여러 셀로 세분화되어 전체 공간을 피라미드 형태로 표현합니다.
사전 계산되는 통계 정보
각 그리드 셀 내부 속성에 대한 통계 데이터(평균, 최댓값, 최솟값 등)는 질의가 발생하기 전에 미리 계산되어 저장됩니다. 덕분에 상위 레벨 셀의 통계 파라미터는 하위 레벨 셀의 파라미터 값들만으로 손쉽게 도출할 수 있습니다.
셀에 저장되는 주요 파라미터는 다음과 같습니다.
- 속성 독립적 파라미터: count(객체 수)
- 속성 의존적 파라미터: mean(평균), stdev(표준편차), min(최솟값), max(최댓값)
- 분포 유형: normal(정규분포), uniform(균등분포), exponential(지수분포), none(분포를 알 수 없는 경우)
파라미터 계산 방식
레코드가 데이터베이스에 적재되는 시점에, 최하위 레벨 셀의 count, mean, stdev, min, max 값들은 레코드로부터 직접 계산됩니다. 분포 유형은 사용자가 사전에 알고 있는 경우 직접 지정할 수 있으며, 그렇지 않으면 카이제곱(χ2) 검정과 같은 가설 검정을 통해 추정합니다.
상위 레벨 셀의 분포 유형은 해당 셀에 포함된 하위 레벨 셀들의 분포 유형 대다수와 임계값 필터링(threshold filtering) 절차를 결합하여 평가합니다. 만약 하위 셀들의 분포가 서로 불일치하고 임계값 검정을 통과하지 못한다면, 상위 셀의 분포 유형은 'none'으로 설정됩니다.
그리드 기반 군집화의 특징
그리드 기반 군집화 기법은 다중 해상도 그리드 데이터 구조를 사용합니다. 객체 공간(object space)을 격자 구조를 이루는 여러 셀로 양자화(quantize)한 뒤, 이 구조 위에서 군집화 연산을 수행합니다. 이 방법의 핵심 장점은 빠른 처리 시간입니다. 처리 시간은 일반적으로 데이터 객체의 수와 무관하며, 양자화된 공간에서 각 차원별 셀의 개수에만 의존합니다.
그리드 기반 접근법의 대표적인 예는 다음과 같습니다.
- STING: 그리드 셀에 저장된 통계 정보를 탐색하여 군집화 수행
- WaveCluster: 웨이블릿 변환(wavelet transform)을 이용해 객체를 군집화
- CLIQUE: 고차원 데이터 공간에서 그리드 및 밀도 기반 군집화 방법을 정의
STING의 장점
- 질의 독립적(Query-independent): 통계 정보가 질의와 무관하게 미리 존재하므로 어떤 질의가 들어와도 즉시 활용 가능합니다.
- 범용적인 데이터 요약: 각 그리드 셀의 데이터에 대한 일반적인 설명을 제공하여 광범위한 클래스의 질의 응답을 지원합니다.
- 우수한 계산 효율: 계산 복잡도는 O(K)이며, 여기서 K는 최하위 레벨의 그리드 셀 개수입니다. 일반적으로 K << N(N은 객체의 총 개수)이므로 대용량 데이터에서도 매우 빠른 성능을 보입니다.