클러스터링 (Clustering)¶

난이도: 초급~중급
선수 지식: 거리 메트릭, 기초 확률/통계
관련 문서: k-NN | 차원 축소 | 손실 함수 | 볼록성

개요¶

클러스터링(Clustering)은 비지도 학습(Unsupervised Learning)의 대표적 기법으로, 레이블 없이 데이터를 유사한 그룹(클러스터)으로 나누는 것이 목적이다.

주요 클러스터링 알고리즘: - K-Means: 중심점 기반, 가장 널리 사용 - DBSCAN: 밀도 기반, 임의 형태 클러스터 발견 - 계층적 클러스터링 (Hierarchical Clustering): 덴드로그램 기반, 다중 스케일 분석 - GMM (Gaussian Mixture Models): 확률 기반, 소프트 할당

핵심 개념¶

1. K-Means¶

알고리즘 (Lloyd's Algorithm)¶

1. k개의 중심점(centroid) 초기화
2. 각 데이터 포인트를 가장 가까운 중심점에 할당
3. 각 클러스터의 중심점을 해당 클러스터 평균으로 갱신
4. 수렴할 때까지 2-3 반복

목적 함수¶

이를 군집 내 제곱합 (WCSS, Within-Cluster Sum of Squares) 또는 관성(inertia)이라고 한다.

초기화 전략¶

k 선택 방법¶

가정과 한계¶

• 가정: 구형 클러스터, 동일 분산, 동일 크기
• 한계: 초기화에 민감, 볼록 클러스터만 가능, k를 사전 지정, 이상치에 민감

변형¶

• Mini-batch K-Means: 배치 단위 업데이트, 대규모 데이터에 빠름
• K-Medoids (PAM): 중심을 실제 데이터 포인트로, 이상치에 강건
• K-Modes: 범주형 데이터용
• K-Prototypes: 혼합 데이터 (연속 + 범주)

복잡도¶

\(O(nkdi)\) (\(n\): 데이터 수, \(k\): 클러스터 수, \(d\): 차원, \(i\): 반복 횟수)

2. DBSCAN¶

Density-Based Spatial Clustering of Applications with Noise

파라미터¶

• \(\epsilon\) (eps): 이웃 반경
• MinPts: 코어 포인트가 되기 위한 최소 이웃 수

포인트 분류¶

flowchart LR
    A[데이터 포인트] --> B{ε 내 이웃 ≥ MinPts?}
    B -->|예| C[코어 포인트<br/>Core Point]
    B -->|아니오| D{코어 포인트의 ε 내?}
    D -->|예| E[경계 포인트<br/>Border Point]
    D -->|아니오| F[노이즈<br/>Noise]

알고리즘¶

1. 임의의 미방문 포인트 선택
2. \(\epsilon\)-이웃 계산
3. 코어 포인트면 클러스터 확장 (밀도 도달성으로 연결)
4. 코어가 아니면 노이즈로 표시 (나중에 경계로 바뀔 수 있음)

파라미터 선택¶

• k-distance plot으로 \(\epsilon\) 결정: k=MinPts에서의 거리를 정렬, 급격한 변화 지점이 적정 \(\epsilon\)
• MinPts \(\ge d + 1\) (차원 + 1) 이 경험적 가이드

장단점¶

변형¶

• HDBSCAN: 계층적 + 밀도 기반, 다양한 밀도 처리 가능
• OPTICS: 순서 기반, 다양한 밀도에서 클러스터 추출

3. 계층적 클러스터링 (Hierarchical Clustering)¶

병합형 (Agglomerative, Bottom-up)¶

1. 각 포인트를 개별 클러스터로 시작
2. 가장 가까운 클러스터 쌍을 병합
3. 원하는 k개가 될 때까지 반복

연결 기준 (Linkage Criteria)¶

덴드로그램 (Dendrogram)¶

• 병합 이력의 트리 시각화
• 원하는 수준에서 "잘라서" k개의 클러스터 획득
• 다중 스케일(multi-scale) 분석 가능

분할형 (Divisive, Top-down)¶

• 하나의 클러스터에서 시작하여 재귀적으로 분할
• 실무에서는 병합형이 훨씬 일반적

복잡도¶

• 시간: \(O(n^3)\) (일반), \(O(n^2 \log n)\) (일부 구현)
• 공간: \(O(n^2)\) (거리 행렬)

4. 가우시안 혼합 모델 (GMM)¶

모델¶

각 클러스터가 가우시안 분포를 따른다고 가정하고, 데이터가 이들의 혼합으로부터 생성되었다고 모델링한다.

EM 알고리즘¶

E-step (기대): 각 포인트의 클러스터별 소속 확률(responsibility) 계산

M-step (최대화): \(\boldsymbol{\mu}_k\), \(\boldsymbol{\Sigma}_k\), \(\pi_k\) 갱신

K-Means와의 비교¶

\(\boldsymbol{\Sigma}_k = \sigma^2\mathbf{I}\) (spherical)로 제약하면 K-Means와 동치가 된다.

공분산 유형¶

모델 선택¶

BIC (Bayesian Information Criterion)와 AIC (Akaike Information Criterion)로 K 결정.

상세 비교표¶

flowchart TD
    A[클러스터링 알고리즘 선택] --> B{클러스터 형태를 아는가?}
    B -->|구형으로 예상| C{클러스터 수를 아는가?}
    C -->|예| D[K-Means]
    C -->|아니오| E[K-Means + 엘보우/실루엣]
    B -->|임의 형태| F{노이즈가 많은가?}
    F -->|예| G[DBSCAN / HDBSCAN]
    F -->|아니오| H{확률적 할당 필요?}
    H -->|예| I[GMM]
    H -->|아니오| J[계층적 클러스터링]
    A --> K{다양한 스케일에서 분석?}
    K -->|예| L[계층적 클러스터링]

클러스터링 평가 지표 (레이블 없이)¶

실루엣 점수 공식:

• \(a(i)\): 같은 클러스터 내 평균 거리
• \(b(i)\): 가장 가까운 다른 클러스터까지의 평균 거리

언제 사용하는가¶

흔한 오해와 함정¶

1. "K-Means는 항상 수렴한다"¶

• 맞다. 하지만 지역 최적해(local optimum)에 수렴한다. 전역 최적이 아닐 수 있으므로 여러 번 다른 초기화로 실행해야 한다.

2. "K-Means의 클러스터는 항상 같은 크기이다"¶

• K-Means는 같은 크기를 가정하지는 않지만, 불균형한 크기에서 성능이 저하되는 경향이 있다.

3. "DBSCAN은 모든 상황에서 K-Means보다 낫다"¶

• DBSCAN은 밀도가 균일하지 않은 데이터에서 어려움을 겪는다. 또한 파라미터(\(\epsilon\), MinPts) 튜닝이 필요하다.

4. "클러스터링 결과는 객관적이다"¶

• 클러스터링은 본질적으로 주관적이다. 같은 데이터에 대해 다른 알고리즘/파라미터는 다른 결과를 줄 수 있으며, 어떤 것이 "정답"인지 판단하기 어려울 수 있다.

다른 주제와의 연결¶

• k-NN: 거리 기반 접근, 거리 메트릭 공유
• 차원 축소: 클러스터링 전 전처리, 시각화
• 볼록성: K-Means 목적 함수는 비볼록 (지역 최적해)
• VC 차원: 비지도 학습의 복잡도 이론

자주 묻는 면접 질문¶

1. K-Means 수렴이 보장되는가?

2. 예, 지역 최적해에는 반드시 수렴. 목적 함수가 매 반복마다 단조 감소하고 유한한 할당 경우의 수

3. K-Means가 초기화에 민감한 이유는?

4. 비볼록 최적화 문제이므로 초기점에 따라 다른 지역 최적에 수렴

5. DBSCAN vs K-Means: 각각 언제 선호하는가?

6. DBSCAN: 임의 형태, 노이즈 존재, k 모름. K-Means: 구형 클러스터, 대규모, k를 알거나 추정 가능

7. 하드 클러스터링과 소프트 클러스터링의 차이는?

8. 하드: 각 포인트가 정확히 하나의 클러스터에 속함 (K-Means). 소프트: 확률적 소속 (GMM)

9. 레이블 없이 클러스터링을 평가하는 방법은?

10. 내부 지표: 실루엣 점수, Davies-Bouldin, Calinski-Harabasz

코드 예시¶

from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.mixture import GaussianMixture
from sklearn.metrics import silhouette_score

# K-Means
kmeans = KMeans(n_clusters=3, init='k-means++', n_init=10, random_state=42)
labels = kmeans.fit_predict(X)
print(f"Silhouette: {silhouette_score(X, labels):.3f}")

# DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X)
n_noise = (labels == -1).sum()
print(f"Clusters: {len(set(labels)) - (1 if -1 in labels else 0)}, Noise: {n_noise}")

# 계층적 클러스터링
agg = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = agg.fit_predict(X)

# GMM
gmm = GaussianMixture(n_components=3, covariance_type='full', random_state=42)
labels = gmm.fit_predict(X)
proba = gmm.predict_proba(X)  # 소프트 할당

# 엘보우 방법으로 k 선택
inertias = []
for k in range(1, 11):
    km = KMeans(n_clusters=k, random_state=42)
    km.fit(X)
    inertias.append(km.inertia_)

용어 정리¶

참고 자료¶

• MacQueen (1967) - "Some Methods for Classification and Analysis of Multivariate Observations"
• Arthur & Vassilvitskii (2007) - "k-means++: The Advantages of Careful Seeding"
• Ester et al. (1996) - "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise" (DBSCAN)
• McInnes et al. (2017) - "hdbscan: Hierarchical density based clustering"
• Dempster, Laird, Rubin (1977) - "Maximum Likelihood from Incomplete Data via the EM Algorithm"