클러스터링 (Clustering)

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

---

핵심 요약: 클러스터링(Clustering)은 레이블(Label) 없이 비슷한 데이터끼리 묶는 비지도 학습(Unsupervised Learning) 기법이다. K-Means는 가장 널리 쓰이는 중심점(Centroid) 기반 방법이고, DBSCAN은 밀도(Density) 기반으로 임의 형태의 군집을 찾으며 노이즈(Noise)도 자동으로 식별한다.

핵심 용어 미리보기:

• 중심점 (Centroid): 클러스터에 속한 데이터 포인트들의 평균 위치. K-Means에서 클러스터를 대표하는 점
• 관성 (Inertia, WCSS): 각 데이터 포인트와 소속 클러스터 중심 사이 거리의 제곱합. 작을수록 클러스터가 조밀하다
• 실루엣 점수 (Silhouette Score): 클러스터 내 응집도와 클러스터 간 분리도를 동시에 측정하는 지표. -1~1 범위이며 1에 가까울수록 좋다
• 코어 포인트 (Core Point): DBSCAN에서 반경 $\epsilon$ 내에 MinPts개 이상의 이웃을 가진 점. 클러스터의 핵심

---

개요

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

주요 클러스터링 알고리즘:

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

---

탄생 배경

클러스터링의 역사는 “유사한 것을 묶는다”라는 인간의 가장 기본적인 인지 활동을 알고리즘으로 형식화한 여정이다. James MacQueen (1967)이 “Some Methods for Classification and Analysis of Multivariate Observations”에서 K-Means라는 이름을 처음 사용했다. 그러나 알고리즘 자체는 Stuart Lloyd가 1957년 Bell Labs에서 이미 개발했으며(1982년 출판), Hugo Steinhaus도 1957년에 유사한 방법을 독립적으로 제안했다.

K-Means의 직관은 단순하다: 교실에서 학생들을 k명의 선생님에게 배정한다고 생각하면, 각 학생은 가장 가까운 선생님의 그룹으로 가고, 선생님은 자기 그룹의 중심으로 이동하는 과정을 반복하는 것이다. 이 단순한 반복이 놀랍도록 효과적인 군집을 만들어낸다.

K-Means의 한계 — 구형 클러스터만 발견 가능, k를 사전에 지정해야 함, 노이즈에 취약 — 를 극복하기 위해 Ester, Kriegel, Sander, Xu (1996)가 DBSCAN을 발표했다. DBSCAN의 혁신은 밀도(density)라는 개념을 도입한 것이다. K-Means가 “가장 가까운 선생님 그룹으로 배정”하는 방식이라면, DBSCAN은 “사람들이 자연스럽게 모여 있는 곳이 그룹이다”라는 발상이다. 덕분에 초승달 모양, 고리 모양 등 임의 형태의 클러스터를 발견할 수 있게 되었고, 어디에도 속하지 않는 노이즈 포인트도 자동으로 식별할 수 있게 되었다.

---

핵심 개념

1. K-Means

알고리즘 (Lloyd’s Algorithm)

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

목적 함수

$\min \sum_{j=1}^{k}\sum_{x_i \in C_j} \|x_i - \mu_j\|^2$

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

숫자로 이해하기

1D 직선 위에 점 8개가 있다고 하자: $\{1, 2, 3, 4, \; 8, 9, 10, 11\}$. $K = 2$로 설정한다.

1단계 — 초기화: 중심점을 임의로 $\mu_1 = 2$, $\mu_2 = 9$로 설정한다.

2단계 — 할당: 각 점을 가장 가까운 중심에 배정한다.

• 클러스터 1: $\{1, 2, 3, 4\}$ (모두 $\mu_1 = 2$에 더 가까움)
• 클러스터 2: $\{8, 9, 10, 11\}$ (모두 $\mu_2 = 9$에 더 가까움)

3단계 — 중심 갱신: 각 클러스터의 평균을 새 중심으로 한다.

• $\mu_1 = (1+2+3+4)/4 = 2.5$
• $\mu_2 = (8+9+10+11)/4 = 9.5$

재할당해도 멤버가 바뀌지 않으므로 수렴(Convergence)! 최종 클러스터: $\{1,2,3,4\}$와 $\{8,9,10,11\}$.

초기화 전략

방법	설명	특징
무작위	랜덤으로 k개 선택	불안정, 나쁜 수렴 가능
K-Means++	$D(x)^2$에 비례하여 초기 중심 선택	표준 방법, 수렴 보장 개선
K-Means||	K-Means++의 병렬 버전	대규모 데이터용

k 선택 방법

방법	설명
엘보우 방법 (Elbow Method)	WCSS vs k 그래프에서 “팔꿈치” 지점
실루엣 점수 (Silhouette Score)	클러스터 내 응집도 vs 클러스터 간 분리도
갭 통계량 (Gap Statistic)	실제 WCSS와 랜덤 분포의 WCSS 차이
정보 기준 (BIC/AIC)	모델 복잡도 페널티 포함

가정과 한계

• 가정: 구형 클러스터, 동일 분산, 동일 크기
• 한계: 초기화에 민감, 볼록 클러스터만 가능, 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: 코어 포인트가 되기 위한 최소 이웃 수

포인트 분류

알고리즘

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

파라미터 선택

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

장단점

