그리드 기반 클러스터링이란?
그리드(grid)는 특히 저차원 데이터에서 데이터 집합을 효율적으로 구성하는 강력한 방법입니다. 핵심 아이디어는 각 속성의 가능한 값 범위를 여러 개의 연속적인 구간으로 나누어 격자 셀(grid cell) 집합을 만드는 것입니다. 이렇게 하면 각 데이터 객체는 자신의 속성 값이 포함된 구간에 해당하는 격자 셀에 자연스럽게 배치됩니다.
데이터를 단 한 번 훑는 것만으로 객체들을 적절한 격자 셀에 할당할 수 있으며, 동시에 각 셀에 포함된 점의 개수와 같은 통계 정보도 함께 수집할 수 있다는 점이 큰 장점입니다.
그리드 기반 클러스터링 알고리즘의 절차
그리드를 활용한 클러스터링에는 여러 가지 구현 방식이 있지만, 대부분 밀도(density) 개념에 기반합니다. 일반적인 알고리즘 절차는 다음과 같습니다.
- 격자 셀들의 집합을 생성한다.
- 객체들을 적절한 셀에 할당하고 각 셀의 밀도를 계산한다.
- 사전에 정의된 임계값 r보다 밀도가 낮은 셀은 제거한다.
- 밀도가 높은 인접 셀들을 연결하여 클러스터를 형성한다.
1. 격자 셀 정의하기
격자 셀을 정의하는 것은 전체 과정에서 가장 기본적인 단계이지만, 동시에 가장 모호한 단계이기도 합니다. 각 속성의 가능한 값을 여러 개의 연속 구간으로 나누는 방법이 다양하기 때문입니다. 연속형 속성의 경우 널리 사용되는 방법 중 하나는 값을 동일한 폭의 구간으로 나누는 것입니다. 이 방식을 모든 속성에 적용하면 결과적으로 모든 격자 셀이 같은 부피(volume)를 가지게 되며, 셀의 밀도는 단순히 해당 셀에 포함된 점의 개수로 쉽게 정의할 수 있습니다.
2. 격자 셀의 밀도
격자 셀의 밀도는 해당 영역의 부피로 점의 개수를 나눈 값으로 정의할 수 있습니다. 다시 말해, 밀도란 영역의 차원과 무관하게 단위 공간당 점의 개수를 의미합니다.
3. 고밀도 셀로부터 클러스터 형성하기
인접한 고밀도 셀들을 묶어 클러스터를 만드는 작업은 비교적 간단합니다. 다만 '인접(adjacent)'을 어떻게 정의할 것인가가 하나의 과제로 남습니다. 또한 이러한 기본 클러스터링 방식에는 몇 가지 한계가 있는데, 예를 들어 클러스터 경계에는 부분적으로 비어 있는 셀이 존재할 수 있습니다. 이런 문제는 알고리즘을 좀 더 정교하게 다듬음으로써 충분히 보완할 수 있습니다.
비공간 속성을 활용한 확장
기본적인 그리드 기반 클러스터링은 밀도 외의 추가 정보를 활용하면 더욱 향상시킬 수 있습니다. 실제 많은 데이터셋은 공간(spatial) 속성과 비공간(non-spatial) 속성을 함께 가집니다. 즉, 객체의 시간적·공간적 위치를 결정하는 속성과 객체의 다른 특성을 설명하는 속성이 공존하는 경우가 많습니다.
대표적인 예가 주택입니다. 주택은 위치라는 공간 속성과 함께 가격, 전용 면적(평방피트) 등 다양한 특성을 지닙니다. 공간적(또는 시간적) 자기상관(spatial autocorrelation) 현상 때문에 동일한 격자 셀에 속한 객체들은 다른 속성들에 대해서도 비슷한 값을 가지는 경향이 있습니다. 이러한 성질을 잘 활용하면 클러스터링의 정확도와 실용성을 한층 높일 수 있습니다.