BIRCH

논문 정보

항목	내용
제목	BIRCH: An Efficient Data Clustering Method for Very Large Databases
저자	Tian Zhang, Raghu Ramakrishnan, Miron Livny
연도	1996
학회	SIGMOD (ACM SIGMOD International Conference on Management of Data)
링크	ACM DL

핵심 아이디어

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)는 대규모 데이터를 한 번의 스캔으로 클러스터링할 수 있게 설계됨.

핵심 혁신: 1. CF (Clustering Feature): 클러스터의 요약 통계량 2. CF Tree: CF들을 저장하는 균형 트리 (B+ Tree와 유사) 3. 점진적 클러스터링: 데이터를 순차적으로 처리, 메모리 제한 내에서 동작

데이터 전체가 아닌 CF만 저장하므로 메모리 효율적.

알고리즘

Clustering Feature (CF)

n개의 d차원 데이터 포인트 \(\{x_1, ..., x_n\}\)에 대해:

\[CF = (n, LS, SS)\]

• \(n\): 포인트 수
• \(LS = \sum_{i=1}^{n} x_i\): 선형 합 (d차원 벡터)
• \(SS = \sum_{i=1}^{n} x_i^2\): 제곱 합 (스칼라 또는 d차원)

CF의 핵심 속성: 가산성 $\(CF_1 + CF_2 = (n_1 + n_2, LS_1 + LS_2, SS_1 + SS_2)\)$

CF만으로 계산 가능한 것들: - 중심점: \(\bar{x} = LS / n\) - 반경: \(R = \sqrt{\frac{SS}{n} - (\frac{LS}{n})^2}\) - 직경: \(D = \sqrt{\frac{2nSS - 2LS^2}{n(n-1)}}\)

CF Tree 구조

                [CF₁, CF₂, CF₃]         ← Root (비리프 노드)
                /      |      \
    [CF₁₁...CF₁ₖ]  [CF₂₁...CF₂ₖ]  [CF₃₁...CF₃ₖ]  ← 비리프 노드
        /    \          |              |
   [entries]  [entries] [entries]   [entries]    ← Leaf 노드

• Branching Factor (B): 비리프 노드의 최대 자식 수
• Threshold (T): 리프 노드 엔트리의 최대 반경/직경
• Leaf entries: 서브클러스터를 나타내는 CF들

단계별 절차

Phase 1: CF Tree 구축 (한 번의 데이터 스캔)
  각 데이터 포인트 x에 대해:
  1. 루트에서 시작하여 가장 가까운 CF를 따라 리프까지 이동
  2. 리프에서 가장 가까운 엔트리 찾기
  3. x를 흡수해도 threshold 이내면 → CF 업데이트
  4. 아니면 → 새 엔트리 생성
  5. 노드가 꽉 차면 → 분할

Phase 2 (선택): 더 작은 CF Tree로 재구축

Phase 3 (선택): 전역 클러스터링
  - 리프의 CF들에 Agglomerative/K-Means 적용

Phase 4 (선택): 클러스터 정제
  - 각 데이터를 가장 가까운 클러스터에 재할당

시간/공간 복잡도

항목	복잡도
시간	O(n) - 한 번의 스캔
공간	O(B × L) - B: branching factor, L: 리프 수

장단점

장점

장점	설명
확장성	O(n) 시간, 제한된 메모리
점진적	스트리밍 데이터 처리 가능
노이즈 처리	Outlier로 분리 가능
유연성	다른 클러스터링 알고리즘과 결합

단점

단점	설명
구형 클러스터 가정	비구형에 부적합
파라미터 민감	threshold, branching factor 튜닝 필요
삽입 순서 의존	데이터 순서에 따라 결과 다름
차원의 저주	고차원에서 성능 저하

언제 쓰는가

적합한 경우

• 대규모 데이터 (> 100K, 수백만까지)
• 메모리 제약이 있을 때
• 스트리밍 데이터
• 구형/컴팩트한 클러스터
• 전처리/요약 단계로 사용 (K-Means 전에)

부적합한 경우