장점	단점
임의 형태 클러스터 발견	밀도가 다른 클러스터에 약함
노이즈 자동 식별	$\epsilon$, MinPts에 민감
k 사전 지정 불필요	고차원에서 성능 저하
결정론적	경계 포인트 할당은 순서 의존

변형

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

---

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

병합형 (Agglomerative, Bottom-up)

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

연결 기준 (Linkage Criteria)

연결 방법	정의	특징
단일 연결 (Single)	클러스터 간 최소 거리	체이닝 문제
완전 연결 (Complete)	클러스터 간 최대 거리	조밀한 클러스터
평균 연결 (Average)	평균 쌍별 거리	절충안
Ward	군집 내 분산 증가 최소화	K-Means와 유사, 가장 많이 사용

덴드로그램 (Dendrogram)

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

분할형 (Divisive, Top-down)

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

복잡도

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

---

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

모델

$P(\mathbf{x}) = \sum_{k=1}^{K} \pi_k \mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$

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

EM 알고리즘

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

$\gamma_{ik} = \frac{\pi_k \mathcal{N}(\mathbf{x}_i|\boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)}{\sum_{j=1}^{K} \pi_j \mathcal{N}(\mathbf{x}_i|\boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j)}$

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

K-Means와의 비교

속성	K-Means	GMM
할당 방식	하드 (0 또는 1)	소프트 (확률적)
클러스터 형태	구형만	타원형 가능
불확실성	없음	소속 확률 제공
공분산 제약	등방성	full, tied, diagonal, spherical

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

공분산 유형

유형	파라미터 수	클러스터 형태
full	$O(d^2)$ per cluster	완전 자유 (타원)
tied	$O(d^2)$ 공유	동일 형태
diagonal	$O(d)$ per cluster	축 정렬 타원
spherical	$O(1)$ per cluster	구형

모델 선택

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

---

상세 비교표

속성	K-Means	DBSCAN	계층적	GMM
k 사전 지정	필요	불필요	선택적	필요
클러스터 형태	구형	임의	연결 방법 의존	타원형
노이즈 처리	불가	자동 식별	불가	어느 정도
확장성	최고	양호	나쁨	중간
소프트 할당	불가	불가	불가	가능
결정론적	아니오	예	예	아니오

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

지표	범위	설명
실루엣 점수 (Silhouette)	[-1, 1]	1에 가까울수록 좋음
Davies-Bouldin Index	[0, ∞)	0에 가까울수록 좋음
Calinski-Harabasz Index	[0, ∞)	클수록 좋음

실루엣 점수 공식:

$s(i) = \frac{b(i) - a(i)}{\max(a(i), b(i))}$

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

---

언제 사용하는가

상황	추천 알고리즘
대규모 데이터, 구형 클러스터	K-Means / Mini-batch K-Means
임의 형태 클러스터, 노이즈 포함	DBSCAN / HDBSCAN
다중 스케일 분석, 시각적 탐색	계층적 클러스터링
확률적 소속, 불확실성 필요	GMM
이상치에 강건해야 하는 경우	K-Medoids, DBSCAN

---

실전 사례

소매업 고객 세분화 - K-Means로 5개 고객 페르소나를 발견하다

한 대형 소매 유통 기업이 300만 고객의 구매 데이터를 분석하여 마케팅 전략을 재설계한 사례이다. 기존에는 마케터의 직관에 기반한 3개 세그먼트(고가치/중가치/저가치)만 사용했으나, K-Means 클러스터링을 적용하자 5개의 뚜렷한 고객 페르소나가 드러났다.

분석에 사용한 특성은 RFM(Recency, Frequency, Monetary) 지표와 카테고리별 구매 비율이었다. 엘보우 방법(Elbow Method)과 실루엣 점수(Silhouette Score)를 결합하여 k=5를 선택했다. 발견된 페르소나는 다음과 같았다:

• 충성 고객(Loyal Champions): 최근 구매, 높은 빈도, 높은 금액 (전체의 8%)
• 잠재 이탈 고객(At Risk): 과거 고빈도였으나 최근 활동 감소 (12%)
• 신규 고객(New Customers): 최근 첫 구매, 낮은 빈도 (18%)
• 할인 추구형(Bargain Hunters): 프로모션 기간에만 활성화 (25%)
• 비활성 고객(Hibernating): 오랜 기간 미구매 (37%)

이 세분화를 기반으로 각 그룹에 맞는 차별화된 캠페인을 실행한 결과, 마케팅 ROI가 34% 향상되었다. 특히 “잠재 이탈 고객” 세그먼트에 집중적인 리텐션 캠페인을 실시하여 이탈률을 크게 줄인 것이 주효했다.

이 사례는 클러스터링이 단순한 탐색적 분석(EDA) 도구를 넘어, 실제 비즈니스 의사결정을 이끄는 강력한 도구가 될 수 있음을 보여준다.

---

흔한 오해와 함정

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. K-Means가 초기화에 민감한 이유는?

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

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

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

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

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

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

   • 내부 지표: 실루엣 점수, 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_)

---

용어 정리

영어	한국어
Clustering	클러스터링 (군집화)
Centroid	중심점 (무게중심)
Inertia (WCSS)	관성 (군집 내 제곱합)
Silhouette Score	실루엣 점수
Dendrogram	덴드로그램
Core Point	코어 포인트
Noise Point	노이즈 포인트
Soft Clustering	소프트 클러스터링
Hard Clustering	하드 클러스터링
Linkage	연결 방법

---

참고 자료

• 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”