BIRCH란 무엇인가?
BIRCH는 Balanced Iterative Reducing and Clustering Using Hierarchies(계층 구조를 활용한 균형 잡힌 반복 축소 및 군집화)의 약자입니다. 계층적 클러스터링(hierarchical clustering)과 반복적 분할(iterative partitioning) 등 다른 클러스터링 기법들을 통합하여, 방대한 양의 수치 데이터를 효율적으로 군집화하도록 설계된 알고리즘입니다.
BIRCH는 클러스터링 특징(Clustering Feature, CF)과 클러스터링 특징 트리(CF Tree)라는 두 가지 핵심 개념을 제공하며, 이를 통해 클러스터에 대한 요약 정보를 저장합니다. 이러한 구조 덕분에 대규모 데이터베이스에서 최고 수준의 속도와 확장성을 달성할 수 있고, 새로 유입되는 객체에 대한 점진적(incremental)·동적(dynamic) 클러스터링에도 효과적으로 대응할 수 있습니다.
클러스터의 기본 통계량
n개의 d차원 데이터 객체(또는 점)로 이루어진 클러스터가 있을 때, 해당 클러스터의 중심(centroid) x0, 반지름 R, 지름 D는 다음과 같이 정의됩니다.
$$x_{0}=\frac{\sum_{i=1}^{n}x_{i}}{n}$$
$$R=\sqrt{\frac{\sum_{i=1}^{n}(x_{i}-x_{0})^{2}}{n}}$$
$$D=\sqrt{\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}(x_{i}-x_{j})^{2}}{n(n-1)}}$$
여기서 R은 클러스터 내 각 멤버 객체에서 중심까지의 평균 거리이며, D는 클러스터 내부 객체들 간의 평균 쌍별 거리(pairwise distance)입니다. R과 D는 모두 중심을 기준으로 클러스터가 얼마나 조밀하게 모여 있는지를 나타내는 지표입니다.
클러스터링 특징(Clustering Feature, CF)
클러스터링 특징(CF)은 클러스터에 대한 정보를 요약하는 3차원 벡터입니다. n개의 d차원 객체 {xi}로 구성된 클러스터의 CF는 다음과 같이 표현됩니다.
CF = (n, LS, SS)
- n: 클러스터에 포함된 데이터 점의 개수
- LS: n개 점들의 선형 합(linear sum), 즉 $\sum_{i=1}^{n}(x_{i})$
- SS: 데이터 점들의 제곱합(square sum), 즉 $\sum_{i=1}^{n}x_{i}^{2}$
통계학적 관점에서 보면, 클러스터링 특징은 해당 클러스터의 0차, 1차, 2차 모멘트(moment)에 대한 요약 통계라고 할 수 있습니다.
CF의 가산성(Additivity)
클러스터링 특징은 덧셈에 대해 닫혀 있다는 중요한 성질을 가집니다. 예를 들어, 서로 겹치지 않는 두 클러스터 C1과 C2가 각각 CF1과 CF2라는 클러스터링 특징을 가지고 있다면, C1과 C2를 합쳐서 만들어진 새로운 클러스터의 CF는 단순히 CF1 + CF2로 계산됩니다.
또한 CF만으로 BIRCH에서 클러스터링 의사결정에 필요한 모든 측정값(중심, 반지름, 지름 등)을 계산할 수 있습니다. 따라서 BIRCH는 전체 객체를 저장하지 않고도 클러스터링 특징으로 데이터를 요약함으로써 저장 공간을 매우 효율적으로 사용합니다.
CF 트리(CF Tree)
CF 트리는 계층적 클러스터링을 위한 클러스터링 특징들을 저장하는 높이 균형(height-balanced) 트리입니다. 트리의 비단말(non-leaf) 노드는 자식 노드(children)를 가지며, 자식 노드들의 CF 값들의 합을 저장함으로써 하위 클러스터에 대한 요약 정보를 관리합니다.
CF 트리의 주요 파라미터
CF 트리는 다음 두 가지 파라미터에 의해 그 크기와 형태가 결정됩니다.
- 분기 계수(Branching Factor, B): 각 비단말 노드가 가질 수 있는 자식 노드의 최대 개수를 정의합니다.
- 임계값(Threshold, T): 트리의 리프(leaf) 노드에 저장되는 하위 클러스터(sub-cluster)의 최대 지름을 정의합니다.
이 두 파라미터를 적절히 조절하면 결과적으로 생성되는 트리의 크기를 제어할 수 있으며, 이를 통해 메모리 사용량과 클러스터링 정밀도 사이의 균형을 맞출 수 있습니다.