Computer >> 컴퓨터 >  >> 프로그래밍 >> 프로그래밍

STING 그리드 기반 클러스터링이란? 개념과 알고리즘 총정리

그리드 기반 클러스터링(grid-based clustering)은 다중 해상도(multi-resolution) 그리드 데이터 구조를 활용하는 군집화 기법입니다. 이 방법은 데이터 객체들이 존재하는 공간 영역을 유한한 개수의 셀(cell)로 양자화하여 그리드 구조를 만들고, 클러스터링에 필요한 모든 연산을 이 그리드 위에서 수행합니다. 가장 큰 장점은 빠른 처리 속도로, 처리 시간은 일반적으로 데이터 객체의 수와 무관하며 양자화된 공간에서 각 차원별 셀 개수에만 좌우됩니다.

그리드 기반 클러스터링은 밀도가 높은(dense) 그리드 셀들을 결합하여 클러스터를 형성합니다. 대표적인 기법으로는 STING, WaveCluster, CLIQUE 등이 있습니다.

STING(Statistical Information Grid)의 개념

STING은 통계 정보 그리드(Statistical Information Grid) 접근 방식으로, 공간 영역을 사각형 셀로 분할합니다. 서로 다른 해상도에 대응하는 여러 계층(level)의 셀이 존재하며, 상위 계층의 각 셀은 하위 계층의 여러 개 작은 셀로 세분화됩니다. 각 셀의 통계 정보는 사전에 계산되어 저장되므로 질의(query)에 신속하게 응답할 수 있습니다.

상위 계층 셀의 통계값은 하위 계층 셀들의 통계값으로부터 간단히 도출할 수 있으며, 다음과 같은 정보가 포함됩니다.

  • count(객체 수), mean(평균), s(표준편차), min(최솟값), max(최댓값)
  • 분포 유형 — 정규분포(normal), 균등분포(uniform) 등

STING은 쿼드트리(quadtree)와 유사한 계층적(hierarchical) 접근 방식으로 공간 영역을 사각형 셀로 나눕니다. 공간 데이터베이스를 단 한 번 스캔하여 각 셀의 통계 파라미터를 결정하며, 전체 과정은 계층적 구조를 구축하는 것에서 시작됩니다. 이렇게 만들어진 트리는 영역을 사분면(quadrant) 단위로 재귀적으로 분할합니다.

공간상의 각 셀은 트리의 노드(node)에 해당하며, 속성에 독립적인 데이터(count)와 속성에 의존적인 데이터(평균, 표준편차, 최솟값, 최댓값, 분포 유형)를 함께 저장합니다. 트리의 노드 수는 데이터베이스의 항목 수보다 적기 때문에 STING BUILD의 시간 복잡도는 O(n)입니다.

STING BUILD 알고리즘

입력(Input)

D // 계층 구조에 배치할 데이터
k // 최하위 계층에서 원하는 셀의 개수

출력(Output)

T // 생성된 트리

알고리즘 동작 과정

// 1단계: 상향식(top-down)으로 빈 트리 생성
T = 초기화된 데이터 값을 가진 루트 노드;   // 처음에는 루트 노드만 존재
i = 1;
repeat
    for each node in level i do
        초기값을 가진 4개의 자식 노드 생성;
    i = i + 1;
until 4^i = k;

// 2단계: 하향식(bottom-up)으로 트리 값 채우기
for each item in D do
    데이터 D의 위치에 해당하는 리프 노드 j를 결정;
    항목의 속성값을 기반으로 j의 값 갱신;
i := log4(k);
repeat
    i := i - 1;
    for each node j in level i do
        4개 자식 노드의 속성값을 기반으로 j의 값 갱신;
until i = 1;