그리드 기반 클러스터링 방법의 개념
그리드 기반(grid-based) 클러스터링 방법은 다중 해상도(multi-resolution) 그리드 데이터 구조를 활용합니다. 이 방법은 객체들이 존재하는 공간을 유한한 개수의 셀(cell)로 양자화하여 그리드 구조를 형성하고, 클러스터링에 필요한 모든 연산을 이 그리드 구조 위에서 수행합니다.
이 방식의 가장 큰 장점은 빠른 처리 속도입니다. 처리 시간은 일반적으로 데이터 객체의 수와 무관하며, 양자화된 공간에서 각 차원별 셀의 개수에만 의존하기 때문에 대용량 데이터에서도 효율적으로 동작합니다.
대표적인 그리드 기반 클러스터링 알고리즘
그리드 기반 접근법의 대표적인 예로는 다음 세 가지 알고리즘이 있습니다.
- STING: 그리드 셀에 저장된 통계 정보를 활용하여 클러스터링을 수행
- WaveCluster: 웨이블릿 변환(wavelet transform) 기법을 이용해 객체를 군집화
- CLIQUE: 고차원 데이터 공간에서 그리드와 밀도를 결합한 방식으로 클러스터링 수행
STING: 다중 해상도 그리드 클러스터링
STING은 그리드 기반의 다중 해상도(multiresolution) 클러스터링 기법으로, 공간 영역을 사각형 셀로 분할합니다. 일반적으로 여러 해상도 수준에 대응하는 여러 층위의 사각형 셀이 존재하며, 이 셀들은 계층 구조를 이룹니다. 즉, 상위 레벨의 각 셀은 더 낮은 레벨의 여러 셀로 분할됩니다.
각 그리드 셀 내 속성에 관한 통계 데이터(평균, 최댓값, 최솟값 등)는 미리 계산되어 저장되므로, 이후 질의 처리 시 빠른 응답이 가능합니다.
통계 파라미터의 구성
상위 레벨 셀의 통계 파라미터는 하위 레벨 셀들의 파라미터로부터 손쉽게 계산할 수 있습니다. 이러한 파라미터는 다음과 같습니다.
- 속성 독립적 파라미터: count(셀 내 객체 수)
- 속성 종속적 파라미터: mean(평균), stdev(표준편차), min(최솟값), max(최댓값)
- 분포 유형: 셀 내 속성 값이 따르는 분포로, 정규(normal), 균등(uniform), 지수(exponential) 분포 또는 none(분포를 특정할 수 없는 경우)
파라미터 계산 및 분포 판정
레코드가 데이터베이스에 적재될 때, 최하위 레벨 셀의 count, mean, stdev, min, max 파라미터는 레코드로부터 직접 계산됩니다. 분포 유형은 사용자가 사전에 알고 있는 경우 직접 지정할 수 있으며, 그렇지 않은 경우 카이제곱(χ2) 검정과 같은 가설 검정을 통해 도출할 수 있습니다.
상위 레벨 셀의 분포 유형은 해당하는 하위 레벨 셀들의 분포 유형에 대한 다수결 원칙에 따라 결정되며, 여기에 임계값 필터링 과정이 함께 적용됩니다. 만약 하위 셀들의 분포가 서로 불일치하고 임계값 검정을 통과하지 못한다면, 상위 셀의 분포 유형은 none으로 설정됩니다.
하향식(Top-Down) 질의 처리 과정
이렇게 구축된 통계 파라미터는 다음과 같이 하향식(top-down) 그리드 기반 접근 방식에서 활용됩니다.
먼저, 질의 응답 절차를 시작할 계층 구조 내의 레벨(layer)을 결정합니다. 이 레벨에는 일반적으로 소수의 셀만 포함되어 있어 초기 탐색 부담이 적습니다. 이후 현재 레벨의 각 셀에 대해, 해당 셀이 주어진 질의와 얼마나 관련이 있는지를 나타내는 신뢰 구간(confidence interval, 추정 확률 범위)을 계산합니다. 이 신뢰 구간을 바탕으로 관련성이 높은 셀만 선별하여 더 낮은 레벨로 내려가며 탐색을 좁혀 나가므로, 전체 데이터를 스캔하지 않고도 효율적인 질의 응답이 가능합니다.