콘텐츠로 이동
Data Prep
상세

Mini-Batch K-Means

논문 정보

항목 내용
제목 Web-Scale K-Means Clustering
저자 David Sculley
연도 2010
학회 WWW (International World Wide Web Conference)
링크 ACM DL

핵심 아이디어

표준 K-Means는 매 반복마다 전체 데이터셋을 순회해야 함. 데이터가 수백만~수십억 개면 비현실적.

Sculley는 Google에서 웹 규모 데이터를 처리하기 위해 미니배치(mini-batch)를 사용한 확률적 최적화를 제안했다:

  1. 매 반복마다 무작위로 작은 배치만 샘플링
  2. 배치 내 데이터만으로 중심점 업데이트
  3. 스트리밍 평균(streaming average) 방식으로 누적 업데이트

결과: 정확도는 약간 손해를 보지만, 속도가 수십~수백 배 빨라진다.

알고리즘

단계별 절차

입력: 데이터 X, 클러스터 수 K, 배치 크기 b, 반복 횟수 t
출력: 클러스터 중심점 μ

1. 초기화: K-Means++ 또는 무작위로 중심점 μ₁, ..., μₖ 선택
2. 각 중심점의 업데이트 카운터 v₁ = v₂ = ... = vₖ = 0

3. t번 반복:
   a. 미니배치 M ⊂ X를 크기 b로 무작위 샘플링

   b. 할당: 각 x ∈ M에 대해
      c(x) = argmin_j ‖x - μⱼ‖²

   c. 업데이트: 각 x ∈ M에 대해
      j = c(x)  // x가 할당된 클러스터
      vⱼ ← vⱼ + 1
      η = 1 / vⱼ  // 학습률 (점점 감소)
      μⱼ ← (1 - η) · μⱼ + η · x  // 스트리밍 평균

스트리밍 평균의 의미

누적 카운터 \(v_j\)번째 업데이트에서 학습률 \(\eta = 1/v_j\)를 사용하면:

\[\mu_j^{(new)} = \frac{v_j - 1}{v_j} \mu_j^{(old)} + \frac{1}{v_j} x\]

이는 지금까지 본 모든 데이터의 단순 평균과 동일함.

시간 복잡도

알고리즘 한 반복 전체 (t 반복)
K-Means O(nKd) O(tnKd)
Mini-Batch O(bKd) O(tbKd)

b << n이므로 속도 향상: O(n/b) 배

장단점

장점

장점 설명
확장성 수억 개 데이터도 처리 가능
메모리 효율 배치만 메모리에 로드
스트리밍 실시간 데이터에 적용 가능
수렴 K-Means와 유사한 품질

단점

단점 설명
약간의 정확도 손실 배치 크기가 작으면 품질 저하
수렴 불안정 배치 샘플링의 분산
하이퍼파라미터 배치 크기, 반복 횟수 튜닝 필요

K-Means vs Mini-Batch K-Means

항목 K-Means Mini-Batch
정확도 높음 약간 낮음 (1-3% 차이)
속도 느림 빠름 (10-100배)
메모리 전체 데이터 배치만
적합 규모 < 100K > 100K

언제 쓰는가

적합한 경우

  • 데이터가 10만 개 이상일 때
  • 전체 데이터를 메모리에 올릴 수 없을 때
  • 스트리밍/온라인 학습이 필요할 때
  • 약간의 정확도 손실이 허용될 때

부적합한 경우

  • 데이터가 작을 때 (표준 K-Means가 더 정확)
  • 최고 수준의 클러스터 품질이 필요할 때
  • 결과 재현성이 엄격히 요구될 때

Python 코드

import numpy as np
from sklearn.cluster import MiniBatchKMeans, KMeans
from sklearn.datasets import make_blobs
import time

# 대규모 데이터 생성
n_samples = 100000
X, y_true = make_blobs(n_samples=n_samples, centers=10, cluster_std=1.0, random_state=42)

print(f"데이터 크기: {X.shape}")

# Mini-Batch K-Means
start = time.time()
mbk = MiniBatchKMeans(
    n_clusters=10,
    batch_size=1024,        # 미니배치 크기
    max_iter=100,           # 최대 반복
    n_init=3,               # 초기화 횟수
    init='k-means++',
    random_state=42
)
mbk.fit(X)
mbk_time = time.time() - start

# 표준 K-Means (비교용)
start = time.time()
km = KMeans(
    n_clusters=10,
    n_init=3,
    random_state=42
)
km.fit(X)
km_time = time.time() - start

# 결과 비교
print(f"\n{'Method':<20} {'Inertia':<15} {'Time (s)':<10}")
print("=" * 45)
print(f"{'Mini-Batch K-Means':<20} {mbk.inertia_:<15.2f} {mbk_time:<10.3f}")
print(f"{'Standard K-Means':<20} {km.inertia_:<15.2f} {km_time:<10.3f}")
print(f"\nSpeed-up: {km_time / mbk_time:.1f}x")
print(f"Inertia difference: {(mbk.inertia_ - km.inertia_) / km.inertia_ * 100:.2f}%")

배치 크기 영향 분석

batch_sizes = [100, 256, 512, 1024, 2048, 4096]
results = []

for bs in batch_sizes:
    start = time.time()
    mbk = MiniBatchKMeans(n_clusters=10, batch_size=bs, n_init=1, random_state=42)
    mbk.fit(X)
    elapsed = time.time() - start
    results.append({
        'batch_size': bs,
        'inertia': mbk.inertia_,
        'time': elapsed
    })

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

# 시각화
import matplotlib.pyplot as plt

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))

ax1.plot(df['batch_size'], df['time'], 'bo-')
ax1.set_xlabel('Batch Size')
ax1.set_ylabel('Time (seconds)')
ax1.set_title('Batch Size vs Training Time')

ax2.plot(df['batch_size'], df['inertia'], 'ro-')
ax2.set_xlabel('Batch Size')
ax2.set_ylabel('Inertia')
ax2.set_title('Batch Size vs Inertia')

plt.tight_layout()
plt.show()

Partial Fit (스트리밍)

# 스트리밍 데이터 시뮬레이션
mbk_streaming = MiniBatchKMeans(n_clusters=10, random_state=42)

# 데이터를 청크로 나눠서 점진적 학습
chunk_size = 10000
for i in range(0, len(X), chunk_size):
    chunk = X[i:i+chunk_size]
    mbk_streaming.partial_fit(chunk)
    print(f"Processed {min(i+chunk_size, len(X)):,} samples, Inertia: {mbk_streaming.inertia_:.2f}")

관련 기법

참고 문헌

  1. Sculley, D. (2010). Web-Scale K-Means Clustering. Proceedings of the 19th International Conference on World Wide Web, 1177-1178.
  2. Bottou, L., & Bengio, Y. (1995). Convergence Properties of the K-Means Algorithms. Advances in Neural Information Processing Systems.