• 비구형 클러스터 (DBSCAN/HDBSCAN 사용)
• 고차원 데이터
• 클러스터 크기가 매우 다를 때

Python 코드

import numpy as np
from sklearn.cluster import Birch
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
import time

# 대규모 데이터 생성
n_samples = 50000
X, y_true = make_blobs(n_samples=n_samples, centers=5, cluster_std=0.8, random_state=42)

# BIRCH 적용
start = time.time()
birch = Birch(
    threshold=0.5,          # 리프 노드 반경 임계값
    branching_factor=50,    # 노드당 최대 자식/엔트리 수
    n_clusters=5,           # 최종 클러스터 수 (None이면 서브클러스터 반환)
    compute_labels=True
)
labels = birch.fit_predict(X)
elapsed = time.time() - start

print(f"데이터 크기: {n_samples:,}")
print(f"처리 시간: {elapsed:.3f}초")
print(f"서브클러스터 수: {len(birch.subcluster_centers_)}")
print(f"최종 클러스터 수: {len(np.unique(labels))}")

# 시각화
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=1, alpha=0.5)
plt.scatter(birch.subcluster_centers_[:, 0], birch.subcluster_centers_[:, 1], 
            c='red', marker='x', s=50, label='Subcluster centers')
plt.title('BIRCH Clustering')
plt.legend()
plt.show()

Threshold 영향 분석

thresholds = [0.1, 0.3, 0.5, 0.7, 1.0]
results = []

for t in thresholds:
    birch = Birch(threshold=t, branching_factor=50, n_clusters=None)
    birch.fit(X)
    n_subclusters = len(birch.subcluster_centers_)
    results.append({'threshold': t, 'subclusters': n_subclusters})

import pandas as pd
df = pd.DataFrame(results)
print(df)

# 시각화
plt.figure(figsize=(8, 5))
plt.plot(df['threshold'], df['subclusters'], 'bo-')
plt.xlabel('Threshold')
plt.ylabel('Number of Subclusters')
plt.title('Effect of Threshold on BIRCH')
plt.show()

점진적 학습 (Partial Fit)

# 스트리밍 시뮬레이션
birch_streaming = Birch(threshold=0.5, n_clusters=5)

chunk_size = 10000
for i in range(0, len(X), chunk_size):
    chunk = X[i:i+chunk_size]
    birch_streaming.partial_fit(chunk)
    n_sub = len(birch_streaming.subcluster_centers_) if birch_streaming.subcluster_centers_ is not None else 0
    print(f"Processed {min(i+chunk_size, len(X)):,} samples, Subclusters: {n_sub}")

# 최종 라벨 예측
final_labels = birch_streaming.predict(X)

BIRCH + K-Means 파이프라인

from sklearn.pipeline import Pipeline
from sklearn.cluster import KMeans

# BIRCH로 요약 후 K-Means로 정제
pipeline = Pipeline([
    ('birch', Birch(threshold=0.5, n_clusters=None)),  # 서브클러스터 생성
    # K-Means는 BIRCH의 subcluster_centers_에 적용
])

# 또는 직접 결합
birch = Birch(threshold=0.5, n_clusters=None)
birch.fit(X)

# 서브클러스터에 K-Means 적용
kmeans = KMeans(n_clusters=5, random_state=42)
subcluster_labels = kmeans.fit_predict(birch.subcluster_centers_)

# 원본 데이터의 최종 라벨
final_labels = subcluster_labels[birch.labels_]

관련 기법

• 계층적 클러스터링 - Phase 3에서 사용 가능
• K-Means - Phase 3에서 사용 가능
• Mini-Batch K-Means - 다른 대규모 클러스터링
• CURE - 비구형 클러스터용 (Guha et al., 1998)

참고 문헌

1. Zhang, T., Ramakrishnan, R., & Livny, M. (1996). BIRCH: An Efficient Data Clustering Method for Very Large Databases. Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, 103-114.
2. Zhang, T., Ramakrishnan, R., & Livny, M. (1997). BIRCH: A New Data Clustering Algorithm and Its Applications. Data Mining and Knowledge Discovery, 1(2), 141-182.