STING 그리드 기반 클러스터링이란?

그리드 기반 클러스터링 방법은 다중 해상도 그리드 데이터 구조를 사용합니다. 클러스터링을 위한 모든 작업이 구현되는 그리드 구조를 형성하는 한정된 수의 셀로 개체 영역을 양자화합니다. 이 방법의 이점은 일반적으로 데이터 개체 수와 무관하며 양자화된 공간의 각 차원에 있는 여러 셀에만 의존하는 빠른 처리 시간입니다.

그리드 기반 클러스터링은 다중 해상도 그리드 데이터 구조를 사용하고 조밀한 그리드 셀을 사용하여 클러스터를 형성합니다. STING, 웨이브 클러스터, CLIQUE 등의 흥미로운 방법이 있습니다.

스팅 − 통계 정보 그리드 접근 방식. 공간 영역은 직사각형 셀로 분할됩니다. 다양한 해결 방법에 해당하는 다양한 수준의 셀이 있습니다. 높은 수준의 각 셀은 다음 낮은 수준의 여러 작은 셀로 분리됩니다. 각 셀의 통계 데이터를 미리 계산하여 저장하고 쿼리에 응답할 수 있습니다. 상위 수준 셀의 사양은 하위 수준 셀의 사양에서 간단히 계산할 수 있습니다.

• 카운트, 평균, s, 최소, 최대
• 분포 유형-정규, 균일 등

STING(통계 정보 그리드 기반 접근)은 공간 영역을 쿼드트리와 유사한 직사각형 셀로 나누는 계층적 접근 방식을 따릅니다. 공간 데이터베이스를 한 번 스캔하고 각 셀에 대한 통계 매개변수를 결정합니다. STING 기법은 일종의 계층적 접근 방식으로 볼 수 있습니다. 첫 번째 단계는 계층적 설명을 만드는 것입니다. 생성된 트리는 영역을 개별적으로 사분면으로 나눕니다.

트리를 만드는 과정은 아래 주어진 알고리즘에 나와 있습니다. 공간의 각 셀은 트리의 노드에 해당하며 속성 독립(개수) 데이터와 속성 종속(평균, 표준 편차, 최소, 최대 분포) 데이터로 설명됩니다. 트리의 노드 수가 데이터베이스의 항목 수보다 적기 때문에 STING BUILD의 복잡도는 O(n)입니다.

알고리즘

입력

D // Data to be placed in the hierarchical structure
k // Number of desired cells at the lowest level

출력

T // Tree
STING BUILD algorithm
// Create an empty tree from top-down
   T = root node with data values initialized; // Initially only root node
   i = 1;
   repeat
      for each node in level i do
      create 4 children nodes with initial values;
   i = i +1;
   until 4i = k;
   // Populate tree from bottom-up for each item in D do
   determine leaf node j related to the position of D;
   update values of j based on attribute values in item;
   i := log4(k);
   repeat
   i: = i - 1;
   for each node j in level i do
update values of j based on attribute values in its 4 children;
until i = 1;